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

Abstract

電腦棋類遊戲在人工智慧領域中是很重要的。而三角殺棋部份，自從許舜欽教授在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 twokinds 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.