Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge

Quentin Cohen-Solal, Tristan CazenavearXiv 2023 · OpenReview

Abstract

In this paper, we extend the Descent framework, which enables learning and planning in the context of two-player games with perfect information, to the framework of stochastic games. We propose two ways of doing this: the first generalizes the search algorithm (Descent) to stochastic games, and the second approximates stochastic games by deterministic games. We evaluate these approaches on the game EinStein würfelt nicht! against state-of-the-art algorithms: Expectiminimax and Polygames (an AlphaZero implementation). Our generalization, Descent Expectiminimax, obtains the best results, while the deterministic approximation also shows promise for specific contexts.

Introduction

Modern game AI typically relies on Monte Carlo Tree Search (MCTS) and a combination of policy and value networks. The Descent framework offers a value-only alternative that uses deep minimax-style searches. While successful in deterministic games like Chess or Go, Descent was not originally designed for stochastic environments where random events, such as dice rolls, introduce "chance nodes" into the search tree. This paper addresses the computational challenge of the increased branching factor in stochastic games to enable self-play learning without prior knowledge.

Methods

The authors propose two primary extensions to the Descent framework for stochastic environments:

1. Stochastic Game Determinization

This approach approximates a stochastic game as a series of deterministic ones. Random events are pre-determined before a match, allowing the AI to play a "fixed" version. Post-match, data is reconstructed using actual probabilities to update the value network. This allows the AI to learn from chance nodes without exhaustive exploration during search.

2. Descent Expectiminimax

This is a direct generalization of the Descent algorithm. The search handles three types of nodes:

  • Max/Min nodes: Selecting optimal moves for players.
  • Chance nodes: Selecting random outcomes based on game probabilities.
  • Backpropagation: Updating values using the weighted average of all possible outcomes (the expectiminimax value).

Additionally, a depth heuristic is employed to reward the agent for winning quickly and losing slowly, providing a denser training signal for the neural network.

Experimental Setup

The primary benchmark is "EinStein würfelt nicht!" (Einstein does not play dice!), a 5x5 board game characterized by perfect information but high stochasticity due to dice rolls.

The 5x5 board of EinStein würfelt nicht!

The evaluation compares the proposed Descent variants against Polygames and a standard Expectiminimax baseline.

Key Results

A round-robin tournament was conducted to evaluate performance. Descent Expectiminimax emerged as the superior variant.

Win rates (W.R.) and confidence intervals (C.R.) for different Descent variants.

Key findings include:

  • Performance: Descent Expectiminimax achieved a 53.9% win rate in the internal tournament and a 57.3% mean win rate against Polygames when using the depth heuristic.
  • Information Density: Unlike AlphaZero's sparse reward signal, Descent learns from the minimax values of the entire search tree, requiring fewer matches to reach proficiency.
  • Heuristic Impact: The depth heuristic significantly improved performance, raising the win rate from 44.5% to 55.5% in head-to-head tests, proving that "winning fast" is a powerful training signal.

Conclusion

The results demonstrate that a value-only approach with deep search is viable for stochastic games. While Descent Expectiminimax provided the best results in this study, the Determinization approach shows promise for games with even larger branching factors. Future work will explore scalability to more complex stochastic environments like Backgammon or card games.

Summary updated

Abstract

In this paper, we extend the Descent framework, which enables learning and planning in the context of two-player games with perfect information, to the framework of stochastic games. We propose two ways of doing this, the first way generalizes the search algorithm, i.e. Descent, to stochastic games and the second way approximates stochastic games by deterministic games. We then evaluate them on the game EinStein wurfelt nicht! against state-of-the-art algorithms: Expectiminimax and Polygames (i.e. the Alpha Zero algorithm). It is our generalization of Descent which obtains the best results. The approximation by deterministic games nevertheless obtains good results, presaging that it could give better results in particular contexts.
BibTeX
@misc{cohensolal2023learning,
  author = {Quentin Cohen-Solal and Tristan Cazenave},
  title = {{Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge}},
  year = {2023},
  eprint = {2302.04318},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.04318},
}
Figure