Go: a greedy player with exact local checks¶

A player that always grabs stones and liberties plays Go surprisingly well in the middle of the game and disastrously at the end: with nothing left to grab, it fills its own eyes and hands its groups to the opponent. This page shows how the library's grounded pattern (propose, check, then act or degrade) stops exactly those blunders with three checks that are exact facts about the position, and states just as exactly what they do not stop.

This page is for anyone who wants to see act-or-degrade on the classic board game, and for engineers who want a template for a game whose checks are local and cheap rather than a deep search. You need no Go knowledge; the next section explains the game in a few paragraphs.

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.

Go 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_go           # the report below
uv run grounded-decision play go --size 9x9          # watch gated vs mcts
uv run grounded-decision play go --size 9x9 --you --guarded   # play, with the gate checking you

Source: src/grounded_decision/examples/games/go_rules.py (the rules), go_search.py (playouts, tree search, a two-move search) and go.py (the game, the players, the gate, the report). Tests: tests/test_games_go.py.

Go in four paragraphs¶

Two players, Black and White, take turns placing a stone of their colour on an empty intersection of an \(N \times N\) grid (9 x 9 for quick games, 19 x 19 for the full game), or passing. Black moves first. Stones never move once placed.

Stones of one colour that touch along the grid lines form a group. The empty intersections next to a group are its liberties. When a move fills a group's last liberty, that group is captured: all its stones come off the board. A group with exactly one liberty left is in atari (one move from capture).

An eye is an empty point surrounded by one player's stones. The opponent cannot play there without being captured at once, so a group with two real eyes can never be captured. Filling your own eye throws that protection away.

The game ends when both players pass in a row. Each player's score is the number of intersections they occupy plus the empty ones only they surround (area scoring). White adds komi, 7.5 points by default, for moving second.

The rules, exactly as implemented¶

The rule set is Tromp–Taylor (John Tromp, "The Rules of Go"), the most precisely specified rule set for Go: ten sentences a program can follow literally.

Rule	What the code does
Board	\(N \times N\), any size from 2 x 2 to 25 x 25 (`--size 9x9`, `13x13`, `19x19`).
Turn	Black first, then alternate. A turn is a pass or a stone on an empty point.
Capture	After a stone is placed, every opponent group with no liberty is removed; then the mover's own groups with no liberty.
Suicide	A move after which the mover's own stones would be removed. Forbidden by default, as in most human rule sets; `GoGame(allow_suicide=True)` gives literal Tromp–Taylor, which allows it. A one-stone suicide is illegal either way (it recreates the previous board).
Positional superko	No move may recreate any earlier whole-board position. This covers simple ko (retaking at once) and longer cycles.
End	Two consecutive passes.
Score	Stones on the board plus empty points that reach only your colour, plus komi for White. Higher score wins; equal scores tie (only possible with whole-number komi). Stones left on the board count as they stand: dead stones must be captured before passing.
Move limit (our addition)	After \(3N^2\) turns the game is scored as if both had passed, so every watched game ends. `move_limit=None` removes it.
Resignation	Off by default; `GoGame(allow_resignation=True)` makes `resign` a legal turn. The built-in players never resign.

Moves are written in the usual coordinates: a column letter (I is skipped, as is traditional) and a row number from the bottom, so D4, J9, pass.

How it is built, briefly: the board is a flat array with a one-cell border of sentinel values, so every point has four neighbour indices and no edge tests are needed. Groups and liberties are found once per position and cached; checking a move touches only the groups next to it. Positions are immutable, so a search can keep as many as it likes. Superko uses Zobrist hashing (a fixed random 64-bit key per point and colour, combined by XOR), and every hash match is confirmed by comparing whole boards, so a hash collision can never make a legal move illegal.

The players¶

Name	What it does	What it guarantees
`random`	A uniformly random legal point that is not one of its own eyes; passes when nothing else is left.	Nothing.
`greedy`	Captures as many stones as it can right now; among equal captures, gives the new stone's group the most liberties. Never passes while it has a legal point.	Nothing.
`mcts`	Monte Carlo tree search: grows a tree of positions, finishing each visit with one random game ("playout"), and plays the most visited move. Seeded, so reproducible.	A probabilistic statement about its own playouts (below).
`search`	Looks at its 8 most promising moves and, for each, at every reply; plays the move whose worst reply is least bad, by an area estimate.	Exact only for that two-move tree and that estimate.
`gated`	`greedy` proposes; three checks decide; if any fails, it plays MCTS's choice among the moves that pass all three (or passes if none does).	The three properties below, on every move.

What the gate checks, and exactly what it guarantees¶

Each check is an exact fact about the current position and the proposed move, computed from the rules. None of them estimates anything.

legal: the move is legal (not on an occupied point, not a forbidden suicide, not a superko repetition).
not_own_eye: the move does not fill a single-point eye of the mover's, by the standard test: every neighbouring point is the mover's stone, and the opponent holds none of the diagonal points (on the edge) or at most one (in the middle). Such a move can never capture anything and never gains a liberty, because all its neighbours are already friendly.
not_self_atari: after the move, the group containing the new stone has at least two liberties, or the move captures something. When it passes on liberties, no single opponent move can capture that group: one stone fills one liberty, and a capture needs every liberty filled.

The fallback only ever plays moves that pass all three checks (and a pass passes them trivially), so every move the gated player makes is legal, fills none of its own eyes, and either captures or leaves its group safe from immediate capture. The tests check this on every gated move of many games, the third property by actually trying every possible reply.

What the gate does not guarantee

It does not make the player good at Go. The eye test is a pattern on nine points, not a verdict on life and death: sometimes filling such a point is right, and sometimes a point it allows is an eye that matters. A self-atari can be a strong sacrifice, and a group with two liberties can still be lost to a ladder or a net. A capturing move may itself be in atari (a ko). The gate removes three specific, cheaply recognised blunders; MCTS decides among what remains.

What you will see¶

The report plays every pairing on 9 x 9 with four seeds, each from both colours (eight games per pairing), plus a short 13 x 13 sample, then shows one override and one finished, scored board. Output of uv run grounded-decision examples games_go:

9x9: 4 seeds, both colours (8 games per pairing); MCTS: 200 playouts per move.
gated = greedy checked by legal, not_own_eye, not_self_atari; fallback MCTS over the moves that pass.
mean margin: final area score difference from that agent's side, komi included.
  pairing           agent    won  lost  drawn  mean moves  mean margin  overrides
  gated vs random   gated      8     0      0       112.2        +60.2         31
                    random     0     8      0       112.2        -60.2          0
  gated vs greedy   gated      8     0      0       150.2        +81.0         90
                    greedy     0     8      0       150.2        -81.0          0
  mcts vs greedy    mcts       6     2      0       186.5        +55.1          0
                    greedy     2     6      0       186.5        -55.1          0
  gated vs mcts     gated      3     5      0        93.2        +21.2         45
                    mcts       5     3      0        93.2        -21.2          0

13x13 sample: 1 seed, both colours.
  pairing           agent    won  lost  drawn  mean moves  mean margin  overrides
  gated vs random   gated      2     0      0       235.5       +115.0         18
                    random     0     2      0       235.5       -115.0          0
  gated vs greedy   gated      2     0      0       308.5       +169.0         55
                    greedy     0     2      0       308.5       -169.0          0
Failed checks behind the 9x9 overrides: not_own_eye 163, not_self_atari 11

How to read it:

Gated beats greedy 8–0, by 81 points on average: the gated player is greedy until a check fails. The 90 overrides are almost all eye-fills at the end of the game, where plain greedy destroys its own groups. That is the whole difference between the two rows.
Gated beats random 8–0 on 9 x 9 and 2–0 on 13 x 13.
MCTS beats greedy 6–2 at only 200 playouts per move.
Gated vs MCTS is 3–5 in games won, although gated's average margin is +21.2 (it wins big and loses narrowly). Eight games cannot separate these two players; the honest reading is "comparable at this playout budget". The gate guarantees the absence of three blunders, not strength.
"mean margin" is the final area score difference from that agent's side, komi included.

The report also checks the rule engine against a known fact: the number of legal positions (every group has a liberty) on 1 x 1, 2 x 2 and 3 x 3 boards, counted by brute force, is 1, 57 and 12,675, the values published by Tromp and Farnebäck ("Combinatorics of Go", 2006).

One override, explained¶

Showcase: a gate override from the 9x9 games, gated (Black) vs random (White), seed 0
(2 overrides in that game's 87 moves). Move 83, Black to move:
      A B C D E F G H J
    9 . X . X . X X . X 9
    8 X X X X X X X X X 8
    7 . X X . X X O . X 7
    6 X . X X O X . . X 6
    5 X X X O O X X X X 5
    4 . X O O O X . X . 4
    3 X X O . O O X X O 3
    2 X X O O O O O O O 2
    1 . X O O O O O . O 1
      A B C D E F G H J
  greedy proposed A4
    [pass] legal: A4 is legal
    [FAIL] not_own_eye: A4 is a single-point eye of Black's (every neighbour is Black's, diagonals not the opponent's): filling it captures nothing and gains no liberty
    [pass] not_self_atari: the group of A4 keeps 13 liberties: no single reply can capture it
  the gate played H7 instead
    MCTS: H7 won 40 of its 40 tree playouts (200 in all)
    P(Black wins a random playout after H7) ∈ [0.98, 1.00] (95%, 200 trials)

X is Black, O is White, . an empty point. Greedy wanted A4 because nothing else captured and A4 joins a large group; but A4 is one of the eyes that keeps Black's big group alive. The gate refused it and played H7, which puts White's lone stone at G7 in atari.

The last line is a probabilistic statement, the kind MCTS can make: 200 independent random playouts after H7, of which Black won enough that, with 95% confidence, a random playout from there is won by Black at least 98% of the time (an exact Clopper–Pearson interval). It is a statement about random playouts, not about best play. The tree's own count ("40 of 40") is not used for the interval, because tree playouts are not independent: the tree chooses where to look next from what it has already seen.

A finished, scored board¶

A final scored position: gated (Black) vs mcts (White), seed 0.
Tromp-Taylor area scoring: x/o mark empty points that reach only Black/White.
      A B C D E F G H J
    9 o O O o O O X X x 9
    8 O O O O O X X X X 8
    7 X O o O O O X X X 7
    6 X X O O X X X X X 6
    5 X X X X X X X X X 5
    4 x X O X X X O O O 4
    3 X X O O X X O O O 3
    2 X O O o O O O O o 2
    1 X X O O O O o O O 1
      A B C D E F G H J
  Black 37 stones + 2 territory = 39; White 36 stones + 6 territory = 42, + 7.5 komi; 0 neutral
  both players passed: Black 39, White 42 + 7.5 komi; White wins by 10.5

Every point is counted: 39 + 42 = 81. Empty points that touch both colours would be neutral and count for no one. That is how area scoring handles a seki, two groups that share liberties where neither side can safely play: both groups keep their stones and the shared points are neutral. The tests build a seki and check both the score and that every move into it fails not_self_atari.

Information regimes¶

Go has no dice: the position is the whole truth. search and gated are worst-case (search assumes the worst reply; the gate's three properties hold against every reply). mcts is probabilistic: its numbers are win rates of random playouts. There is no clairvoyant benchmark for Go: the only randomness a player cannot see is the opponent's own tie-breaking seed, and a player that read it would measure how well one can exploit a pseudo-random generator, which says nothing about Go. See information regimes.

Play it¶

uv run grounded-decision play go --size 9x9                      # gated vs mcts, live board
uv run grounded-decision play go --agents gated,random --view history --max-steps 40 --delay 0
uv run grounded-decision play go --size 13x13 --agents mcts,greedy
uv run grounded-decision play go --size 9x9 --you                # you are Black
uv run grounded-decision play go --size 9x9 --you --guarded      # the gate checks your moves
uv run grounded-decision play go --list                          # every agent, in one line each

Type a point (D4), pass, q to quit or ? for help. With --guarded your move is only a proposal: if it fails a check, the engine plays its own safe move and tells you which check failed.

On a colour terminal, Black stones are ●, White ○, star points +, the last stone has a highlighted background, stones captured by the last move flash as ✶, and once the game is over each side's area is shaded (◦). In the plain ASCII style (--style ascii, or output that is not a terminal) the board is x, o, . and +.

Limits¶

The players are weak by Go standards: MCTS with a few hundred uniformly random playouts per move and no learned knowledge. The point of the example is the gate, not playing strength.
The playouts check simple ko only and never commit suicide; they are estimates. Every move actually played comes from the full rules.
The comparison is eight games per pairing; differences of one or two games mean nothing.
The move limit is not part of Tromp–Taylor. It changes nothing in practice for these players on 9 x 9 except when greedy, which never passes, keeps refilling a board it has lost.

Next: checkers, where the check is a verified search rather than a local pattern; the games overview.