題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 棋類機(jī)器博弈系統(tǒng)研究與關(guān)鍵技術(shù)優(yōu)化
- 小類：
- 信息技術(shù)
- 簡介：
- 機(jī)器博弈是人工智能的一個傳統(tǒng)研究課題。本文以六子棋，亞馬遜棋，手機(jī)平臺和自動對弈測試平臺四個方面來論述一個機(jī)器博弈系統(tǒng)的構(gòu)成。 六子棋在知識表示上采用棋局的動態(tài)更新，并在搜索算法中加入空著剪枝；亞馬遜棋采用了蒙特卡洛搜索算法，并融合α-β算法，使估值更容易；自動對弈平臺實(shí)現(xiàn)了程序的自動對弈，節(jié)約了測試時間；手機(jī)程序完成了跨平臺移植，實(shí)現(xiàn)了博弈系統(tǒng)在手機(jī)平臺的運(yùn)行，也證明了程序和算法的優(yōu)越性。
- 詳細(xì)介紹：
- 機(jī)器博弈是人工智能的一個傳統(tǒng)研究課題，其中，搜索算法和估值函數(shù)是難點(diǎn)。本文以六子棋，亞馬遜棋，手機(jī)平臺和自動對弈測試平臺四個方面來論述一個機(jī)器博弈系統(tǒng)的構(gòu)成。 1）六子棋方面，知識表示應(yīng)用了棋局動態(tài)更新，逐步推進(jìn)的方法，對局面進(jìn)行動態(tài)存儲，達(dá)到了簡化局面估值復(fù)雜的目的；在基于α-β的NegaScout搜索算法中加入空著剪枝，保證了搜索效率；在某些節(jié)點(diǎn)選擇性地采用單迫著和雙迫著策略，提高了程序的估值效果和勝率。 2）亞馬遜棋方面，采用了蒙特卡洛搜索算法，并融合傳統(tǒng)的α-β算法，實(shí)現(xiàn)了基于不同約束條件的選擇性著法生成；通過估值函數(shù)選取部分節(jié)點(diǎn)來進(jìn)行模擬，再從中選取估值最高的著法，這樣既增加了模擬的可靠性也減少了對估值的依賴。 3）自動對弈平臺方面，為了更好的測試和驗(yàn)證程序，開發(fā)了這個平臺，能夠?qū)崿F(xiàn)程序的自動對弈，節(jié)約了測試時間，同時使棋類博弈系統(tǒng)更加完善。 4）手機(jī)程序方面，完成了Windows平臺下的程序向Android (Linux)平臺下移植，實(shí)現(xiàn)了博弈系統(tǒng)在手機(jī)平臺的運(yùn)行，同時也證明了程序和算法的優(yōu)越性。 在2010年中國機(jī)器博弈錦標(biāo)賽中，基于上述思想的六子棋、亞馬遜棋程序和手機(jī)程序都取得了良好的成績，說明了本文研究工作的正確性、有效性和實(shí)用性。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 本文旨在棋類機(jī)器博弈系統(tǒng)的研究和關(guān)鍵技術(shù)的優(yōu)化，以六子棋和亞馬遜棋作為切入點(diǎn)，對機(jī)器博弈問題中的搜索算法和估值函數(shù)等問題進(jìn)行探究，實(shí)現(xiàn)了自動對弈測試平臺，并實(shí)現(xiàn)了程序向手機(jī)平臺的移植。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 本文是設(shè)計(jì)和實(shí)現(xiàn)了計(jì)算機(jī)博弈程序，并在關(guān)鍵技術(shù)上進(jìn)行優(yōu)化：1）六子棋知識表示采用動態(tài)局面存儲，簡化估值函數(shù)，結(jié)合單迫著和雙迫著處理殘局；2）亞馬遜棋采用蒙特卡洛搜索算法和α-β搜索算法的結(jié)合，加入了具有動態(tài)約束條件的著法生成，降低了對估值的依賴；3）完成了程序的自動對弈測試，減少人工參與，縮短了測試周期；4）實(shí)現(xiàn)了六子棋程序向手機(jī)平臺的移植，并能夠高效運(yùn)行。
應(yīng)用價值和現(xiàn)實(shí)意義
- 本文總結(jié)了在實(shí)踐操作中一些經(jīng)驗(yàn)和體會，分析了某些關(guān)鍵技術(shù)，并提出了優(yōu)化的方法，增加了自動對弈測試功能，對機(jī)器博弈系統(tǒng)進(jìn)行了很好的補(bǔ)充；并將六子棋程序移植到手機(jī)上，關(guān)注手機(jī)開發(fā)，在流行的手機(jī)平臺上開發(fā)復(fù)雜的棋牌類游戲進(jìn)行了探索，將理論研究與實(shí)踐應(yīng)用有機(jī)地結(jié)合。
學(xué)術(shù)論文摘要
- 機(jī)器博弈是人工智能的一個傳統(tǒng)研究課題。本文以六子棋，亞馬遜棋，手機(jī)平臺和自動對弈測試平臺四個方面來論述一個機(jī)器博弈系統(tǒng)的構(gòu)成。 1）六子棋方面，知識表示應(yīng)用了棋局動態(tài)更新，對局面進(jìn)行動態(tài)存儲，達(dá)到了簡化局面估值復(fù)雜的目的；在基于α-β的NegaScout搜索算法中加入空著剪枝，保證了搜索效率；在某些節(jié)點(diǎn)選擇性地采用單迫著和雙迫著策略，提高了程序的估值效果和勝率。2）亞馬遜棋方面，采用了蒙特卡洛搜索算法，并融合傳統(tǒng)的α-β算法，實(shí)現(xiàn)了基于不同約束條件的選擇性著法生成；通過估值函數(shù)選取部分節(jié)點(diǎn)來進(jìn)行模擬，這樣既增加了模擬的可靠性也減少了對估值的依賴。3）自動對弈平臺方面，為了更好的測試和驗(yàn)證程序而開發(fā)，能夠?qū)崿F(xiàn)程序的自動對弈，節(jié)約了測試時間，同時使棋類博弈系統(tǒng)更加完善。4）手機(jī)程序方面，完成了Windows平臺下的程序向Android (Linux)平臺下移植，實(shí)現(xiàn)了博弈系統(tǒng)在手機(jī)平臺的運(yùn)行，同時也證明了程序和算法的優(yōu)越性。 在2010年中國機(jī)器博弈錦標(biāo)賽中，基于上述思想的六子棋、亞馬遜棋程序和手機(jī)程序都取得了良好的成績，說明了本文研究工作的正確性、有效性和實(shí)用性。
獲獎情況
- 在2010年第四屆中國機(jī)器博弈錦標(biāo)賽中，獲得以下獎項(xiàng)： 1）“東秦之星”六子棋程序獲得了二等獎； 2）“六子靈童”六子棋手機(jī)程序獲得了三等獎； 3）“東秦之星”亞馬遜棋程序獲得了二等獎。
鑒定結(jié)果
- 獎項(xiàng)屬實(shí)
參考文獻(xiàn)
- [1]Allis L V, Herik H.J van den, Huntjens M P H. Go-Moku Solved by New Search Techniques [J]. Journal of Computational Intelligence, 1995, 12(1): 7-24 [2]Wágner J, Virag I. Solving Renju [J]. ICGA Journal, 2001, 24(1): 30-34. [3]Hsieh Ming Yu, Tsai Shi-Chun, On the Fairness and Complexity of Generalized k-in-a-row Games [J]. Theoretical Computer Science, 2007, 385(1-3): 88-100. [4]李果, 六子棋計(jì)算機(jī)博弈及其系統(tǒng)的研究與實(shí)現(xiàn)[D], 重慶, 重慶大學(xué), 2007. [5]Beal D F. Experiments with the null move [J]. In Advances in Computer Cehss 5. Elsevier Science. 1989: 65-79. [6]Beal D. Null Moves [J]. Advances in Computer Chess 5, 1987. [7]Tabibi O. D, Netanyahu N. S. Verified Null-Move Pruning {D, 2002 #155}[J]. ICGA Journal, 2002, 25(3): 153–161. [8]Schaseffer J. Experiments in Search and Knowledge [D]. Ph.D. Dissertation, University of Waterloo, 1986. [9]Chen B. N, Liu P. F, Hsu S. C, Hsu T. S. Hsu. Knowledge Inferencing on Chinese Chess Endgames [C]. Computers and Games 2008, LNCS 5131, 2008: 180-191.
同類課題研究水平概述
- 機(jī)器博弈的研究廣泛而深入。早在上世紀(jì)五十年代，就有人設(shè)想利用機(jī)器智能來實(shí)現(xiàn)機(jī)器與人的對弈。國內(nèi)外許多知名學(xué)者和知名科研機(jī)構(gòu)都曾經(jīng)涉足這方面的研究，歷經(jīng)半個多世紀(jì)，到目前為止已經(jīng)取得了許多驚人的成就。如， ? 1997年IBM的“深藍(lán)”戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫，使IBM的股票市值飆升了上百億美元，引發(fā)了廣泛而深遠(yuǎn)的影響。 ? 2007年，由《Science》雜志評選的十大科技突破中，就包括了加拿大阿爾波特大學(xué)的科研成果——解決了西洋跳棋“博弈問題”也就是說，在西洋跳棋的博弈中計(jì)算機(jī)將永遠(yuǎn)“立于不敗之地”。 雖然，機(jī)器博弈的研究取得了一些出乎意料的成果，但在“它的研究是否能揭示人類智能本質(zhì)這個問題上”仍然爭論不斷。本文的工作從實(shí)踐的角度出發(fā)，以設(shè)計(jì)和實(shí)現(xiàn)能夠與人類大師水平相媲美的計(jì)算機(jī)程序?yàn)槟繕?biāo)，避免探討哲學(xué)、認(rèn)知科學(xué)相關(guān)的話題。機(jī)器博弈研究的先驅(qū)者已經(jīng)積累下來不少先進(jìn)的算法，本文正是沿著先驅(qū)者的腳步，進(jìn)行實(shí)踐，提出問題，發(fā)現(xiàn)問題，并嘗試去解決問題。 六子棋是從2005年才被提出的，因?yàn)榱悠灞任遄悠鍙?fù)雜的多，但目前六子棋的研究成果還借鑒五子棋，這是需要突破的。本文設(shè)計(jì)和實(shí)現(xiàn)了一個六子棋程序，旨在進(jìn)一步研究六子棋問題，并尋求更優(yōu)秀的解決方案，同時也在六子棋的知識表示方面做了一些新的嘗試。 亞馬遜棋是一種分支因子很大的棋類。國際象棋程序主要用確定性的搜索算法，如alpha-beta搜索進(jìn)行求解，而大分支因子的程序用alpha-beta的效果一般比較差。在亞馬遜棋中，基于選擇性的搜索方法要稍好些，比如UCT，本文對兩種方法都進(jìn)行了嘗試。 手機(jī)功能的開發(fā)已經(jīng)受到廣泛關(guān)注，由于其性能不斷提升，使得擁有復(fù)雜算法的程序移植到手機(jī)平臺成為可能。鑒于手機(jī)本身的方便性，在手機(jī)上玩棋牌游戲無疑將會受到棋迷們的歡迎。因此，本文將研究內(nèi)容與流行技術(shù)進(jìn)行有機(jī)結(jié)合，把“東秦之星”六子棋程序移植到了手機(jī)上，并成功地參加了2010年全國競賽，受到了參賽者的關(guān)注。
