Paper deep dive
Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games
Quentin Cohen-Solal
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/27/2026, 7:07:13 AM
Summary
The paper proposes 'Unbounded Maxn', a novel search algorithm that generalizes the 'Unbounded Minimax' algorithm from two-player zero-sum games to the multi-player perfect-information game framework. The algorithm maintains key principles like unbounded search and incremental state resolution while adapting to multi-objective settings. Experimental results across several benchmark games (e.g., Blokus, Hex, and custom multi-player versions) demonstrate that Unbounded Maxn, especially with the 'safe decision' variant, outperforms existing multi-player algorithms like Maxn, Paranoid, BRS, and MCTS.
Entities (10)
Relation Signals (5)
Unbounded Maxn â generalizes â Unbounded Minimax
confidence 100% · In this section, we introduce our generalization of Unbounded Minimax to the multi-player setting. We call this algorithm Unbounded Maxn.
Unbounded Minimax â ispartof â AthĂ©nan architecture
confidence 100% · It forms, with its safe decision variant, the core search component of the Athénan architecture
Unbounded Maxn â outperforms â Maxn
confidence 90% · demonstrating that the proposed algorithm surpasses the average performance of other multiplayer algorithms.
Unbounded Maxn â outperforms â MCTS
confidence 90% · demonstrating that the proposed algorithm surpasses the average performance of other multiplayer algorithms.
Unbounded Maxn â outperforms â BRS
confidence 90% · demonstrating that the proposed algorithm surpasses the average performance of other multiplayer algorithms.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In this article, we generalize Unbounded Minimax, the state-of-the-art search algorithm for zero sums two-player games with perfect information to the framework of multiplayer games with perfect information. We experimentally show that this generalized algorithm also achieves better performance than the main multiplayer search algorithms.
Tags
Links
- Source: https://arxiv.org/abs/2604.17378v1
- Canonical: https://arxiv.org/abs/2604.17378v1
Trouble viewing inline? Open PDF directly â
Full Text
68,412 characters extracted from source content.
Expand or collapse full text
Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games Quentin Cohen-Solal1 1LAMSADE, UniversitĂ© Paris-Dauphine, PSL, CNRS, Paris, France quentin.cohen-solal@dauphine.psl.eu Abstract In this article, we generalize Unbounded Minimax, the state-of-the-art search algorithm for zero sums two-player games with perfect information to the framework of multiplayer games with perfect information. We experimentally show that this generalized algorithm also achieves better performance than the main multiplayer search algorithms. 1 Introduction Adversarial search in perfect-information games is a central area of artificial intelligence, driving significant theoretical and practical advances. For two-player zero-sum games, search algorithms such as Minimax and its numerous extensions have established a robust conceptual framework, enabling effective methods over large combinatorial state spaces. Among these extensions, Unbounded Minimax Korf and Chickering (1996); Cohen-Solal (2020) has recently emerged as a state-of-the-art algorithm Cohen-Solal (2025). Unbounded Minimax explores the most promising action sequences in a best-first manner, without being constrained by a depth limit as in standard minimax searches. It forms, with its safe decision variant, the core search component of the AthĂ©nan architecture Korf and Chickering (1996); Cohen-Solal (2020), the leading software in international game competitions. Over six years, AthĂ©nan won 57 gold medals at the Computer Olympiad Cohen-Solal and Cazenave (2021, 2023a, 2025a), tripled the record for gold medals in a single year Cohen-Solal and Cazenave (2023a), and held the title in 20 games. Its main competitor, AlphaZero Silver et al. (2018), relies on Monte Carlo Tree Search Coulom (2007). Experimental evaluations demonstrate that AthĂ©nan outperforms AlphaZero by up to 30 times, at least in the studied context (reasonable computing power) Cohen-Solal and Cazenave (2023b). Extending these successes to the multi-player setting, however, remains an open challenge. Games with more than two players, even under perfect information, introduce fundamental structural difficulties: the absence of simple duality, the presence of multiple objectives, non-transitive preferences, impact of tie-breaking strategies, explosion of possible equilibria, and several mathematical properties are lossed such as the minimax theorem. These characteristics make most direct generalizations of algorithms designed for two-player zero-sum games inadequate. In particular, in multi-player settings, it appears infeasible to anticipate many turns in advance without introducing simplifications that generate strong biases. In addition, extending an algorithm that relies on scalar minimax values to a vector-valued setting is not straightforward, as dominance relations are only partial and may be incomparable. Furthermore, many multiplayer algorithms have been proposed, but their relative performance is an open problem. It is unknown whether a better multiplayer algorithm exists, at least with regard to average performance, and if not, under what conditions one algorithm outperforms another. In this paper, we propose a novel search algorithm for multi-player perfect-information games that generalizes Unbounded Minimax. Our approach preserves the key principles that make Unbounded Minimax effective: unbounded search, incremental state resolution, and the prioritization of critical action sequences, while adapting them to a multi-objective, non-strictly antagonistic setting. This allows us to mitigate the combinatorial explosion, which is even more severe in multi-player games, and thereby enables longer-term planning in this generalized context. In addition, we perform an experimental evaluation across several benchmark multi-player games, demonstrating that the proposed algorithm surpasses the average performance of other multiplayer algorithms. These results open the way to a unified conceptual treatment of adversarial search in perfect-information games, covering both two-player and multi-player cases while maintaining competitive large-scale performance. The remainder of this paper is organized as follows. In Section 2, we review related work, covering Unbounded Minimax and classical multi-player game algorithms. Section 3.1 formalizes our new search algorithms: Unbounded MaxnMax^n and Unbounded MaxnMax^n with safe decision. In Section 3.2, we describe our experimental protocol, including the evaluation setup, technical details, and the set of games considered. We then present its results in Section 3.3. Finally, Section 4 concludes the paper and outlines directions for future work. 2 Related Work Symbols Definition s a game state a an action of the game actionsâ(s)actions (s ) action set of the state s for the current player firstâplayerâ(s)first\ player (s ) true if the current player of the state s is the first player playerâ(s)player (s ) number of the player that must play in s endedâ(s)ended (s ) true if s is an end-game state aâ(s)a(s) state obtained after playing the action a in the state s timeâ()time ( ) current time in seconds S keys of the transposition table T T transposition table: T=(cs,a,vs,a,ns,a,rs,a)|sâSâ§aâactionsâ(s)T= \ (c_s,a,v_s,a,n_s,a,r_s,a )\,|\,sâ S\ \ a (s) \ tmaxt_max search time per action t time elapsed since the start of the search ns,an_s,a number of times the action a is selected in state s vs,av_s,a partial minimax value obtained after playing action a in state s cs,ac_s,a completion value obtained after playing action a in state s rs,ar_s,a resolution value obtained after playing action a in state s fΞâ(s)f_Ξ(s) heuristic evaluation function (of non-terminal game tree leaves) ftâ(s)f_t(s) evaluation of terminal states, e.g. game gain or score btâ(s)b_t(s) Two-players gain function: 11 if the first player wins, 0 in case of a draw, -1 if the first player loses btâ(s)b_t(s) Multi-players gain function: btâ(s)p=1b_t(s)_p=1 if player p wins, btâ(s)p=â1b_t(s)_p=-1 if player p loses, btâ(s)p=0b_t(s)_p=0 otherwise. Table 1: Index of symbols 2.1 Best Action Searching in Game Trees The vast majority of game-search algorithms rely on representing a game as a tree, where nodes correspond to game states and edges correspond to actions that allow transitions from one state to another. The terminal nodes represent end-game states and are assigned multi-dimensional values according to the final game outcome. Typically vââ1,0,1nvâ \-1,0,1 \^n where n is the number of players and vj=1v_j=1 means player j wins, vj=0v_j=0 means draw, and vj=â1v_j=-1 means player j loses. More generally, vâânv ^n and vjv_j is the score of player j. This valuation can be propagated to the other nodes under the assumption that all players play optimally. However, this theoretical valuation is generally intractable in practice, as game trees represent enormous state spaces. Consequently, algorithms must estimate these multi-dimensional values or the corresponding strategies to make practical multi-player game-playing decisions. 2.2 Base Multi-player Searches: MaxnMax^n, Paranoid, k-best pruning The MaxnMax^n algorithm Luckhart and Irani (1986) is the canonical approach for deterministic multi-player games: it constructs a game tree to a fixed depth, evaluates the leaf nodes with a heuristic evaluation function, and propagates these values back up the tree under the assumption that all players independently maximize their own payoff. MaxnMax^n remains the simplest and most fundamental framework for reasoning about multi-player adversarial behavior. In MaxnMax^n, the value of a state where the player j must play is the value vâ(s)v (s ) of its child-state s whose component vâ(s)jv (s )_j is maximum. Unfortunately, this multiplayer generalization of the minimax algorithm causes it to lose many of its properties. In particular, several standard minimax improvements are no longer applicable in this context, such as alpha-beta pruning Knuth and Moore (1975), which significantly reduces combinatorial explosion. An alternative approach, known as Paranoid search Sturtevant and Korf (2000), reduces the multi-player setting to a two-player zero-sum game by assuming that all opponents form a coalition against the player which must play (the root player). Although this pessimistic assumption often enables deeper searches, particularly through the application of alphaâbeta pruning, it introduces strong biases and can lead to overly conservative play. Another technique used to circumvent combinatorial explosion is k-best pruning Baier and Winands (2018). This involves keeping only the k best actions a priori, which artificially reduces the branching factor to k and thus allows for longer-term planning. This pruning can remove optimal strategies; it is an inexact pruning, unlike the alpha-beta pruning of the two-player framework. Another drawback of this technique is that it is parameterized by a constant k which needs to be tuned. 2.3 Best Reply Search: BRSBRS and BRS+BRS^+ Best-Reply Search (BRSBRS) was proposed as a novel compromise between MaxnMax^nand Paranoid search. BRSBRS restricts opponentsâ behavior by allowing only the opponent with the strongest counter-move to act between two consecutive turns of the root player, while the other players do not play. This significantly reduces the branching factor and enables deeper lookahead for the root player. Empirical evaluations demonstrated that BRSBRS can outperform MaxnMax^n and often surpass Paranoid search in games such as Chinese Checkers, Focus, and Rolit. However, the original formulation of BRSBRS may generate invalid game states by violating the proper turn order among opponents. This consequently requires modifying the game implementation so that these invalid states can be played, which is not always technically possible and is costly in terms of human resources. This limitation was addressed by BRS+BRS^+, which refines the original algorithm to preserve turn consistency during the search. BRS+BRS^+ relies on move ordering to select representative opponent moves that are not explicitly searched, thereby maintaining valid game trajectories while retaining the computational advantages of BRSBRS. With BRS+BRS^+, between two consecutive turns of the root player, one opponent acts normally, while the others play their representative moves. Experimental results in Four-Player Chess show that BRS+BRS^+ significantly improves upon BRSBRS, achieving higher win rates against MaxnMax^n, Paranoid, and BRSBRS itself, at least in some contexts. 2.4 Monte-Carlo Tree Search: MCTSMCTS and MCTShMCTS_h Monte Carlo Tree Search (MCTS) Browne et al. (2012); Coulom (2007) reframed game search for domains where hand-crafted evaluation functions are inadequate. Instead of evaluating every leaf node with a heuristic, MCTS performs randomized simulations (playouts) and uses their outcomes to guide a best-first expansion of the search tree through four iterative steps: selection, expansion, simulation, and backpropagation. MCTS has achieved remarkable success across a wide range of board and real-time games. MCTSMCTS is parameterized by a constant C which needs to be tuned (theoretical value 2 2). It has been extended to the multiplayer framework, in the same way that minimax has been generalized to MaxnMax^n Sturtevant (2008). It has also been modified in various ways to incorporate knowledge to improve its performance by biasing its selections and/or simulations Browne et al. (2012). The simplest method is to replace state evaluation by playouts with heuristic evaluation Ramanujan and Selman (2011). We denote this variant by MCTShMCTS_h. 2.5 Unbounded Minimax and Safe Decision 2.5.1 Unbounded Minimax Unbounded (Best-First) Minimax Cohen-Solal (2025); Korf and Chickering (1996); Cohen-Solal and Cazenave (2025b); Cohen-Solal (2020, 2021) is a variant of the classical Minimax algorithm for two-player, zero-sum, perfect-information games. Standard Minimax explores all possible game evolutions up to a fixed depth d, evaluating states under the assumption that the first player maximizes its payoff while the second player minimizes it. However, for large d, exhaustive exploration becomes impractical, as the number of states grows exponentially with depth. Unbounded Minimax addresses this limitation by replacing uniform depth-limited exploration with a best-first, non-uniform search strategy. Rather than expanding all states, it selectively explores those estimated most promising, enabling very deep local lookahead. More specifically, it determines the best current sequence of explored actions and extends it by one action and iteratively restarts this process. Importantly, Unbounded Minimax is not parameterized by a predefined search depth: it incrementally extends the most relevant action sequences by one action and can be interrupted at any time, yielding a valid current solution. 2.5.2 Safe Unbounded Minimax Unbounded Minimax was subsequently enhanced with the safe decision technique Cohen-Solal (2025, 2020). This approach combines the standard Unbounded Minimax search procedure with the safe decision strategy. The safe decision is a variant for the final action-selection rule. Thus, in this variant, only the criterion used to choose the action after the search is modified. In the base Unbounded Minimax, the selected action is the one that leads to the child state with the best value. Under the safe decision strategy, however, the action played is the safest one, defined as the action most frequently selected during the search. In other words, the chosen action is the one that maximizes the number of times it has been selected from the root. Because the search is conducted in best-first order, the most frequently selected action is also the one that was most often evaluated as best throughout the search. This leads to robustness against evaluation errors. Moreover, it is the action for which the algorithm has the greatest visibility over possible future developments, as its corresponding subtree has been explored most extensively. 2.5.3 Unbounded Minimax with Completion Unbounded Minimax has also been improved by the completion technique Cohen-Solal (2021, 2020). First, it avoids exploring actions that lead to solved states (i.e., states whose exact value is known; in other words, further exploration of their subtrees can never change their value), which prevents the algorithm from getting stuck in suboptimal fixed points. Second, it always selects after the search an action leading to a solved winning state and never selects, when avoidable, an action leading to a solved losing state. Unbounded Minimax with completition (without and with Safe Decision) is described in Algorithm 1 Algorithm 1 Unbounded Best-First Minimax with completion. It computes the best action to play in the generated non-uniform partial game tree starting from the root state s with tmaxt_max as research time. See Table 1 for the definitions of symbols. Note: tuples are lexicographically ordered. To obtain the safe decision version: replace best_action in the last line of Unbounded_Minimax by safe_action. 3 Contributions 3.1 A New Search Algorithm for Multi-Player Games In this section, we introduce our generalization of Unbounded Minimax to the multi-player setting. We call this algorithm Unbounded MaxnMax^n. Like Unbounded Minimax, this algorithm iteratively extends the a priori best action sequence as long as search time remains. The difference is that, state values are now tuples of values corresponding to each playerâs values and instead of the first player maximizing the terminal value and the second player minimizing it, each player here independently maximizes their own value at its turn (player p maximizes its completion value câ(s,a)pc(s,a)_p and its partial minimax value vâ(s,a)pv(s,a)_p). Thus, in this generalized context, the notion of a âbestâ action reduces to maximizing the current playerâs own utility component, independently of the other playersâ outcomes (this is not necessarily optimal, since the actual objective is to achieve a higher payoff than oneâs opponents rather than to maximize an absolute score). The Unbounded MaxnMax^n algorithm with completion and optionally with safe decision is described in Algorithm 2. Algorithm 2 Unbounded MaxnMax^n (with completion). The Unbounded_Minimax method (which should therefore be renamed here as Unbounded_MaxnMax^n) and iteration method are the same as in the two-player case (see Algorithm 1) (except that câ(s,a)c(s,a) is initialized to (0,âŠ,0)(0,âŠ,0) instead of 0). The other methods are overloaded and described here. This algorithm computes the best action to play in the generated non-uniform partial game tree starting from the root state s with tmaxt_max as research time. See Table 1 for the definitions of symbols. Note: tuples are lexicographically ordered. To obtain the safe decision version: replace best_action in the last line of Unbounded_Minimax by safe_action. 3.2 Experimental Study of Multi-Player Searches We now present the experiments conducted to evaluate the contributions of this paper. We will present its results in the following section. We begin by presenting the experimental protocol (Section 3.2.1). Then we explain how the evaluation functions used by the search algorithms were generated (Section 3.2.2). Next, we describe the machines used (Section 3.2.3), and finally present the other details of the experiment (Section 3.2.4). 3.2.1 Evaluation Protocol We experimentally compare the following algorithms: BRSBRS, BRS+BRS^+, MCTSMCTS, MCTShMCTS_h, Paranoid, standard MaxnMax^n, MaxnMax^n with k-best pruning and our new algorithm Unbounded MaxnMax^n with classic decision and with safe decision. We use standard MaxnMax^n as benchmark adversary using a lossless parallelization procedure, called Child Batching Cohen-Solal (2025, 2020) (child Batching consists in evaluating the children states of states in parallel by the neural network). We evaluate each algorithm on the following 8 games: 3 classic games: Hey, Thatâs My Fish!, Blokus, Three-Players Hex as well as 5 multiplayer versions of classic two-player games that we introduce: Quadrothello and Triinversion (generalizing the game of Othello to four and three player respectively), Quadamazons (generalizing the game Amazons to four player), and other generalizations of Hex with a different degree of interaction between players: Separed Teamhex and Threehex. Corresponding rules are in Appendix. Each algorithm faces the benchmark adversary P times where P is the number of players in the game: each evaluated algorithm takes a different player number each time. In other words, it plays once as the first player, once as the second player, etc⊠These matches are repeated 30Ă3030Ă 30 times: we use 30 different evaluation functions per game. More precisely, each algorithm is evaluated for each evaluation fonction fif_i (iâ0,29iâ \0,29 \) that it uses and for each opponents evaluation function group fj+kk=0Pâ2 \f_j+k \_k=0^P-2 (jâ0,29jâ \0,29 \). In other words, for all i,jâ0,29i,jâ \0,29 \, the evaluated algorithm using fif_i confronts in a same match the following opponents: the benchmark adversary with the evaluation fjf_j, the benchmark adversary with the evaluation fj+1f_j+1, âŠ, and the benchmark adversary with the evaluation fj+Pâ2f_j+P-2. This corresponds to 2700 (resp. 3600) matches for each evaluated algorithm and for each 3-player (resp. 4-player) game. The performance evaluation of an algorithm for a specific game is therefore based on this number of matches. The performance of a search algorithm is the average of the binary scores obtained at the end of its matches (1 for a victory, 0 for a draw and -1 for a defeat). Each search algorithm uses the same search time: 10 seconds per action (order of magnitude of search time in competition). In this experiment, we evaluated Unbounded MaxnMax^n with safe decision without Child Batching and the MTCS-based algorithms without Child Batching because Child Batching cannot be used with MCTSMCTS. In addition, we evaluated all other algorithms with Child Batching. Note that BRSBRS has not been evaluated on all games because that would have required re-impeding all games to handle invalid states. BRSBRS games are: Separed Teamhex, Quadrothello, 3 Player Hex, Threehex, and Triinversion. Note that, regardless of whether the evaluated algorithms use Child Batching, the benchmark adversary always does. Therefore, all algorithms can be directly compared. 3.2.2 Evaluation Functions Training We now present how the evaluation functions used in the experiments of this paper were learned. The evaluation functions were generated using AthĂ©nan Cohen-Solal (2020) ; the reinforcement learning algorithm, by remplacing its core component Descent Minimax, with its generalization for multi-player games Cohen-Solal (2021) (which consists of replacing the minimax paradigm with the MaxnMax^n paradigm). AthĂ©nan involves sequentially performing self-play matches using the learned evaluation function to guide the search process, deciding which actions to take during the matches and how to explore the search tree. The data encountered (the associations states-values) is then learned at the end of each match to update the evaluation function. This thus forms a self-improving loop. The AthĂ©nan hyperparameters used to generate each evaluation function are the following: search time per action t=2t=2, batch size B=3000B=3000, duplication factor ÎŽ=3ÎŽ=3, memory size M=75M=75, the selection action method is still the ordinal law but its parameter is X X with X a unform random variable in [0,1], neural network optimizer: Adam Kingma and Ba (2014) with λ=0.0001λ=0.0001 as learning rate. The neural network architecture used is as follow: a convolutional layer, 44 residual blocks He et al. (2016) (containing 2 convolutional layers), a convolutional layer with 1Ă11Ă 1 as kernel size, a Global Sum Polling layer Aich and Stavness (2018), a flatten layer, a dense layer with N neurons (see Table in Appendix for the N value), and a final dense layer with P neurons (the output ; P: the number of players). Each convolutional layer has C channels (see Table in Appendix for the C value). The activation function is the ReLU. Each of the evaluation functions is the result of 10 days of training. 3.2.3 Computer Used We provide details of the machines used in the experiments described in this article. For reinforcement learning the experiment evaluation functions, we used the Jean-Zay A100 partition: 8 CPU with 58 Go of RAM and 1 GPU A100 with 80 Go of RAM (per learning process). To perform the evaluation matches, we used the Jean-Zay V100 partition: 10 CPU with 40 Go of RAM and 1 GPU V100 with 16 Go of RAM. 3.2.4 Other Details of the Experiment We give for each algorithm: the average performance over all games, the associated 95% stratified bootstrapping confidence interval (lower and upper bound) and the performance for each game with its 95% confidence radius. The percentages detailing performance for each game have been rounded to the nearest percent to reduce size and improve readability of data tables. Algorithms based on a fixed search depth (BRSBRS, BRS+BRS^+, MaxnMax^n with and without k-best pruning, and Paranoid) use iterative deepening Korf (1985) to be parameterized by a search time. All algorithms use transposition tables Greenblatt et al. (1988). This allows the game tree to be transformed into a directed acyclic graph, which therefore simplifies the state space. Evaluation functions for MCTShMCTS_h need to by The evaluation functions for MCTShMCTS_h need to take values in [0,1][0,1]. We use the following normalization, applied component by component, to obtain such evaluation functions, transforming an evaluation function f with values in âR into an evaluation function fnf_n with values in [0,1][0,1]: fnâ(s)=maxâĄ(minâĄ(fâ(s),M),m)âmMâmf_n(s)= ( (f (s ),M ),m )-mM-m with s a game state, f the state evaluation function, M the maximum practical value for f, m the minimum practical value of f. More formally, M=maxâĄVM= V and m=minâĄVm= V with V=fâ(sâČ)|sâČâSV= \f (s )\,|\,s â S \ where S is a set of states from matches played using f generated during 24 hours. 3.3 Results of the Experimental Study Quadamazons Blokus Hey, Thatâs My Fish! Separed Teamhex Quadrothello 3 Player Hex Triinversion Threehex Safe Unbounded MaxnMax^n -45 ±3 -46 ±3 1 ±4 -16 ±3 -16 ±3 -7 ±1 -1 ±4 -33 ±4 MaxnMax^n -46% ±2% -48% ±2% -27% ±3% -16% ±3% -53% ±2% -7% ±1% -37% ±3% -36% ±3% MCTShC=2MCTS_h^C= 2 -54 ±2 -79 ±1 -58 ±3 -38 ±3 -79 ±1 -7 ±1 -70 ±2 -43 ±3 MCTShC=22MCTS_h^C= 22 -54 ±2 -78 ±2 -55 ±3 -37 ±3 -75 ±2 -8 ±1 -67 ±2 -45 ±3 MCTShC=24MCTS_h^C= 24 -54 ±2 -76 ±2 -48 ±3 -39 ±3 -68 ±2 -8 ±1 -64 ±2 -44 ±3 MCTShC=28MCTS_h^C= 28 -56 ±2 -76 ±2 -42 ±3 -36 ±3 -64 ±2 -7 ±1 -57 ±3 -45 ±3 MCTSC=2MCTS^C= 2 -28 ±3 -99 ±0 -92 ±1 -92 ±1 -100 ±0 -1 ±0 -85 ±1 -97 ±0 MCTSC=22MCTS^C= 22 -20 ±3 -99 ±0 -90 ±1 -91 ±1 -100 ±0 0 ±0 -86 ±1 -96 ±1 MCTSC=24MCTS^C= 24 -11 ±3 -99 ±0 -87 ±1 -88 ±1 -100 ±0 1 ±0 -84 ±2 -94 ±1 MCTSC=28MCTS^C= 28 -16 ±3 -99 ±0 -88 ±1 -88 ±1 -100 ±0 2 ±0 -86 ±1 -92 ±1 Table 2: Binary scores for all games of the evaluated algorithms without batching against MaxnMax^n with batching (red > orange > pink). We now present the results of the experiment. In Section 3.3.1, we present the performance of MCTSMCTS and MCTShMCTS_h as well as some algorithms without Child Batching. Section 3.3.2 presents the performance of BRSBRS by comparing it with other algorithms using also Child Batching, restricting our analysis to the games where BRSBRS can be applied. In Section 3.3.3, we present the performance of all the algorithms, except MCTSMCTS, MCTShMCTS_h, and BRSBRS, with Child Batching, on all the games. 3.3.1 MCTSMCTS, MCTShMCTS_h, and algorithms without Child Batching We thus evaluate the following algorithms without Child Batching: MCTSMCTS, MCTShMCTS_h, and Unbounded MaxnMax^n with Safe Decision without Child Batching, and MaxnMax^n. The algorithms performances are described in Table 3 (mean over the games) and Table 2 (details). Safe Unbounded MaxnMax^n achieves the best average performance, followed by MaxnMax^n, then MCTShMCTS_h, and finally MCTSMCTS. This result generalizes across all games except Quadamazons and 3-Player Hex. On these two games, MCTSMCTS achieves the best performance, after which the average performance ranking is recovered. Notably, MCTSMCTS even outperforms the algorithms using Child Batching on Quadamazons and equalizes them on 3-Player Hex (see Table 5). Since MCTSMCTS does not rely on any game-specific knowledge, we infer that the learned evaluation functions for these two games are of low quality. The first conclusion of this paper, which is not surprising, is that when learning fails to provide a high-quality evaluation function, MCTSMCTS delivers better performance. This study nevertheless shows that such cases are rather rare (one game out of eight which is problematic). Note that Child Batching increases performance by about 6%. Let us now focus more specifically on MCTShMCTS_h. Excluding MCTSMCTS, MCTShMCTS_h achieves the worst performance on all games. When compared to the other algorithms using Child Batching (see Table 5), MCTShMCTS_h remains far inferior, even after removing the 6% gain due to Child Batching, and even when considering the best parameters for MCTSMCTS and the worst parameters for the other algorithms. We note a single exception: MCTShMCTS_h performs better than Paranoid on the sole game Quadrothello, which can be interpreted as the fact that assuming all opponents seek to minimize oneâs score is a very poor heuristic for this game, despite the computational gains. The second conclusion is thus that MCTShMCTS_h is the worst-performing algorithm in the context of our experiments, even if it could be used with Child Batching. mean lower bound upper bound Safe Unbounded MaxnMax^n -21.88 -22.83 -20.94 MaxnMax^n -35.23 -36.13 -34.34 MCTShMCTS_h (best C=28C= 28) -49.76 -50.6 -48.96 MCTSMCTS (best C=24C= 24) -71.27 -71.79 -70.76 Table 3: Average binary scores over all games of the evaluated algorithms without batching against MaxnMax^n with batching. 3.3.2 BRSBRS with Child Batching We now analyze the performance of BRSBRS by comparing it with the other algorithms while restricting ourselves to the games on which BRSBRS could be applied. Recall that BRSBRS creates invalid states that are not allowed by the game rules, and therefore it requires modifying the game implementations in order to be used, which entails a far from negligible human cost. Performance of BRSBRS are described in Table 4 (mean over the BRSBRS games) and Table 5 (details). BRSBRS is the algorithm with the worst average performance among the algorithms using child batching. In particular, it achieves the poorest performance on each of the two generalizations of Othello. However, it belongs to the leading group on the three generalizations of Hex. Nevertheless, BRS+BRS^+ consistently obtains better results than BRSBRS. This study therefore confirms the inferiority of BRSBRS compared to BRS+BRS^+ and indicates that there is no need to further investigate BRSBRS. mean lower bound upper bound Safe Unbounded MaxnMax^n -8.25 -9.46 -7.03 Unbounded MaxnMax^n -24.41 -25.57 -23.27 BRSBRS -39.15 -40.14 -38.11 BRS+BRS^+ -32.03 -33.12 -30.95 Paranoid -32.6 -33.67 -31.54 MaxnMax^n -26.86 -28.01 -25.71 Table 4: Average binary scores over the games where BRSBRS has been used of the evaluated algorithms with batching against MaxnMax^n with batching (red > orange > pink). Quadamazons Blokus Hey, Thatâs My Fish! Separed Teamhex Quadrothello 3 Player Hex Triinversion Threehex Safe Unbounded MaxnMax^n -40 ±3 -45 ±3 6 ±4 -10 ±3 -12 ±3 1 ±1 5 ±4 -24 ±4 Unbounded MaxnMax^n -45 ±2 -58 ±2 -13 ±3 -18 ±3 -33 ±3 -2 ±1 -19 ±3 -46 ±3 BRSBRS -15 ±3 -89 ±1 -1 ±1 -54 ±3 -25 ±3 BRS+BRS^+ -37 ±3 -42 ±2 -15 ±3 -12 ±3 -81 ±1 -1 ±1 -29 ±3 -24 ±3 Paranoid -39 ±3 -37 ±3 -25 ±3 -9 ±3 -81 ±1 -1 ±1 -36 ±3 -24 ±3 MaxnMax^n -45 ±2 -47 ±2 -28 ±3 -13 ±3 -48 ±2 -4 ±1 -33 ±3 -32 ±3 k-best MaxnMax^n (k=30k=30) -44 ±2 -47 ±2 -29 ±3 -14 ±3 -50 ±2 -4 ±1 -35 ±3 -32 ±3 k-best MaxnMax^n (k=20k=20) -44 ±2 -47 ±2 -25 ±3 -12 ±3 -50 ±2 -4 ±1 -39 ±3 -35 ±3 k-best MaxnMax^n (k=14k=14) -43 ±2 -48 ±2 -21 ±3 -14 ±3 -50 ±2 -3 ±1 -41 ±3 -34 ±3 k-best MaxnMax^n (k=10k=10) -45 ±2 -46 ±2 -12 ±3 -13 ±3 -45 ±2 -3 ±1 -34 ±3 -34 ±3 k-best MaxnMax^n (k=8k=8) -47 ±2 -50 ±2 -16 ±3 -16 ±3 -46 ±2 -3 ±1 -36 ±3 -34 ±3 k-best MaxnMax^n (k=7k=7) -46 ±2 -52 ±2 -13 ±3 -13 ±3 -42 ±2 -3 ±1 -28 ±3 -32 ±3 k-best MaxnMax^n (k=6k=6) -46 ±2 -52 ±2 -10 ±3 -14 ±3 -40 ±2 -3 ±1 -33 ±3 -30 ±3 k-best MaxnMax^n (k=5k=5) -48 ±2 -56 ±2 -14 ±3 -15 ±3 -34 ±3 -2 ±1 -29 ±3 -32 ±3 k-best MaxnMax^n (k=4k=4) -46 ±2 -61 ±2 -8 ±3 -17 ±3 -33 ±3 -2 ±1 -24 ±3 -32 ±3 k-best MaxnMax^n (k=3k=3) -44 ±2 -62 ±2 -9 ±3 -21 ±3 -34 ±3 -4 ±1 -20 ±3 -31 ±3 k-best MaxnMax^n (k=2k=2) -50 ±2 -69 ±2 -12 ±3 -20 ±3 -39 ±3 -6 ±1 -35 ±3 -33 ±3 Table 5: Binary scores for all games of the evaluated algorithms with batching against MaxnMax^n with batching (red > orange > pink) 3.3.3 Algorithms with Child Batching We now present the performance of the following algorithms with Child Batching: BRS+BRS^+, Paranoid, MaxnMax^n, MaxnMax^n with k-best pruning, and our new algorithms: Unbounded MaxnMax^n with classic decision and Unbounded MaxnMax^n with safe decision. The algorithms performances are described in Table 6 (mean over the games) and Table 5 (details). Unbounded MaxnMax^n with safe decision obtains the best average performance and it is the best algorithm, possibly tied, over 77 of the 88 studied games (Blokus is the exception). It is strictly the best algorithm over 33 of the 88 studied games (Quadrothello, Triinversion, Threehex). Unbounded MaxnMax^n without Safe Decision obtains the second best average performance. However, it is not the best-performing algorithm on any game and achieves second-best performance on only 3 games. On 4 of the 8 games, it obtains performance that is significantly worse than BRS+BRS^+, Paranoid, and MaxnMax^n. In addition, MaxnMax^n and BRS+BRS^+ achieve the third-best average performance. BRS+BRS^+ achieves the best performance on 2 of the 8 games (Quadamazons and Threehex). MaxnMax^n is not the best-performing algorithm on any game. In fact, it is never better than BRS+BRS^+, except on a single game, Quadrothello, where it performs largely better. Moreover, Paranoid is the fifth-best algorithm in terms of average performance. Nevertheless, it reaches the best performance level on 4 of the 8 games (Quadamazons, Blokus, Separed Teamhex, Threehex). Finally, we note that k-best pruning improves performance of MaxnMax^n on only 3 of the 8 games (Hey, Thatâs My Fish!, Quadrothello, Triinversion). BRS+BRS^+ when combined with k-best pruning could possibly match the performance of Safe Unbounded MaxnMax^n on one of the 3 games (namely, Hey, Thatâs My Fish!). For the other two games, using k-best pruning with BRS+BRS^+ or Paranoid should not change the relative performance ranking of the algorithms. mean lower bound upper bound Safe Unbounded MaxnMax^n -16.48 -17.42 -15.54 Unbounded MaxnMax^n -31.05 -31.96 -30.13 BRS+BRS^+ -32.61 -33.5 -31.71 Paranoid -33.46 -34.35 -32.58 MaxnMax^n -32.69 -33.6 -31.77 k-best MaxnMax^n (best k=6k=6) -30.39 -31.31 -29.48 Table 6: Average binary scores over all games of the evaluated algorithms with batching against MaxnMax^n with batching. 4 Conclusion 4.1 Summary In this paper, we investigated search algorithms for multi-player perfect-information games. We generalized the state-of-the-art algorithm for two-player zero-sum perfect-information games, namely Unbounded Minimax with Safe Decision, and its variant: Unbounded Minimax with classic decision, to this setting. We then compared their performances in an exceptionally large and robust study with the main multi-player search algorithms from the literature. We showed that our generalization with safe decision also achieves the best average performance for a medium search time. More precisely, we have shown that it is the best-performing algorithm for 7 out of the 8 games studied, and significantly superior in 3 games. In addition, we retrieve several findings from the literature, but this time within a robust and large study: Paranoid and BRS+BRS^+ which excel on certain games, k-best pruning which improves performance on some games, BRS+BRS^+ which outperforms BRSBRS, and safe decision which outperforms classic decision. More precisely, we showed that our generalization of Unbounded Minimax with classic decision achieves the second-best average performance but is never the top-performing algorithm on any individual game. We also repeated this study in the context of a short search time (1 second), the results, available in Appendix, are analogous to the medium times (10 seconds). Overall, we have shown that our algorithm, Safe Unbounded MaxnMax^n, is the search algorithm to be preferred as a first choice for multi-player perfect-information games, when learning an evaluation function is feasible (i.e., when access to a GPU over several days is available). When this is not possible, or in the rare cases where learning fails to provide a sufficiently strong evaluation function, base MCTS is the algorithm of choice. 4.2 Future work On the game where Unbounded MaxnMax^n is not the best, namely Blokus, Paranoid achieves the best result. A hybridization of Paranoid with Unbounded MaxnMax^n, that is, modeling Blocus as a two-player game using the Paranoid strategy allowing the application of Safe Unbounded Minimax (the two-player algorithm), should constitute the state of the art for this game. This hypothesis will be verified in a future study. More generally, this modification could represent the state of the art on four other games, since Safe Unbounded MaxnMax^n matches Paranoid performance on these games. More generally, we plan to study how the degree of interaction between players affects the performance of search algorithms, and if performance is linked, design a search algorithm that automatically and dynamically adapts during the game to the current degree of interaction to optimize its performance. References [1] S. Aich and I. Stavness (2018) Global sum pooling: a generalization trick for object counting with small datasets of large images. arXiv preprint arXiv:1805.11123. Cited by: §3.2.2. [2] H. Baier and M. H. Winands (2018) MCTS-minimax hybrids with state evaluations. Journal of Artificial Intelligence Research 62, p. 193â231. Cited by: §2.2. [3] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton (2012) A survey of monte carlo tree search methods. Transactions on Computational Intelligence and AI in games 4 (1), p. 1â43. Cited by: §2.4, §2.4. [4] C. Chao (2018) Blokus game solver. Cited by: §4.4.1. [5] Q. Cohen-Solal and T. Cazenave (2021) DESCENT wins five gold medals at the computer olympiad. ICGA Journal 43 (2), p. 132â134. Cited by: §1. [6] Q. Cohen-Solal and T. Cazenave (2023) Athenan wins sixteen gold medals at the computer olympiad. ICGA Journal 45 (3). Cited by: §1. [7] Q. Cohen-Solal and T. Cazenave (2023) Minimax strikes back. AAMAS. Cited by: §1. [8] Q. Cohen-Solal and T. Cazenave (2025) AthĂ©nan wins 11 gold medals at the 2024 computer olympiad. ICGA Journal, p. 13896911251315102. Cited by: §1. [9] Q. Cohen-Solal and T. Cazenave (2025) On some improvements to unbounded minimax. arXiv preprint arXiv:2505.04525. Cited by: §2.5.1. [10] Q. Cohen-Solal (2020) Learning to play two-player perfect-information games without knowledge. arXiv preprint arXiv:2008.01188. Cited by: §1, §1, §2.5.1, §2.5.2, §2.5.3, §3.2.1, §3.2.2, §4.4.3. [11] Q. Cohen-Solal (2021) Completeness of unbounded best-first game algorithms. arXiv preprint arXiv:2109.09468. Cited by: §2.5.1, §2.5.3, §3.2.2. [12] Q. Cohen-Solal (2025) Study and improvement of search algorithms in two-players perfect information games. arXiv preprint arXiv:2505.09639. Cited by: §1, §2.5.1, §2.5.2, §3.2.1. [13] R. Coulom (2007) Efficient selectivity and backup operators in monte-carlo tree search. In Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers, p. 72â83. Cited by: §1, §2.4. [14] R. D. Greenblatt, D. E. Eastlake, and S. D. Crocker (1988) The greenblatt chess program. In Computer chess compendium, p. 56â66. Cited by: §3.2.4. [15] J. Hartjes (2019) The feasibility of ignoring opponents in multi-player games. Masterâs Thesis. Cited by: §4.4.1. [16] K. He, X. Zhang, S. Ren, and J. Sun (2016) Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition, p. 770â778. Cited by: §3.2.2. [17] D. P. Kingma and J. Ba (2014) Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980. Cited by: §3.2.2. [18] D. E. Knuth and R. W. Moore (1975) An analysis of alpha-beta pruning. Artificial Intelligence 6 (4), p. 293â326. Cited by: §2.2. [19] R. E. Korf and D. M. Chickering (1996) Best-first minimax search. Artificial intelligence 84 (1-2), p. 299â337. Cited by: §1, §1, §2.5.1. [20] R. E. Korf (1985) Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence 27 (1), p. 97â109. Cited by: §3.2.4. [21] C. Luckhart and K. B. Irani (1986) An algorithmic solution of n-person games.. In AAAI, Vol. 86, p. 158â162. Cited by: §2.2. [22] J. Nijssen and M. H. Winands (2013) Search policies in multi-player games. Icga Journal 36 (1), p. 3â21. Cited by: §4.4.1. [23] J. A. M. Nijssen (2013) Monte-carlo tree search for multi-player games. Cited by: §4.4.1. [24] R. Ramanujan and B. Selman (2011) Trade-offs in sampling-based adversarial planning.. In ICAPS, p. 202â209. Cited by: §2.4. [25] M. P. Schadd and M. H. Winands (2011) Best reply search for multiplayer games. IEEE Transactions on Computational Intelligence and AI in Games 3 (1), p. 57â66. Cited by: §4.4.1. [26] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al. (2018) A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362 (6419), p. 1140â1144. Cited by: §1. [27] N. R. Sturtevant and R. E. Korf (2000) On pruning techniques for multi-player games. AAAI/IAAI 49, p. 201â207. Cited by: §2.2. [28] N. R. Sturtevant (2008) An analysis of uct in multi-player games. In International conference on computers and games, p. 37â49. Cited by: §2.4. Appendix We present in this document the details of the experiments. First, note that the N value and C value of the neural networks for each game are in Table 7. In Section 4.3, we present the results of our repeated experiment, modifying the associated search time to analyze the short-time behavior of the algorithms. In Section 4.4, we present the games used as benchmarks for the experiments in this article. 4.3 Short time experiment We repeated the experiment from our main article. Everything is identical except for the search time of each evaluated algorithm and the reference algorithm, which is set at 1 second (instead of 10 seconds). Performance of algorithms without Child Batching is in Table 8 (average) and in Table 10 (details). Average performance over all BRSBRS games of algorithms with Child Batching is in Table 9. Performance of algorithms with Child Batching is in Table 12 (average) and in Table 11 (details). The results are analogous to the medium-time context, with a few minor differences that we will detail. MaxnMax^n achieves better performance than Paranoid and BRS+BRS^+. This is interpreted by the fact that as the time is shorter, the impact of the branching factor is less strong, there is therefore less need for pruning, and therefore the pruning done by BRS+BRS^+ and Paranoid which are pruning with biases have a stronger negative impact on performance (their bias is not compensated by the ability to plan relatively over a longer term). k-best MaxnMax^n now significantly improves performance in Separated Teamhex, and even achieves the best performance in this game, outclassing Safe Unbounded MaxnMax^n. Although Unbounded MaxnMax^n is still the best algorithm on average, it is now only the best algorithm, possibly tied, on 6 of the 8 games. However, in both games, it achieves performance close to that of the best algorithm. In addition, it is now significantly the best algorithm on 4 of the 8 games (the game Hey, Thatâs My Fish! is added to the same list as for the 10-second time). MCTS is no longer the best algorithm on Quadamazons. Therefore, MCTS remains the worst algorithm in short time. We interpret this as meaning that in short time, MCTS doesnât have enough time to converge to a correct solution. Approaches based on learned heuristics are thus more efficient because they begin the search already possessing some knowledge. MCTShMCTS_h is now better than Safe Unbounded MaxnMax^n without Child Batching on two games: Threehex and 3-Player Hex (and is still inferior on the others). And we still have the fact that MCTShMCTS_h performs worse than all other algorithms with child batching on all games except two, instead of just one with 10 secondes: Quadrothello and Separated Teamhex (Separated Teamhex is added). In these two exceptions, MCTShMCTS_h is still far from the best performance, especially on Quadrothello. C N Quadamazons 166166 1343 Blokus 166166 1260 Hey, Thatâs My Fish! 166166 1386 Separed Teamhex 166166 1260 Quadrothello 166166 1343 3-player Hex 166166 1354 Triinversion 166166 1373 Threehex 166166 1354 Table 7: Number of convolutional channels C and hidden dense neurons N used by AthĂ©nan for each studied game. mean lower bound upper bound Safe Unbounded MaxnMax^n -37.87 -38.77 -36.96 MCTShC=24MCTS_h^C= 24 -47.63 -48.46 -46.8 MCTShC=28MCTS_h^C= 28 -45.62 -46.46 -44.77 MCTSC=24MCTS^C= 24 -85.12 -85.51 -84.74 MCTSC=28MCTS^C= 28 -84.74 -85.12 -84.37 Table 8: Average binary scores over all games of the evaluated algorithms without batching against MaxnMax^n with batching (search time 1âs1s ; red > orange > pink). mean lower bound upper bound Safe Unbounded MaxnMax^n -21.1 -22.06 -20.13 Unbounded MaxnMax^n -30.69 -31.84 -29.51 BRSBRS -40.07 -41.1 -39.06 BRS+BRS^+ -36.06 -37.14 -34.98 Paranoid -36.65 -37.71 -35.59 MaxnMax^n -28.24 -29.39 -27.1 Table 9: Average binary scores over the games where BRSBRS has been used of the evaluated algorithms with batching against MaxnMax^n with batching (search time 1âs1s ; red > orange > pink). Quadamazons Blokus Hey, Thatâs My Fish! Separed Teamhex Quadrothello 3 Player Hex Triinversion Threehex Safe Unbounded MaxnMax^n -48 ±3 -49 ±3 -30 ±4 -23 ±3 -33 ±3 -26 ±2 -15 ±4 -77 ±2 MCTShC=24MCTS_h^C= 24 -55 ±2 -66 ±2 -50 ±3 -26 ±3 -67 ±2 -8 ±1 -48 ±3 -48 ±3 MCTShC=28MCTS_h^C= 28 -56 ±2 -66 ±2 -46 ±3 -26 ±3 -62 ±2 -9 ±1 -41 ±3 -45 ±3 MCTSC=24MCTS^C= 24 -64 ±2 -100 ±0 -97 ±0 -96 ±0 -100 ±0 -26 ±1 -91 ±1 -97 ±0 MCTSC=28MCTS^C= 28 -64 ±2 -99 ±0 -97 ±0 -96 ±0 -100 ±0 -19 ±1 -92 ±1 -98 ±0 Table 10: Binary scores for all games of the evaluated algorithms without batching against MaxnMax^n with batching (search time 1âs1s ; red > orange > pink). Quadamazons Blokus Hey, Thatâs My Fish! Separed Teamhex Quadrothello 3 Player Hex Triinversion Threehex Safe Unbounded MaxnMax^n -41 ±3 -45 ±3 0 ±4 -18 ±3 -18 ±3 -2 ±2 -7 ±4 -25 ±4 Unbounded MaxnMax^n -47 ±2 -57 ±2 -17 ±3 -34 ±3 -37 ±3 -8 ±1 -29 ±3 -40 ±3 BRSBRS -20 ±3 -83 ±1 -5 ±1 -52 ±3 -31 ±3 BRS+BRS^+ -41 ±2 -44 ±2 -30 ±3 -16 ±3 -78 ±2 -5 ±1 -38 ±3 -34 ±3 Paranoid -41 ±2 -42 ±2 -35 ±3 -16 ±3 -79 ±1 -5 ±1 -40 ±3 -33 ±3 MaxnMax^n -43 ±2 -47 ±2 -27 ±3 -16 ±3 -49 ±2 -5 ±1 -32 ±3 -34 ±3 k-best MaxnMax^n (k=30k=30) -45 ±2 -45 ±2 -25 ±3 -10 ±3 -49 ±2 -3 ±1 -35 ±3 -27 ±3 k-best MaxnMax^n (k=16k=16) -45 ±2 -48 ±2 -25 ±3 -12 ±3 -48 ±2 -3 ±1 -33 ±3 -26 ±3 k-best MaxnMax^n (k=10k=10) -42 ±2 -51 ±2 -16 ±3 -10 ±3 -49 ±2 -3 ±1 -33 ±3 -25 ±3 k-best MaxnMax^n (k=7k=7) -46 ±2 -45 ±2 -16 ±3 -12 ±3 -51 ±2 -2 ±1 -31 ±3 -27 ±3 k-best MaxnMax^n (k=4k=4) -47 ±2 -49 ±2 -14 ±3 -9 ±3 -45 ±2 -4 ±1 -30 ±3 -28 ±3 k-best MaxnMax^n (k=3k=3) -46 ±2 -54 ±2 -10 ±3 -12 ±3 -41 ±2 -4 ±1 -28 ±3 -29 ±3 k-best MaxnMax^n (k=2k=2) -46 ±2 -65 ±2 -15 ±3 -15 ±3 -40 ±2 -3 ±1 -28 ±3 -27 ±3 Table 11: Binary scores for all games of the evaluated algorithms with batching against MaxnMax^n with batching (search time 1âs1s ; red > orange > pink) mean lower bound upper bound Safe Unbounded MaxnMax^n -14.46 -15.69 -13.24 Unbounded MaxnMax^n -35.54 -36.45 -34.63 BRS+BRS^+ -37.41 -38.29 -36.54 Paranoid -38.02 -38.91 -37.15 MaxnMax^n -33.05 -33.98 -32.14 k-best MaxnMax^n (best k=4k=4) -29.77 -30.71 -28.85 Table 12: Average binary scores over all games of the evaluated algorithms (except BRSBRS) with batching against MaxnMax^n with batching (search time 1âs1s ; red > orange > pink). 4.4 Games We now detail the rules of the games used as benchmarks for our experiments. To avoid any ambiguity, the games we introduce are also provided with their source code in supplementary materials (otherwise we provide a link to the official rules). 4.4.1 Blokus Blokus is a classic abstract game. It is a game of tile placement, enclosure, chaining, and hand management. More precisely, it is an abstract strategy game played on a square grid board. Each player is assigned a distinct color and a fixed set of 21 polyomino pieces of varying shapes and sizes. Players alternately place one piece of their color onto the board, subject to strict spatial constraints. A legal placement requires that the newly placed piece does not share an edge with any previously placed piece of the same color; instead, it must touch at least one corner of an existing piece of that color. Pieces of different colors may touch freely along edges or corners. The objective is to maximize the number of pieces placed on the board. The game ends when no player can make a legal move, and the score is determined by the total number of pieces successfully placed. The standard game is played on a 20Ă20 grid (400 squares) and includes 84 polyomino pieces, divided into four color sets of 21 pieces each. For each color, the set consists of one monomino, one domino, two trominoes, five tetrominoes, and twelve pentominoes. It is ranked as the 61th best abstract game (on the boardgamegeek website ranking). Blokus has been used on multiple occasions as a benchmark for artificial intelligence algorithms [4, 23, 22, 15, 25]. Complete rules of Blokus are available here. Note that the associated terminal evaluation that we used is the score of the game. 4.4.2 Hey, Thatâs My Fish! Hey, Thatâs My Fish! is a game of Grid Movement, Map Reduction with Variable Set-up. More precisely, it is an abstract strategy game in which players control multiple penguin tokens moving on a hexagonal grid of ice tiles. Each tile is labeled with a fixed number of fish (one to three), which determine the scoring potential of that tile. The tiles are initially placed at random. On each turn, a player selects one of their penguins and moves it in a straight line across any number of contiguous ice tiles, following hexagonal directions. After the move, the tile from which the penguin departed is removed from the board, creating an impassable gap that permanently alters the game topology. In addition, the player collects the removed tile (on which their token was located). When a penguin has no legal moves remaining, it is removed from play. The game ends when all penguins have been removed. The winner is the player who has accumulated the largest total number of fish across all collected tiles. It is ranked as the 81th best abstract game and the 391 best family game (on the boardgamegeek website ranking). Complete rules of Hey, Thatâs My Fish! are available here Note that the associated terminal evaluation that we used is the score of the game. 4.4.3 3-Player Hex Three-Player Hex is played on a board with hexagonal cells and overall hexagonal shape. In this study, boards have 7 cells per side. Players alternate turns by placing a stone of their assigned color on an unoccupied cell. The objective, as in standard Hex, is to form a continuous chain of stones connecting the two opposite sides of the board designated for their color. There are two variations of this game. In the first, which we have implemented, the game ends in a draw when none of the three players can connect their edges. In the other variation, as soon as a player cannot connect their edges, they are eliminated, and as soon as two players are eliminated, the third wins. Complete rules of 3-Player Hex are available on Ludii. Note that the presence of a third player eliminates the connection guarantees of strategics patterns that are the basis of two-player hex strategies Note that the associated terminal evaluation that we used is the additive deep heuristic [10]. 4.4.4 Threehex We introduce an alternative three-player generalization of Hex designed to better preserve the strategic properties of the two-player game, by significantly reducing the joint interaction between the two opponents that arises in the classical three-player variant of Hex. The objective of the game remains unchanged: a player wins by being the first to connect their two designated sides of the board with a chain of pieces of their color. However, it is now allowed to place a piece on a cell that already contains a piece belonging to another player, except when that player is the next player in turn. More precisely, player 0 may place a piece on an empty cell or on a cell containing a single piece belonging to player 2; player 1 may place a piece on an empty cell or on a cell containing a single piece belonging to player 0; and player 2 may place a piece on an empty cell or on a cell containing a single piece belonging to player 1. A player who has no legal move must pass. If all players pass consecutively, the game ends in a draw. Note: if a piece is overlaid by another piece, it still counts toward connecting the corresponding sides of the board. The length of each playerâs designated board edges is 7 in these experiments. With this modification, only one of the two opponents can prevent a given player from connecting their two sides, namely the next player in turn. As a result, each player primarily aims to block their predecessor while simultaneously attempting to complete their own connection. Symmetrically, each player is themselves blocked by their successor. This interaction structure partially restores strategic patterns characteristic of the two-player game. In addition, indirect interactions arise when attempting to counter the player who is blocking us. Depending on where a player places pieces to block their predecessor, that predecessor may respond by placing pieces in locations that, in turn, block the third player. Consequently, players must act so as to block their immediate predecessor as effectively as possible, while anticipating that the opponentâs response will hinder the remaining player. This leads to bidirectional blocking interactions among all three players. 4.4.5 Separed Teamhex We introduce the game Separed Teamhex as a 4-player generalization of the game Hex. Game Overview Separed Teamhex is a connection game played by four players on a square hexagonal board (same board as in two-player hex). Players are arranged into two fixed teams of two, and victory can be achieved either individually or jointly with an ally. Board and Pieces The game is played on an NĂNĂ N square hexagonal board, with N even (default N=20N=20). Each cell can contain at most one stone. Each player has a distinct stone color. The board is divided into zones A, B, C, and D (see Figure 1). Players and Teams There are four players, indexed 0,1,2,3\0,1,2,3\. Teams are fixed: âą Team A: players 0 and 2 âą Team B: players 1 and 3 Stones of a player and their ally are considered connected for the purpose of path formation for shared wins. Turn Order, Color, and Moves Player 0 is Back, player 1 is White, player 2 is Blue, player 3 is Yellow. In turn, a player can only play a piece of their color on any empty cell in a specific zone. In each zone, only two players can play (the rules of two-player Hex are found locally). The turn order and the allowed zones associated with the corresponding action are as follows: black player plays in zone A, then yellow player plays in zone A, then white player plays in zone B, then black plays in zone B, then blue plays in zone C, then white plays in zone C, then yellow plays in zone D, then blue plays in zone D. This cycle repeats until the end of the game. The game ends immediately when a winning condition is met. Figure 1: Board for Separed Teamhex Adjacency and Connectivity Connectivity follows Hex-style adjacency: each cell has up to six neighbors. Player-Specific Goal Edges Each player is assigned two disjoint segments of the outer board boundary, i.e. of the board sides (see Figure 1). Team sides are the union of team members sides (we find the double pair of opposite edges from the two-player game). Winning Conditions After each move, the game checks whether a connected component (using Hex adjacency) touches two opposite board sides for at least one player or for at least one team. Two types of victory are distinguished. Strong (Individual) Win: a player achieves a strong win if their own stones alone form a connected path between their two sides. Team (Shared) Win: if no strong win exists, but a connected path exists between the two sides of the team using stones from both allied players, then both allies win jointly. Scoring âą Strong individual win: â Winning player: +2 â All other players: â2 âą Team win: â Each winning ally: +1 â Each opposing player: â1 Note that the associated terminal evaluation that we used is the score of the game. Termination âą The game always terminates immediately upon the first detected winning configuration. âą There are no draws. 4.4.6 Quadamazons We introduce the following generalization of the game Amazons for 4 players. Board The board is a square grid of size NĂNĂ N (N even ; default N=14N=14) with a multi-interaction distance parameter d (default d=2d=2). The parameter d divides the board into 9 atomic zones: 4 zones of size (N2âd)Ă(N2âd) ( N2-d )Ă ( N2-d ) where only two players can play; 2 zones (N2âd)Ă(2â d) ( N2-d )Ă (2· d ) and 2 zones (2â d)Ă(N2âd) (2· d )Ă ( N2-d ) where three players can play and one zone (2â d)Ă(2â d) (2· d )Ă (2· d ) where all 4 players can play. As in the classic game, cells can be empty, occupied by a player piece called amazon or blocked by an arrow (a neutral permanent obstacle piece). Initial Setup Each player starts with 4 amazons pieces. Initial positions are fixed on the board edges (see Figure 2). Figure 2: Actions The game proceeds in turns. Each turn is composed of two steps and each step is composed of two phases. The first phase of each step consists in moving one of their amazon: all amazons move like a chess queen (possible movements: in a straight line in one of the 8 directions, at any distance, to arrive at an empty square, but cannot pass over an obstacle: i.e. an amazon or an arrow). Each amazon can only move within the area associated with their player: the rectangle (N2+d)ĂN ( N2+d )Ă N or NĂ(N2+d)NĂ ( N2+d ) corresponding to the space on the board surrounded by the two lines of the playerâs color (see Figure 2). Each player zone is divided into two sub-zones by a dotted line (two sub-zones of size (N2+d)ĂN2 ( N2+d )Ă N2 or N2Ă(N2+d) N2Ă ( N2+d )). If the first amazon moved during the current turn arrives in one of the two sub-zones, the second amazon to move must end up in the other sub-zone. The second phase of each step consists in placing an arrow as if it had been pulled by the amazon that had just moved (as in the classic game). The legal actions for an arrow are any empty case starting from the new position of the amazon by following the legal movement of the chess queen. In addition, the arrow must be placed in the sub-zone where the amazon is newly located or be placed in the exact position where the amazon was before its movement. Elimination and Turn Order If a player has no legal move at the first phase of their first step, it is eliminated. Eliminated players are skipped. If a player has no legal move at the first phase of their second step, their step is passed. The game continues until all players are eliminated, or only one player remains with legal moves. End of Game and Scoring The game ends in two cases: 1. All players are eliminated: the last player to be eliminated is declared the winner. Scores are assigned by reverse elimination order: last eliminated player scores 11, the second last eliminated player scores 0, third last player scores â1-1, and the first eliminated player scores â2-2. 2. One player remains: the remaining player is the winner. Their score equals the number of legal moves available at termination: s. The last eliminated player scores 0, the second last eliminated player scores âs-s, and the first eliminated player scores â2âs-2s. Note that the associated terminal evaluation that we used is the score of the game. 4.4.7 Quadrothello We introduce the following generalization of Othello (also known as Reversi) for four players, that we called Quadrothello. A multiplayer version of Othello, called Rolit, already exists. However, this game suffers from two major flaws: unlike the two-player game, an eliminated player can return to the game, and the game is extremely chaotic, making planning impossible in practice. The generalization we propose allows us to significantly increase control in order to be a more interesting benchmark for comparing search algorithms. Overview As in the two-player game, players compete to control as many board cells as possible when the game ends. However, players are restricted to specific zones, meaning that only two players can play in any given zone. This allows for a localized version of the two-player Othello rules, thus preserving its control and strategies. However, actions performed in one zone can affect other zones, making it a true multiplayer game. Board and Players The game is played on a square board of size NĂNĂ N (N even, default N=14N=14). The board is partitioned into four overlapping zones of shape NĂN2NĂ N2 or N2ĂN N2Ă N, one per player (see Figure 3): âą Player 0 (black): top half âą Player 1 (white): right half âą Player 2 (green): bottom half âą Player 3 (blue): left half. Figure 3: Quadrothello board at the start of the game (the semicircles indicate the playersâ zones). Each player starts with four stones, placed near the center of the board in a local symmetric configuration. Turn Order Players take turns in cyclic order: 0â1â2â3â0ââŠ0â 1â 2â 3â 0ââŠ. If a player has no legal moves, their turn is automatically skipped. Legal Moves A move consists of placing a stone on an empty cell inside the current playerâs zone. A move is legal if and only if the cell is empty and there exists at least one direction (among the 8 surrounding directions: horizontal, vertical, diagonal) such that: âą One or more consecutive opponent stones are encountered, âą Followed by a stone belonging to the current player. After placing a stone, all opponent stones between the two player stones are captured (remplaced by current player stones). Game End The game ends when all four players consecutively have no legal moves. Scoring and Winner Each playerâs score is the number of stones they own on the board. At game end, the player(s) with the maximum score win. Ties are allowed (multiple winners). Note that the associated terminal evaluation that we used is the score of the game. 4.4.8 Triinversion We propose the following other generalization of Othello, this time for three player, that we called Triinversion. This is no longer exactly a generalization but a variation: the game is played on a hexagonal board, so there are only 6 directions for alignment. Unlike Quadrothello, there are no spatial constraints on placement. However, in order to have more control over the captures of pieces, the capture rules have been modified. Board and Players The game is played by three players, indexed as Player 0 (cyan), Player 1 (magenta), and Player 2 (yellow). The board is a hexagonal hex board of side length l (default parameter length l=6l=6). Each cell can contain at most one piece, owned by one of the three players. Special adjacency rules apply at the geometric center to preserve hexagonal connectivity: the central position is not a playable position and all pair of positions adjacent to the center, which which are opposite each other with respect to the center, are considered adjacent (and therefore aligned for captures). Each player has a direct opponent and an indirect opponent. Player 0âs direct opponent is player 2, player 1âs direct opponent is player 0, and player 2âs direct opponent is player 1. The other opponent is the indirect opponent. Initial Setup At the beginning of the game, six pieces are placed symmetrically around the center: see Figure 4. Figure 4: Triinversion board at the start of the game. Turn Order Players take turns in cyclic order: Player 0 â Player 1 â Player 2 â Player 0 â âŠ. If a player has no legal moves, they must pass. If all three players consecutively have no legal moves, the game ends. Legal Moves A legal action is to place a piece of their color on an empty cell in such a way that a line of their direct opponentâs pieces is surrounded by that piece and either one of their pieces or one of their indirect opponentâs pieces. By placing such a piece, all of their direct opponentâs pieces are removed and replaced by their pieces. As a reminder, two alignments of pieces of the same player in the same direction separated only by the always empty central cell are considered as a single alignment and can therefore be surrounded and replaced all at once. Game Termination The game ends when all three players consecutively have no legal moves. Winner Determination and Scoring The winner is the player with the highest final score. In case of a tie, the tied players are jointly considered winners. A playerâs score is their number of pieces plus the number of pieces of their indirect opponent. Note that the associated terminal evaluation that we used is the score of the game.