簡易檢索 / 詳目顯示

回結果列表
研究生： 陳俊佑
Jyun-You Chen
論文名稱： 八層及九層三角殺棋的勝負問題之改進與研究
On the study and Improvement of 8 Layer and 9 Layer Triangular Nim
指導教授： 林順喜
Lin, Shun-Shii
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2010
畢業學年度： 98
語文別： 中文
論文頁數： 70
中文關鍵詞： 三角殺棋 、人工智慧 、回溯分析 、倒推法
英文關鍵詞： Triangular Nim, Artificial Intelligence, Retrograde
論文種類： 學術論文
相關次數： 點閱：188  下載：14 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 電腦棋類遊戲在人工智慧領域中是很重要的一環。三角殺棋的部份，於1985年由許舜欽教授研究出七層三角殺棋的結果後便一直沒有更高層數三角殺棋的相關文獻了。直至2009年才有白聖群以及林宏軒兩位研究生各自做了八層三角殺棋的破解研究。
    在本論文中，我們使用CPU規格為Intel Xeon E5520 2.27GHz(雙處理器)，記憶體總量為36G Byte 的機器，證明了九層三角殺棋於取得最後一子為敗的規則下，是先手必勝的結果。另外我們也應用 Divide-and-Conquer以及Sprague-Grundy function等方法，列出了九層三角殺棋於取得最後一子為勝的規則下，保證下了必敗的著手。
    我們除了找出九層三角殺棋的結果，也對八層三角殺棋的解法做了分析與改良，提出可以大幅度節省破解所需空間及時間的辦法，更有效率的使用記憶體。雖然以目前的硬體設備只能應用在八層以下的三角殺棋，但是這個概念或許也可以應用在往後的更高層數三角殺棋求解上。

    Computer chess game is a very important part in the field of artificial intelligence. There is no research on Triangular Nim in higher dimensions since Professor Shun-Chin Hsu solved the 7 Layer Triangular Nim in 1985. Then the 8 Layer Triangular Nim had been solved by two graduate students Bai and Lin independently until 2009.
    In this thesis, a dedicated computer equipped with Intel Xeon E5520 2.27GHz(Dual Processor) CPU and 36G Bytes RAM is utilized to conduct our experiments. Thus, we get the result that in the 9 Layer Triangular Nim, the first player can win in misere play. Besides, we also list all the legal moves which can lead the first player lose the game in normal play, by using divide-and-conquer and Sprague-Grundy function.
    In addition to finding the results of 9 Layer Triangular Nim, we also analyze and improve the program for solving the 8 Layer Triangular Nim. We can greatly save time and space. Although the current hardware can only be applied in solving the 8 Layer Triangular Nim, but this concept may be applied to solve Triangular Nim in higher dimensions in the future.

    摘 要 I ABSTRACT II 誌 謝 III 附圖目錄 VI 附表目錄 VIII 第一章 緒論 1 第一節 前言 1 第二節 研究動機 4 第三節 論文架構 4 第二章 相關文獻及基礎理論 5 第一節 相關研究成果 5 第二節 倒推法 7 第三節 產生可行著手 10 第三章 九層三角殺棋之破解 15 第一節 利用必敗盤面的非完全資訊嘗試破解 15 第二節 減少棋子數與重新編碼 19 第三節 Divide-and-Conquer 28 第四節 利用Sprague-Grundy Function 解九層三角殺棋 31 第五節 淺層搜尋演算法 37 第四章 八層三角殺棋之加速與空間之節省 46 第一節 三角殺棋的等價性質與複雜度 46 第二節 重新編碼 46 第三節 於九層三角殺棋上之應用 50 第五章 結論及未來研究方向 53 第一節 結論 53 第二節 未來研究方向 54 附錄 A 九層三角殺棋已知必敗之著手列表 55 參考著作 70

    [1]Charles L. Bouton，“Nim, A Game with a Complete Mathematical Theory,”The Annals of Mathematics, 2nd Ser., Vol. 3, No. 1/4. (1901-1902), pp. 35-39.

    [2]“Wikipedia/Nim,” http://en.wikipedia.org/wiki/Nim.

    [3]群想網路科技， 「CYC 遊戲大聯盟」，http://cyc9.cycgame.com/cyc/cgi-bin/manual.php?i=manG&game=Nim。

    [4]許舜欽，“三角殺棋的電腦解法及其實現”，電腦季刊，第16卷，第4期，pp.15-23, Dec. 1982.

    [5]許舜欽，“利用電腦探討七層角殺棋的勝負問題”，Proc. Of 1985 NCS, pp.798-802, Dec. 1985.

    [6]白聖群，“八層三角殺棋的勝負問題之研究”，2009 National Computer Symposium (NCS 2009)，Workshop on Artificial Intelligence, Fuzzy, and U-Learning (AFU), Taipei, Taiwan, 2009.

    [7]林宏軒，“八層三角殺棋之解法”，2009 National Computer Symposium (NCS 2009), Workshop on Algorithms and Bioinformatics (AB), Taiwan, 2009.

    [8]Grundy, P. M. (1939). "Mathematics and games". Eureka 2: 6–8. Reprinted, 1964, 27: 9–11.

    [9]“Wikipedia/Sprague-Grundy Theorem,”http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem.

    [10]“Wikipedia/Nim,” http://en.wikipedia.org/wiki/Nim.

    [11]S. Russell, P. Norving, Artificial Intelligence: A Modern Approach, 2/E, PEARSON, 2003.

    [12]“Wikipedia/ Alpha-beta pruning,”http://en.wikipedia.org/wiki/Alpha-beta_pruning.

    [13]吳身潤，人工智慧程式設計，維科圖書，2002 年3月。

    下載圖示
    QR CODE