八層及九層三角殺棋的勝負問題之改進與研究

On the study and Improvement of 8 Layer and 9 Layer Triangular Nim

陳俊佑(Jyun-You Chen)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2010年)

摘要

電腦棋類遊戲在人工智慧領域中是很重要的一環。三角殺棋的部份，於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.

並列關鍵字

Triangular Nim ； Artificial Intelligence ； Retrograde

參考文獻

[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.

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

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

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

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