cs.AINov 18, 2026
SaveStudy and Improvement of Search Algorithms in Stochastic Perfect-Information
Abstract
In this article, we generalize Unbounded Minimax, the state- of-the-art search algorithm for deterministic zero-sum two- player games with perfect information to the framework of stochastic zero-sum two-player games with perfect informa- tion. We experimentally show that this generalized algorithm achieves better performance than the main stochastic search algorithms.
Figures & tables
| Symbols | Definition |
|---|---|
| action set of the state (for the current player) | |
| true if is an end-game state | |
| new state after playing action in the state | |
| Game probability that action is selected in state | |
| current time in seconds | |
| Integer truncation function |
Table 1: Index of symbols
Algorithm 1 Unbounded Expectiminimax (with completion). This algorithm computes the best action to play in the generated non-uniform partial game tree starting from the root state with as search 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 search() by safe_action().
| EinStein würfelt nicht! | ||
|---|---|---|
| Backgammon | ||
| Kingdomino | ||
| Mighty Duel Kingdomino | ||
| Azul | ||
| Martian Dice |
Table 2: Number of convolutional channels and hidden dense neurons used by Athénan for each studied game.
| Azul | Backgammon | Can’t Stop | Einstein würfelt nicht! | Kingdomino | Mighty Duel Kingdomino | Martian Dice | Shogun | |
|---|---|---|---|---|---|---|---|---|
| Unbounded Expectiminimax | 4 ±4 | 2 ±4 | 6 ±3 | -3 ±4 | 19 ±4 | 9 ±4 | -1 ±4 | 19 ±4 |
| Safe Unbounded Expectiminimax | 20 ±4 | -4 ±4 | 1 ±3 | -23 ±4 | 25 ±4 | 10 ±4 | -7 ±4 | 18 ±4 |
| classic Expectiminimax with Completion | -7 ±4 | -4 ±4 | 4 ±3 | 0 ±4 | -3 ±4 | 2 ±4 | 0 ±4 | 0 ±4 |
| Safe Unbounded Exp. without Completion | -8 ±4 | -3 ±4 | -5 ±3 | -3 ±4 | 7 ±4 | -2 ±4 | -2 ±4 | 7 ±4 |
| Unbounded Exp. without Completion | -18 ±4 | 0 ±4 | -2 ±3 | -2 ±4 | 1 ±4 | -2 ±4 | -6 ±4 | 7 ±4 |
| classic Expectiminimax | -13 ±4 | -7 ±4 | -4 ±3 | 2 ±4 | 3 ±4 | -6 ±4 | 1 ±4 | -26 ±4 |
Table 3: Binary scores for all games of the evaluated algorithms without batching against Expectiminimax with batching (All algorithms have 10s per action).
| mean | lower bound | upper bound | |
|---|---|---|---|
| Unbounded E +C | 6.77 | 5.61 | 7.93 |
| Safe Unbounded E +C | 5.01 | 3.87 | 6.17 |
| Expectiminimax +C | -0.99 | -2.15 | 0.18 |
| Safe Unbounded E | -1.43 | -2.59 | -0.26 |
| Unbounded E | -2.7 | -3.87 | -1.55 |
| Expecti. | -6 | -7.18 | -4.82 |
Table 4: Average binary scores over all games of the evaluated algorithms without batching against classic Expectiminimax with batching (E: Expectiminimax ; +C: with Completion). All algorithms have 10s per action.
| mean | lower bound | upper bound | |
|---|---|---|---|
| Unbounded E +C | 1.51 | 0.35 | 2.66 |
| Safe Unbounded E +C | 4.69 | 3.55 | 5.84 |
| Safe Unbounded E | 1.72 | 0.57 | 2.87 |
| Unbounded E | -3.81 | -4.98 | -2.65 |
| Expectiminimax +C | -3.84 | -5.01 | -2.7 |
| Expectiminimax | -5.12 | -6.27 | -3.97 |
Table 5: Average binary scores over all games of the evaluated algorithms without batching against classic Expectiminimax with batching (E: Expectiminimax ; +C: with Completion). All algorithms have 1s per action.
| Azul | Backgammon | Can’t Stop | Einstein würfelt nicht! | Kingdomino | Mighty Duel Kingdomino | Martian Dice | Shogun | |
|---|---|---|---|---|---|---|---|---|
| Unbounded Expectiminimax | -6 ±4 | -1 ±4 | 2 ±3 | 3 ±4 | 1 ±4 | -10 ±4 | 0 ±4 | 22 ±4 |
| Safe Unbounded Expectiminimax | 14 ±4 | 3 ±4 | 3 ±3 | -10 ±4 | 10 ±4 | 7 ±4 | -2 ±4 | 13 ±4 |
| Safe Unbounded Exp. without Completion | -1 ±4 | 4 ±4 | -5 ±3 | -2 ±4 | 8 ±4 | 3 ±4 | -4 ±4 | 9 ±4 |
| Unbounded Exp. without Completion | -20 ±4 | 1 ±4 | -2 ±3 | 0 ±4 | -4 ±4 | -14 ±4 | -3 ±4 | 11 ±4 |
| classic Expectiminimax with Completion | -18 ±4 | -3 ±4 | 5 ±3 | 0 ±4 | -4 ±4 | -1 ±4 | 0 ±4 | -10 ±4 |
| classic Expectiminimax | -16 ±4 | 1 ±4 | 0 ±3 | -1 ±4 | 0 ±4 | -2 ±4 | 2 ±4 | -25 ±4 |
Table 6: Binary scores for all games of the evaluated algorithms without batching against Expectiminimax with batching (All algorithms have 1s per action).
| mean | lower bound | upper bound | |
|---|---|---|---|
| -29.38 | -30.44 | -28.33 | |
| -27.21 | -28.26 | -26.14 | |
| -24.87 | -25.91 | -23.81 | |
| -19.95 | -21.03 | -18.85 | |
| -13.44 | -14.57, | -12.29 | |
| -8.62 | -9.78 | -7.49 |
Table 7: Average binary scores over all games of and for different values of against classic Expectiminimax with batching (10 seconds per search).
| Azul | Backgammon | Can’t Stop | Einstein würfelt nicht! | Kingdomino | Mighty Duel Kingdomino | Martian Dice | Shogun | |
|---|---|---|---|---|---|---|---|---|
| -83 ±2 | -23 ±4 | -14 ±4 | -3 ±4 | -3 ±4 | -6 ±4 | -3 ±4 | -99 ±1 | |
| -71 ±3 | -23 ±4 | -6 ±4 | -5 ±4 | -9 ±4 | -2 ±4 | -4 ±4 | -98 ±1 | |
| -62 ±3 | -22 ±4 | -2 ±3 | 1 ±4 | -6 ±4 | -7 ±4 | -4 ±4 | -97 ±1 | |
| -33 ±4 | -24 ±4 | 4 ±3 | -1 ±4 | -6 ±4 | -4 ±4 | -4 ±4 | -93 ±1 | |
| 1 ±4 | -21 ±4 | 7 ±3 | -5 ±4 | -6 ±4 | -3 ±4 | -4 ±4 | -77 ±3 | |
| 24 ±4 | -14 ±4 | 6 ±3 | -7 ±4 | -6 ±4 | 0 ±4 | -5 ±4 | -66 ±3 |
Table 8: Binary scores for all games of and for different values of against classic Expectiminimax with batching (10 seconds per search).
| mean | lower bound | upper bound | |
|---|---|---|---|
| -29.6 | -30.67 | -28.55 | |
| -27.49 | -28.52 | -26.42 | |
| -24.78 | -25.84 | -23.71 | |
| -20.46 | -21.56, | -19.36 | |
| -15.59 | -16.7 | -14.48 | |
| -13.82 | -14.94 | -12.68 |
Table 9: Average binary scores over all games of and for different values of against classic Expectiminimax with batching (10 seconds per search).
| Azul | Backgammon | Can’t Stop | Einstein würfelt nicht! | Kingdomino | Mighty Duel Kingdomino | Martian Dice | Shogun | |
| -78 ±3 | -26 ±4 | -13 ±4 | -5 ±4 | -5 ±4 | -5 ±4 | -8 ±4 | -99 ±1 | |
| -71 ±3 | -26 ±4 | -8 ±4 | 0 ±4 | -8 ±4 | -5 ±4 | -3 ±4 | -99 ±1 | |
| -57 ±3 | -26 ±4 | -2 ±4 | 1 ±4 | -9 ±4 | -7 ±4 | 0 ±4 | -99 ±1 | |
| -31 ±4 | -23 ±4 | 3 ±3 | -3 ±4 | -7 ±4 | -5 ±4 | -2 ±4 | -96 ±1 | |
| 6 ±4 | -20 ±4 | 5 ±3 | -5 ±4 | -8 ±4 | -6 ±4 | -6 ±4 | -91 ±2 | |
| 20 ±4 | -20 ±4 | 2 ±3 | -11 ±4 | -10 ±4 | -2 ±4 | -6 ±4 | -83 ±2 |
Table 10: Binary scores for all games of and for different values of against classic Expectiminimax with batching (10 seconds per search).
| mean | lower bound | upper bound | |
|---|---|---|---|
| -30.77 | -31.77 | -29.74 | |
| -29.06 | -30.09 | -28.03 | |
| -29.11 | -30.11 | -28.07 | |
| -26.16 | -27.21 | -25.1 | |
| -20.65 | -21.72 | -19.55 | |
| -16.45 | -17.58 | -15.32 |
Table 11: Average binary scores over all games of and for different values of against classic Expectiminimax with batching (1 seconds per search).
| Azul | Backgammon | Can’t Stop | Einstein würfelt nicht! | Kingdomino | Mighty Duel Kingdomino | Martian Dice | Shogun | |
|---|---|---|---|---|---|---|---|---|
| -89 ±2 | -35 ±4 | 5 ±3 | -6 ±4 | -10 ±4 | -9 ±4 | -5 ±4 | -98 ±1 | |
| -87 ±2 | -35 ±4 | 5 ±3 | -5 ±4 | -4 ±4 | -7 ±4 | -2 ±4 | -97 ±1 | |
| -83 ±2 | -31 ±4 | 2 ±3 | -4 ±4 | -6 ±4 | -11 ±4 | -2 ±4 | -97 ±1 | |
| -72 ±3 | -29 ±4 | 1 ±3 | -2 ±4 | -10 ±4 | -7 ±4 | 1 ±4 | -93 ±2 | |
| -46 ±4 | -25 ±4 | 3 ±3 | -4 ±4 | -5 ±4 | -6 ±4 | -1 ±4 | -81 ±2 | |
| -24 ±4 | -23 ±4 | 5 ±3 | -10 ±4 | 0 ±4 | -8 ±4 | -4 ±4 | -67 ±3 |
Table 12: Binary scores for all games of and for different values of against classic Expectiminimax with batching (1 seconds per search).
| mean | lower bound | upper bound | |
|---|---|---|---|
| -30.07 | -31.07 | -29.07 | |
| -29.12 | -30.14 | -28.1 | |
| -28.87 | -29.88 | -27.84 | |
| -26.31 | -27.36 | -25.25 | |
| -22.93 | -24 | -21.84 | |
| -19.34 | -20.44 | -18.22 |
Table 13: Average binary scores over all games of and for different values of against classic Expectiminimax with batching (1 seconds per search).
| Azul | Backgammon | Can’t Stop | Einstein würfelt nicht! | Kingdomino | Mighty Duel Kingdomino | Martian Dice | Shogun | |
| -88 ±2 | -43 ±4 | 4 ±3 | -1 ±4 | -6 ±4 | -3 ±4 | -5 ±4 | -99 ±1 | |
| -85 ±2 | -38 ±4 | 4 ±3 | 0 ±4 | -3 ±4 | -9 ±4 | -2 ±4 | -99 ±0 | |
| -80 ±2 | -42 ±4 | 1 ±3 | 0 ±4 | -3 ±4 | -7 ±4 | -1 ±4 | -99 ±1 | |
| -68 ±3 | -33 ±4 | 2 ±3 | -1 ±4 | -4 ±4 | -8 ±4 | 0 ±4 | -98 ±1 | |
| -44 ±4 | -34 ±4 | 3 ±3 | -3 ±4 | -8 ±4 | -5 ±4 | 2 ±4 | -93 ±1 | |
| -16 ±4 | -29 ±4 | 4 ±3 | -12 ±4 | -4 ±4 | -8 ±4 | -7 ±4 | -82 ±2 |
Table 14: Binary scores for all games of and for different values of against classic Expectiminimax with batching (1 seconds per search).
| game tree size | chance weights | BGG rating | |
|---|---|---|---|
| EinStein würfelt nicht! | |||
| Backgammon | |||
| Azul | |||
| Kingdomino | |||
| Mighty Duel Kingdomino | |||
| Martian Dice |
Table 15: Some characteristics of the benchmark games: the game tree size estimation is where is the mean branching factor and is the mean number of states in a full match ; the combinatorial weight of chance estimation is defined as the mean over matches of where is the set of chance states of , is the set of decision states of , and is the branching factor of state . Values are computed from random matchs. The BGG rating is the game’s rating as given by the BoardGameGeek community ( https://boardgamegeek.com ).
Figure 1: The two starting areas at EinStein wuerfelt nicht.
More in this topic
Zero-Sum Games
Zero-sum games study strategic settings where one player's gain is another's loss and equilibrium play protects against worst-case opponents.
See all 51 papersIn 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.
Completeness of Unbounded Best-First Minimax and Descent Minimax
In this article, we focus on search algorithms for two-player perfect information games, whose objective is to determine the best possible strategy, and ideally a winning strategy. Unfortunately, some search algorithms for games in the literature are not able to always determine a winning strategy, even with an infinite search time. This is the case, for example, of the following algorithms: Unbounded Best-First Minimax and Descent Minimax, which are core algorithms in state-of-the-art knowledge-free reinforcement learning. They were then improved with the so-called completion technique. However, whether this technique sufficiently improves these algorithms to allow them to always determine a winning strategy remained an open question until now. To answer this question, we generalize the two algorithms (their versions using the completion technique), and we show that any algorithm of this class of algorithms computes the best strategy. Finally, we experimentally show that the completion technique improves winning performance.
Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis
We present a finite-sample analysis of decentralized learning in two-player zero-sum matrix games and stochastic games, with a focus on best-response-based learning algorithms. In matrix games, the learning algorithm is payoff-based and symmetric: each player updates its policy using only its own payoff observations, incrementally moving toward an estimated smoothed best response to the opponent's latest policy. For stochastic games, we build on this matrix-game primitive to develop a learning algorithm called value iteration with smoothed best response (VI-SBR), which combines smoothed-best-response learning in induced matrix games with a decentralized, model-free approximation of minimax value iteration. We establish finite-sample guarantees in both settings. For matrix games, our results imply a sample complexity of for finding an -Nash distribution and, with explicit exploration, for finding an -Nash equilibrium. For stochastic games, we prove that the exploration-enhanced VI-SBR algorithm achieves a sample complexity of for finding an -Nash equilibrium. Technically, our analysis develops a coupled Lyapunov-drift framework. This framework simultaneously handles stochastic iterative algorithms with multiple interacting stochastic iterates, the non-zero-sum auxiliary games generated by independently updated value functions, and the time-inhomogeneous Markovian noise induced by time-varying policies. The resulting tools may be useful more broadly for analyzing learning algorithms with coupled stochastic iterates and nonstationary sampling processes.