Scalable Decision Making for Games of Imperfect Information

Samuel Sokota; Eugene Vinitsky; Hengyuan Hu; Zhiyuan Fan; J. Zico Kolter; Gabriele Farina

cs.LGNov 10, 2025

Scalable Decision Making for Games of Imperfect Information

Authors: Samuel Sokota, Eugene Vinitsky, Hengyuan Hu, Zhiyuan Fan, J. Zico Kolter, Gabriele Farina

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

10{,}000

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 $T$ , for each of the 12 types $T\in\{$ 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 $T$ for each of the 12 types $T\in\{\text{Spy},\dots,\text{Bomb}\}$ , 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.

Table 15

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 $T\in\{\text{Spy},\dots,\text{Marshal}\}$ .
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.

Table 16

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 $T\in\{\text{Spy},\dots,\text{Marshal}\}$ .
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.

Table 17

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 $T\in\{\text{Spy},\dots,\text{Marshal}\}$ .
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.

Table 18

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.

Table 19

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 $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ 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 $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ that has now been captured.

Table 20

Channel(s)	Description
131–140	Whether a piece of the player of type $T\in\{\text{Spy},\dots,\text{Marshal}\}$ died in this square, due to cause of death 1.
141–150	Whether a piece of the player of type $T\in\{\text{Spy},\dots,\text{Marshal}\}$ died in this square, due to cause of death 2.
151–180	Whether a piece of the player of type $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ 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 $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ died in this square, due to cause of death 6.
191–250	Same as channels 131–190, but for the opponent.

Table 21

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 $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ .
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.

Table 22

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 $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ .
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.

Table 23

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 $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ .
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.

Table 24

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 $T\in\{\text{Spy},\dots,\text{Marshal},\text{Bomb}\}$ .
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.

Table 25

Channel(s)	Description
303–354	Same as channels 251–302, but for the opponent.

Table 26

Channel(s)	Description
355–454	Starting location of each piece on the board, one-hot encoded. Specifically, channel $355+k$ encodes in position $(i,j)\in\{1,\dots,10\}^{2}$ whether the piece currently occupying square $(i,j)$ started from square $k$ , according to a row-major ordering of the squares.

Table 27

Hyperparameter	Value
Number of consecutive battleless moves after which a draw is declared	$100$
Number of moves after which a draw is declared	$4{,}000$

Table S2: Game rules training hyperparameters.

Hyperparameter	Value
Number of parallel environments	$1{,}536$ per GPU
Generated setups per player	$1{,}000$ per GPU
Number of moves between training iterations	$202$

Table S3: Data collection hyperparameters.

Symbol	Meaning
$\bar{\sigma}$	Setup for which a game was completed.
$\sigma$	A prefix of $\bar{\sigma}$ .
$\theta_{t}$	Parameters that generated $\bar{\sigma}$ .
$\theta$	Current parameters.
$\pi_{\theta_{t}}(\bar{\sigma}\mid\sigma)$	Probability of $\bar{\sigma}$ given $\sigma$ under $\theta_{t}$ .
$h_{\theta_{t}}(\sigma)$	Predicted conditional entropy of setup prefix $\sigma$ under $\theta_{t}$ .

Table S4: Setup learning notation.

Hyperparameter	Value
Adam learning rate	$5\times 10^{-5}$
Batch size	$1{,}024$ per GPU
Number of epochs per training iteration	$5$
Importance ratio clipping parameter	$0.2$
Conditional entropy prediction loss coefficient	$1$
Reverse KL to data collection policy loss coefficient	$0.1$

Table S5: Setup learning hyperparameters.

Symbol	Meaning
$x$	A position of the acting player, represented as described in Section S2 .
$\{x^{\prime}\}$	The sequence of positions subsequent to $x$ for the same player.
$\theta_{t}$	The parameters that played the move at position $x$ .
$\theta$	The current parameters.
$v_{\theta_{t}}(x)$	Predicted win, loss, draw probabilities at $x$ under $\theta_{t}$ .
$v_{\theta}(x)$	Predicted win, loss, draw probabilities at $x$ under $\theta$ .

Table S6: Move learning notation.

Hyperparameter	Value
Importance ratio clipping parameter	$0.2$
Advantage filtering quantile threshold	$0.75$
Advantage filtering magnitude threshold	$0.01$
Exponential moving average smoothing factor	$0.999$
Advantage estimation $\lambda$	$0.5$
Outcome estimation $\lambda$	$0.8$

Table S7: Move learning hyperparameters.

Hyperparameter	Value
Adam learning rate	$5\times 10^{-5}$
Maximum gradient norm	$0.5$
Batch size	game length $/2$
Data type	bfloat16
Exponential moving average smoothing factor	$0.99$
Number of environments	$1{,}024$

Table S8: Belief learning hyperparameters.

Hyperparameter	Value
Depth	4
Embedding dimension	512
Number of heads	8
Learned positional embedding initialization standard deviation	$0.1$
Feedforward dimension	$2{,}048$
Total parameters	$12.6$ million

Table S9: Setup network information.

Hyperparameter	Value
Depth	$8$
Embedding dimension	$384$
Number of heads	$8$
Learned positional embedding initialization standard deviation	$0.1$
Feedforward dimension	$1{,}536$
Total parameters	$14.7$ million

Table S10: Move network information.

Hyperparameter	Value
Encoder depth	$6$
Number of decoder blocks	$4$
Number of heads	$8$
Embedding dimension	$512$
Dropout	$0.2$
Learned positional embedding initialization	Kaiming uniform [ 58 ]

Table S11: Belief network information.

Hyperparameter	Value
Reverse KL to magnet policy loss coefficient	$0.002$
Reverse KL to policy network loss coefficient	$0.02$
Number of rollouts	$1{,}000$
Rollout depth	$40$

Table S12: Search hyperparameters.

Panel of Figure 39 — Figure S1: Loss values for setup learning over the training run.

Panel of Figure 40 — 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 $\alpha$ .

Panel of Figure 41 — Figure S3: Loss values for move learning over the training run.

Panel of Figure 42 — 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 $\alpha$ .

Panel of Figure 43 — 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

2{,}000

). Raw checkpoint pairs were evaluated over

2{,}000

games. The

32{,}000

-iteration row and column average two evaluation blocks and therefore aggregate

4{,}000

games per off-diagonal entry; all other off-diagonal entries use

2{,}000

games. Each entry shows the average score of the row checkpoint against the column checkpoint, with wins scored as

+1

, draws as

0

, and losses as

-1

Hyperparameter	Value
Number of consecutive battleless moves after which a draw is declared	$100$
Number of moves after which a draw is declared	$2{,}000$

Table S13: Barrage Stratego game rules training hyperparameters.

Hyperparameter	Value
Number of parallel environments	$1{,}024$ per GPU
Generated setups per player	$1{,}000$ per GPU
Number of moves between training iterations	$202$

Table S14: Barrage Stratego data collection hyperparameters.

Hyperparameter	Value
Adam learning rate	$5\times 10^{-5}$
Batch size	$1{,}024$ per GPU
Number of epochs per training iteration	$2$
Importance ratio clipping parameter	$0.2$
Conditional entropy prediction loss coefficient	$1$
Reverse KL to data collection policy loss coefficient	$0.1$

Table S15: Barrage Stratego setup learning hyperparameters.

Hyperparameter	Value
Importance ratio clipping parameter	$0.2$
Advantage filtering quantile threshold	$0.5$
Advantage filtering magnitude threshold	$0.01$
Exponential moving average smoothing factor	$0.999$
Advantage estimation $\lambda$	$0.0$
Outcome estimation $\lambda$	$0.0$

Table S16: Barrage Stratego move learning hyperparameters.

Hyperparameter	Value
Adam learning rate	$2\times 10^{-5}$
Maximum gradient norm	$0.5$
Exponential moving average smoothing factor	$0.99$
Number of environments	$1{,}024$

Table S17: Barrage Stratego belief learning hyperparameters.

Hyperparameter	Value
Depth	$4$
Embedding dimension	$512$
Number of heads	$8$
Learned positional embedding initialization standard deviation	$0.1$
Feedforward dimension	$2{,}048$
Total parameters	$12.6$ million

Table S18: Barrage Stratego setup network information.

Hyperparameter	Value
Depth	$7$
Embedding dimension	$288$
Number of heads	$8$
Learned positional embedding initialization standard deviation	$0.1$
Feedforward dimension	$864$
Total parameters	$6.1$ million

Table S19: Barrage Stratego move network information.

Hyperparameter	Value
Encoder depth	$6$
Decoder depth	$6$
Number of heads	$8$
Embedding dimension	$512$
Feedforward dimension	$2{,}048$
Dropout	$0.1$

Table S20: Barrage Stratego belief network information.

Hyperparameter	Value
Number of rollouts	$1{,}024$
Rollout depth	$10$
Update step size	$10$
Magnet policy regularization (step size $\times$ temperature)	$0.01$
Minimum samples per legal action	$10$

Table S21: Barrage Stratego search hyperparameters.

Hyperparameter	Value
Importance ratio clipping parameter	$0.2$
Exponential moving average smoothing factor	$0.9999$
Advantage estimation $\lambda$	$0.83$
Discount factor $\gamma$	$0.999$
Adam learning rate	$\displaystyle 3.5\times 10^{-4}\!\left(1-\left(\frac{t}{T}\right)^{\!0.4}\right)$
Entropy coefficient	$\displaystyle 0.035\!\left(1.05-0.2\left(\frac{t}{T}\right)^{\!2}\right)$

Table S22: Hanabi actor learning hyperparameters (shared across 2–5 players).

Hyperparameter	Value
Adam learning rate	$1\times 10^{-4}$
Batch size	$128$
Number of training steps	$10^{6}$
Number of parallel environments	$4{,}800$

Table S23: Hanabi belief learning hyperparameters.

Hyperparameter	Value
Private net	$3$ -layer MLP (hidden dim $512$ , ReLU)
Public net	$1$ -layer MLP (hidden dim $512$ , ReLU)
Public LSTM	$2$ -layer LSTM (hidden dim $512$ )
Policy head	Linear ( $512\to\|\mathcal{A}\|$ )
Value head	Linear ( $512\to 1$ )
Total parameters	$5.9$ million

Table S24: Hanabi actor network architecture.

Hyperparameter	Value
Observation encoder	$2$ -layer MLP (hidden dim $512$ , ReLU)
Sequence	$2$ -layer LSTM (hidden dim $512$ )
Autoregressive card prediction – Embedding	Linear ( $25\to 64$ , no bias)
Autoregressive card prediction – LSTM	$1$ -layer LSTM (input dim $576$ , hidden dim $512$ )
Autoregressive card prediction – Output	Linear ( $512\to 25$ )
Total parameters	$7.05$ – $7.37$ million

Table S25: Hanabi belief network architecture.

Hyperparameter	Value
Number of rollouts	$10{,}000$
Update step size	$30$
Rollout temperature	$0$

Table S26: Hanabi search hyperparameters.

Hyperparameter	Value
Importance ratio clipping parameter	$\displaystyle 0.02\cdot\min\left\{\frac{5000}{\text{Training iteration number}},1\right\}$
Exponential moving average smoothing factor	$0.999$
Advantage estimation $\lambda$	$0.95$
Outcome estimation $\lambda$	$0.95$
Reverse KL to data collection policy loss coefficient	$0$
Muon learning rate	$\displaystyle 4\times 10^{-4}\cdot\min\left\{\frac{5000}{\text{Training iteration number}},1\right\}$

Table S27: Dou Dizhu actor learning hyperparameters.

Hyperparameter	Value
Muon [ 60 ] learning rate	$4\times 10^{-4}$
WSD scheduler stable ratio	$0.9$
Maximum gradient norm	$1.0$
Time steps collected per iteration	$2{,}048$

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	$4$
Embedding dimension	$128$
Number of heads	$4$
Feedforward depth	$3$
Feedforward dimension	$256$
Total parameters	$1.9$ million

Table S29: Dou dizhu actor network information.

Hyperparameter	Value
Transformer depth	$4$
Embedding dimension	$256$
Number of heads	$4$
Feedforward depth	$2$
Feedforward dimension	$256$
Total parameters	$3.3$ million

Table S30: Dou Dizhu belief network information.

Hyperparameter	Value
Number of rollouts	$200$
Update step size	$5$
Rollout temperature	$0$

Table S31: Dou dizhu search hyperparameters.

No. of players	No. of search players	Score	Perfect
2	0	$24.454\pm 0.008$	$69.58\%\pm 0.33\%$
	1	$24.614\pm 0.008$	$75.72\%\pm 0.43\%$
	2	$24.654\pm 0.007$	$77.53\%\pm 0.42\%$
3	0	$24.612\pm 0.008$	$77.61\%\pm 0.29\%$
	1	$24.780\pm 0.006$	$84.77\%\pm 0.36\%$
	2	$24.837\pm 0.005$	$87.81\%\pm 0.33\%$

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

\pm

standard errors over

10{,}000

games per condition.

Row vs Col	Ataraxos	Policy Network	PerfectDou	DouZero
Ataraxos	—	$0.107\pm 0.012$	$0.199\pm 0.015$	$0.350\pm 0.016$
Policy Network	$-0.107\pm 0.012$	—	$0.152\pm 0.004$	$0.286\pm 0.004$
PerfectDou	$-0.199\pm 0.015$	$-0.152\pm 0.004$	—	$0.142\pm 0.004$
DouZero	$-0.350\pm 0.016$	$-0.286\pm 0.004$	$-0.142\pm 0.004$	—

Table S33: Dou dizhu role-averaged performance. Entries report means

\pm

standard errors. Comparisons involving Ataraxos use

10{,}000

duplicated deals; other comparisons use

100{,}000

duplicated deals.

P \ L	Ataraxos	Policy Network	PerfectDou	DouZero
Ataraxos	$0.696\pm 0.035$	$0.827\pm 0.035$	$0.855\pm 0.034$	$1.003\pm 0.034$
Policy Network	$0.612\pm 0.035$	$0.707\pm 0.011$	$0.811\pm 0.011$	$0.877\pm 0.011$
PerfectDou	$0.456\pm 0.036$	$0.507\pm 0.011$	$0.601\pm 0.011$	$0.656\pm 0.011$
DouZero	$0.301\pm 0.037$	$0.304\pm 0.011$	$0.373\pm 0.011$	$0.453\pm 0.011$

Table S34: Performance broken down by game role. The row agent is the peasants; the column agent is the landlord. Entries report means

\pm

standard errors. Comparisons involving Ataraxos use

10{,}000

duplicated deals; other comparisons use

100{,}000

duplicated deals.

Figure S8: Role-averaged score of Ataraxos against PerfectDou under varying search update step sizes. Each setting was evaluated over

2{,}500

duplicated deals. The dashed line shows the performance of the policy network (i.e., Ataraxos without search).

Explore similar work

Jun 22, 2026cs.LG

Superhuman AI for Generals.io Using Self-Play Reinforcement Learning

We present a superhuman AI agent for Generals.io, a real-time strategy game that requires both long-horizon planning and short-term tactics under strong imperfect information. Trained for four days on 4x NVIDIA H200 GPUs, our agent reaches #1 on the public 1v1 leaderboard of over 5,000 human players, leading the second-ranked player by the same margin that separates second place from 25th, and beats the two top-ranked humans head-to-head with a combined 199-70 record across 269 ladder matches. A key enabler is a JAX-native simulator that reaches tens of millions of frames per second on a single GPU, roughly a 10,000x speedup over the prior simulator. On top of this, we train a vision transformer policy end-to-end by self-play with a policy-gradient loop and sparse win/loss reward, using top-advantage sample filtering and an exponential moving average of the policy parameters. Taken together, our findings highlight what matters, and what does not, once a fast simulator removes the data bottleneck.

Matej Straka, Viliam Lisý, Martin Schmid

Department of Applied Mathematics, Charles University, Prague, Czech Republic · Department of Computer Science, Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic · Charles University +1

Self-Play Simulation-Based Reinforcement Learning Policy Gradient

Ask PDF

Sep 28, 2026cs.AI

SAGE: Structured Strategic Reasoning for Efficient LLM Game Playing

A strong LLM strategic agent should reason prospectively over uncertain futures, adapt its strategy to opponents' behavioral tendencies, and continuously recalibrate its decision process from interaction experience. However, incorporating these sources in free-form reasoning could lead to unsupported strategic assumptions, inconsistent opponent estimates, and harmful interference from irrelevant historical interactions. To address these issues, we propose SAGE, a training-free inference-time framework that structures LLM strategic reasoning around three coordinated operations: anchor, adapt, and recalibrate. SAGE first anchors reasoning to an equilibrium policy that provides a strategically valid prior. It then conditions deviations from this anchor on a soft belief over opponent behavioral tendencies, enabling opponent-specific exploitation. Finally, SAGE distills strategically related interactions into counterfactual hypotheses about previously missing considerations, allowing past experience to recalibrate the model's reasoning. We evaluate SAGE on three repeated imperfect-information games: Leduc Hold'em, Liar's Dice, and Goofspiel, against various opponent types in each game. Compared with reasoning-intensive LLM agents, including Suspicion-Agent, ReTA, Agent-Pro, EMO, and Hypothetical Minds, SAGE achieves up to a 127.6% payoff improvement in Liar's Dice while reducing input and output token usage by up to 80% and 90%, respectively. In direct match-up play, it attains non-negative mean payoff against 5/10, 8/10, and 8/10 evaluated opponents in Leduc Hold'em, Liar's Dice, and Goofspiel, respectively, while using relatively fewer tokens. Code is available at https://github.com/chenzhwsysu57/SAGE.

Zhiwei Chen, Tianchun Wang, Zhongtao Rao +3

The Hong Kong University of Science and Technology (Guangzhou) · Johns Hopkins University · Microsoft +2

Strategic Reasoning Large Language Model Agents Exploitation

Ask PDF

Apr 19, 2026cs.GT

Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games

In 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.

Quentin Cohen-Solal

LAMSADE, Universit´e Paris-Dauphine, PSL, CNRS, Paris, France

Imperfect-Information Games Minimax Search Algorithms Improvement

Ask PDF