利用啟發式法則與數種訓練策略來評估中國跳棋程式

Abstract

中國跳棋(Chinese Checkers)是一個知名且充滿挑戰性的完全資訊遊戲。與一些其他的傳統遊戲如五子棋、圍棋不同，賽局樹的搜索空間並不會隨著遊戲的進行而越來越小。若是單純使用AlphaZero架構之演算法，在短時間內甚至難以訓練出初學者程度之程式。過去雖有使用蒙地卡羅樹搜索法結合深度學習與強化學習，並應用於中國跳棋上的演算法，但是仍有改進的空間。若是能夠適當的加入一些中國跳棋的先備知識，應該能使棋力進一步的提升。本研究針對中國跳棋設計數種策略，修改了前代程式Jump的設計，人為的增加先備知識，以期有更好的棋力，並且針對中國跳棋在神經網路訓練初期棋力很弱的問題，提出一連串的解決方案與策略，使其能夠在不使用人為訓練資料以及預訓練的狀況下，能夠獲得一定的棋力，並且對這些策略的特點進行探討，分析出各個策略的優缺點。Chinese Checkers is a well-known and challenging board game with perfect information. Unlike some other traditional games, such as Gomoku and Go, the search space of the game tree does not decrease as the game progresses. In the past, Monte Carlo Tree Search combining deep learning and reinforcement learning was used in some Chinese Checkers programs, but there’s still room for improvement. If some heuristics of Chinese Checkers can be properly added, it should be able to further improve the strength.In this work, we present an approach that combines Monte Carlo Tree Search, deep learning, and reinforcement learning with several heuristic methods. We modified the predecessor program Jump, and the heuristics were manually investigated in order to improve its strength. Furthermore, a series of strategies are proposed to solve the training problem when the neural network is not precise in the early stage of training without any hand-made training data and without pre-training. We analyze and discuss the advantages and disadvantages of each strategy.