Stratego is chess with the identities hidden. Each player arranges forty
pieces in secret, so before the first move the opponent's army can be any
of more than arrangements, and the game tree has about
states (Perolat et al., 2022). Poker, the other classical imperfect-information
benchmark, hides a two-card hand: 1,326 possibilities, few enough to
enumerate. The methods that solved poker by transforming the game into its
public tree scale with the amount of hidden information, so they never
reached Stratego. That is why the game stayed a human stronghold after
chess, Go and poker had fallen, and why DeepMind's DeepNash reached the top
three on an online platform but not the level of top human players.
A hidden opponent row could be any arrangement of the remaining types, and each battle collapses part of that uncertainty.
Value depends on frequencies
In a perfect-information game the right move is the one leading to the
position of highest value. Under hidden information the value of a move
depends on how often you would have made it in other situations, because
the opponent's beliefs, and therefore their replies, are shaped by those
frequencies. A Marshal that always charges a hidden piece gets baited onto
a Bomb. A Marshal that never does gets ignored. The right frequency is a
property of the whole strategy, not of the position.
The Ataraxos paper draws these dependencies as a graph: nodes are decisions,
and an edge says whether making one decision more often raises or lowers
the value of another. Even among decisions made at the same moment the
graph is dense, and the dependencies also run across time, since earlier
decisions determine the posterior over hidden pieces at later ones.
Changing how often one decision is made raises the value of some decisions and lowers the value of others.
What this rules out
Search that simply maximises value at each node, the recipe behind chess
and Go engines, is not enough, because a pure best response is
predictable and therefore exploitable. Enumerating the hidden information,
the recipe behind poker solvers, is impossible at . What remains is
learning a stochastic strategy directly, and finding a way to make search
respect that strategy's frequencies. DeepNash did the first with
game-theoretic dynamics; Ataraxos did both with regularised self-play and a
search that mimics one more learning step.
The size of the hidden information
Forty pieces of twelve types give
distinct arrangements, about , before a single move. Each battle
reveals two types and each long Scout move one, and a moved piece rules
out Bomb and Flag, so the posterior narrows through the game; but the
number of configurations consistent with a mid-game observation is still
astronomically beyond enumeration. Every player on the ladder has to
answer the same question with sampling: how many configurations to draw,
from which distribution, and how to act on values averaged across them.
What this program studies
The engine here plays the competitive rules at 84 million random moves per
second across this workstation's 32 threads, which makes it possible to
try each of these ideas at a small scale. The ladder starts with search
over sampled hidden configurations, moves to learned evaluations, and ends
with the two learning rules from the papers compared under the same
compute budget. The question is which ideas carry the strength and which
only carry the cost.