Case Study · Game AI · Search
Durak, Searched
The idea
Durak (дурак, “fool”) is what a deck of cards is for in a Russian-speaking household. Thirty-six cards, a trump suit, and a premise unlike almost any Western card game: nobody wins durak. Play continues until all but one player has shed their cards, and that last player simply loses: they are the fool. The asymmetry runs deeper than the name. Every bout has an attacker, who leads cards, and a defender, who must beat each one in suit or with trump; a defender who can’t (or decides it’s not worth the trumps) picks up the whole table, and everyone watches those cards go into their hand, face-up.
That last detail is why durak makes an interesting AI problem rather than just a nostalgic one. It is a game of imperfect information (you can’t see your opponent’s hand or the order of the stock), so the textbook game-tree machinery (minimax, vanilla Monte Carlo tree search) doesn’t apply: there is no single tree to search, because there is no single state. But the information isn’t uniformly hidden, either. The trump indicator sits face-up under the stock. Every discarded card crossed the table in the open. And every card a defender picks up is public knowledge until they play it. Good durak players track all of this without thinking of it as card counting; an agent that didn’t would be playing a different, worse game.
The plate below is the playable thing: deal yourself a hand and play the searcher, which runs 500 determinizations per move as you go. The full table, with the perevodnoy (transfer) variant, a 52-card deck option (the classic Russian game drops the 2s through 5s for a 36-card deck; keep them in for a longer, more crowded game), a card-counting toggle, and the Russian vocabulary of the game, lives at /durak; the rules themselves, diagrammed position by position, are at /durak/how-to-play. Then read on for how it decides.
ISMCTS · 500 determinizations a move
waiting for your lead
Even on cards, and in no hurry.
6 cards in hand
· the table is clear ·
the bot is waiting
Your lead; play any card.
The approach
The agent is single-observer ISMCTS: Information Set Monte Carlo Tree Search (Cowling, Powley & Whitehouse, 2012). The trick is to make the uncertainty part of the sampling: each search iteration deals a determinization (a random completion of the hidden cards consistent with everything the searcher has legitimately observed) and runs one tree-search pass on that completed, perfect-information game. All iterations share a single tree indexed by the searcher’s information set, with UCB statistics corrected by availability counts, so an action is judged only against the determinizations in which it was actually legal. A thousand determinizations later, lines that only work when the hidden cards fall one lucky way stop looking clever.
“Legitimately observed” is where the engine earns its keep. The game state
tracks a known set per player (cards picked up face-up and not yet
replayed), and the determinizer pins those in the opponent’s sampled hand
instead of shuffling them into the unknown. The playable plate above follows
the same rule: the bot always counts the cards you picked up face-up, because it
watched them cross the table. What the card-counting toggle changes is only
whether the UI does the same remembering for you; leave it off and you count
the bot’s pickups yourself, the way you would at a real table.
The engine itself is a small, strictly-typed state machine (legal-move generation, the bout lifecycle with throw-ins capped at min(6, defender’s hand), take-versus-beat resolution, refill order, the endgame), with a test suite covering the rule edge cases that card-game engines usually rot on (simultaneous exits are a draw; a defender’s last-card parry closes the bout itself; thrown-in cards land in the taker’s hand and in public knowledge). Baselines are a uniform-random player and a greedy one that spends cheap cards and hoards trumps, a fair sketch of how most people actually play. In a seat-alternating round-robin (400 games per pairing, fixed seed), ISMCTS at 800 iterations per move beats the random player in 399 games of 400 and the greedy baseline in about three of every four decisive games (291–88, with 21 draws): a clear edge, with room above it that the rest of this page is about.
What the searcher is allowed to know
An information set is the collection of world states you cannot tell apart. Sitting where the searcher sits in the position below, you can name twenty-three of the thirty-six cards: your own hand, the sixteen in the bita, whatever is on the table, and the trump card lying face up under the stock. The other thirteen are the information set. Six of them are in your opponent’s hand and seven are in the stock, and every way of splitting thirteen cards into a six and a seven is a different world that looks identical from the chair. There are 1,716 of them at that moment. Right after the deal, with twenty-nine cards unaccounted for, there are 475,020, and there is no useful sense in which the searcher is “in” any one of them.
That is why minimax and ordinary Monte Carlo tree search do not apply: both want a single state at the root and there isn’t one. ISMCTS answers by declining to choose. Each iteration samples a determinization, one complete world drawn from the information set, and searches that world for a single playout; the statistics accumulate in one tree indexed by what the searcher can actually observe, so a line that only pays off in one lucky arrangement gets outvoted by the arrangements where it doesn’t. The sampler therefore needs a distribution over the information set, and the shipped determinizer uses the simplest one available: it collects everything it has legitimately seen, shuffles the rest uniformly, and deals the opponent as many cards as the opponent is holding. That is the flat prior and nothing more. It counts, and it does not infer.
The plate below is what the next layer up looks like. The baseline is already worth stating precisely: conditioned on the counts, every unseen card is in your hand with probability h/(h+t) where h is your hidden card count and t is the stock’s, which is the hypergeometric answer and is where card counting stops. Evidence goes on top of it as likelihood ratios. A defender who takes rather than covering a jack of spades would, if they held the queen of the same suit, have been making a plainly bad play, so that card’s ratio is 0.1; if they held a trump instead, declining to spend it on a lone jack is ordinary good play, so the ratio is 0.45 and the card barely moves. The ratios multiply into a weight per card, and the posterior is the weighted distribution over subsets of the unseen pool of exactly the right size, a conditional Bernoulli whose marginals come out of an elementary-symmetric-polynomial recursion rather than out of sampling. The plate prints the sum of those marginals, which has to equal your hidden card count exactly, at every step.
Two caveats, and they are the interesting part. The first is that none of this is a dump of the bot’s internals. The shipped agent computes no probability at all; it counts what it saw, deals the rest uniformly, and lets the tree statistics do the work. The overlay is a clean Bayesian model of the same information, built to show what the searcher is entitled to believe rather than what it does believe, and to make the gap visible. The second is that every inference here is about a rational opponent, not a logical one. A defender who could have beaten a card and did not is playing badly, not impossibly, so no likelihood ratio in the figure is ever zero. Probabilities of exactly zero belong only to cards that are face up somewhere, and those are deductions. The distinction between “certainly not” and “probably not” is the whole difference between counting and inferring, and the figure keeps the two apart on purpose.
Step 1 of 7
It leads the jack of spades. You take.
The first real evidence, and it is evidence about what you do not hold. The queen and ace of spades would have covered the jack cheaply, so taking while holding either is close to a blunder and both fall hard. Any diamond would also have covered it, but spending a trump on a lone jack is exactly what a good player refuses to do, so the diamonds barely move: the ratio pushes them down, the rest of the pool rising pushes them back up, and the two nearly cancel. Everything that could not have covered the jack climbs, because six cards still have to come from somewhere.
Searcher J♥K♠8♥9♦A♣
Table J♠ ?
You
koloda 8 · kozyr ♦ (6♦) · bita 16 · attacking searcher
| Suit | 6 | 7 | 8 | 9 | 10 | J | Q | K | A |
|---|---|---|---|---|---|---|---|---|---|
| ♠ | 6♠ 0% bita | 7♠ 0% bita | 8♠ 0% bita | 9♠ 0% bita | 10♠ 0% bita | J♠ 0% table | Q♠ 12% | K♠ 0% bot | A♠ 12% |
| ♥ | 6♥ 0% bita | 7♥ 0% bita | 8♥ 0% bot | 9♥ 0% bita | 10♥ 62% | J♥ 0% bot | Q♥ 0% bita | K♥ 62% | A♥ 62% |
| ♦ | 6♦ 0% kozyr | 7♦ 0% bita | 8♦ 0% bita | 9♦ 0% bot | 10♦ 41% | J♦ 41% | Q♦ 41% | K♦ 41% | A♦ 41% |
| ♣ | 6♣ 0% bita | 7♣ 0% bita | 8♣ 0% bita | 9♣ 0% bita | 10♣ 0% bita | J♣ 62% | Q♣ 62% | K♣ 62% | A♣ 0% bot |
Largest moves · Q♠ 46% → 12% · A♠ 46% → 12% · 10♥ 46% → 62%
The counting, checked
- Unseen cards
- 13
- In your hand
- 6 hidden + 0 up
- In the stock
- 7 hidden + 1 up
- Sum of the grid
- 6.000000
The marginals have to add up to your hidden card count, exactly, at every step. That identity is what makes this a distribution rather than thirty-six independent guesses.
Trumps in your hand
Expected trumps in your hand: 2.03. This is the sort of number a determinized search gets by counting samples. The pool is small enough to integrate exactly instead, so these are the true figures for the model, not estimates of them.
The evidence, and what each piece is worth
Declined to beat
A defender who takes is saying they cannot, or will not, cover J♠. Holding a higher card of the same suit and taking anyway is close to a blunder, so those cards fall hard. Refusing to spend a trump on a cheap attack is ordinary good play, so trumps barely move.
Q♠ ×0.1 A♠ ×0.1 10♦ ×0.45 J♦ ×0.45 Q♦ ×0.45 K♦ ×0.45 A♦ ×0.45
Every ratio is strictly greater than zero, on purpose. A defender who could have beaten a card and did not is playing badly, not impossibly, so none of these is a proof. The only zeros in the grid belong to cards that are face up somewhere, and those are deductions.
The hands, face up
- You were holding
- 10♥ 10♦ A♥ J♣ Q♣ J♦
- The stock held
- Q♠ A♠ K♥ Q♦ K♦ A♦ K♣
- Brier score, this belief
- 0.198
- Brier score, flat prior
- 0.249
Wiring this into the agent is a smaller change than it looks: determinize() would sample the
opponent’s hand from the weights instead of from a uniform shuffle, which is weighted sampling
without replacement and a few lines. The hard part is not the machinery, it is earning the numbers.
Every ratio in the figure is a claim about how a decent club player behaves, and I picked them by
argument rather than by measurement; they belong in a file where they can be fitted against real
game records or self-play logs, and until they are, a confidently wrong prior is worse than a flat
one, because determinized search will happily build long plans on top of it. The last step of the
plate makes that concrete at the smallest possible scale: under perevodnoy the model double-counts a
single decision as two pieces of evidence, and the card it is most wrong about is the one card the
opponent was actually holding.
Where the code lives
The project is splitting along the line it always had. The interface (the plate above, the full table at /durak, the card animations, the variant toggles) lives in the site’s repo and keeps growing there; its engine is the small TypeScript state machine, vendored as browser scaffolding and now carrying UI-facing rules such as the perevodnoy transfer. The computer science (the searcher, the evaluation harness, and whatever eventually replaces the hand-written rollouts) is being rewritten from scratch in Python, in its own repo, by my own hand: partly because search code you rewrote is search code you understand, partly so the ideas below have somewhere serious to land. The TypeScript agent stays vendored here until the Python one exists to be measured against it.
The learner, sketched
The rollouts are where the next gain is, and the plan has a name in my notes: the learner. Right now every ISMCTS playout finishes the game with the same hand-written greedy policy (spend cheap cards, hoard trumps), a fair sketch of a club player but a fixed one: the search can only be as sharp as the games it imagines, and it imagines them with a heuristic that never gets better. The learner replaces that fixed rollout with a small trained policy, so the quality of the imagined games rises with training instead of staying frozen at whatever I typed by hand.
The shape borrows from AlphaZero, adapted for hidden cards. A compact network
reads the observable state (your hand, the trump, the stock size, the discard
pile, and the known set the engine already tracks) and returns two things: a
prior over legal moves, which steers selection toward promising actions
(swapping UCB for a PUCT rule), and a scalar value estimate, which lets a
playout stop early instead of playing every bout to the end. Training is a
self-play loop: the current searcher plays itself, each move is labeled with the
visit distribution the search settled on and the eventual win or loss, and the
network is nudged toward that policy and that outcome. Next generation, the
sharper network makes the next round of self-play sharper still. Nothing here
needs a human transcript; the only supervision is who ended up the fool.
Two cautions keep this a sketch rather than a promise. First, naive self-play in an imperfect-information game can chase its own tail: a policy tuned only against copies of itself learns to beat itself, not to play soundly, and durak’s hidden cards make that trap real. The principled alternative is counterfactual regret minimization (CFR, and its neural cousin Deep CFR), which converges toward equilibrium rather than toward a fixed opponent; which framing actually fits durak’s cheap-determinization structure is an open question I would rather measure than guess. Second, even a trained rollout still models none of the opponent’s reasoning, the gap the last section names; a self-play agent begins to price in what a play reveals (a defender who takes rather than trumps is confessing a thin hand), but only a searcher that reasons about its own observability closes that door. The learner is the next rung of the Python rewrite, and it is written down here precisely so it has somewhere serious to land.
Known limits, and the next rungs
Determinized search has two documented failure modes, strategy fusion (within any one determinization the search “knows” the hidden cards, so it can overvalue lines whose payoff depends on information it won’t actually have) and non-locality, and single-observer ISMCTS softens the first without eliminating either. The agent also models none of the opponent’s reasoning about its hand: it counts your cards but doesn’t ask what your plays reveal. Both gaps have the same shape as the etymology project’s lesson (the machinery is only as trustworthy as its epistemics), and both are why the results table says “beats the club baseline,” not “solved.” The obvious next rungs, a proper evaluation against multiple-observer ISMCTS and self-play-tuned playout policies in place of the hand-written greedy rollouts, both belong to the Python rewrite.
One smaller feature of the plate has the same epistemic flavor. It has a Go back control, because misclicking a card into the wrong slot and having no way out was the loudest complaint. The interesting part was holding undo to the same rules as the bot: it reverts only your own moves within the current turn, and the moment the searcher has replied, or a bout has closed and both hands have refilled from the stock, the history is cleared. Reaching back across any of those would let you re-roll the bot’s answer, peek at a card it just revealed before taking your move back, or read the order of the hidden stock, none of which a player at a real table could do. So the button quietly disables itself rather than pretend the unwind is free, which felt like the right shape for a project whose whole point is being careful about what a player is actually allowed to know.