以棋型分數、開局庫、平行化方法改良 MCTS 外圍開局五子棋程式

Improving an MCTS Outer-Open Gomoku Program with Pattern Scores, Opening Book, and Parallelization

蔡秉倫(Tsai Ping Lung)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程學系/碩士(2023年)

https://doi.org/10.6345/NTNU202300882

摘要

五子棋是一個古老的棋類遊戲，它有著簡單易學且豐富多樣的策略和高度的競技性的特點。由於原始規則的不公平性，現在的五子棋有各種不同的棋規，例如交換行棋權的SWAP2、帶有禁手規則的Renju、外圍開局五子棋等。儘管棋規各異，但遊戲的勝利目標始終是達成“連五”。
本論文旨在研究外圍開局五子棋相關的各層面，探討包括現有的遊戲策略和演算法等技術應用。我們的目標是透過設計棋型分數、開局庫的方法來提升傳統MCTS外圍開局五子棋程式的棋力，並利用平行化的方法加速程式的效能。最後，我們將和第三方程式進行比較測試，用來評估其棋力。

關鍵字

五子棋 ； 蒙地卡羅樹搜索 ； 開局庫

並列摘要

Gomoku is an ancient board game characterized by its simplicity, diverse strategies, and high level of competitiveness. Due to the inherent unfairness in the original rules, there are various variations of Gomoku, such as SWAP2, which allows the second player to swap colors, Renju, which incorporates forbidden move rules for the first player, and Outer-Open Gomoku. Despite the rule variations, the objective of the game remains the same: achieving a “five-in-a-row” pattern.
This thesis aims to investigate different aspects of Outer-Open Gomoku, including the game strategies, and algorithms. Our goal is to enhance the playing strength of MCTS Outer-Open Gomoku program by designing scores for some specific patterns and using opening book. Additionally, we improve its performance through parallelization techniques. Finally, we compare and test the program against third-party programs to evaluate its strength.

並列關鍵字

Gomoku ； MCTS ； Opening Book

參考文獻

[1] Crazy Stone, https://www.remi-coulom.fr/CrazyStone/.

[2] UCT (Upper Confidence bounds applied to Trees), https://cs.stackexchange.com/q/111619.

[3] D. Silver et al., “Mastering the Game of Go with Deep Neural Networks and Tree Search,” Nature 2016 529:7587, vol. 529, no. 7587, pp. 484–489, 2016.

[4] D. Silver et al., “Mastering the Game of Go without Human Knowledge,” Nature 2017 550:7676, vol. 550, no. 7676, pp. 354–359, 2017.

[5] L. V. Allis, Searching for Solutions in Games and Artificial Intelligence, Ph.D. Thesis, University of Limburg, Maastricht, 1994.