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

Abstract

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