電腦暗棋機率型節點搜尋及相關問題之研究

Abstract

在過去幾十年裡，人工智慧在對局領域取得了長足的進步。其中帶有隨機因素的對局遊戲也成為一個重要的子領域。而暗棋可以翻棋子的獨特玩法所產生的機率行為，對於電腦來說是設計時的一大挑戰。本篇論文將進行電腦暗棋程式的相關研究，並且對暗棋中的機率型節點的搜尋提供一些改進的策略。我們將基於alpha-beta搜尋實作暗棋程式，並根據棋種之間的競爭關係設計審局函數。在搜尋機率型節點時，我們採用star搜尋演算法進行剪枝，最後發現star2搜尋演算法在預先探測時，若搭配好的排序可以大幅降低搜尋時間、減少搜尋節點，並且擁有較好的戰績。