電腦五子棋程式JacksonFive之設計與實作

五子棋（Gomoku）是個歷史悠久的棋類遊戲，規則簡單但遊戲複雜度相當高，非常具有研究價值。其中比較常見的搜尋演算法有MiniMax、Alpha Beta Pruning、Iterative Deepening及Monte Carlo Tree Search（MCTS）等等。在這些演算法的實作細節中，存在著一些可以改進搜尋效率或精準度的地方。包括MCTS中的expansion階段可以利用米字型遮罩來減少搜尋廣度、simulation階段加上深度加權的調整，使得不同模擬深度有不同的分數。在最傳統的MCTS算法中，也存在著一些尚待解決的問題。例如贏率稀釋問題，最優走步的贏率會被其他分支稀釋掉，因此分支愈多的子樹會被稀釋得更嚴重，因此，本論文提出了兩種解決稀釋問題的方法。 MCTS也存在一個缺點，就是不管盤面為何，都要經過固定的搜尋時間、或是一定的模擬次數才會決定走步。因此，本論文提出了一套時間控管機制，可以針對不同的盤面情況，給予不同的MCTS搜尋時間。透過種種的改良，我所撰寫的程式JacksonFive也參加過數次的電腦對局比賽的外五棋項目，其中在TCGA 2015拿到銅牌、ICGA 2016拿到銅牌、TAAI 2017拿到銅牌、TCGA 2017拿到銀牌、ICGA 2018拿到金牌。另外，本論文的部份成果已發表在The 10th International Conference on Computers and Games (CG 2018)的一篇論文中。

關鍵字

電腦對局；五子棋；蒙地卡羅樹；贏率加權；深度加權

並列摘要

Gomoku is a long-existing chess game that, despite its simple rules, has high game complexity, thus making it worthy of study. Commonly used search algorithms in Gomoku include MiniMax, Alpha Beta Pruning, Iterative Deepening and Monte Carlo Tree Search (MCTS). However, the search efficiency and precision of these algorithms can still be improved. For example, in MCTS, using a Union jack-shaped mask can narrow the breadth of search in the expansion phase, while adding depth reward adjustment to the simulation phase can help differentiate the scores in different depth simulations. The traditional MCTS algorithm also has its weaknesses. For example, the win rate of the optimal move will be averaged by other branches, and the more branches a node has, the more pronounced the averaging effect. In response to this problem, this thesis provides two solutions. Another problem with the traditional MCTS is that, before it determines a move, it requires a fixed amount of search time or number of times running simulations, regardless of the board position. As a solution to this problem, this thesis provides a method that can regulate the MCTS search time according to the board position. With a series of modifications, our program, JacksonFive, competed in the category of Outer-Open Gomoku in several computer game competitions and has won a bronze medal at the TCGA 2015, a bronze medal at the ICGA 2016, a bronze medal at the TAAI 2017, a silver medal at the TCGA 2017 and a gold medal at the ICGA 2018. In addition, some of the findings of this study have been published in a paper in the 10th International Conference on Computers and Games (CG 2018).