研究生: |
劉孟謙 |
---|---|
論文名稱: |
電腦象棋程式Shark的設計與實作 The Design and Implementation of the Chinese Chess Program Shark |
指導教授: | 林順喜 |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2014 |
畢業學年度: | 102 |
語文別: | 中文 |
論文頁數: | 83 |
中文關鍵詞: | 位棋盤 、人工智慧 、電腦象棋 |
英文關鍵詞: | BitBoard, artificial intelligence, computer Chinese chess |
論文種類: | 學術論文 |
相關次數: | 點閱:213 下載:27 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
電腦對局在人工智慧領域一直是一個非常吸引人的項目,而電腦象棋相關研究發展遠不及國外西洋棋來的豐富,而象棋是我國國粹,因此我們希望針對電腦象棋的領域進行深入的研究探討。本研究以網路上開源的象棋程式「象眼」為基礎,設計改良開發成象棋程式Shark,以供象棋棋手精進棋力、參與各項電腦對局競賽,並期望能與人類大師抗衡。
下棋程式的棋力與搜尋演算法、審局函數息息相關,本研究主要針對這兩項進行改良。我們以軟體工程的概念設計加強演算法的可靠性;研發新的資料結構—BitBoard大幅的增進了審局函數的效能,讓程式能搜尋得更深、且讓特殊棋型的偵測以及複雜的長捉盤面處理可以非常有效率的實現;另外增強程式對於兵卒的掌握以及使用Material Table建構更多程式對於中殘局的知識。
原始象眼估計其棋力約有六段,改良後的Shark與象眼對弈已有80%的勝率,並且於2013年12月參加TAAI電腦對局比賽獲得銅牌、經過再改良後2014年6月參加TCGA電腦對局比賽獲得銀牌,在眾多持續開發多年的象棋程式中擠進了一席之地,估計其棋力已晉升至七段。其後我們將繼續開發改良,期望能更精進棋力,向頂尖程式與人類大師看齊。
Computer gaming is a very interesting subject in artificial intelligence. Compared with Chess, Chinese chess (XiangQi) has fewer researches. Since Chinese chess is the quintessence of Chinese culture, we decide to make a further study on the subject.
Our Chinese chess program "Shark" is improved from "ElephantEye" -an open source Chinese chess program on the Internet. Shark has participated in the TAAI2013 and TCGA 2014computer game tournaments.
The strength of a Chinese chess program depends on its search algorithms and evaluation functions. We attempt to improve the two parts. We apply software engineering principles to improve the reliability of the search algorithms, develop a new data structure -BitBoard to improve the performance of the evaluation functions, make our program able to search deeper, recognize patterns more efficient, and detect the perpetual chase well. Then we build Material Table to establish the knowledge of mid-to-end games.
ElephantEye is ranked about 6 dan. So far Shark has won 80%of the games against ElephantEye. And it wonthebronze medal in TAAI2013, the silver medal in TCGA2014. Itis ranked about 7 dan.
We will continuously improve our Shark program.The ultimate goal is to compete with the strongest program and the human masters.
【1】 Jaap van den Herik, Jos Uiterwijk, Jack van Rijswijck, “Games Solved: Now and in the Future. Artificial Intelligence”, Vol. 134, Nos.1-2, pp. 277-311, (2002)
【2】 涂志堅,“電腦象棋的設計與實現”,中山大學碩士論文,(2004)。
【3】 象棋巫師,http://www.xqbase.com/index.htm
【4】 Alexander Brudno, “Bounds and valuations for shortening the search of estimates”, Problemy Kibernetiki (10) 141–150 and Problems of Cybernetics (10) 225–241, (1963)
【5】 D. E. Knuth and R. W. Moore, “An Analysis of Alpha-Beta Pruning”, Artificial Intelligence 6(4), 293-326, (1975)
【6】 Alexander Reinefeld, “An improvement to the Scout tree search algorithm”, ICCA Journal, (1983)
【7】 Breuker DM, Uiterwijk JWHM, and Herik HJ van den, “Replacement Schemes for Transposition Tables”, ICGA Journal, (1994)
【8】 Chess Programming WIKI, https://chessprogramming.wikispaces.com/
【9】 施宣丞,電腦暗棋程式DarkCraft的設計與實作,國立臺灣師範大學資工所碩士論文,(2012)
【10】 David Levy, David Broughton, Mark Taylor , “The SEX Algorithm in Computer Chess”, ICCA Journal, Vol. 12, No. 1, (1989)
【11】 Intel Instruction Set Architecture Extensions
https://software.intel.com/en-us/intel-isa-extensions