Misty: An Open-Source Fog of War Chess Engine
In short
- Misty is an open-source fog of war chess engine in Python and Rust, under the GPL:
pip install misty-chess, or play it in the browser on Mistboard.- It follows Obscuro (Zhang and Sandholm, ICLR 2026): it keeps every board consistent with what it has seen, samples a fixed number of them, and runs counterfactual regret minimization over the sample.
- Search cost stays flat whether the belief holds four hundred positions or forty million; what grows is how much of it the sample misses, and a faster search is what lets the sample grow.
- Every departure from the paper is listed with its reason and, where measured, its cost, and the open problems are GitHub issues.
Misty is an open-source fog of war chess engine, released under the GPL. pip install misty-chess, or play it in the browser without installing anything.
It implements the architecture of Obscuro (Zhang and Sandholm, ICLR 2026), the first superhuman agent for the game. The paper ships no code, on arXiv or OpenReview. The other open implementation I know of is obscuro-chess, a JavaScript port started in August 2026. Misty is the Python and Rust one, with a documented engine protocol and a public server to play it on. Every place it departs from the paper is listed below, with the reason and, where it has been measured, the cost.
It plays on Mistboard, a site I built for games like this one. When lichess listed the variants it might add in 2015, it put dark chess among “probably some of the lowest in priority. It would be difficult to prevent cheating in them (unless there is a way to have games as fully private) and they utterly lack the element of spectacle. Requires a complex referee-ing system.” Mistboard is that referee. The server holds the real board. Each player, each engine and each spectator receives only what that seat is allowed to see, so there is no hidden state in anyone’s browser to read, and a finished game replays in full for anyone to check.
Three kinds of help would move it most: people who play fog chess playing a set against it, anyone with a fog engine playing theirs against it, and anyone picking up one of the open problems. The end of the post says how.
The problem
In fog of war chess you see only the squares your own pieces could move to. Your opponent’s moves are invisible. You observe their consequences instead: a piece of yours disappears, a square you were watching changes, and you work backwards from there.
Move 9 of a real five-minute game on the site, Misty as Black. All three boards are the same position from White's side. White cannot see 14 of Black's pieces; Black cannot see 15 of White's. Neither player ever sees the middle board.
That removes the assumption every classical engine is built on. Stockfish searches a tree rooted at one position. Under fog there is no one position. There is the set of every board consistent with everything you have observed, and you need a move that holds up across it.
Call that set P. Twice in a game it is small enough to draw.
The two boards consistent with it
g5 is the one square on the rank Black cannot see into.
Five of 236,480
A real middlegame, from the game embedded further down. Four are drawn uniformly from the set; the fifth is the real board.
Black worked out that a piece exists without ever seeing it, from a hole in its own vision. That kind of inference has no counterpart in ordinary chess. The deduction still left two boards standing, and Black has to move against both.
By the middlegame there is nothing left to draw. The engine cannot choose a move for the position it is in, because it does not know which position that is. It chooses one move that will be played in all of them. How big P gets is the whole problem.
Over 216 games against Misty by September 2026, the median decision faced 74 consistent boards and one in ten faced more than 7,000. The largest in a game against a person reached 82 million; in a game of Misty against itself, 346 million distinct boards. The paper puts single information sets in this game as high as 109.
The first decision always faces exactly 20 boards, one per legal opening move. By the twelfth the median is still only 84, while the worst tenth face 19,427 and the worst hundredth peak near 2.5 million. Then contact drains it. Every capture and every piece that walks into vision is information, and by the forty-fifth decision, in the games that last that long, the median is down to 42. That is a property of the game rather than a policy: Misty has no term that rewards gaining information and does not play for contact, which is one of the more interesting things it could learn to do.
Games
Four games: two where Misty reasons about what it cannot see, one where fog confuses both sides, and one loss that shows what the belief’s size costs. Each board has a White, Truth and Black switch above it: pick a side to see only what that side could see.
Misty against itself, at thirty seconds a move. A capture tells Black that White’s queen can only be on one square. Black moves a knight to attack it from a square White cannot see, and takes the queen next move. Stockfish, seeing the whole board, would not play the knight move; under fog it wins. The study has all eleven self-play games.
Misty against an anonymous guest, at ten minutes plus five. After 11…b6 a black knight on a6 is loose, and for five moves Misty leaves it: in most of the positions it thinks possible the square is guarded, usually by a bishop that in fact left c8 on move 2, out of its sight. When a second attacker lines up, it takes with the bishop, risking a bishop rather than its queen. The guest cannot see White’s queen on a3 either, takes back with the queen, and loses it. The guest resigned at move 37.
Another self-play game shows what fog does when neither side can see much. Black castles queenside where White cannot see it, and when a black knight lands on c5, White takes it: it thought the square behind, d8, held Black’s queen, and gave a rook there about one chance in a hundred. The capture opens the d-file onto White’s own queen. From there both queens run loose among pieces neither side can fully see, material swings every few moves, and the game ends when White pins down the one fact it needs. It has never seen Black’s king, but every position it thinks possible puts it on c8, and 27.Re8+ finds it.
And one loss, to a friend, which shows what the belief’s size costs. On move 30 Misty took a rook it thought was probably defended, and a gap in its safety checks let the capture through; the queen it lost for the rook is what became 1.6. Then White, winning easily, moved quietly where Misty could not see. Each unseen move multiplied the positions Misty had to keep: 4 after the capture, 55,000 five moves later, then 1.4 million, 3.6 million and 6.5 million. Its moves took 9, 11, then 16 seconds against a five-second budget. The next update, to 9.5 million positions, ran past the server’s limit for a reply, and the server forfeited Misty with nearly four minutes left on its clock. The study of Misty’s games against people has seven more.
How Misty picks a move
Six steps, following the paper, at the settings that ship in 1.6 (the v1.6-net-prune profile, in misty-chess 0.1.3).
Belief: every consistent board
After the opponent’s invisible move, Misty filters P against what it observed and drops every board the observation rules out. After its own move it advances every board. P is held exactly, every consistent position enumerated in Rust and rebuilt every ply: no particle filter, no approximation. Production caps it at 16 million positions.
Above the cap Misty keeps a uniform random sample and plays on; the worst game on record peaked at 7.7 GB doing it. In the one game that crossed it, from June, the belief grew to 82 million boards while the opponent promoted a pawn out of sight, and the real position fell out of the sample. Misty made its next two decisions against a set that did not contain the board it was on. Then the new queen took its king. Each ply is built from the last one only, so nothing brings the truth back; replaying the observation history with a new sampling seed would (#10). If P ever comes up empty the engine raises instead of repairing it, because an empty set means the observation model is wrong.
The Rust enumerator is about 500 times faster than the Python one. The Python stays as an oracle: the test suite replays real games and requires the two to agree at every ply. That check has caught more bugs than it has cost, and it is the part of the design most worth keeping.
Sample: a fixed number of worlds from P
From P Misty draws a fixed number of root worlds at random: 32 in 1.6, a setting in the profile, where the paper uses a few hundred. Fixing it is why search cost does not grow with the belief: whether P holds four hundred positions or forty million, the search sees the same number of them. Why not raise it is a question about the clock, answered under what a move costs.
Every consistent board gets the same weight, though they are not equally likely. A board where the opponent spent three tempi shuffling a rook fits the evidence and is nearly impossible in fact. Misty has no opponent model to tell them apart. Neither does Obscuro. obscuro-chess does: a move prior fitted on 246 Chess.com games.
Search: one tree, keyed by what Misty has seen
The sampled worlds grow one game tree together. A node in it is an observation history: everything the player to move has seen so far. Worlds that would look identical to Misty land on the same node and share one strategy. That grouping is what information set means, and it is why the search returns one answer.
It rules out the obvious approach, which is to hand each world to Stockfish and count votes. A vote lets you play different moves in positions you cannot tell apart, and at the board you cannot do that. Averaging Stockfish’s scores across worlds fails for a subtler reason: each score assumes that after this move you will know which world you are in.
Take two worlds, equally likely, and two moves. After wait, the next move is a guess between two squares: guess right and you win, wrong and you lose. Safe is a small edge in both worlds.
world 1 world 2 average really
wait, then guess +1 +1 +1 0
safe +0.3 +0.3 +0.3 +0.3
Handed one world at a time, Stockfish always guesses right, because in its world there is nothing to guess, so wait averages to a certain win. At the board Misty cannot tell the worlds apart, guesses right half the time, and wait is worth nothing. The search avoids this by putting worlds that look the same on one node, which forces the same guess in both.
The opponent also gets a say. They choose what you see, so if you always answer a hidden threat the same way, they learn it and steer into the branch you are not covering. Misty looks for the strategy that concedes least to an opponent who knows how it decides. Sometimes that strategy is a coin flip between two moves.
The tool for finding it is counterfactual regret minimization, the family of algorithms that solved poker.
Every node holds a mix: a probability for each move, starting even. One pass over the tree does four things, bottom up:
leaf v = tanh(centipawns / 500)
move v(a) = average of a over the worlds
node v(I) = Σ x(a) · v(a)
regret R(a) ← max(0, R(a) + v(a) − v(I))
next mix x(a) ∝ max(0, R(a) + Δ(a))
Here x is the node’s current mix and Δ(a) the change R(a) just got. The first line puts Stockfish’s score on a scale from −1 to +1: a pawn up is about +0.2, a rook up about +0.75, and taking the king is exactly +1. The second and third are averages. At a node where the opponent moves, its values are weighted by the opponent’s current mix, so a move’s value is what it earns across every world Misty cannot tell apart, against the way the opponent is playing right now.
Regret is the running total of how much better each move did than the mix did. Say a node plays two moves half the time each, and this pass they score +0.12 and +0.08. The node is worth +0.10, so the first move gains 0.02 of regret and the second falls to zero, since regret never goes negative. On the next pass the mix leans on the first move. Meanwhile every opponent node has done the same thing against Misty’s mix, which shifts the values, which shifts the mixes again. The passes stop changing things when no move at any node beats its own mix. That is the equilibrium, and it takes thousands of passes rather than one because both sides are adjusting to each other.
The smallest version fits in a table. You can guard one of two squares, and your opponent attacks one you cannot see. An unguarded attack on a costs you a full point, on b half a point. Run the same update, both sides at once:
| Pass | You guard a | They attack a |
|---|---|---|
| 1 | 100% | 0% |
| 2 | 11% | 87% |
| 3 | 83% | 53% |
| 10 | 72% | 28% |
| 20 | 67% | 33% |
Each side overreacts to the other at first, then it settles: guard a two times in three, and neither side can do better by changing. That settled mix is what the search is looking for.
The last line is the one refinement over plain regret matching. Adding the most recent change is a prediction that the next pass will look like this one. It is what lets Misty play from the current mix at the end rather than an average of every mix it passed through; this family is called predictive CFR+.
Four of the 32 worlds drawn from 12,567. Tinted are the 13 squares these four disagree about, and Black can see none of them, which is why all four are the same position as far as the search is concerned.
One strategy over Black's 30 legal moves. 5 further moves hold less than 0.001 between them.
Because every sampled world presents Black with the same observation history, they share one node in the search tree, and the 20,768 iterations of this five-second move accumulate regret there together. The output is a single distribution. Purification then has to turn it into one move, which here means separating e5 from Qf5 on a gap of 0.0017.
That is one real decision at five seconds, and the coin flip arriving in practice: two moves within 0.002 of each other. Each iteration is one pass over every node, then one new leaf. At 2,000 leaves the tree stops growing and the passes carry on over a fixed tree until the clock runs out, so most of a move’s iterations refine the mix rather than extend the tree. The clock is the only stopping rule; nothing checks that the mix has settled (#8).
Scope: how far out to solve
A fixed depth is the wrong place to stop under fog. What matters is how far a position is from one somebody could confuse it with. Misty joins two nodes when either player cannot tell them apart and expands only leaves within a few such steps, which is where it starts reasoning about what its opponent does not know about it.
Evaluation: Stockfish at the leaves
New leaves are scored by Stockfish 18 at depth one. It runs on one thread with a 16 MB hash, built from source at a pinned commit so every deploy runs the same binary. Before that pin production ran whatever the Linux distribution shipped, which was 14; the two were within noise in the one arm that compared them. Versions have not been swept further, because leaf evaluation is 11% of a move. Stockfish never sees fog. It answers only “how good is this concrete board”, which is the question it answers best, and the fog reasoning stays in the layer above. That has a cost the layer above cannot repair: a pawn tension is neutral to a classical engine and decisive under fog, because whoever captures gains vision. The paper puts the evaluator’s weight at about 262 Elo.
Commit: one move out of a distribution
The search ends holding a probability for each move, and Misty plays the top one. Obscuro can mix between moves safely because it checks candidates against a strategy carried over from the previous move. Misty throws its tree away between moves, so it has nothing to check a mix against, and forcing the mix went 0 wins, 7 losses, 1 draw.
Guards run last, vetoing moves that hang a major piece or walk the king into a capture across enough of the belief. They are not in the paper, and they are not a rare backstop: in the eleven games above they replaced the search’s choice on 17% of moves. They catch the mistakes that make an engine look foolish to a human, and they cause some of their own. In the self-play game above, three of the worst moves on either side were the guards’ choices, not the search’s: they look one move ahead, and a pawn fork takes two. A search that sees those dangers itself, so the guards can go, is the open problem underneath most of the others.
The settings
| Setting | Ships at | Turning it up |
|---|---|---|
| Belief cap | 16,000,000 positions | Exactness held longer, at gigabytes of RAM |
| Root worlds sampled | 32 | More of the belief in view, fewer iterations each |
| Expansion budget | 2,000 leaves per move | A wider tree, and a slower pass over it |
| Scope order | 2 | A larger subgame, more of it re-solved per move |
| Leaf evaluation depth | 1 | Better leaf scores, drastically fewer of them |
| Move budget | 5 seconds | Everything above, proportionally |
Roots, expansions and scope live in the profile v1.6-net-prune; the belief cap and move budget come from the caller; leaf depth is fixed in the evaluator. At order 2, leaves within three confusion steps are eligible to expand, and the band between one and two steps is re-solved during the search.
What a move costs
Every production move records where its time went. Averaged over 913 of them:
| Step | Average | Share |
|---|---|---|
| Equilibrium pass | 3.91 s | 69% |
| Stockfish on new leaves | 0.61 s | 11% |
| Rest of expansion | 0.18 s | 3% |
| Leaf selection | 0.16 s | 3% |
| Scope | 0.06 s | 1% |
| Outside the search: belief update, guards, commit, transport | 0.68 s | 12% |
| Total | 5.68 s |
The equilibrium pass is the per-iteration update of every node in the tree, which is why it dominates. The belief update, the step everyone expects to be expensive, averages 6 milliseconds. The guards run after the search clock stops, which is why a five-second move takes 5.7; on one decision profiled locally, they took 1.2 seconds.
A move is bounded by wall clock: time_budget_seconds, 5 in production, which the game clock can lower. The profile also carries an iteration cap, set at ten million so that time always binds first. Pass no time budget and no clock, and the iteration cap becomes the stopping rule. A 5,000-iteration run chose the same move, built the same tree and gave the same top four probabilities in three separate processes. That is the mode for anything you want to reproduce, because a timed move depends on how fast the machine happened to be.
Cost is also the answer to the obvious question: why sample 32 worlds when the paper uses a few hundred? Every world is walked on every pass, so a pass costs in proportion to the number of worlds. Same position, same clock:
| Root worlds | Iterations in 5s | Tree nodes |
|---|---|---|
| 32, what ships | 45,068 | 6,322 |
| 128 | 10,645 | 25,291 |
| 200 | 5,958 | 43,070 |
| 256, the top of the paper’s range | 4,958 | 52,557 |
Eight times the worlds buys nine times fewer passes. The 2,000-leaf budget is shared across the worlds too, so at 256 each world gets about eight leaves instead of sixty, and the tree is still growing for 40% of the move. At 32, the tree is done early and about 43,000 passes refine the mix on it. More worlds sees more of the belief and solves each one worse. In head-to-head games at a fixed five seconds, 64, 128 and 200 worlds each lost to 32 in every cell but one.
So raising it needs throughput first, and the equilibrium pass is where the throughput is. Bounding it to the scope the expansion already obeys (#6), or splitting it across cores, is where a multiple would come from. Copying the paper’s one-solver, two-expander split is not: it parallelises expansion, which is 14% of the clock. Timed numbers depend on the machine, so the laptop numbers here compare with each other and not with production.
Against the paper
Misty is guided by Obscuro, not a faithful reproduction of it. Row by row against the paper:
| In the paper | Here | Why |
|---|---|---|
| Search tree and equilibrium carried between moves | Discarded and re-sampled every move | Built in 1.1, removed in 1.2; below |
| Reach gifts, per information set | A single scalar margin, set to zero | Not built |
| A blueprint strategy for the safety gadget | Reaches ~38% coverage at small P, ~0 at scale |
A consequence of the first row |
| Resolve and Maxmargin regimes, switched between | Resolve only | The switch exists behind an environment variable and never shipped |
| A root set of a few hundred worlds | 32 | Throughput; see what a move costs |
| CFR with partial pruning, so an iteration usually takes time sublinear in the size of the tree | Every iteration walks the whole tree | Not built; it is why the tree stops at 2,000 leaves (#6) |
| One solver thread and two expanding a shared tree | One thread | Not built, and would parallelise the part of the clock that is already starved |
The first row causes the second and third. The blueprint is the previous move’s search, so with re-sampled roots it covers about 38% of the worlds at small P and none at scale. Without it, Misty’s safety gadget over-defends, so it runs in the opening only.
The carried tree was built in 1.1 and removed in 1.2: in the opening it cost about 125 centipawns on the true board and ran 21% fewer iterations. The middlegame, where P is large and the blueprint would matter, is where it should pay.
What’s next
The work is tracked as issues under the strength label, each with its evidence, a proposed fix and the measurement that would show it worked. In order of what each should buy:
- Throughput (#6). The equilibrium pass walks the whole tree every iteration, though the scope already limits which leaves can grow. Bounding the pass the same way should be worth a multiple, not a percentage, and the world count is waiting on it: the head-to-head that 32 worlds won at today’s speed gets rerun at the new one.
- The carried tree, in the middlegame (#11). Carrying the search between moves cost about 125 centipawns in the opening, where the belief is small. The middlegame is where the paper says it pays, and mixing between moves and a working safety gadget both depend on it.
- A search that does not need the guards. They replace the search’s choice on 17% of moves and cause some of the worst. A two-move danger like the pawn fork has to be seen by the search itself; the test is a match with the guards switched off.
- Fixes with a known shape: spending the time bank (#7), stopping when the mix has settled rather than when the clock runs out (#8), converting won endgames against a bare king (#9), and recovering the real board past the belief cap (#10).
This post describes 1.6, September 2026. The issues are the current state.
Play it, test it, build on it
Play it. Misty is on Mistboard, no account and no install. The bot there runs the same engine and profile the repo ships. Games against people are the scarcest data Misty has, and they show what self-play cannot.
Get in touch. If you play fog chess and want a set against it, work on imperfect-information games, want to use Misty in research or a project, or found something wrong in this post, email contact@brianhliou.com.
Build on it. pip install misty-chess gets you the engine; the README covers the Rust extension and what the pure-Python fallback costs. The engine speaks a JSON protocol over stdio, documented in the repo. A server sends redacted observations only, so a live engine has no path to the truth.
Bring an engine. Misty has almost nothing to measure itself against. A fog of war engine that speaks the protocol can play it on the same server, and the result gets published, whichever way it goes.