簡易檢索 / 詳目顯示

研究生: 吳聲佑
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 1.1 研究背景 1 1.2 研究動機及目的 2 1.3 研究流程 3 第二章 文獻探討 5 2.1 背景 5 2.2 夏威夷跳棋性質與棋規 6 2.2.1 夏威夷跳棋性質 6 2.2.2 盤面放置方式 8 2.2.3 開局方式 8 2.2.4 走步方式與勝敗條件 9 2.3 夏威夷跳棋之策略 10 2.4 夏威夷跳棋之數學方法 10 第三章 夏威夷跳棋的破解方法分析 13 3.1 夏威夷跳棋破解嘗試方法一:回溯分析法與倒推法 13 3.1.1 回溯分析法 13 3.2.2 倒推法 16 3.1.3 回溯分析法與倒推法應用分析 18 3.2 夏威夷跳棋破解嘗試方法二:組合對局理論中的獨立性來加速 18 3.2.1 3×3 夏威夷跳棋之組合對局值計算 19 3.2.2 組合對局理論之應用分析 24 3.3 夏威夷跳棋破解嘗試方法三:And-Or Tree 與Greedy Best-First Search 25 3.3.1 夏威夷跳棋之And-Or Tree 25 3.3.2 夏威夷跳棋之And-Or Tree 應用分析 28 第四章 方法與實踐 29 4.1 夏威夷跳棋之資料結構 29 4.2 夏威夷跳棋走步方式之加速設計 30 4.2.1 夏威夷跳棋走步之同時取得某一方向可移動棋子之盤面 30 4.2.2 夏威夷跳棋可走步盤面使用之Bitwise設計 34 4.3 And-Or Tree 與Greedy Best-First Search之設計 35 4.4 平行化之加速設計 35 第五章 實驗結果 38 5.1 設備與參數 38 5.2 比較對象 38 5.3 綜合比較結果 39 5.3.1 二維陣列與Bitboard設計之效能比較 39 5.3.2 純And-Or Tree與Greedy Best-First Search策略比較 39 5.3.3 Greedy Best-First Search與己方走步最大優先策略比較 40 5.3.4 深度優先平行化加速之比較 40 5.3.5 廣度優先平行化加速之比較 41 5.4 目前破解盤面結果 41 5.4.1 方形盤面之必勝玩家與其計算時間 42 5.4.2 矩形盤面之必勝玩家與其計算時間 43 第六章 結論及未來方向 45 6.1 結論 45 6.2 未來展望 45 參考文獻 47

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

    無法下載圖示 電子全文延後公開
    2026/08/15
    QR CODE