研究生: |
吳聲佑 Wu, Sheng-Yu |
---|---|
論文名稱: |
夏威夷跳棋較小盤面的分析與破解 Analysis and Solving of the Small-Scale Board in Hawaiian Checkers (Konane) |
指導教授: |
林順喜
Lin, Shun-Shii |
口試委員: |
林順喜
Lin, Shun-Shii 吳毅成 Wu, I-Chen 周信宏 Chou, Hsin-Hung 陳志昌 Chen, Jr-Chang 顏士淨 Yen, Shi-Jim |
口試日期: | 2024/07/15 |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2024 |
畢業學年度: | 112 |
語文別: | 中文 |
論文頁數: | 48 |
中文關鍵詞: | 夏威夷跳棋 、組合對局理論 、倒推法 、回溯分析法 、與或樹 、平行程式 |
英文關鍵詞: | Kōnane, Combinatorial Game Theory, Retrograde Analysis, Backtracking, And-Or Tree, Parallel Programming |
研究方法: | 實驗設計法 |
DOI URL: | http://doi.org/10.6345/NTNU202401646 |
論文種類: | 學術論文 |
相關次數: | 點閱:71 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
夏威夷跳棋(Kōnane)為一款由波利尼西亞人所發明的雙人、完全資訊、零和且無隨機性之遊戲。而夏威夷跳棋有趣的地方在於-並非以吃子多者為勝,而是讓對方無可走步者為勝。這使得夏威夷跳棋在分析當前盤面的好壞時,不容易產生好的評估函數進行分析。
本論文以破解8×8以下之方形棋盤為目標,並以許多不同的棋類破解方式例如:倒推法、回溯分析法、組合對局理論、And-Or Tree等嘗試破解。並對夏威夷跳棋的盤面做Bitboard的盤面設計與使用Bitwise的方式進行走步移動作以及搭配平行化的技術做加速。
而實驗結果顯示,以倒推法與回溯分析法的方式進行破解會因為夏威夷跳棋之endgame盤面並非固定,加上在倒推與回溯分析時可能產生無法回歸至初始盤面的分支,而達不到理想的破解方式。而組合對局理論因為實作判斷組合對局值的計算過於繁瑣亦不能達到好的效果。最後本論文是以And-Or Tree的方式搭配Greedy Best-First Search的走步優先方式,以29小時30分31秒的時間成功破解7×7的夏威夷跳棋盤面。
Kōnane, invented by Polynesians, is a two-player, perfect information, zero-sum game with no randomness. An interesting aspect of Kōnane is that the winner is not determined by capturing the most pieces, but by rendering the opponent unable to make a move. This unique win condition makes it challenging to develop effective evaluation functions for analyzing the game states.
This thesis aims to solve Kōnane on square boards of size up to 8×8, employing various solving techniques such as retrograde analysis, backtracking, combinatorial game theory, and And-Or Trees. The board design utilizes Bitboards, and move generation is implemented using Bitwise operations, and accelerated with parallelization techniques.
Experimental results indicate that retrograde and backtracking methods are not ideal for solving Kōnane due to the non-fixed nature of endgame positions and potential branches that cannot revert to the initial board state. The combinatorial game theory approach also proved ineffective due to the complexity of computing game values. Ultimately, this thesis successfully solved the 7×7 Kōnane board in 25 hours, 45 minutes and 31 seconds using an And-Or Tree approach combined with Greedy Best-First Search prioritization.
[1] Hearn, R.A. (2009). Amazons, Konane, and Cross Purposes are PSPACE-complete. In M.H. Albert and R.J. Nowakowski (Eds.), Games of No Chance 3 (MSRI Publications 56), pp. 287–306. Cambridge University Press. doi:10.1017/CBO9780511807251.015.
[2] Jos Uiterwijk (2021). Maastricht University, The Netherlands. Solving Narrow Konane boards. In ICGA Journal 43 (2021) 162–183, doi:10.3233/ICG-220198.
[3] Thompson, D. (2005). Teaching a Neural Network to Play Konane. Bachelor Thesis, Department of Computer Science, Bryn Mawr College.
[4] Hendrick, K. (2018). Analysis of Artificial Intelligence Techniques for Konane. Bachelor Thesis, Department of Computer Science, Texas Christian University.
[5] 白聖群,八層及九層三角殺棋的勝負問題之改進與研究,國立臺灣師範大學資訊工程研究所碩士論文,2009。
[6] 林宏軒,八層三角殺棋之解法, 2009 National Computer Symposium (NCS 2009), Workshop on Algorithms and Bioinformatics, Taiwan, 2009.
[7] 李明臻,台灣直棋的勝負問題之研究,國立臺灣師範大學資訊工程研究所碩士論文,2011。
[8] 黃郁雯,冷卻骨牌遊戲之組合對局值,國立交通大學多媒體工程研究所碩士論文,2011。
[9] M. D. Ernst, Playing Konane Mathematically: A Combinatorial Game-theoretic Analysis. UMAP Journal, 16(2), 95-121, 1995.
[10] Intel® Intrinsics Guide, Available:https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#ig_expand=498,5139,5139.
[11] P. Norvig, Available:https://github.com/norvig/pytudes/blob/main/ipynb/Konane.ipynb.
[12] 徐讚昇,電腦對局理論,臺大出版中心,2017。
[13] OpenMP Tutorial, Available:https://www.openmp.org/resources/tutorials-articles.