Generalized Proof-Number Monte-Carlo Tree Search
Jakub Kowalski, Dennis J. N. J. Soemers, Szymon Kosakowski, Mark H. M. Winands · 2025
Read Generalized Proof-Number Monte-Carlo Tree Search by Jakub Kowalski, Dennis J. N. J. Soemers, Szymon Kosakowski, Mark H. M. Winands (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-13249.txt.
Introduction
Jakub Kowalski and three co-authors present a generalized search method for game playing programs in this 2025 paper. Monte Carlo Tree Search explores game trees by sampling, guided by a score rule. Proof Number Search instead tracks how close a node is to a proven win or loss. Recent work mixed the two, using proof counts to steer sampling. The authors rebuild that mix with three changes.
First, proof counts are tracked per player, which removes the need for separate disproof counts and opens the method to games with more than two players. Second, simpler steering rules proved as strong as complex ones. Third, the method now handles score bounds, not just wins and losses. Across eleven board games, the new search won far more often in eight of them.
Catalog record
| CREATOR | Jakub Kowalski, Dennis J. N. J. Soemers, Szymon Kosakowski, Mark H. M. Winands |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-13249
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalized Proof-Number Monte-Carlo Tree Search Jakub Kowalski, Dennis J. N. J. Soemers, Szymon Kosakowski, Mark H. M. Winands Abstract This paper presents Generalized Proof-Number Monte-Carlo Tree Search: a generalization of recently proposed combinations of Proof-Number Search (PNS) with Monte-Carlo Tree Search (MCTS), which use (dis)proof numbers to bias UCB1-based Selection strategies towards parts of the search that are expected to be easily (dis)proven. We propose three core modifications of prior combinations of PNS with MCTS. First, we track proof numbers per player. This reduces code complexity in the sense that we no longer need disproof numbers, and generalizes the technique to be applicable to games with more than two players. Second, we propose and extensively evaluate different methods of using proof numbers to bias the selection strategy, achieving strong performance with strategies that are simpler to implement and compute. Third, we merge our technique with Score Bounded MCTS, enabling the algorithm to prove and leverage upper and lower bounds on scores—as opposed to only proving wins or not-wins. Experiments demonstrate substantial performance increases, reaching the range of 80% for 8 out of the 11 tested board games. † † paperid: 9404 † † orcid: 0000-0003-1932-4278 † † orcid: 0000-0003-3241-8957 † † orcid: 0009-0006-7992-0310 † † orcid: 0000-0002-0125-0824 1 Introduction Monte-Carlo Tree Search (MCTS) [ Coulom(2007) , Kocsis and Szepesvári(2006) ] is a best-first search method guided by the results of Monte-Carlo simulations, well established in game AI [ Browne et al.(2012)Browne, Powley, Whitehouse, Lucas, Cowling, Rohlfshagen, Tavener, Perez, Samothrakis, and Colton , Świechowski et al.(2023)Świechowski, Godlewski, Sawicki, and Mańdziuk ] . Using the results of previous simulations, the method gradually builds up a game tree in memory and increasingly becomes better at accurately estimating the values of the most promising moves. MCTS has substantially advanced the state of the art in several deterministic game domains, in particular Go [ Silver et al.(2017)Silver, Schrittwieser, Simonyan, Antonoglou, Huang, Guez, Hubert, Baker, Lai, Bolton, Chen, Lillicrap, Hui, Sifre, van den Driessche, Graepel, and Hassabis ] , but also other board games including Amazons [ Lorentz(2008) ] , Hex [ Arneson et al.(2010)Arneson, Hayward, and Henderson ] , Lines of Action [ Winands et al.(2010)Winands, Björnsson, and Saito ] , and General Game Playing (GGP) [ Björnsson and Finnsson(2009) ] . In tactical games, where the main line towards the winning position is typically narrow with many non-progressing alternatives, MCTS may often lead to an erroneous outcome because the nodes’ values in the tree do not converge fast enough to their game-theoretic value. To mitigate this effect, MCTS variants have been proposed that integrate minimax search [ Winands et al.(2008)Winands, Björnsson, and Saito , Winands and Björnsson(2011) , Lanctot et al.(2014)Lanctot, Winands, Pepels, and Sturtevant , Baier and Winands(2015) ] . Recently, Proof-Number Search (PNS) [ Allis et al.(1994)Allis, van der Meulen, and van den Herik ] has been integrated in MCTS [ Doe et al.(2022)Doe, Winands, Soemers, and Browne , Randall et al.(2024)Randall, Müller, Wei, and Hayward ] . PNS has the advantage proving endgames faster than traditional minimax in many domains. The variant PN-MCTS [ Kowalski et al.(2024)Kowalski, Doe, Winands, Górski, and Soemers ] has been shown to improve over default MCTS in domains such as Lines of Action, MiniShogi, Knightthrough, and Awari. In this paper, we propose a generalization of PN-MCTS, called Generalized Proof-Number Monte-Carlo Tree Search (GPN-MCTS). First, this extension of PN-MCTS tracks proof numbers per player, which reduces code complexity in the sense that we no longer need disproof numbers, and generalizes the technique to be applicable to games with more than two players. Second, GPN-MCTS contains different enhancements of using proof numbers to bias the UCT selection strategy [ Kocsis and Szepesvári(2006) ] , achieving strong performance with strategies that are simpler to implement and compute. Third, PN-MCTS is integrated with Score Bounded MCTS [ Cazenave and Saffidine(2011) ] , enabling the technique to prove and leverage upper and lower bounds on scores—as opposed to only proving wins or non-wins. For the purpose of the experiments, GPN-MCTS was implemented in the Ludii general game playing system [ Piette et al.(2020)Piette, Soemers, Stephenson, Sironi, Winands, and Browne ] . 1 1 1 After the reviewing process a pull request would be proposed to include GPN-MCTS into the official public repository of the Ludii project. Although it is not guaranteed to work for every game, in many cases when it works, its improvements are significant, reaching 80% win rate on 8 out of the 11 tested board games, and over 60% on the remaining three. Moreover, we show that it pairs well with the Score-bounded MCTS enhancement. This paper is organized as follows. First, Section 2 describes the foundational methodology for this paper, MCTS and PNS. Next, Generalized Proof-Number MCTS is introduced in Section 3 . Subsequently, the approach is tested on a diverse set of games in Section 4 . Finally, the paper concludes and gives an outlook on future research in Section 5 . 2 Background 2.1 Monte Carlo Tree Search Monte Carlo Tree Search (MCTS) [ Coulom(2007) , Kocsis and Szepesvári(2006) ] is a best-first search method that gradually builds up a search tree, balancing exploitation of parts that seem promising based on earlier iterations, with explorations of parts that were infrequently explored. It does this by iterating through four strategic steps [ Chaslot et al.(2008)Chaslot, Winands, van den Herik, Uiterwijk, and Bouzy ] , depicted in Figure 1 , until a time or iteration budget expires. Figure 1: Outline of Monte-Carlo Tree Search. Selection Step. The selection step traverses the tree, starting from the root node, until a node is reached for which there are still legal actions that have not yet been expanded into nodes of the search tree (or until a terminal node is reached). This step implements the trade-off between exploration and exploitation. One of the most common baseline implementations of MCTS—referred to as Upper confidence Bounds applied to Trees (UCT) [ Kocsis and Szepesvári(2006) ] —uses the UCB1 strategy [ Auer et al.(2002)Auer, Cesa-Bianchi, and Fischer ] to choose among the children of any given current node. It works as follows. Let I be the set of nodes immediately reachable from the current node p . The selection strategy selects the child b of node p that satisfies Formula ( 1 ): \mathit{b\in\mathrm{argmax}_{i\in I}\left(v_{i}+C\times\sqrt{\frac{\ln{n_{p}}}{n_{i}}}\right)}, (1) where v_{i} is the estimated value of the node i , n_{i} is the visit count of i , and n_{p} is the visit count of p . C is a hyperparameter which can be tuned experimentally. Here, ties are broken randomly. Expansion Step. As previously stated, the selection step continues until a node is reached that has not yet expanded all of its children. Among the children that have not been stored in the tree, one is selected uniformly at random. This node L is then added as a new leaf node. If the selection step arrives at a terminal node, the expansion and subsequent play-out steps are skipped. Play-out Step. From the new leaf node L onwards, the play-out step is performed. Moves are selected in self-play until the end of the game is reached. This step might consist of playing uniformly random moves or—often