Study and Improvement of Search Algorithms in Stochastic Perfect-Information

Quentin Cohen-Solal, Tristan CazenavearXiv 2026 · arXiv

TL;DR

This paper introduces Unbounded Expectiminimax, a novel search algorithm that brings the efficiency of best-first search to stochastic games like Backgammon and Azul. By sampling only one chance outcome per iteration while maintaining exact value backups, the algorithm avoids the exponential "combinatorial explosion" of traditional methods and consistently outperforms Monte Carlo Tree Search (MCTS) and classic Expectiminimax.

What Problem Does This Paper Address?

In the world of AI for games, we have a solid handle on deterministic games like Chess or Go. Algorithms like Unbounded Minimax allow computers to explore the most promising moves deeply without being restricted by a fixed search horizon. However, adding a roll of the dice or a shuffle of cards—stochasticity—breaks these traditional guarantees.

The primary challenge is the "combinatorial explosion." In a stochastic game, every "chance node" (like a dice roll) branches out into multiple possible outcomes. Standard search algorithms like Expectiminimax try to expand all these outcomes, which causes the search tree to grow so fast that the AI can only "see" a few moves ahead. While Monte Carlo Tree Search (MCTS) handles this by using random simulations, it often suffers from high variance and requires careful tuning of exploration parameters. The authors sought a way to combine the deep, best-first exploration of Unbounded Minimax with the probabilistic requirements of stochastic games.

Methods

The authors propose Unbounded Expectiminimax, which generalizes the best-first approach to the stochastic setting. Its key innovations include:

  • Selective Sampling at Chance Nodes: Unlike classic Expectiminimax, which expands every possible outcome of a dice roll, this algorithm expands only one sampled outcome per iteration. This allows the search to reach much deeper positions within a fixed time budget.
  • Exact Backpropagation: While it samples outcomes like MCTS, it doesn't rely on Monte Carlo averages. Instead, it uses exact expectiminimax backup operations (weighted averages based on game probabilities) to propagate values up the tree.
  • The Completion Technique: This prunes "solved" states (where a win or loss is guaranteed) from the search, preventing the AI from wasting time on settled parts of the game tree.
  • Safe Decision Rule: Instead of just picking the move with the highest estimated value, the "Safe" variant picks the move that was most frequently identified as the best during the search process, increasing robustness against errors in the evaluation function.

Datasets

The researchers evaluated their algorithms across 8 diverse stochastic games:

  • Azul, Kingdomino, Mighty Duel Kingdomino, Can’t Stop, Backgammon, EinStein würfelt nicht!, Shogun, and Martian Dice.

To ensure statistical significance, they didn't just use one "brain" for the AI. They trained 30 independent neural network evaluation functions for each game using the Athénan architecture. The final evaluation involved a massive tournament of 14,400 matches per algorithm.

Key Insights and Ideas

  • Depth over Breadth: By sampling chance outcomes rather than expanding them all, the algorithm effectively "tunnels" deeper into the game tree. This is particularly effective when the AI has a reasonably accurate evaluation function to guide it.
  • Parameter-Free Search: Unlike MCTS, which requires tuning an exploration constant ($C$), Unbounded Expectiminimax is driven entirely by backed-up values. This makes it easier to apply to new games without domain-specific tweaking.
  • The Power of "Completion": One of the most significant performance boosts came from the Completion technique. Identifying and pruning solved states improved average performance by approximately 8%.
  • Evaluation Quality is King: Because the algorithm preserves exact backup operations, its performance scales directly with the accuracy of the underlying neural network. In the "ideal" case of a perfect evaluation function, the optimal move could be identified in a single iteration.

Key Results

The experimental results were clear: Unbounded Expectiminimax (especially with the Completion technique) is the new state-of-the-art for this category of games.

Table 4: Average binary scores over all games (10s per action). Unbounded E + C shows the highest mean score.

As shown in Table 4, Unbounded E + C achieved a mean binary score of 6.77, significantly outperforming classic Expectiminimax (-6.0) and various MCTS flavors (ranging from -7.24 to -55.73).

Interestingly, the "Safe Decision" rule, which is a massive win in deterministic games, showed more nuanced results here. While it helped in short-duration searches (1 second per move), its advantage diminished in longer searches (10 seconds per move) for some games.

Table 3: Binary scores for all games of the evaluated algorithms without batching against Expectiminimax with batching (All algorithms have 10s per action).

Limitations and Future Work

While the algorithm is highly effective, the authors note that its success is tied to the availability of a "reasonably accurate" evaluation function. If the neural network's estimates are poor, the best-first search might focus its efforts on the wrong branches of the tree.

The authors suggest two main paths for future research:

  1. Multiplayer Games: Extending this framework to games with more than two players.
  2. Imperfect Information: Adapting the search to handle games where some information is hidden (like Poker or Bridge), which adds another layer of complexity beyond simple stochasticity.

Summary updated

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.
BibTeX
@misc{cohensolal2026study,
  author = {Quentin Cohen-Solal and Tristan Cazenave},
  title = {{Study and Improvement of Search Algorithms in Stochastic Perfect-Information}},
  year = {2026},
  eprint = {2611.24486},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24486},
}
Figure