cs.LGNov 10, 2025
SaveScalable Decision Making for Games of Imperfect Information
Organizations: Carnegie Mellon University · NYU Tandon School of Engineering · Stanford University · Massachusetts Institute of Technology
Abstract
Real-world decision-making generally involves hidden information, that is, information that is unknown to one agent but possessed by another. Unfortunately, the presence of large amounts of hidden information renders established reinforcement learning and search approaches ineffective. Even with multimillion-dollar industrial research efforts, top-human-level play at Stratego---a board wargame with hidden information on a massive scale---has remained beyond the reach of artificial intelligence (AI). Here we introduce Ataraxos, an AI for Stratego based on general techniques that we developed for both self-play reinforcement learning and test-time search under hidden information. Ataraxos defeated the most decorated human Stratego player of all time by a large margin---achieving, to our knowledge, the first superhuman result in the game's history---while consuming orders of magnitude less compute and data than previous efforts. Using the same techniques, we built a superhuman AI for Barrage Stratego and state-of-the-art AIs for Hanabi and dou dizhu, all with low cost and high sample efficiency. The success of this approach across adversarial, cooperative and team games establishes a design pattern for reinforcement learning and search that is effective under large amounts of hidden information, a longstanding desideratum of the field of strategic decision-making.
Figures & tables
Figure 1: Graphical representation of differential relationships between decision frequencies and values among contemporaneous counterfactuals under imperfect information. Nodes represent decisions. The colour/dash pattern of an edge represents whether changing the frequency of a decision on one end of the edge increases (blue/solid) or decreases (brown/dashed) the marginal value of the decision on the other end of the edge. The interconnectedness of frequencies and values across decisions makes it difficult to intuit the frequencies with which decisions should be made.
Figure 2: An illustration of the game of Stratego. a The starting position of a game from the perspective of the red player. Each player arranges their pieces in secret, so the types of the blue pieces are concealed from the red player (and vice versa). From this starting position, the players alternate moves, each of which is defined by the displacement of a single piece, as in chess. b A move in the game for the blue player. On this move, because a blue piece moves onto a square occupied by a red piece, there is a battle. During a battle, the types of both pieces are revealed and at least one of the two is captured (determined based on their types and attack-defence roles). If a Flag (see piece on a1) is captured in battle, the capturing player wins the game.
Figure 3: Effective win probability implied by the network value predictions over the games played against Pim Niemeijer. Effective win probability is the expected value of the game with winning assigned value 1, drawing assigned value 1/2, and losing assigned value 0.
List of extendeddatafigures 1 Setup and move network diagrams. Top, the setup network is a decoder-only transformer that generates setups by autoregressively placing the 40 pieces onto squares of the board in row-major order (i.e., first row, first column; first row, second column; and so forth). (A) As input, the setup network takes tokenized piece types with learned absolute positional embeddings [ 34 ] . As output, for each setup prefix, the setup network provides: (B) an estimate of the conditional probability of winning, losing, or drawing a self-play game; (C) an estimate of the conditional entropy of the setup; and (D) probabilities for placing pieces of each type on that square. Bottom, the move network is an encoder-only transformer that selects the piece to move and the square to which to move it. (E) As input, the move network takes tokenized representations of the occupiable squares with learned absolute positional embeddings, and an additional token for value prediction. The move network outputs: (F) a categorical prediction of the game outcome; and (G) probabilities for the moves computed using a key–query matrix product [ 33 ] .
List of extendeddatafigures 4 Diagram of belief architecture. (A) The input to the encoder is a tokenized representation of the occupiable squares with learned absolute positional embeddings, similar to the move network. (B) The output of the encoder is filtered to keep only tokens corresponding to squares occupied by hidden pieces of the opponent. Keys and values for these tokens are passed into transformer decoder layers. The inputs (C) and outputs (D) to the decoder are the types and predictions about the types of the opponent hidden pieces, respectively, in row-major order; the inputs use learned positional embeddings.
List of extendeddatafigures 2 Performance and entropy of Ataraxos as a function of compute. a Elo of the policy networks over the course of training, as measured by performance against a fixed reference opponent. Quantifying skill level in Stratego by Elo is useful but flawed, as randomization can compress margins (i.e., make margins between two players smaller than would be predicted by their respective margins against a common third player whose skill level lies between them), among other reasons. b The entropy of the setups and c the entropy of the moves (in expectation over the self-play distribution of positions). Dynamic damping shepherds these entropies smoothly downward over training, preventing them from collapsing. d Elo of search on a single H100 under varying rollout counts and search depths with 95% confidence intervals. Deeper searches with more rollouts produce stronger performance but require more time per move. During the evaluation, Ataraxos used a 40-ply 1,000-rollout search that averaged about 1.26 seconds per move—a pace of play faster than that of human players.
List of extendeddatafigures 3 Stratego board layout and piece mechanics. a An example starting position. The light blue blocks in the middle of the board are called lakes and cannot be occupied by the pieces of either player. b Multiplicities, movement abilities, and combat rules for Stratego pieces. Scouts can move an arbitrary number of squares in cardinal directions; other movable pieces can move a single square in cardinal directions. By rank means that the higher numbered piece defeats the lower numbered piece.
List of extendeddatafigures 5 Ablations of the training run. a Single-seed ablations. Without distributed training (yellow), Ataraxos follows a similarly shaped trajectory of improvement over the course of scheduled annealing, but at a substantially lower Elo. Series marked with “&” additionally remove the indicated component. When setup learning is also removed (and replaced by a fixed uniform distribution over setups), the shape of the Elo trajectory flattens—both because of the weakness of uniformly distributed setups and because of the bad assumptions the associated self-play distribution causes the move network to make about the pieces of its opponents. Removing bfloat16 and advantage filtering substantially slows iterations due to more expensive network calls and larger training datasets, respectively. Removing advantage filtering also causes a large increase in move entropy and large decrease in sample efficiency. b Ablations of learning-rate annealing, advantage filtering, and regularization annealing across three seeds. Lines show the mean across seeds and shading shows the minimum and maximum seed performance. All three ablated components materially affect performance over the course of training.
List of extendeddatatables 1 Elo of search with varying hyperparameters. The first row shows direct sampling from the move network (i.e., no search); the second shows the search that was used in the evaluation. Both Elo and time expended increase with the depth of the search and the number of rollouts. Reverse KL regularization strength has a large effect on performance. Removing the reverse KL term to the move network devastates performance—causing it to drop well below that of the move network—because the search overfits to idiosyncrasies of the move network that fail to generalize to other opponents. The final row ablates the learned belief model, replacing it with the belief associated with the uniformly random policy.
List of extendeddatafigures 6 Comparison of current iterates and exponential moving averages across three seeds. a Performance against a fixed reference model over training, with the line showing the mean across seeds and the shading showing the minimum and maximum seed performance. b Difference at each iteration between the strongest and weakest seed. The exponential moving average attains similar or better mean performance while exhibiting lower variation across seeds.
List of extendeddatafigures 7 Estimated probabilities (in percent) of pieces being different types in setups chosen by Ataraxos, assuming that the Flag is on the left side of the setup.
List of extendeddatafigures 8 The setups Ataraxos played in the series against Pim Niemeijer.
List of extendeddatafigures 9 Performance of Ataraxos on Hanabi over games with standard errors. a Average score. b Percentage of perfect (25-point) games.
| Method | Input | Output | Description |
|---|---|---|---|
| CurrentStep | (none) | 64-bit integer | Returns the number of state updates performed by the simulator. |
| ActingPlayer | time step | 0 or 1 | The player acting at the current time step (0 for the red player, 1 for the blue player). |
| ComputeLegalActionMask | time step | (none) | Computes the legal action mask for the acting player at the given time step. The answer is written in a preallocated tensor kept by the rollout buffer. |
| ComputeInfostateTensor | time step | (none) | Computes the information state for the acting player at the given time step. The answer is written in a preallocated tensor kept by the rollout buffer. |
| ComputeRewardPl0 | time step | (none) | Computes the reward for the red player at the given time step. The reward is set to 0 for those boards that are not terminated at the given time step. The answer is written in a preallocated tensor kept by the rollout buffer. |
| ComputeIsUnknownPiece | time step | (none) | Computes a boolean tensor indicating which pieces are unknown to the acting player. The answer is written in a preallocated tensor kept by the rollout buffer. |
Table S1: Historical simulator queries exposed by the API.
| Channel(s) | Description |
|---|---|
| 0–11 | Indicator of whether the piece occupying each square belongs to the player and has type , for each of the 12 types Spy, Scout, Miner, Sergeant, Lieutenant, Captain, Major, Colonel, General, Marshal, Flag, Bomb . |
| 12–23 | For each square, probability that it belongs to the opponent and has type for each of the 12 types , assuming the setup and moves were selected uniformly at random. |
| 24–35 | Same as channels 12–23, but from the point of view of the opponent player. |
| 36 | Indicator of what squares on the board are occupied by hidden pieces of the player. |
| 37 | Indicator of what squares on the board are occupied by hidden pieces of the opponent. |
| 38 | Indicator of what squares on the board are empty. |
| Channel(s) | Description |
|---|---|
| 43–52 | Indicator of whether the piece occupying the square belongs to the player, and has ever threatened a piece of the opponent which, at the time of the threat, was a revealed piece of type . |
| 53 | Indicator of whether the piece occupying the square belongs to the player, and has ever threatened a piece of the opponent which, at the time of the threat, was hidden. |
| Channel(s) | Description |
|---|---|
| 54–63 | Indicator of whether the piece occupying the square belongs to the player, and has ever evaded a threat from an opponent’s piece which, at the time of the threat, was a revealed piece of type . |
| 64 | Indicator of whether the piece occupying the square belongs to the player, and has ever evaded a threat from an opponent’s piece which, at the time of the threat, was hidden. |
| Channel(s) | Description |
|---|---|
| 65–74 | Indicator of whether the piece occupying the square belongs to the player, and has ever been actively adjacent to an opponent’s piece which, at the time of the adjacency, was a revealed piece of type . |
| 75 | Indicator of whether the piece occupying the square belongs to the player, and has ever been actively adjacent to an opponent’s piece which, at the time of the adjacency, was hidden. |
| Channel(s) | Description |
|---|---|
| 76–85 | Same as channels 43–52, but from the point of view of the opponent player. |
| 86 | Same as channel 53, but from the point of view of the opponent player. |
| 87–96 | Same as channels 54–63, but from the point of view of the opponent player. |
| 97 | Same as channel 64, but from the point of view of the opponent player. |
| 98–107 | Same as channels 65–74, but from the point of view of the opponent player. |
| 108 | Same as channel 75, but from the point of view of the opponent player. |
| Channel(s) | Description |
|---|---|
| 109–119 | Indicator of whether the given square was occupied, at the start of the game, by a piece of the player of type that has now been captured. |
| 120–130 | Indicator of whether the given square was occupied, at the start of the game, by a piece of the opponent of type that has now been captured. |
| Channel(s) | Description |
|---|---|
| 131–140 | Whether a piece of the player of type died in this square, due to cause of death 1. |
| 141–150 | Whether a piece of the player of type died in this square, due to cause of death 2. |
| 151–180 | Whether a piece of the player of type died in this square, due to causes of death 3–5 (channels 151–160, 161–170, and 171–180, respectively). |
| 181–190 | Whether a piece of the player of type died in this square, due to cause of death 6. |
| 191–250 | Same as channels 131–190, but for the opponent. |
| Channel(s) | Description |
|---|---|
| 251–261 | Whether the piece in the square belongs to the player, and has ever protected a piece of the player which, at the time of the protection, had revealed type . |
| 262 | Whether the piece in the square belongs to the player, and has ever protected an empty square. |
| 263 | Whether the piece in the square belongs to the player, and has ever protected a piece of the player which, at the time of the protection, was not revealed. |
| Channel(s) | Description |
|---|---|
| 264–274 | Whether the piece in the square belongs to the player, and has ever protected against a piece of the opponent which, at the time of the protection, had revealed type . |
| 275 | Padding channel (all zeros). |
| 276 | Whether the piece in the square belongs to the player, and has ever protected against a piece of the opponent which, at the time of the protection, was not revealed. |
| Channel(s) | Description |
|---|---|
| 277–287 | Whether the piece in the square belongs to the player, and has ever been protected by a piece of the player which, at the time of the protection, had revealed type . |
| 288 | Padding channel (all zeros). |
| 289 | Whether the piece in the square belongs to the player, and has ever been protected by a piece of the player which, at the time of the protection, was not revealed. |
| Channel(s) | Description |
|---|---|
| 290–300 | Whether the piece in the square belongs to the player, and has ever been protected against a piece of the opponent which, at the time of the protection, had revealed type . |
| 301 | Padding channel (all zeros). |
| 302 | Whether the piece in the square belongs to the player, and has ever been protected against a piece of the opponent which, at the time of the protection, was not revealed. |
| Channel(s) | Description |
|---|---|
| 303–354 | Same as channels 251–302, but for the opponent. |
| Channel(s) | Description |
|---|---|
| 355–454 | Starting location of each piece on the board, one-hot encoded. Specifically, channel encodes in position whether the piece currently occupying square started from square , according to a row-major ordering of the squares. |
| Hyperparameter | Value |
|---|---|
| Number of consecutive battleless moves after which a draw is declared | |
| Number of moves after which a draw is declared |
Table S2: Game rules training hyperparameters.
| Hyperparameter | Value |
|---|---|
| Number of parallel environments | per GPU |
| Generated setups per player | per GPU |
| Number of moves between training iterations |
Table S3: Data collection hyperparameters.
| Symbol | Meaning |
|---|---|
| Setup for which a game was completed. | |
| A prefix of . | |
| Parameters that generated . | |
| Current parameters. | |
| Probability of given under . | |
| Predicted conditional entropy of setup prefix under . |
Table S4: Setup learning notation.
| Hyperparameter | Value |
|---|---|
| Adam learning rate | |
| Batch size | per GPU |
| Number of epochs per training iteration | |
| Importance ratio clipping parameter | |
| Conditional entropy prediction loss coefficient | |
| Reverse KL to data collection policy loss coefficient |
Table S5: Setup learning hyperparameters.
| Symbol | Meaning |
|---|---|
| A position of the acting player, represented as described in Section S2 . | |
| The sequence of positions subsequent to for the same player. | |
| The parameters that played the move at position . | |
| The current parameters. | |
| Predicted win, loss, draw probabilities at under . | |
| Predicted win, loss, draw probabilities at under . |
Table S6: Move learning notation.
| Hyperparameter | Value |
|---|---|
| Importance ratio clipping parameter | |
| Advantage filtering quantile threshold | |
| Advantage filtering magnitude threshold | |
| Exponential moving average smoothing factor | |
| Advantage estimation | |
| Outcome estimation |
Table S7: Move learning hyperparameters.
| Hyperparameter | Value |
|---|---|
| Adam learning rate | |
| Maximum gradient norm | |
| Batch size | game length |
| Data type | bfloat16 |
| Exponential moving average smoothing factor | |
| Number of environments |
Table S8: Belief learning hyperparameters.
| Hyperparameter | Value |
|---|---|
| Depth | 4 |
| Embedding dimension | 512 |
| Number of heads | 8 |
| Learned positional embedding initialization standard deviation | |
| Feedforward dimension | |
| Total parameters | million |
Table S9: Setup network information.
| Hyperparameter | Value |
|---|---|
| Depth | |
| Embedding dimension | |
| Number of heads | |
| Learned positional embedding initialization standard deviation | |
| Feedforward dimension | |
| Total parameters | million |
Table S10: Move network information.
| Hyperparameter | Value |
|---|---|
| Encoder depth | |
| Number of decoder blocks | |
| Number of heads | |
| Embedding dimension | |
| Dropout | |
| Learned positional embedding initialization | Kaiming uniform [ 58 ] |
Table S11: Belief network information.
| Hyperparameter | Value |
|---|---|
| Reverse KL to magnet policy loss coefficient | |
| Reverse KL to policy network loss coefficient | |
| Number of rollouts | |
| Rollout depth |
Table S12: Search hyperparameters.
Figure S1: Loss values for setup learning over the training run.
Figure S2: Other setup-related values over the training run. a Entropy of the setup distribution. b Proportion of data whose importance ratio is clipped. c Norm of the gradient of the loss. d Entropy maximization coefficient .
Figure S3: Loss values for move learning over the training run.
Figure S4: Other move-related values over the training run. a Entropy of moves over self-play distribution. b Proportion of data whose importance ratio is clipped. c Norm of the gradient of the loss. d Value function change. e Adam learning rate. f Coefficient to magnet policy .
Figure S5: Other information about the training process and games. a Time expenditure of different components of the reinforcement learning loop. Iteration speed is bottlenecked by training and data collection for the move network. b Proportion over training of each of the four possible game endings: Flag capture, forced win (i.e., by virtue of the other player having no legal moves), forced draw (i.e., by virtue of neither player having legal moves), and a 100-move rule draw (i.e., by virtue of there having been 100 consecutive battleless moves). Ataraxos playing against itself draws a much higher proportion of games than humans playing against one another. c The average length of self-play games over training. Ataraxos playing against itself results in much longer games than humans playing against one another. d The average return (win=1, loss=-1, draw=0) for the red player (the first moving player) over training. The roughly equal returns of the red and blue players in the self-play of Ataraxos games support the human belief that move priority is not strategically significant in Stratego.
Figure S6: Pairwise evaluation of 22 checkpoints from the training run (those whose iteration indices were divisible by ). Raw checkpoint pairs were evaluated over games. The -iteration row and column average two evaluation blocks and therefore aggregate games per off-diagonal entry; all other off-diagonal entries use games. Each entry shows the average score of the row checkpoint against the column checkpoint, with wins scored as , draws as , and losses as .
| Hyperparameter | Value |
|---|---|
| Number of consecutive battleless moves after which a draw is declared | |
| Number of moves after which a draw is declared |
Table S13: Barrage Stratego game rules training hyperparameters.
| Hyperparameter | Value |
|---|---|
| Number of parallel environments | per GPU |
| Generated setups per player | per GPU |
| Number of moves between training iterations |
Table S14: Barrage Stratego data collection hyperparameters.
| Hyperparameter | Value |
|---|---|
| Adam learning rate | |
| Batch size | per GPU |
| Number of epochs per training iteration | |
| Importance ratio clipping parameter | |
| Conditional entropy prediction loss coefficient | |
| Reverse KL to data collection policy loss coefficient |
Table S15: Barrage Stratego setup learning hyperparameters.
| Hyperparameter | Value |
|---|---|
| Importance ratio clipping parameter | |
| Advantage filtering quantile threshold | |
| Advantage filtering magnitude threshold | |
| Exponential moving average smoothing factor | |
| Advantage estimation | |
| Outcome estimation |
Table S16: Barrage Stratego move learning hyperparameters.
| Hyperparameter | Value |
|---|---|
| Adam learning rate | |
| Maximum gradient norm | |
| Exponential moving average smoothing factor | |
| Number of environments |
Table S17: Barrage Stratego belief learning hyperparameters.
| Hyperparameter | Value |
|---|---|
| Depth | |
| Embedding dimension | |
| Number of heads | |
| Learned positional embedding initialization standard deviation | |
| Feedforward dimension | |
| Total parameters | million |
Table S18: Barrage Stratego setup network information.
| Hyperparameter | Value |
|---|---|
| Depth | |
| Embedding dimension | |
| Number of heads | |
| Learned positional embedding initialization standard deviation | |
| Feedforward dimension | |
| Total parameters | million |
Table S19: Barrage Stratego move network information.
| Hyperparameter | Value |
|---|---|
| Encoder depth | |
| Decoder depth | |
| Number of heads | |
| Embedding dimension | |
| Feedforward dimension | |
| Dropout |
Table S20: Barrage Stratego belief network information.
| Hyperparameter | Value |
|---|---|
| Number of rollouts | |
| Rollout depth | |
| Update step size | |
| Magnet policy regularization (step size temperature) | |
| Minimum samples per legal action |
Table S21: Barrage Stratego search hyperparameters.
| Hyperparameter | Value |
|---|---|
| Importance ratio clipping parameter | |
| Exponential moving average smoothing factor | |
| Advantage estimation | |
| Discount factor | |
| Adam learning rate | |
| Entropy coefficient |
Table S22: Hanabi actor learning hyperparameters (shared across 2–5 players).
| Hyperparameter | Value |
|---|---|
| Adam learning rate | |
| Batch size | |
| Number of training steps | |
| Number of parallel environments |
Table S23: Hanabi belief learning hyperparameters.
| Hyperparameter | Value |
|---|---|
| Private net | -layer MLP (hidden dim , ReLU) |
| Public net | -layer MLP (hidden dim , ReLU) |
| Public LSTM | -layer LSTM (hidden dim ) |
| Policy head | Linear ( ) |
| Value head | Linear ( ) |
| Total parameters | million |
Table S24: Hanabi actor network architecture.
| Hyperparameter | Value |
|---|---|
| Observation encoder | -layer MLP (hidden dim , ReLU) |
| Sequence | -layer LSTM (hidden dim ) |
| Autoregressive card prediction – Embedding | Linear ( , no bias) |
| Autoregressive card prediction – LSTM | -layer LSTM (input dim , hidden dim ) |
| Autoregressive card prediction – Output | Linear ( ) |
| Total parameters | – million |
Table S25: Hanabi belief network architecture.
| Hyperparameter | Value |
|---|---|
| Number of rollouts | |
| Update step size | |
| Rollout temperature |
Table S26: Hanabi search hyperparameters.
| Hyperparameter | Value |
|---|---|
| Importance ratio clipping parameter | |
| Exponential moving average smoothing factor | |
| Advantage estimation | |
| Outcome estimation | |
| Reverse KL to data collection policy loss coefficient | |
| Muon learning rate |
Table S27: Dou Dizhu actor learning hyperparameters.
| Hyperparameter | Value |
|---|---|
| Muon [ 60 ] learning rate | |
| WSD scheduler stable ratio | |
| Maximum gradient norm | |
| Time steps collected per iteration |
Table S28: Dou dizhu belief learning hyperparameters.
Figure S7: Dou dizhu belief-model training dynamics. Card-ownership accuracy (left) is the fraction of autoregressive hidden-card predictions for which the model identifies the ground-truth holder of the card. Loss (right) is the corresponding mean negative log-likelihood assigned to the ground-truth holder of the card. Both metrics are averaged over valid hidden-card predictions within each belief sequence and then over sequences.
| Hyperparameter | Value |
|---|---|
| Transformer depth | |
| Embedding dimension | |
| Number of heads | |
| Feedforward depth | |
| Feedforward dimension | |
| Total parameters | million |
Table S29: Dou dizhu actor network information.
| Hyperparameter | Value |
|---|---|
| Transformer depth | |
| Embedding dimension | |
| Number of heads | |
| Feedforward depth | |
| Feedforward dimension | |
| Total parameters | million |
Table S30: Dou Dizhu belief network information.
| Hyperparameter | Value |
|---|---|
| Number of rollouts | |
| Update step size | |
| Rollout temperature |
Table S31: Dou dizhu search hyperparameters.
| No. of players | No. of search players | Score | Perfect |
|---|---|---|---|
| 2 | 0 | ||
| 1 | |||
| 2 | |||
| 3 | 0 | ||
| 1 | |||
| 2 |
Table S32: Performance of Ataraxos on Hanabi variants with different numbers of players. We evaluate Ataraxos with different numbers of search players in each variant. Entries report means standard errors over games per condition.
| Row vs Col | Ataraxos | Policy Network | PerfectDou | DouZero |
| Ataraxos | — | |||
| Policy Network | — | |||
| PerfectDou | — | |||
| DouZero | — |
Table S33: Dou dizhu role-averaged performance. Entries report means standard errors. Comparisons involving Ataraxos use duplicated deals; other comparisons use duplicated deals.
| P \ L | Ataraxos | Policy Network | PerfectDou | DouZero |
| Ataraxos | ||||
| Policy Network | ||||
| PerfectDou | ||||
| DouZero |
Table S34: Performance broken down by game role. The row agent is the peasants; the column agent is the landlord. Entries report means standard errors. Comparisons involving Ataraxos use duplicated deals; other comparisons use duplicated deals.
Figure S8: Role-averaged score of Ataraxos against PerfectDou under varying search update step sizes. Each setting was evaluated over duplicated deals. The dashed line shows the performance of the policy network (i.e., Ataraxos without search).