AlphaZero-based Proof Cost Network to Aid Game Solving

Ti-Rong Wu · Chung-Chin Shih · Ting Han Wei · Meng Yu Tsai · Wei-Yuan Hsu · I-Chen Wu

Keywords: [ deep reinforcement learning ] [ Monte-Carlo tree search ]

[ Abstract ]
[ Visit Poster at Spot E0 in Virtual World ] [ OpenReview
Thu 28 Apr 2:30 a.m. PDT — 4:30 a.m. PDT


The AlphaZero algorithm learns and plays games without hand-crafted expert knowledge. However, since its objective is to play well, we hypothesize that a better objective can be defined for the related but separate task of solving games. This paper proposes a novel approach to solving problems by modifying the training target of the AlphaZero algorithm, such that it prioritizes solving the game quickly, rather than winning. We train a Proof Cost Network (PCN), where proof cost is a heuristic that estimates the amount of work required to solve problems. This matches the general concept of the so-called proof number from proof number search, which has been shown to be well-suited for game solving. We propose two specific training targets. The first finds the shortest path to a solution, while the second estimates the proof cost. We conduct experiments on solving 15x15 Gomoku and 9x9 Killall-Go problems with both MCTS-based and FDFPN solvers. Comparisons between using AlphaZero networks and PCN as heuristics show that PCN can solve more problems.

Chat is not available.