夏威夷跳棋較小盤面的分析與破解

Abstract

夏威夷跳棋(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.