八層三角殺棋的勝負問題之研究

On the Study of 8 Layer Triangular Nim

白聖群

指導教授 ： 林順喜

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

摘要

電腦棋類遊戲在人工智慧領域中是很重要的。而三角殺棋部份，自從許舜欽教授在1985年研究出七層三角殺棋結果後。三角殺棋更多層數的結果，就沒有任何相關文獻了。
　　在本論文中，我們使用CPU為AMD Athlon64 X2 4000+ 2.1GHz，記憶體為8G Byte的個人電腦，花費約十四個小時半的時間，證明了兩種規則的八層三角殺棋皆為先手勝。
　　我們除了找到八層三角殺棋的結果，也提出了一些解三角殺棋勝負時，可以加快搜尋勝負速度的方法。雖然研究過程中花費許多時間在倒推法上，但我們也研究出來所有先前求出的盤面是可以運用到之後要求解的三角殺棋。並且提出了一個管理記憶體的方式，使得在求解三角殺棋的過程中，盤面資訊狀態可以儲存，這樣就可以利用較少量記憶體來解八層三角殺棋，而不必動用到虛擬記憶體。

關鍵字

人工智慧 ； 三角殺棋

並列摘要

Computer chess games are very important in the field of artificial intelligence. There is no research results on Triangular Nim in higher dimensions Since Professor Shun-Chin Hsu solved 7 layer triangular Nim in 1985.
In this thesis, a personal computer equipped with AMD Athlon64 X2 4000+ 2.1GHz CPU and 8 GBytes RAM is utilized to conduct our experiments. Thus, it spends 14.5 hours and gets the results that two kinds of 8 layer Triangular Nim are a first-player win.
In addition, we find some skills for improving the performance of our programs. We can save the sub-problem results and reuse these results for solving Triangular Nim in higher dimensions. A memory management scheme is also proposed to reduce the memory requirements which can avoid the virtual memory swapping.

並列關鍵字

artificial intelligence ； Triangular Nim

參考文獻

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

[3] Alan Tucker，“Applied Combinatorics＂，John Wiley & Sons; 3rd edition，June 1994.

[9] 謝曜安，“電腦暗棋之設計及實作”，國立臺灣師範大學資訊工程研究所碩士論文，2008。

[10] 方裕欽，“UCT算法的適用性及改進策略研究－以黑白棋為例”，國立臺灣師範大學資訊工程研究所碩士論文，2008。

[2]“Wikipedia＂，網址：http://en.wikipedia.org/wiki/Nim