Agents and checks by game¶
Every game you can play or audit has several agents: different ways
of choosing a move, with different guarantees. This page lists them all,
generated from the descriptions in each game's module, so it always
matches the code. The same text is available on the command line:
grounded-decision play GAME --list --verbose and
grounded-decision play GAME --explain AGENT.
Each agent declares an information regime (see Seeing the future, assuming the worst, or betting on the odds): worst-case agents assume nothing about the future, so what they prove holds whatever happens, probabilistic agents bet on a model of what happens next and carry confidence statements, and clairvoyant agents are benchmarks that see the future. The gated agent of each game is the grounded pattern: a fast proposal, checks, and a safe fallback.
tictactoe¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | uniformly random open square (baseline) |
rule_of_thumb |
baseline | win, block, centre, corner, side; fast but can be forked (loses as O) |
perfect |
worst-case | the exact solver's best square; never loses |
grounded (gated) |
worst-case | rule of thumb, gated by the solved game; provably never loses |
noisy_rule |
baseline | rule of thumb with random mistakes (an opponent model) |
minimax |
worst-case | exact minimax: assumes the opponent is perfect (worst-case) |
expectimax |
probabilistic | maximises win chance against a random opponent, never risking a loss |
expectimax_rule |
probabilistic | maximises win chance against a noisy rule-of-thumb opponent, never risking a loss |
gambler |
probabilistic | maximises win chance against a random opponent, even at the risk of losing |
clairvoyant |
clairvoyant (benchmark) | knows the opponent's exact policy and exploits it (benchmark only) |
random: Picks uniformly among the open squares. It has no strategy and no guarantee; it is the yardstick the other agents are measured against.
rule_of_thumb: Each move: win if it can, otherwise block an immediate threat, otherwise take the centre, then a corner, then a side. Instant, and right most of the time, but it never looks for forks (moves creating two threats), so a careful opponent beats it when it plays O.
perfect: Looks up every open square in the solved game (all 5,478 positions, solved once in milliseconds) and plays the best: keep a forced win, otherwise keep the draw, preferring squares that win most often against random play. It never loses. Worst-case regime.
grounded: The gated agent. The rule of thumb proposes a square; two checks look it up in the solved game (never_loses, keeps_forced_win); if either fails, the move degrades to the perfect player's square. Provably never loses, while keeping most of the rule of thumb's own moves. Choose it to see the gate catch a blunder.
noisy_rule: The rule of thumb, except that one move in five is a uniformly random open square. It exists as an opponent model for the probabilistic agents and the regime table, not as a player to imitate.
minimax: Exact minimax: assumes the opponent plays perfectly, so it only cares about the guaranteed result (draw from the start). Worst-case regime: it gives up winning chances against weak opponents to be safe against strong ones.
expectimax: Among the squares that never risk a loss, picks the one with the highest chance of winning if the opponent plays uniformly at random (computed exactly). Probabilistic regime: it bets on the opponent's likely behaviour but keeps the never-lose guarantee.
expectimax_rule: Like expectimax, but the opponent model is the noisy rule of thumb instead of uniform random play. Against that opponent it wins far more often than minimax, still never risking a loss.
gambler: Maximises win chance against a random opponent with no never-lose restriction. It wins slightly more against random play but has a forced loss against a careful opponent: the cost of dropping the guarantee.
clairvoyant: Is told the opponent's exact deterministic policy and searches against it, so it exploits every weakness. A benchmark for what perfect knowledge of the opponent is worth, never a real player.
Checks run by the gated agent (grounded):
never_loses: After this square, the mover can still avoid losing whatever the opponent does (exact lookup in the solved game).keeps_forced_win: If the mover could force a win before this square, it still can after it.
snake¶
| Agent | Regime | In one line |
|---|---|---|
greedy |
baseline | shortest path to the apple; dies as the snake grows (baseline) |
greedy_with_tail_check |
baseline | greedy only if the tail stays reachable; never dies here but usually stalls |
manhattan |
baseline | steps straight towards the apple (O(1) baseline for huge boards) |
cycle |
baseline | follows a Hamiltonian cycle; provably always wins, slowly |
grounded (gated) |
worst-case | greedy proposals gated by the cycle-order invariant; proven to win (retraces its trail) |
grounded_multi |
worst-case | grounded, but the body may be ordered along ANY of 4-8 cycles; either orientation; proven |
planned_shortest |
worst-case | A* to each apple, accepted only with a re-entry certificate; proven to win |
planned_proven |
worst-case | A* routes scored for the next apple too, re-entry certified; proven, much faster |
probabilistic |
probabilistic | like planned_proven but scores the expected next apple; proven safe, fastest online |
planned_survival |
worst-case | A* with a tail-reach certificate; never dies but may stall (survival only) |
clairvoyant |
clairvoyant (benchmark) | plans with the future apple sequence (benchmark only) |
planned_proven_multi |
worst-case | planned_proven with multi-cycle certificates; proven, usually faster |
probabilistic_multi |
probabilistic | probabilistic with multi-cycle certificates; proven safe, fastest online on most boards |
clairvoyant_multi |
clairvoyant (benchmark) | clairvoyant with multi-cycle certificates (benchmark only) |
greedy: Takes the first step of a shortest path to the apple around the body (breadth-first search). Guarantees nothing: as the snake grows it walks into dead ends and dies. Cost per move grows with the board. A baseline only.
greedy_with_tail_check: Follows greedy only if, after the step, the head could still reach the tail; otherwise it chases its tail. In practice it rarely dies but it often circles without eating until the stall limit ends the game; nothing is proven. Cost per move grows with the board.
manhattan: Steps along the larger of the row or column gap to the apple, avoiding only immediate death. Constant time per move on any board, and blind to traps, so it dies. It is the O(1) proposer the grounded snake uses on large boards.
cycle: Always moves to the next cell of one fixed route that visits every cell once and returns to the start (a Hamiltonian cycle). Provably never dies and always fills the board, but it ignores the apple, so it is slow. Constant time per move.
grounded: A greedy step is the proposal; it is played only if it is legal, keeps the body in the order of the board's cycle, and gets closer to the apple along that cycle; otherwise the snake plays the certified move closest to the apple. Proven never to die and to eat every apple within one lap, in the worst-case regime (whatever the apples do). Constant time per move above 32 x 32. It always circles the board in the cycle's one direction.
grounded_multi: Like grounded, but the body only has to stay in order along at least one of a family of cycles (the board's cycle turned, mirrored and reversed: 8 on most boards, 4 when one side is odd), and the distance to the apple is the least over those cycles. Same proof (never dies, every apple within one lap), worst-case regime, constant time per move for the family (measured 1.5 to 2.3 times slower than grounded). Choose it to see the snake use both orientations; it is not reliably faster.
planned_shortest: Searches (A* over cell and time) for the shortest route to the apple after which the body is back in cycle order, simulates it exactly, and plays it if the re-entry certificate accepts it; otherwise a grounded move. Proven, worst-case. Myopic: the straight cuts leave gaps that later apples turn into laps, so it is not faster than grounded.
planned_proven: Like planned_shortest, but chooses among certified routes by route length plus the worst-case cost of the next apple, so it keeps the body compact. Proven never to die and to eat every apple within one lap; worst-case regime. Each search is capped (20,000 nodes) and amortised (about 1,000 nodes per move). The best proven player that assumes nothing about the apples.
probabilistic: Like planned_proven, but scores routes by length plus the expected cost of the next apple, apples being uniform over the free cells. The safety proof is the same (it never depends on where apples land); only the speed is a bet on the odds. Probabilistic regime, same cost as planned_proven. The fastest single-cycle online player.
planned_survival: Plans the shortest route and accepts it if, after eating, the head can still reach the tail; otherwise it makes a move that keeps the tail reachable. Proven never to die, not proven to keep eating: it often stalls. Cost O(N) per move. Shown to explain why the re-entry certificate matters.
clairvoyant: The planned_proven machinery, but routes are scored by simulating the real future apples from the seed. Same safety proof; clairvoyant regime, so it is a benchmark that prices not knowing the future, never a real player.
planned_proven_multi: planned_proven with multi-cycle certificates: it searches routes that end with the body in order along each cycle of the family, accepts any that does, limits routes to the least cycle distance D, and falls back to grounded_multi. Proven, worst-case; up to about 9 searches per planning attempt instead of 4, under the same amortised budget. Usually 5-9% fewer moves than planned_proven; 7% more on 10 x 7.
probabilistic_multi: probabilistic with multi-cycle certificates and expected scoring over the cycles the body ends ordered along. Proven safe, probabilistic regime, the same cost as planned_proven_multi. Choose it for the fewest moves without foresight on most boards; it commits to whichever orientation suits the apples instead of always the same one.
clairvoyant_multi: The clairvoyant benchmark with multi-cycle certificates and a probabilistic_multi lookahead. Benchmark only.
Worlds (--world MODE, or MODE:p to mix a mode with random):
| World | What it does |
|---|---|
random |
a uniformly random free cell (the standard game) |
nearest |
a kind world: the free cell closest to the head (around the body) |
farthest |
a static adversary: the free cell farthest from the head (unreachable first) |
adversarial |
an adaptive adversary: simulates the actual agent and picks the cell it takes longest to eat, or dies on (bounded search) |
Checks run by the gated agent (grounded):
legal: The move stays on the board, misses the body, and does not turn back into the neck.keeps_body_ordered: After the move the body still lies in the order of the board's cycle, so following the cycle stays safe.moves_closer_on_cycle: The move shortens the distance to the apple measured along the board's cycle.keeps_some_cycle_ordered: After the move the body still lies in order along at least one cycle of the family, so following that cycle stays safe.moves_closer_on_some_cycle: The move shortens D, the least distance to the apple along the cycles the body is ordered along.reenters_cycle_order: Simulated exactly, the route is legal, ends by eating, and leaves the body in the order of the board's cycle.reenters_some_cycle_order: Simulated exactly, the route is legal, ends by eating, and leaves the body in order along at least one cycle of the family.tail_reachable_after: Simulated exactly, the route is legal, ends by eating, and afterwards the head can still reach the tail (survival only, not progress).
checkers¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | uniformly random legal move (baseline) |
greedy |
baseline | maximises material right after its own move; blunders into replies |
gated (gated) |
worst-case | greedy, gated by a verified search: no material blunder within the horizon |
search |
worst-case | alpha-beta with iterative deepening (depth 6) |
noisy_search |
baseline | search with random mistakes (an opponent model) |
alphabeta |
worst-case | alpha-beta assuming the worst reply (worst-case) |
expectimax |
probabilistic | averages over a model of the opponent's replies (probabilistic) |
clairvoyant |
clairvoyant (benchmark) | simulates the opponent's actual policy (benchmark only) |
random: Plays a uniformly random legal move (captures are still mandatory). The baseline.
greedy: Plays the move that leaves it with the most material right after its own move (a man is worth 100, a king 150). Instant, but blind to the reply: it walks into exchanges and double jumps.
gated: The gated agent. Greedy proposes a move; legal checks the rules and no_material_blunder runs a verified 4-ply alpha-beta search to make sure the proposal is within half a man of the best move it can see; if not, it plays that search's best move instead. Guarantees no material blunder inside the searched horizon; nothing beyond it. Worst-case regime, about 1–2 ms per move.
search: Alpha-beta with iterative deepening, move ordering and a transposition table, to depth 6, under an evaluation of material, advancement and back-row guard. Strongest player here; about 10 ms per move.
noisy_search: A depth-2 alpha-beta that plays a random legal move one time in four; an opponent model for the regime table.
alphabeta: A 3-ply alpha-beta that assumes the opponent always picks the reply worst for it. Worst-case regime: safe, but passive against a weak opponent.
expectimax: A 3-ply search that averages over a model of the opponent's replies (greedy with 10% noise) instead of assuming the worst. Probabilistic regime: wins faster against that kind of opponent, at some risk.
clairvoyant: A 3-ply search that simulates the opponent's actual policy, including its random choices. A benchmark for perfect foresight, never a real player.
Checks run by the gated agent (gated):
legal: The move obeys the rules, including mandatory captures and completing every multi-jump.no_material_blunder: A verified alpha-beta search to the gate's horizon finds the proposal no worse than the best move by more than half a man.
chinese_checkers¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | a uniformly random legal move; never finishes a race (a baseline) |
greedy |
baseline | the move that lowers distance to go the most right now (the common baseline); no guarantee |
lookahead |
baseline | two own moves deep, other players ignored; strongest racer here, no guarantee |
gated (gated) |
worst-case | greedy proposals checked for progress and no stragglers (worst-case); proven to finish a solo race; with others it never wastes a move while a progressing one exists |
expectimax |
probabilistic | two own moves deep, every other player's reply averaged over a model (greedy, random 20% of the time) (probabilistic) |
clairvoyant |
clairvoyant (benchmark) | benchmark: two own moves deep with every other agent's actual replies until its next turn (sees the future) |
random: Picks a uniformly random legal move (ties broken by a seed derived from the position, so games replay exactly). It guarantees nothing and in practice never fills its goal: in the solo race it ends at the move cap with almost no piece home. Cost: one move generation per move. Choose it as the floor every other agent must beat, or as a chaotic opponent; it declares no information regime.
greedy: Generates every step and every jump chain of every piece and plays the move that lowers its distance to go the most right now; ties are broken by a seeded draw. It looks no further than this move, so it leaves stragglers behind and shuffles sideways near the end; nothing is guaranteed. Cost: one move generation per move (well under a millisecond on the standard star). Choose it as the common baseline, and as the proposer the gated agent checks.
lookahead: Scores each move by the distance it gains now plus the best gain of its own next move, ignoring what the other players do in between, and plays the best. It sets up jump ladders greedy misses and is the strongest racer here, but it proves nothing and assumes the board stays still. Cost: about a hundred times greedy (one move generation per candidate move). Choose it when you want the strongest opponent; it declares no information regime.
gated: Greedy proposes; three checks run (legal, makes_progress, keeps_pack); if any fails, a certified fallback plays the move with the least distance to go among those passing all three. Worst-case regime: it assumes nothing about the other players. In the solo race it is proven to finish (every move lowers the potential, within (R0 + 1)(H + 1) moves); with other players it is proven never to waste a turn while a progressing move exists and never to raise its distance to go unless every move does, but others can block it, so finishing is not proved. Cost: a few breadth-first searches per move. Choose it when you need a guarantee about your own progress rather than the best placing.
expectimax: Looks two of its own moves deep and, in between, averages over every other player's reply drawn from a model (greedy's move, or a uniformly random one 20% of the time); with three or more players the expectation is estimated from a few seeded sampled lines of replies. Probabilistic regime: its scores are expectations under that model, and they mean nothing about opponents the model does not describe. Cost: tens of move generations per move, more with more players. Choose it to see what betting on a model of the others buys.
clairvoyant: Runs the same two-move search as expectimax, but the engine shows it the actual next move of every other predictable player (a sealed copy of each agent, chained in turn order until its own next turn). Clairvoyant regime: a benchmark that sees the future, not a real player; humans and other clairvoyant seats cannot be foreseen, and then it ignores replies and says so. Cost: one copy and one decision per other player per candidate, the slowest agent here. Choose it only to measure what not seeing the future costs the online agents.
Checks run by the gated agent (gated):
legal: The proposed move is one of the legal moves in this position.makes_progress: The move lowers the player's distance to go, or keeps it and brings a piece closer to an open goal hole, unless no legal move does either (then it must be one of the best available).keeps_pack: After the move no piece is stranded: the rearmost piece is at the goal's doorstep, or trails the next piece by at most two spaces, or is catching up, unless no progressing move manages that.
go¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | uniformly random legal point that is not its own eye; passes when none is left (no guarantee) |
greedy |
baseline | most stones captured now, then most liberties; never passes while it has a legal point (no guarantee) |
search |
worst-case | 2-ply minimax search: best worst case over every reply, under an area estimate (exact for that tree only) |
mcts |
probabilistic | UCT tree search with random playouts; reports an exact interval for its playout win rate (probabilistic) |
gated (gated) |
worst-case | greedy proposes; legal + not_own_eye + not_self_atari are checked exactly; else MCTS over moves that pass (each move has all three properties) |
random: Plays a uniformly random legal point that is not one of its own single-point eyes, and passes when none is left; the draw is seeded by the position, so games replay exactly. It guarantees nothing beyond legality and declares no information regime. Cost: one scan of the board per move. Choose it as the floor every other agent must beat.
greedy: Plays the point that captures the most stones now, then the one leaving its group the most liberties; it never passes while it has a legal point. It looks one move ahead, so it walks into self-atari and fills its own eyes; nothing is guaranteed and no regime is declared. Cost: one placement test per legal point. Choose it as the baseline, and as the proposer the gated agent checks.
search: Takes the most promising moves by an area estimate (eight by default) and, for each, the worst case over every legal reply, pass included; it plays the best worst case (alpha-beta pruning does not change the value). Worst-case regime: the value is exact for that two-move tree under the area estimate, not for the game. Cost: one estimate per (move, reply) pair, so it grows with the board squared. Choose it to see a short-sighted worst-case player.
mcts: Monte Carlo tree search: a thousand random playouts per move steer an upper-confidence tree, and it plays the move the search rates best; it then runs extra independent playouts to give an exact (Clopper-Pearson) interval on its chance of winning a random playout from there. Probabilistic regime: the interval is about random playouts, not about a strong opponent. Cost: about a thousand playouts per move (the slowest agent here). Choose it as the strongest player.
gated: Greedy proposes; three checks run exactly (legal, not_own_eye, not_self_atari); if any fails, the fallback runs MCTS over only the moves that pass, or passes if none does. Every move it plays has all three properties, proved by construction, but the checks are local tactics: they do not make it win. Cost: greedy's when the proposal passes, MCTS's on an override. Choose it to see a fast, fallible player made locally safe.
Checks run by the gated agent (gated):
legal: The move is legal: an empty point (or a pass), no suicide in the default rules, and no repeat of an earlier whole-board position (positional superko).not_own_eye: The stone does not fill a single-point eye of the mover's own, which would capture nothing and throw away a life-giving point.not_self_atari: After the stone its group has at least two liberties or captures something, so no single reply can capture it.
tetris¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | a uniformly random legal placement (baseline) |
greedy |
worst-case | Dellacherie's one-piece evaluation (six board features); ignores the preview |
lookahead |
worst-case | best two-piece line through the previewed piece, same evaluation |
expectimax |
probabilistic | lookahead plus the expected next unseen piece (assumes the random world) |
gated (gated) |
worst-case | lookahead gated by exact preview checks; every possible loss announced in advance |
clairvoyant |
clairvoyant (benchmark) | beam search over the true future pieces (benchmark; seeded worlds only) |
random: Picks uniformly among the legal placements of the current piece. No strategy and no guarantee: it tops out within a few dozen pieces. The yardstick for the others.
greedy: Pierre Dellacherie's one-piece controller: every placement is scored by landing height (-1), eroded piece cells (+1), row transitions (-1), column transitions (-1), holes (-4) and cumulative wells (-1), weights as documented by Thiery and Scherrer (2009), and the best is played. It never looks at the preview. Fast (one evaluation per placement, about 34 per piece); worst-case regime because it assumes nothing about unseen pieces, though it proves nothing either.
lookahead: For the best ten placements of the current piece, finds the best placement of the previewed piece and scores the two-piece line (the first piece's own terms plus the full evaluation after the second). With no preview it is greedy. About 10 x 34 evaluations per piece; worst-case regime. It is the gated agent's proposer.
expectimax: Lookahead, then for its five best lines the mean over the seven pieces of the best placement of the first piece not yet shown: it bets that pieces are uniform and independent. Probabilistic regime: its model is the random world, so in the bag, sz, adversarial and kind worlds the assumption is not met (reported as such). About 5 x 7 x 34 extra evaluations per piece.
gated: The lookahead's placement is the proposal. Exact checks search every way to place the previewed pieces after it: it is played if they all still fit and can leave the top four rows empty (so the next unseen piece fits whatever it is). Otherwise the fallback plays the placement that best keeps those properties. Proven (worst-case, any world): it never tops out while its moves keep the next unseen piece placeable, and any loss is preceded by a WARNING at least preview + 1 pieces earlier. It cannot promise to survive forever: nobody can (Burgiel 1997; Brzustowski 1992). With --mode realtime the proposal is a resting place (tucks and spins included) with its planned keys; a fourth check, executable_before_lock, requires those keys to get there before the piece locks under gravity, and the fallback is the safest lock the planner can still reach in time. A person plays real time with --agents you on a clock of ten ticks a second, each key pressed acting on the next tick: a or left arrow, d or right arrow, w, x or up arrow to turn clockwise, z counter-clockwise, s or down arrow to soft drop, space or f to hard drop, . to wait (no key: wait); p pauses, q quits. Without a terminal each tick reads a line. With --guarded every key is checked.
clairvoyant: Reads the true future sequence from the seed and runs a beam search (width 6) four pieces deep with the same evaluation. Clairvoyant regime: a benchmark pricing what the preview leaves unseen, never a real player. Refused in the adversarial and kind worlds, whose pieces depend on the moves (there is no fixed future to see).
Worlds (--world MODE, or MODE:p to mix a mode with random):
| World | What it does |
|---|---|
random |
each piece uniform over the seven, independently (the classic generator) |
bag |
the guideline 7-bag: every block of seven pieces is a shuffled set |
sz |
only S and Z, alternating (Burgiel's sequence: forces a loss on widths 6, 10, 14, ...) |
adversarial |
Bastet-style: the piece whose best placement leaves the worst board |
kind |
the piece whose best placement leaves the best board |
Checks run by the gated agent (gated):
legal: The piece fits at the top in that rotation, can slide to that column, and drops.executable_before_lock: --mode realtime only: the planned keys lock the piece in the proposed place before it locks anywhere else, played tick by tick under gravity and the lock delay (exact). For a person's key: a lock as safe as the safest one before the key is still reachable in time.fits_preview: After the placement, every previewed piece can still be placed, in order (exhaustive search over their placements).unseen_piece_fits: The previewed pieces can be placed leaving the top four rows empty, so the first piece not yet shown fits whatever the world picks.
hexxagon¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | a uniformly random legal move (baseline) |
noisy_greedy |
baseline | greedy, but a random move 20% of the time (an opponent model) |
greedy |
baseline | the move that raises the margin most right now; ignores the reply |
gated (gated) |
worst-case | greedy, checked against every reply: takes forced wins, never allows a winning reply or a losing exchange when avoidable (worst-case) |
expectimax |
probabilistic | maximises the expected margin after the reply under the noisy-greedy model, exactly (probabilistic) |
search |
worst-case | alpha-beta on the margin, iterative deepening under a 3,000-node budget (worst-case); the strongest player here |
clairvoyant |
clairvoyant (benchmark) | sees the opponent's actual next reply and plays best against it (benchmark only) |
random: Picks a uniformly random legal move with its own seeded generator. No strategy, no guarantee, no information regime: the floor every other agent must beat. Cost: one move generation per move.
noisy_greedy: Plays greedy's move, except that one move in five is uniformly random. It exists as the opponent model of expectimax and the regime table, not as a player to imitate; it declares no regime. Cost: one move generation.
greedy: Plays the move that raises its margin (own pieces minus the opponent's) the most right now: a clone converting k pieces gains 1 + 2k, a jump 2k. Ties are broken by a draw seeded by the position and the match seed, so games replay exactly. It never looks at the reply, so it jumps out of solid walls and leaves holes the opponent clones into. Cost: one move generation. The gated agent's proposer; declares no regime.
gated: Greedy proposes; four checks weigh every legal reply exactly (legal, takes_forced_win, no_losing_reply, holds_exchange); if one fails, the fallback plays the move whose margin after the best reply is largest. Worst-case regime. Proved: it wins within two plies whenever that can be forced, never allows an immediately winning reply when avoidable, and never lets the best reply take back more than the move gained when some move avoids it. Not proved: winning; a deeper search beats it. Cost: about linear in the legal moves (each move updates only the replies near it, proved equal to enumerating every reply); well under a millisecond on the standard board.
expectimax: For every move, computes exactly the expected margin after the opponent's reply if the opponent is noisy_greedy (greedy's best moves, uniformly, 80% of the time; any legal move 20%), and plays the best. Probabilistic regime: the expectation is only as good as the model; against a different opponent it means nothing. Cost: the gated agent's two-ply table, about linear in the legal moves.
search: Negamax alpha-beta on the margin with iterative deepening, a best-move table and moves ordered by immediate gain, stopped by a node budget (3,000 nodes, so the same position always gets the same move). Finished games score the final margin plus or minus 10,000. Worst-case regime: it assumes the opponent minimises its margin. It proves nothing about the game's result; it is simply the strongest player here. Cost: tens of milliseconds per move.
clairvoyant: Shown the opponent's actual next reply to each of its moves (a sealed copy of the real agent, private random numbers included), it plays the move with the best margin after that reply. Clairvoyant regime: a benchmark that sees the future, never a real player. Against a human it cannot see anything; then it plays the gated fallback's move and says so. Cost: one opponent decision per legal move.
Checks run by the gated agent (gated):
legal: The proposed move is one of the legal moves in this position.takes_forced_win: If some move wins the game within two plies whatever the opponent replies, the proposal is one of them.no_losing_reply: If some move leaves the opponent no reply that wins the game at once, the proposal is one of them.holds_exchange: The opponent's best reply converts back no more than the proposal gains (margin after the reply at least the margin now), unless no move achieves that; then the proposal must lose the least possible over the two plies.
minesweeper¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | reveals a uniformly random closed cell (baseline) |
rules |
baseline | single-cell rules, then a random guess; opens in a corner |
solver |
probabilistic | exact constraint solving: proved-safe cells, then the least risky guess |
gated (gated) |
worst-case | rules, gated by proof: acts only on proved cells, prices every guess |
clairvoyant |
clairvoyant (benchmark) | sees the mines and never guesses (benchmark only) |
random: Reveals a uniformly random closed cell every move. It never flags and never reasons; on beginner boards it almost always loses. The yardstick.
rules: The rules a person learns first: if a number already touches as many proved mines as it shows, its other closed neighbours are safe; if it has exactly as many closed neighbours left as mines missing, they are all mines. It reveals safe cells, flags mines, and when no rule applies guesses a random closed cell. It opens in the top-left corner. Sound but incomplete: it misses deductions that need two numbers together or the mine count.
solver: Exact constraint solving over the closed cells next to numbers, with the global mine count: it counts every consistent layout (weighted by the ways to place the remaining mines on the other closed cells) and gets each cell's exact mine probability as a fraction. It reveals a cell with probability 0 if there is one, flags cells with probability 1, and otherwise reveals the least risky cell (ties: the one with fewest closed neighbours). Probabilistic regime: its guesses are optimal one step at a time for the random world only.
gated: The gated agent. The rules agent proposes; the check proved_safe (proved_mine for a flag) passes only on a proof, by a single-cell rule or by the exact count. If it fails, the move degrades to the solver's: a proved-safe cell when one exists, otherwise the least risky guess, and the record states that risk exactly (and that it assumes the random world). With a person proposing (--you --guarded), an unprovable guess is the person's to make: the gate abstains. Worst-case regime: every claim it makes holds in every world; it wins in the no_guess and kind worlds, and in the adversarial world exactly when no guess is needed.
clairvoyant: Is shown the mines and reveals only safe cells (zeros first), so it always wins where the mines are fixed by the seed (random, no_guess). A benchmark for what hidden information costs, not a player. In the lazy worlds (adversarial, kind) the mines depend on the moves, so it has nothing to see and plays the solver's move, saying so.
Worlds (--world MODE, or MODE:p to mix a mode with random):
| World | What it does |
|---|---|
random |
the standard game: mines uniformly at random after the first click |
no_guess |
a board that can be cleared from the first click without guessing (generated, with the deduction trace as proof) |
adversarial |
mines decided lazily: any revealed cell that can still be a mine is one |
kind |
mines decided lazily: any revealed cell that can still be safe is safe |
Checks run by the gated agent (gated):
proved_safe: For a reveal: no layout of mines consistent with the board and the mine count puts a mine on this cell (a single-cell rule or the exact count). The first click is always safe.proved_mine: For a flag: every consistent layout puts a mine on this cell.keeps_proved_flags: For an unflag: the cell is not a proved mine.legal: The move names a closed cell (and a reveal is not on a flag).
2048¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | a uniformly random legal move (baseline) |
greedy |
baseline | the move that merges the most points now (baseline) |
corner |
baseline | one move ahead, keep big tiles ordered from the bottom-left corner (classic rule) |
expectimax |
probabilistic | averages over spawns with their true odds, 2 moves deep (3 when the board is nearly full) |
minimax |
worst-case | assumes the worst spawn (cell and value), same depth as expectimax |
gated (gated) |
worst-case | expectimax proposals, played only if they keep the best worst-case survival horizon |
clairvoyant |
clairvoyant (benchmark) | sees the seed's next 4 spawns and searches them exactly (benchmark; random world only) |
random: Plays a uniformly random legal move from its own seeded generator. A floor for every comparison.
greedy: Plays the move whose merges score the most points right now; ties go to the move leaving more empty cells. Looks one move ahead and ignores the spawn.
corner: Scores the board after each legal move by its tiles weighted 4^k along a snake-shaped path from the bottom-left corner (the bigger the tile, the further along the path it should be) and plays the best; ties go down, left, right, up. The classic 'keep it in the corner' rule, one move deep.
expectimax: Searches two moves deep (three when at most three cells are empty): after each of its moves it averages over every possible spawn (each empty cell equally likely; a 2 with probability 0.9, a 4 with 0.1) and assumes it then plays its best reply; leaves are scored by the line heuristic of Robert Xiao's 2048 AI (empty cells, merges, monotone rows and columns). Probabilistic regime: its values are expectations under the random world; in any other world its notes say the assumption is not met.
minimax: The same search and heuristic, but every spawn is assumed to be the worst one for the player (cell and value). Worst-case regime: its value is a lower bound on the heuristic two moves on whatever the world does. It plays more cautiously than expectimax in the random world and holds up better against hostile spawns.
gated: Expectimax proposes; the gate computes, exactly, each legal move's worst-case survival horizon (how many more turns the player can surely keep moving whatever tiles appear, up to 3) and plays the proposal only if its horizon is the best available. Otherwise it plays the move of best horizon with the best worst-case value. Proved in every world: no gated move ever gives up guaranteed survival another move would have kept. Scores are measured, not proved.
clairvoyant: Is shown the next four spawn draws of the seed (the random world's future, fixed in advance) and tries every sequence of four moves against those exact spawns. A benchmark that prices not knowing the future, never a real player; refused in worlds whose spawns depend on the moves.
Worlds (--world MODE, or MODE:p to mix a mode with random):
| World | What it does |
|---|---|
random |
standard: a 2 (90%) or a 4 (10%) on a uniformly random empty cell, from the seed |
kind |
the spawn (cell and value) leaving the best position after the player's best reply |
evil |
a fixed adversary: the spawn leaving the worst position after the player's best reply |
adversarial |
adapts to the agent: simulates its reply to the 6 worst-looking spawns and picks the worst outcome |
Checks run by the gated agent (gated):
legal: The move changes the board (a move that slides nothing is not allowed).survives_any_spawn: After the move, every possible new tile (any empty cell, a 2 or a 4) leaves a legal move, whenever some legal move achieves that.best_survival_horizon: The move's worst-case survival horizon (turns the player can surely keep moving whatever tiles appear, computed exactly up to 3) equals the best of any legal move.
connect4¶
| Agent | Regime | In one line |
|---|---|---|
random |
baseline | uniformly random column (baseline) |
greedy |
baseline | win if it can, else block, else the column that best extends its lines |
search |
worst-case | alpha-beta with iterative deepening, 20,000 positions per move |
gated (gated) |
worst-case | greedy, gated by four exact threat checks (3 plies); safe search fallback |
solver |
worst-case | the exact solver's column when provable in budget (small boards), else search |
noisy_greedy |
baseline | greedy with random mistakes (an opponent model) |
alphabeta |
worst-case | 3-ply minimax assuming the worst reply (worst-case) |
expectimax |
probabilistic | 3-ply search averaging over a model of the replies (probabilistic) |
clairvoyant |
clairvoyant (benchmark) | simulates the opponent's actual policy (benchmark only) |
random: Drops a disc in a uniformly random column that is not full. The baseline.
greedy: Wins at once if it can, otherwise blocks an immediate threat, otherwise plays the column whose disc extends the most of its open lines and closes the most of the opponent's (the seed chooses among near-ties). One ply of lookahead: it never sees a double threat coming and happily plays under the opponent's winning cell.
search: Negamax alpha-beta with iterative deepening, a transposition table, best-move-first ordering and exact pruning of moves that lose at once. Leaves are scored by winning cells and central discs. A node budget of 20,000 positions per move (not a clock) keeps it reproducible. A decisive value is a proof of a forced result within the searched depth.
gated: The gated agent. Greedy proposes; four exact checks decide: takes_win, blocks_threat, not_under_threat and no_loss_in_two (the opponent cannot force a win within its next two moves), each applied when avoidable. If one fails it plays the search's best column among those passing every check. Guaranteed: never misses a win in one, never allows an avoidable loss within the opponent's next two moves. Not guaranteed: perfect play.
solver: Scores every column with the exact solver and plays the best (fastest win, slowest loss). Perfect play whenever every column is proved within 300,000 positions: always on boards up to about 5x5, and in 7x6 endgames. When the budget runs out it plays the search's column and says 'not proved'.
noisy_greedy: Greedy, except that one move in five is a random column. An opponent model for the regime table.
alphabeta: A 3-ply minimax that assumes the opponent always picks the reply worst for it. Worst-case regime.
expectimax: A 3-ply search that averages over a model of the opponent (greedy with 20% noise) instead of assuming the worst. Probabilistic regime.
clairvoyant: A 3-ply search that replays the opponent's actual policy, random choices included. A benchmark for perfect foresight, never a real player.
Checks run by the gated agent (gated):
takes_win: If some column completes a line now, the move does.blocks_threat: If the opponent could complete a line on its next move, the move blocks it (when a single block exists).not_under_threat: The move does not land directly under a cell where the opponent would complete a line (unless every candidate does).no_loss_in_two: After the move the opponent cannot force a win within its next two moves (unless no candidate avoids it).
breakout¶
| Agent | Regime | In one line |
|---|---|---|
random |
worst-case | a uniformly random action each tick (baseline) |
follow |
worst-case | moves under the lowest ball as it is now; no prediction |
intercept |
worst-case | the exact landing point of the first ball down, and the shortest way there |
aim |
probabilistic | meets the ball where the next flight breaks the most bricks (assumes uniform spin) |
worst_case |
worst-case | meets the ball where every spin leaves the next flight catchable |
gated (gated) |
worst-case | aim, gated by exact one-tick checks: every reachable ball caught, losses announced |
clairvoyant |
clairvoyant (benchmark) | aim with the coming spins known (benchmark; random world only) |
random: Picks uniformly among the legal actions each tick. Loses its balls quickly.
follow: Moves the paddle towards the lowest falling ball's current position. It predicts nothing, so a fast ball bouncing off a wall beats it. Worst-case regime: it assumes nothing, and proves nothing either.
intercept: Forecasts exactly where the first ball comes down (the game's own physics played forward, brick bounces included) and moves the shortest way to the reachable point under it closest to the landing point, so the ball bounces steeply. It never aims. Worst-case regime.
aim: For the first ball down, plays out the next flight after a bounce in each of the paddle's eight zones and chooses where to meet the ball: among the meeting points it can reach whose next flight is missed for at most 10% of the spins, the most bricks expected, every spin equally likely. Probabilistic regime: its model is the random world, so against the adversarial spin the assumption is not met (reported as such). It is the gated agent's proposer.
worst_case: Chooses a meeting point at which every spin the rules allow (up to epsilon) leaves the next flight catchable, and among those the one that breaks the most bricks for sure; with none, the one with the most ticks to spare. Worst-case regime: it assumes nothing about the spin.
gated: Aim's action is the proposal. Each tick the gate plays it one tick ahead for every spin and checks that the first ball down can still be reached in time (catches_next, exact) and that it can still be met where every spin leaves the next flight catchable (bounce_safe). Otherwise the fallback moves towards the best spin-proof meeting point, or under the ball. Proven (worst case, any world, one ball in play): every ball the paddle can reach is caught, and a ball is lost only after the gate says its guarantee lapses (no spin-proof bounce exists), a whole flight earlier. A person plays with --agents you: the arrows or a and d move (and keep moving until another key in a terminal), down or s stops, space, up or w launches, f fires the laser, p pauses, q quits; --guarded checks every tick.
clairvoyant: Reads the coming spins from the seed and aims exactly: the meeting point whose next flight, with the real spin, is catchable and breaks the most bricks. A benchmark pricing what the spin's uncertainty costs, never a real player; refused in the kind and adversarial worlds, whose spins depend on the moves.
Worlds (--world MODE, or MODE:p to mix a mode with random):
| World | What it does |
|---|---|
random |
capsules drawn at random (Arkanoid's mix); spin uniform in [-epsilon, epsilon] |
kind |
the capsule worth most to the player now; the spin that eases the next catch most |
adversarial |
the capsule worth least now; the spin that makes the next catch hardest |
Checks run by the gated agent (gated):
legal: The action is allowed now (launch with a ball on the paddle, fire in laser mode).catches_next: One tick after the action, for every spin a bounce in that tick may get, the paddle can still get under the first ball to come down before it lands (exact: the forecast plays the game's physics forward; the reach is a closed form).bounce_safe: One tick after the action, for every spin, the paddle can still meet the first ball down at a point where every spin leaves the next flight catchable.