Concepts

Determinization and expectimax

The simplest way to search under hidden information is to remove it. Sample a complete arrangement of the opponent's hidden pieces that agrees with everything public (the revealed types, the counts of lost pieces, and which hidden pieces have moved and therefore cannot be Bombs or the Flag), search that perfect-information game to a fixed depth, and average the resulting values over many samples. Each sample is a determinization; the average over samples is where the "expecti" in expectimax comes from.

What the engine provides

The observation carries the public two-square and chase trackers, so a determinized state obeys exactly the same rules as the real game: a sampled world cannot make a move the arbiter would refuse. The sampler draws moved pieces from the movable unknown types and unmoved pieces from the rest, uniformly, in a few hundred nanoseconds per world. The expectimax player then runs an alpha-beta search inside each world with a hand-written leaf that adds material (a Marshal is worth twelve Scouts, a Miner two and a half because only Miners defuse Bombs), advancement, Flag safety and mobility.

Strategy fusion

Determinization has a known flaw, named strategy fusion by Cowling, Powley and Whitehouse: the searcher assumes it will know which world it is in when it chooses its next move, so it happily plans a different second move for each world. In the real game one move has to serve every world. The effect is that determinized search overvalues moves whose payoff depends on information it does not have, such as an attack on a hidden piece that is a Bomb in half the worlds and a Sergeant in the other half: in the worlds where it is a Sergeant the search "knows" to attack, in the others it "knows" to walk past. Averaging hides that no single policy achieves both.

The rung after this one, n-tuple evaluation, does not fix strategy fusion; it replaces the hand-written leaf. The fix comes with learned stochastic policies: a policy trained on the information state cannot condition on what it does not observe.

Cost

Sixteen worlds times an alpha-beta search to depth two with captures extended is a few tens of thousands of node evaluations per move. At the engine's 17 ns per move application and a leaf that costs about as much as move generation, that is under a hundred milliseconds on one core, and the arena runs many games at once so a 200-game match finishes in minutes. Depth three multiplies the count by the branching factor, about 28 on average, and is where the two-second budget starts to bind. The search reports its node count and depth reached per move so the sweep can plot strength against cost honestly.

The registered comparison

The expectimax rung is promoted if depth-2 search over 16 sampled worlds beats the greedy baseline on 200 paired games under the training rules, with the per-seed contrast's 95% interval above zero and a mean of at most two seconds per move. The registration is expectimax against greedy; the result is not in yet.