(54.227.48.147) 您好!臺灣時間:2018/02/18 16:22          離開系統
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
研究生:陳俊佑
研究生(外文):Jyun-You Chen
論文名稱:八層及九層三角殺棋的勝負問題之改進與研究
論文名稱(外文):On the study and Improvement of 8 Layer and 9 Layer Triangular Nim
指導教授:林順喜林順喜引用關係
指導教授(外文):Shun-Shii Lin
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文出版年:2009
畢業學年度:98
語文別:中文
論文頁數:70
中文關鍵詞:三角殺棋人工智慧回溯分析倒推法
外文關鍵詞:Triangular NimArtificial IntelligenceRetrograde
相關次數:
  • 被引用被引用:0
  • 點閱點閱:431
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:28
  • 收藏至我的研究室書目清單書目收藏:0
電腦棋類遊戲在人工智慧領域中是很重要的一環。三角殺棋的部份,於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.

摘 要 I
ABSTRACT II
誌 謝 III
附圖目錄 VI
附表目錄 VIII
第一章 緒論 1
第一節 前言 1
第二節 研究動機 4
第三節 論文架構 4
第二章 相關文獻及基礎理論 5
第一節 相關研究成果 5
第二節 倒推法 7
第三節 產生可行著手 10
第三章 九層三角殺棋之破解 15
第一節 利用必敗盤面的非完全資訊嘗試破解 15
第二節 減少棋子數與重新編碼 19
第三節 Divide-and-Conquer 28
第四節 利用Sprague-Grundy Function 解九層三角殺棋 31
第五節 淺層搜尋演算法 37
第四章 八層三角殺棋之加速與空間之節省 46
第一節 三角殺棋的等價性質與複雜度 46
第二節 重新編碼 46
第三節 於九層三角殺棋上之應用 50
第五章 結論及未來研究方向 53
第一節 結論 53
第二節 未來研究方向 54
附錄 A 九層三角殺棋已知必敗之著手列表 55
參考著作 70

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

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

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

[4]許舜欽,“三角殺棋的電腦解法及其實現”,電腦季刊,第16卷,第4期,pp.15-23, Dec. 1982.

[5]許舜欽,“利用電腦探討七層角殺棋的勝負問題”,Proc. Of 1985 NCS, pp.798-802, Dec. 1985.

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

[7]林宏軒,“八層三角殺棋之解法”,2009 National Computer Symposium (NCS 2009), Workshop on Algorithms and Bioinformatics (AB), Taiwan, 2009.

[8]Grundy, P. M. (1939). "Mathematics and games". Eureka 2: 6–8. Reprinted, 1964, 27: 9–11.

[9]“Wikipedia/Sprague-Grundy Theorem,”http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem.

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

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

[12]“Wikipedia/ Alpha-beta pruning,”http://en.wikipedia.org/wiki/Alpha-beta_pruning.

[13]吳身潤,人工智慧程式設計,維科圖書,2002 年3月。
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為畢業學校提供,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡速修正。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔