簡易檢索 / 詳目顯示

研究生: 劉孟謙
論文名稱: 電腦象棋程式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
論文種類: 學術論文
相關次數: 點閱:226下載: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.

    摘要 i ABSTRACT ii 致謝 iii 目錄 iv 圖目錄 vi 表目錄 viii 第1章 緒論 1 1.1 研究背景 1 1.2 研究目的 2 1.3 研究意義 2 第2章 文獻探討 4 2.1 相關論文及程式介紹 4 2.1.1 象眼 4 2.1.2 ELP 4 2.1.3 棋謀 5 2.1.4 象棋世家 5 2.1.5 BrainChess 5 2.2 電腦對局理論 6 2.3 演算法 8 2.3.1 Mini-Max Search 8 2.3.2 Alpha-Beta Search 10 2.3.3 PVS 13 2.3.4 水平線效應、寧靜搜尋 16 2.4 資料結構 18 2.4.1 棋盤表示與走步生成 18 2.4.2 Transposition Table 20 2.5 審局函數 22 2.6 後續發展 23 第3章 方法與步驟 24 3.1 資料結構的改進 24 3.1.1 適用於象棋的BitBoard 24 3.1.2 BitBoard的棋盤表示法 26 3.1.3 棋子表示法 27 3.1.4 Intrinsic函數 29 3.1.5 BitBoard的基本操作指令 31 3.1.6 以BitBoard加速走步產生 34 3.1.7 Magic Hash 39 3.2 演算法改進 41 3.2.1 走步排序策略 41 3.2.2 Late move reduction (LMR) 44 3.2.3 PVS的改良 46 3.2.4 控制格計算 47 3.2.5 長捉的偵測 49 3.3 審局函數改進 56 3.3.1 子力價值 56 3.3.2 特殊棋型 58 3.3.3 自由度 63 3.3.4 Material Table 66 第4章 實驗結果與未來發展 69 參考文獻 73 附錄A – TAAI 2013電腦對局比賽棋譜 74 附錄B – TCGA 2014電腦對局比賽棋譜 79

    【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

    下載圖示
    QR CODE