基本信息
- 項目名稱：
- 棋類機器博弈系統(tǒng)研究與關鍵技術優(yōu)化
- 小類：
- 信息技術
- 大類：
- 自然科學類學術論文
- 簡介：
- 機器博弈是人工智能的一個傳統(tǒng)研究課題。本文以六子棋，亞馬遜棋，手機平臺和自動對弈測試平臺四個方面來論述一個機器博弈系統(tǒng)的構(gòu)成。 六子棋在知識表示上采用棋局的動態(tài)更新，并在搜索算法中加入空著剪枝；亞馬遜棋采用了蒙特卡洛搜索算法，并融合α-β算法，使估值更容易；自動對弈平臺實現(xiàn)了程序的自動對弈，節(jié)約了測試時間；手機程序完成了跨平臺移植，實現(xiàn)了博弈系統(tǒng)在手機平臺的運行，也證明了程序和算法的優(yōu)越性。
- 詳細介紹：
- 機器博弈是人工智能的一個傳統(tǒng)研究課題，其中，搜索算法和估值函數(shù)是難點。本文以六子棋，亞馬遜棋，手機平臺和自動對弈測試平臺四個方面來論述一個機器博弈系統(tǒng)的構(gòu)成。 1）六子棋方面，知識表示應用了棋局動態(tài)更新，逐步推進的方法，對局面進行動態(tài)存儲，達到了簡化局面估值復雜的目的；在基于α-β的NegaScout搜索算法中加入空著剪枝，保證了搜索效率；在某些節(jié)點選擇性地采用單迫著和雙迫著策略，提高了程序的估值效果和勝率。 2）亞馬遜棋方面，采用了蒙特卡洛搜索算法，并融合傳統(tǒng)的α-β算法，實現(xiàn)了基于不同約束條件的選擇性著法生成；通過估值函數(shù)選取部分節(jié)點來進行模擬，再從中選取估值最高的著法，這樣既增加了模擬的可靠性也減少了對估值的依賴。 3）自動對弈平臺方面，為了更好的測試和驗證程序，開發(fā)了這個平臺，能夠?qū)崿F(xiàn)程序的自動對弈，節(jié)約了測試時間，同時使棋類博弈系統(tǒng)更加完善。 4）手機程序方面，完成了Windows平臺下的程序向Android (Linux)平臺下移植，實現(xiàn)了博弈系統(tǒng)在手機平臺的運行，同時也證明了程序和算法的優(yōu)越性。 在2010年中國機器博弈錦標賽中，基于上述思想的六子棋、亞馬遜棋程序和手機程序都取得了良好的成績，說明了本文研究工作的正確性、有效性和實用性。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 本文旨在棋類機器博弈系統(tǒng)的研究和關鍵技術的優(yōu)化，以六子棋和亞馬遜棋作為切入點，對機器博弈問題中的搜索算法和估值函數(shù)等問題進行探究，實現(xiàn)了自動對弈測試平臺，并實現(xiàn)了程序向手機平臺的移植。
科學性、先進性及獨特之處
- 本文是設計和實現(xiàn)了計算機博弈程序，并在關鍵技術上進行優(yōu)化：1）六子棋知識表示采用動態(tài)局面存儲，簡化估值函數(shù)，結(jié)合單迫著和雙迫著處理殘局；2）亞馬遜棋采用蒙特卡洛搜索算法和α-β搜索算法的結(jié)合，加入了具有動態(tài)約束條件的著法生成，降低了對估值的依賴；3）完成了程序的自動對弈測試，減少人工參與，縮短了測試周期；4）實現(xiàn)了六子棋程序向手機平臺的移植，并能夠高效運行。
應用價值和現(xiàn)實意義
- 本文總結(jié)了在實踐操作中一些經(jīng)驗和體會，分析了某些關鍵技術，并提出了優(yōu)化的方法，增加了自動對弈測試功能，對機器博弈系統(tǒng)進行了很好的補充；并將六子棋程序移植到手機上，關注手機開發(fā)，在流行的手機平臺上開發(fā)復雜的棋牌類游戲進行了探索，將理論研究與實踐應用有機地結(jié)合。
學術論文摘要
- 機器博弈是人工智能的一個傳統(tǒng)研究課題。本文以六子棋，亞馬遜棋，手機平臺和自動對弈測試平臺四個方面來論述一個機器博弈系統(tǒng)的構(gòu)成。 1）六子棋方面，知識表示應用了棋局動態(tài)更新，對局面進行動態(tài)存儲，達到了簡化局面估值復雜的目的；在基于α-β的NegaScout搜索算法中加入空著剪枝，保證了搜索效率；在某些節(jié)點選擇性地采用單迫著和雙迫著策略，提高了程序的估值效果和勝率。2）亞馬遜棋方面，采用了蒙特卡洛搜索算法，并融合傳統(tǒng)的α-β算法，實現(xiàn)了基于不同約束條件的選擇性著法生成；通過估值函數(shù)選取部分節(jié)點來進行模擬，這樣既增加了模擬的可靠性也減少了對估值的依賴。3）自動對弈平臺方面，為了更好的測試和驗證程序而開發(fā)，能夠?qū)崿F(xiàn)程序的自動對弈，節(jié)約了測試時間，同時使棋類博弈系統(tǒng)更加完善。4）手機程序方面，完成了Windows平臺下的程序向Android (Linux)平臺下移植，實現(xiàn)了博弈系統(tǒng)在手機平臺的運行，同時也證明了程序和算法的優(yōu)越性。 在2010年中國機器博弈錦標賽中，基于上述思想的六子棋、亞馬遜棋程序和手機程序都取得了良好的成績，說明了本文研究工作的正確性、有效性和實用性。
獲獎情況
- 在2010年第四屆中國機器博弈錦標賽中，獲得以下獎項： 1）“東秦之星”六子棋程序獲得了二等獎； 2）“六子靈童”六子棋手機程序獲得了三等獎； 3）“東秦之星”亞馬遜棋程序獲得了二等獎。
鑒定結(jié)果
- 獎項屬實
參考文獻
- [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]李果, 六子棋計算機博弈及其系統(tǒng)的研究與實現(xiàn)[D], 重慶, 重慶大學, 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.
同類課題研究水平概述
- 機器博弈的研究廣泛而深入。早在上世紀五十年代，就有人設想利用機器智能來實現(xiàn)機器與人的對弈。國內(nèi)外許多知名學者和知名科研機構(gòu)都曾經(jīng)涉足這方面的研究，歷經(jīng)半個多世紀，到目前為止已經(jīng)取得了許多驚人的成就。如， ? 1997年IBM的“深藍”戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫，使IBM的股票市值飆升了上百億美元，引發(fā)了廣泛而深遠的影響。 ? 2007年，由《Science》雜志評選的十大科技突破中，就包括了加拿大阿爾波特大學的科研成果——解決了西洋跳棋“博弈問題”也就是說，在西洋跳棋的博弈中計算機將永遠“立于不敗之地”。 雖然，機器博弈的研究取得了一些出乎意料的成果，但在“它的研究是否能揭示人類智能本質(zhì)這個問題上”仍然爭論不斷。本文的工作從實踐的角度出發(fā)，以設計和實現(xiàn)能夠與人類大師水平相媲美的計算機程序為目標，避免探討哲學、認知科學相關的話題。機器博弈研究的先驅(qū)者已經(jīng)積累下來不少先進的算法，本文正是沿著先驅(qū)者的腳步，進行實踐，提出問題，發(fā)現(xiàn)問題，并嘗試去解決問題。 六子棋是從2005年才被提出的，因為六子棋比五子棋復雜的多，但目前六子棋的研究成果還借鑒五子棋，這是需要突破的。本文設計和實現(xiàn)了一個六子棋程序，旨在進一步研究六子棋問題，并尋求更優(yōu)秀的解決方案，同時也在六子棋的知識表示方面做了一些新的嘗試。 亞馬遜棋是一種分支因子很大的棋類。國際象棋程序主要用確定性的搜索算法，如alpha-beta搜索進行求解，而大分支因子的程序用alpha-beta的效果一般比較差。在亞馬遜棋中，基于選擇性的搜索方法要稍好些，比如UCT，本文對兩種方法都進行了嘗試。 手機功能的開發(fā)已經(jīng)受到廣泛關注，由于其性能不斷提升，使得擁有復雜算法的程序移植到手機平臺成為可能。鑒于手機本身的方便性，在手機上玩棋牌游戲無疑將會受到棋迷們的歡迎。因此，本文將研究內(nèi)容與流行技術進行有機結(jié)合，把“東秦之星”六子棋程序移植到了手機上，并成功地參加了2010年全國競賽，受到了參賽者的關注。
