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 papers