Combining Monte-Carlo Tree Search with Proof-Number Search
This incremental improvement benefits game AI researchers and developers by enhancing performance in specific board games.
The paper tackled the problem of improving decision-making in games by combining Proof-Number Search and Monte-Carlo Tree Search into a new method called PN-MCTS, which achieved win rates up to 94.0% and outperformed basic MCTS in games like Lines of Action and MiniShogi.
Proof-Number Search (PNS) and Monte-Carlo Tree Search (MCTS) have been successfully applied for decision making in a range of games. This paper proposes a new approach called PN-MCTS that combines these two tree-search methods by incorporating the concept of proof and disproof numbers into the UCT formula of MCTS. Experimental results demonstrate that PN-MCTS outperforms basic MCTS in several games including Lines of Action, MiniShogi, Knightthrough, and Awari, achieving win rates up to 94.0%.