Checkers: a greedy player with a verified tactical gate¶

A player that grabs whatever material is on offer plays checkers badly: it takes a piece and walks straight into a two-for-one. This page shows how the library's grounded pattern (propose, check, then act or degrade) turns that greedy player into one that never makes a material blunder the engine can see within a fixed number of moves, and states exactly how far that promise goes.

This page is for anyone who wants to watch the act-or-degrade idea on a real board game, and for engineers who want a template for a game with a search-based check. You need no checkers knowledge beyond "pieces move diagonally and capture by jumping"; the rules are listed below.

Try it in your browser

The board below plays this game's recorded example with no download; Play live runs this package itself in your browser, in Pyodide (about 7 MB, downloaded once), and the play page has every setting.

Checkers runs here when JavaScript is on; the play page has it too, and the commands below run it in a terminal.

Run it¶

uv run grounded-decision examples games_checkers   # the report below
uv run grounded-decision play checkers             # watch or play a game
uv run grounded-decision play checkers --agents gated,greedy --view history --coords

Source: src/grounded_decision/examples/games/checkers.py (rules, players, report) and checkers_search.py (the search, which knows nothing about checkers). Tests: tests/test_games_checkers.py.

The rules, exactly as implemented¶

English draughts (American checkers) on the dark squares of an \(N \times N\) board, \(N\) even (8 by default; 10 x 10 and larger work with the same rules). Red moves first from the top; each side starts with \(N/2 - 1\) rows of men (12 men each on 8 x 8).

Rule	What the code does
Men	Step one square diagonally forward.
Capture	Jump an adjacent enemy piece onto the empty square beyond; men jump forward only.
Captures are mandatory	If any capture exists, every legal move is a capture. Any capture may be chosen (no "take the most" rule).
Multi-jumps	A move is the whole jump sequence: a piece that can jump again must. Each branch of a sequence is its own move.
Jumped pieces	Stay on the board until the move ends, so no piece is jumped twice. The mover's starting square counts as empty.
Crowning	A man reaching the far row becomes a king and the move ends there, even if the new king could jump on.
Kings	Step and jump one square in all four diagonal directions (no flying kings).
Losing	A player with no legal move (no pieces, or all blocked) loses.
Draw	After 80 consecutive plies (40 moves each) with no capture and no man move. The official rule lets a player claim this; here it is automatic.

The draw rule also guarantees every game ends: men only move forward and captures only remove pieces, so a game can only go on with kings shuffling, and the counter stops that. There is no repetition rule.

Squares are numbered in the standard way, which the report uses for moves (11-15 is a step, 19x12x3 a double jump, (crowned) marks crowning):

    1   2   3   4        Red's men start on 1-12,
  5   6   7   8          White's on 21-32.
    9  10  11  12
 13  14  15  16
   17  18  19  20
 21  22  23  24
   25  26  27  28
 29  30  31  32

Checking the move generator¶

Counting every sequence of legal moves from the start (a perft count) is the standard test of a move generator, because a single wrong rule changes the numbers. The report prints depths 1 to 6, and the tests check 1 to 7 against the published English-draughts values:

Depth (plies)	1	2	3	4	5	6	7
Move sequences	7	49	302	1,469	7,361	36,768	179,740

Each rule in the table above also has its own test with a hand-built position (mandatory capture, a forced double jump, branching jumps, crowning that stops a jump sequence, a king capturing backwards, a man that cannot, a blocked side losing, the draw counter).

The four players¶

random: A uniformly random legal move.
greedy: The move that leaves it with the most material straight after its own move (a man is worth 1, a king 1.5), ignoring the reply. Ties are broken at random.
search: Alpha-beta search 6 plies deep (a ply is one player's move). It deepens one ply at a time and tries the previous iteration's best move first, then bigger captures, and remembers positions it has already scored (a transposition table). Lines are never cut off in the middle of a capture sequence. Positions at the end of a line are scored by material (man 100 points, king 150), advancement (2 points per row a man has moved forward) and a back-row guard (10 points per man still on its own back row, where it stops enemy men from crowning).
gated: Greedy proposes; two checks decide; if either fails, the gate plays the best move of a 4-ply search instead.

What the gate checks¶

legal: the proposal is one of the legal moves. A human proposer who ignores a capture is told "a capture is available and capturing is mandatory".
no_material_blunder: a 4-ply search (the verified horizon \(h = 4\), continued through any captures still pending) works out the value of the best move and the value of the proposal, both exactly, in the same search. The proposal passes if it trails the best move by at most half a man (50 points).

If both pass the gate acts on greedy's move; otherwise it degrades to the search's best move, which passes the second check by construction (it is the best).

The report¶

From uv run grounded-decision examples games_checkers:

== Games: checkers with a verified tactical gate ==
Rules: English draughts on 8 x 8; captures mandatory; a move is a whole jump
sequence; crowning ends the move; no legal move loses; draw after 40 moves
each without a capture or a man move.
Move counts from the start, depth 1-6 (perft): 7, 49, 302, 1469, 7361, 36768

Each pairing: 6 seeded openings (4 random plies), both colours.
search = alpha-beta depth 6; gated = greedy checked by a depth-4 search (tolerance 0.50 men).
  pairing            agent     won  drawn  lost  mean plies  overrides  nodes/move
  gated vs greedy    gated      12      0     0        39.0         39         341
                     greedy      0      0    12        39.0          0           0
  gated vs random    gated      12      0     0        53.0         51         370
                     random      0      0    12        53.0          0           0
  gated vs search    gated       0      3     9       101.2        160         357
                     search      9      3     0       101.2          0        2250
  search vs greedy   search     12      0     0        39.8          0        2237
                     greedy      0      0    12        39.8          0           0

Showcase: gated (Red) vs greedy, seed 5. Red wins: White has no pieces left after 49 plies; the gate overrode greedy 2 times.
First override, at ply 17 (Red to move):
      r   r   .   r
    .   .   r   r
      .   .   .   r
    .   .   .   .
      .   .   w   .
    w   .   .   .
      .   .   .   w
    w   w   .   w
  greedy proposed 12-16
    [pass] legal: 12-16 is legal
    [FAIL] no_material_blunder: at depth 4, 12-16 scores -2.10 men; the best move 7-10 scores -0.04 men (it gives up 2.06 men, more than the 0.50 allowed)
  why: after 12-16, best play goes 19x12x3 (crowned) 2-6 3x10
  the gate played 7-10 instead

How to read it:

Each pairing is 12 games: 6 openings, each played once with each player as Red. An opening is the start position after 4 random plies chosen by a fixed seed, so the games differ but every run is identical. "Mean plies" is the average game length; "overrides" counts the moves where the gate rejected greedy's proposal; "nodes/move" is the average number of positions the player's search visited per move.
The gate fixes greedy. Greedy on its own loses every game to the search player. Gated, the same proposer wins all 12 games against plain greedy and all 12 against random, while the gate overrides only about one move in six (39 of its roughly 230 moves against greedy).
The gate is not a stronger engine. Against the 6-ply search, gated loses 9 and draws 3. Its check looks 4 plies ahead and only asks "does this lose material?", so it accepts quiet positional mistakes that a deeper search exploits. It also searches far less: about 350 positions per move against about 2,250.
The showcase is one move from the first gated-versus-greedy game with seed 5. Red's greedy proposal 12-16 gains nothing and leaves a hole: White's man on 19 jumps twice, 19x12x3, taking two men and crowning. The check compares the two values (−2.10 men for 12-16, −0.04 for the best move 7-10), finds a shortfall of 2.06 men, more than the 0.50 allowed, and the gate plays 7-10. The "why" line is the search's best play for both sides after the rejected move.

Exactly what the gate guarantees¶

Write \(V_h(m)\) for the value of move \(m\) in the depth-\(h\) search tree: every line followed for \(h\) plies, then on through any captures still pending, with lines that end the game scored as wins or losses and the remaining end positions scored by the evaluation above (material, advancement, back-row guard; 100 points to a man). For every move \(m\) the gated player makes,

\[ m \text{ is legal} \quad\text{and}\quad V_h(m) \;\ge\; \max_{m'} V_h(m') - 50 . \]

In words: within \(h = 4\) plies (plus the captures they leave pending), no line the search considers makes the played move worse than the best move by more than half a man, as the evaluation measures it.

Why the numbers are exact rather than estimates: alpha-beta pruning with a full window at the root returns the true minimax value of the tree (it only skips branches that provably cannot change it), and the transposition table reuses an entry only for the same position at the same remaining depth, as the bound it was stored as. The tests compare the search against plain minimax without pruning or a table on 40 positions at depths 1 to 3, and re-check the guarantee with plain minimax on gated games.

What the gate does not guarantee

Not perfect play. A shot that lands on ply 5 after a quiet move is invisible to a 4-ply check. The tournament against the 6-ply search shows the cost.
Not positional quality. Any loss smaller than half a man passes, and so does any mistake the evaluation does not measure.
The evaluation is a heuristic. "Half a man" is measured by it, not by the true value of the position.

To check deeper, raise the horizon (GatedCheckersAgent(GreedyAgent(), TacticalVerifier(horizon=6))): the guarantee then holds to 6 plies, and each move costs about as much as the search player's.

Watching a game: the board in the terminal¶

play checkers draws a real checkerboard: with colour, light and dark squares get wood-coloured backgrounds; without colour (NO_COLOR or --color never) the playable dark squares carry a dot · and the light squares stay blank. Red's men are ● and White's ○; kings are crowned with a ring, ◉ and ◎, and drawn bold. The last move is drawn as a joined diagonal line (╱ ╲, ╳ where a multiple jump turns) from its origin to the piece that moved, and every piece it captured is flashed as a red ✕ for that one position. --coords writes the standard square numbers (1 to 32) on the empty dark squares, the numbers used in move names such as 20x27 (on by default when you have a seat).

The panel beside the board shows each side's material as a bar (pieces left out of 12), the men, kings and captures, and a sparkline of the piece count over the last moves. These two frames are from uv run grounded-decision play checkers --agents gated,greedy --view history --max-steps 30 --style unicode --color never; first Red's capture 20x27, then White's recapture 31x24:

┌────────────────┐  move 11  ● Red (gated · worst-case): 20x27
│  ●   ●   ●   ● │    ACT  the proposal passed the 2 checks that ran
│●   ●   ●   ●   │      ✓ legal                  20x27 is legal
│  ·   ·   ·   ● │      ✓ no_material_blunder    at depth 4, 20x27 scores +1.10 men; the best move 20x27 scor…
│●   ·   ·   ·   │      material_after=2  nodes_searched=73  best_value=110
│  ○   ·   ○   ╱ │    moves 11 · acts 6 · overrides 0 · captured by Red 2 · captured by White 0 · …
│●   ○   ○   ✕   │    ● Red ██████████ 12 men · 0 kings · took 2  ▁▁▁▁▁▁▁▁▁▁▁
│  ○   ·   ●   ○ │    ○ White ████████▍░ 10 men · 0 kings · took 0  ██▅▅▅▅▅▅▅▅▁
│○   ○   ○   ○   │
└────────────────┘

┌────────────────┐  move 12  ○ White (greedy): 31x24
│  ●   ●   ●   ● │      material_after=-1
│●   ●   ●   ●   │    moves 12 · acts 6 · overrides 0 · captured by Red 2 · captured by White 1 · …
│  ·   ·   ·   ● │    ● Red █████████▏ 11 men · 0 kings · took 2  ███████████▁
│●   ·   ·   ·   │    ○ White ████████▍░ 10 men · 0 kings · took 1  ██▅▅▅▅▅▅▅▅▁▁
│  ○   ·   ○   · │
│●   ○   ○   ○   │
│  ○   ·   ✕   ○ │
│○   ○   ╱   ○   │
└────────────────┘

Later in the same game, with --coords (move 30; Red has a king, ◉):

┌────────────────┐  move 30  ○ White (greedy): 27-23
│  ●   ●   ●   ● │      material_after=-5.5
│●   6   7   8   │    moves 30 · acts 14 · overrides 1 · captured by Red 9 · captured by White 4 · …
│  9   10  11  12│    ● Red ██████▋░░░ 7 men · 1 king · took 9  ████▆▅▅▅▃▁
│●   ●   15  16  │    ○ White ██▌░░░░░░░ 3 men · 0 kings · took 4  █▇▇▇▆▅▄▄▂▁
│  ◉   18  19  ○ │
│21  22  ○   24  │
│  25  26  ╲   ○ │
│29  30  31  32  │
└────────────────┘

Boards of 16 x 16 and larger have more than 99 dark squares; their numbers do not fit in a square, so --coords shows none there.

Performance¶

These figures are from one development machine; the report never prints timings, so its output stays identical between runs. The tests check generous upper bounds and print the measured rates with pytest -s.

Measurement	Result
Perft to depth 8 (845,931 sequences)	0.6 s
`search` (depth 6), per move	about 10 ms, 2,400 positions, about 245,000 positions/s
`gated` (depth-4 check), per move	about 1.5 ms, 370 positions
`greedy` and `random`, per move	under 0.1 ms
Legal moves from the start of a 100 x 100 board (99 moves)	under 0.1 ms

Board representation: each side's men and kings are bits of four Python integers (bitboards). The dark squares are packed row by row with one spare bit after every pair of rows, so a diagonal step is always a shift by \(N/2\) or \(N/2 + 1\) bits, and a step off the board's edge lands on a spare bit that is never a square. "Every Red man that can step down-right" is then one shift and one AND for the whole board, which is why move generation stays cheap on large boards. Positions are immutable and hashable, so they can key the transposition table.

Extending it¶

Another board size: CheckersGame(10) (or configure(10, 10)) uses the same rules with 4 rows of men each. Agents read the size from the game they are given.
Another proposer: guarded(proposer) wraps any player, including a human, in the same two checks and fallback.
Another game with a search-based gate: checkers_search.AlphaBeta searches any game that provides legal moves, a move function, an evaluation and a "do not stop here" test (SearchProblem), so the same exactness argument carries over.

Related: Games: tic-tac-toe and snake shows the same pattern with checks proven over the whole game rather than to a horizon.