簡易檢索 / 詳目顯示

研究生: 李明臻
Ming-Zhen Li
論文名稱: 台灣直棋的勝負問題之研究
指導教授: 林順喜
Lin, Shun-Shii
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2011
畢業學年度: 99
語文別: 中文
論文頁數: 50
中文關鍵詞: 電腦直棋回溯分析演算法人工智慧
論文種類: 學術論文
相關次數: 點閱:135下載:29
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 電腦棋類遊戲在人工智慧領域中是很重要的,各種棋類遊戲研究層出不窮。直棋(Morris)遊戲屬於雙人遊戲的一種,自從Ralph Gasser教授在1996年提出破解Nine Men's Morris的結果之後,有關Morris games更高一層或其它版本的研究,相關文獻就十分少見。
    台灣規則的直棋遊戲是Twelve Men's Morris在台灣的變體。在本論文中,我們使用CPU規格為Intel Xeon E5520 2.27GHz(雙處理器),記憶體總量為36 GByte 的機器,證明了台灣規則的直棋遊戲在開始雙方各拿六子及九子的情況,其結果都為和棋。
    我們除了找到台灣規則的直棋遊戲在開始雙方各拿六顆棋子及九顆棋子的勝負結果是和棋,更從破解Nine Men's Morris的方法中,在放子階段提出跟原本作法不同的破解方法。在研究台灣規則的直棋遊戲的過程中,找到了將資料庫分割得更細的方法以及加速旋轉對稱運算的方法,並且將其運用在資料庫技術及回溯分析演算法上。

    Computer chess games are very important in the field of artificial intelligence. There are very few research results on Morris in higher dimensions or in other variations since Professor Ralph Gasser solved Nine Men's Morris in 1996.
    The board of Taiwan Morris game is same as the board of Twelve Men's Morris. In this thesis, a personal computer equipped with AMD Athlon64 X2 4000+ 2.1GHz CPU and 36 GBytes RAM is utilized to conduct our experiments. Thus, it gets the results of Taiwan Morris game that each player starts with six or nine pieces are a first-player draw.
    In addition, we find some skills for improving the performance of our programs. We used retrograde analysis algorithm and databases in the opening stage of Taiwan Morris games. We also describe some methods employed to accelerate the calculation, such as rotation and symmetry permutation.

    摘 要 i ABSTRACT ii 誌 謝 iii 附表目錄 vi 附圖目錄 vii 第一章、 緒論 1 第一節、 簡介 1 第二節、 研究動機 2 第三節、 論文組織 3 第二章、 相關研究探討 4 第一節、 台灣直棋 4 第二節、 直棋(Morris)相關研究成果 8 第三節、 回溯分析演算法 12 第四節、 殘局庫 15 第三章、 如何破解台灣直棋 18 第一節、 回溯分析演算法的改良 18 第二節、 殘局資料庫的改良 22 第三節、 放子階段的作法 26 第四節、 Zobrist hashing 演算法 29 第四章、 其它加速方法 31 第一節、 旋轉及對稱 31 第二節、 回溯分析演算法運用旋轉及對稱 35 第三節、 加速相似運算 37 第五章、 實驗成果 42 第一節、 實驗設計 42 第二節、 六子台灣直棋 42 第三節、 九子台灣直棋 46 第六章、 結論與未來研究方向 49 第一節、 結論 49 第二節、 未來研究方向 49 參考著作 50

    [1] Ralph Gasser, "Applying Retrograde Analysis to Nine Men’s Morris," Heuristic Programming in Artificial Intelligence; The Second Computer Olympiad, D.N.L. Levy and D.F. Beal (ed.), Ellis Horwood, London, 1991, 161-173.
    [2] Ralph Gasser, "Solving Nine Men's Morris," R.J. Nowakowski (Ed.), Games of No Chance. MSRI Publications, Vol. 29, Cambridge University Press, Cambridge, MA, 1996, pp. 101-113.
    [3] 白聖群, "八層三角殺棋的勝負問題之研究" ,國立臺灣師範大學資訊工程研究所碩士論文,2009。
    [4] 黃文樟, "電腦象棋深象中局程式的設計與實作" ,國立臺灣師範大學資訊工程研究所碩士論文,2006。
    [5] 謝曜安, "電腦暗棋之設計及實作" ,國立臺灣師範大學資訊工程研究所碩士論文,2008。
    [6] 吳光哲, "電腦象棋搜尋圖歷史交互作用問題之研究" ,台灣大學資訊工學研究所碩士論文,2005。
    [7] 許舜欽, "直棋的電腦解法及其實現" ,國立台灣大學工程學刊,第三十二期,第1-10頁,1982。

    下載圖示
    QR CODE