Dark Hex

Repository with strategies, proofs, and code

Standard Dark Hex is solved on 3×4 and 4×4 boards. With optimal play, Red wins about 21.16% and 79.34% of the time, respectively.

The exact probabilities are 14279 / 67484 for 3×4 and 5345119702052171 / 6736824633547900 for 4×4. The result comes with optimal randomized strategies for both players. Exact best-response checks against those strategies establish matching lower and upper bounds. For 3×4, the previous published bound was 1/7 to 1/4.

The game

Board sizes are given as columns × rows. Red connects top to bottom; Blue connects left to right. Players see their own stones and remember their own probes, but cannot see the opponent's stones. If a probe hits an occupied cell, it fails privately and the player tries again. A successful placement ends the turn. Red's first move is hidden from Blue.

The strategies

The published strategies give probabilities for the next probe at each private history. Explore either player's 4×4 strategy from the GitHub certificates. An optimal strategy guarantees the game's value, but may make weaker moves in histories that do not affect that guarantee.

The explorer shows the published 4×4 pair. The certificates share identical continuations to keep the strategies compact. Those optimal strategies are not unique: in realization weights, the known optimal sets have affine dimension at least 7 for Red and 15 for Blue. Blue's first-probe probabilities can vary among optimal strategies.

Public openings

In this variant, Red's first stone is announced before Blue moves. Every opening is solved. The boards show Red's win probability (%) for each announced opening, assuming optimal play afterward.

On 3×4, b2 and b3 are the best announced openings. Red's win probability falls from 21.16% to 14.29%, a drop of 6.87 percentage points.

On 4×4, d1 and a4 are best. Red's win probability falls from 79.34% to 74.02%, a drop of 5.32 percentage points.