My rules of Go, on arbitrary directed graphs

Approximate readability: 9.20 (8662 characters, 1871 words, 106 sentences, 4.63 characters per word, 17.65 words per sentence)

These are rules for the game of Go that elegantly generalize the game to arbitrary directed graphs, made by my sibling and I. (This post probably won't be interesting unless you're Go player and/or a mathematician.)

Our ruleset uses stone scoring because it's super simple and clear what that means. It uses divide-and-choose for komi because the first move is more valuable on some graphs than others. It uses a novel divide-and-choose method to address (super)ko. An ordinary superko rule would be well-defined here too.

The rules

INTRO: Go is a class of infinite combinatorial games1 between two players, one for each finite2 directed graph and starting state. Points have three possible states: empty, filled with a black stone, and filled with a white stone. (Most common is a 19x19 grid with each point having arcs to the orthogonally adjacent points, in which all points begin empty.) Each player has a rational-number score that begins at 0. There is also a set of previous board states, the “history”.

KOMI: The first player chooses a rational number, Komi. The second player chooses to be “White” or “Black”. The first player becomes the other color. White gains Komi score.

TURNS: Black and White take turns, with Black going first. Before each turn, the current position is added to the history. Then either player may delete the entire history. On your turn, you either place a stone of your color on an empty point, or pass.

CAPTURING: A stone's “liberties” are the empty points reachable from it by a path whose internal points are stones of its color. After you place a stone, all opposite-color stones with no liberties are simultaneously removed, then all same-color stones with no liberties are simultaneously removed.

KO: After you place a stone, you may make a ko bid. In a ko bid, you choose a nonnegative rational amount of score. Your opponent may ignore it, or they may choose either player to be the “ko winner”. If they do: The ko winner may reset the board state to any state in the history. The ko loser gains the amount of score you chose. Then it becomes the ko winner's turn.

WINNING: The following actions are “unsustainable”, in increasing order of unsustainability: making a ko bid, choosing yourself to be a ko winner, ignoring a ko bid, deleting the history. A player's “unsustainability” is the most unsustainable action that they did infinitely many times. If either player did infinitely many unsustainable actions, the player with lower unsustainability wins. Otherwise, the scores are eventually constant, and the winner is determined by score and stones, as follows: a player's “live stones” are the points that eventually always contain a stone of that player's color. Each player adds their eventual score to their number of live stones, to get a final score. If one player has a higher final score than the other, that player wins. If neither player wins, it's a draw.

Notes

Although this game theoretically has infinite moves, it is practical to play in real life. Typically, both players would end the game by saying “I pass forever if you do”, and then it's understood that infinite passes have taken place.

The ko rule is quite fun. When you get in a loop (of any length), you delete the history, then the next time around the loop, you make a ko bid. That way, the ko winner can take an extra move from whichever point in the loop they prefer, but not from before the loop. Literally speaking, you can bid on any move, even if there isn't a ko. But with good players, if there's no actual infinite loop, there's no reason to make a ko bid, and no reason not to ignore one.

The “unsustainability” rule forces people to eventually answer ko bids instead of ignoring them forever. It includes “choosing yourself to be a ko winner” to deal with endgame kos that only one player can win. That player should be able to bid 0 instead of having to arbitrarily choose a small amount. This rule prevents the other player from just winning for 0 forever. In the case of complex loops, the unsustainability rule forces the players to offer bids that include the whole loop, rather than repeatedly deleting the history so that their opponent can only reset to points in the loop that are more favorable to themself.

The history deletion rule gives the game a cute property: two perfect players could theoretically sit down at a board and continue the game with perfect play, without knowing any of the history of that game. (They'd only need to know whose turn it was.)

I have a bunch of mathematical conjectures about this ruleset, but I haven't proved any of them. Proving things about infinite combinatorial games can be pretty hard.

“Perfect play” conjecture: For all graphs, with all starting states, there is a win-or-draw strategy for both players.

I will call a strategy “reasonable” if it is never unsustainable unless the opponent is more unsustainable. The idea is that if two reasonable strategies play against each other, the result should be sustainable.

“The ko rules basically work” conjecture: We may also require that such strategies are reasonable.

Score-independence conjecture: We may also require that such strategies' choices of move are independent of the current scores.

“Going first is good” conjecture: All graphs that start with an empty board have a win-or-draw strategy that chooses a nonnegative Komi.

“Perfect Komi” conjecture: On any graph, all win-or-draw strategies choose the same Komi.

“Score-independent strategies are score-maximizing” conjecture: On any graph, any reasonable, score-independent, win-or-draw strategy is also a score-maximizing strategy. That is, if the opponent is not unsustainable, it guarantees at least the maximum relative score that can be guaranteed by any strategy. This is technically a trivial corollary because any reasonable win-or-draw strategy guarantees at least 0 relative score, and 0 is always the maximum relative score that can be guaranteed in a game where the opponent also has a win-or-draw strategy. However, I claim that reasonable, score-independent, win-or-draw strategies also maximize their guaranteed relative score after any given incorrect play by the opponent, at which point it is possible to guarantee a relative score higher than 0.

Unstable components

Consider an isolated pair of points that are only connected to each other. Without a superko rule, the players can keep playing back and forth in this space.

Now, suppose there are N such pairs. With superko, the game can be completed, but it takes Ω(2N) moves to do so. Intuitively, it seems like games should be possible to complete in O(N) moves, where N is the number of points on the board. This is one of the reasons I didn't want to use a superko rule. (Our rules allow infinite loops, but at least the loop can begin within O(N) moves.)

In our rules, these pairs are always worth 0. That seems much more elegant to me. Neither player has an incentive to play in one. If either player does, the other player can just capture back indefinitely. So after all real points are decided, the game would end with them capturing back and forth forever, meaning that neither point becomes a live stone.3

Stability conjecture: Each graph is “stable” or “unstable”, independent of what stones start out in it. In an unstable graph, both players have a strategy that always wins if the opponent eventually passes. In a stable graph, both players have a win-or-draw strategy that always eventually passes. (Of all my conjectures, this is the one I'm least confident about. I haven't thought of any way the stability can be dependent on the stones, but Go does have some very weird corner cases even on a normal board.)

“A normal board is stable” conjecture: The 19x19 grid is a stable graph.

“Independence of disconnected settled boards” conjecture: If two win-or-draw strategies that always eventually pass play against each other on a stable graph, we call the resulting position a “settled board”. For any of the above conjectures, we can also require that the strategies' choices of move, other than deciding Komi, are independent of any combination of settled boards being added to the initial state as disconnected components, as long as their opponent doesn't play inside any of the settled boards. (Note that this is not true with a superko rule, because settled boards may contain unremovable ko threats.) Also, we can require that their choices of Komi should only differ by exactly the relative total numbers of stones on the added settled boards.

– Eli

Footnotes:
  1. Formally, an infinite combinatorial game can be defined like this: A “move” is a natural number. A “strategy” is a function from finite sequences of moves (the game history) to moves (the next move to play). When two strategies are matched up against each other, such that they take turns choosing the next move, they produce an infinite sequence of moves. A “game” is a function from infinite sequences of moves to a game result (who won). When you're defining an infinite combinatorial game, you usually don't specify exactly how the game's moves map to natural numbers, because that is tedious and unimportant. You only need to understand that the moves can be represented that way. back
  2. These rules can be generalized to infinite graphs, but they would have to be more complicated, and I haven't thought of an infinite graph that actually makes an interesting game. Here are some of the interesting cases:
    • An infinite normal board. Each player plays more live stones forever.
    • Infinitely many disconnected rows of 3 points, which start with white stones at the ends and empty points in the middle. Here, White has infinite stones on every turn, but Black captures all of them.
    • A normal board, plus infinitely many additional points that only have an arc to the bottom left corner of the normal board. This is equivalent to a normal game, except that owning that corner is worth infinite points. What's more, there can be a ko for ownership of that corner, which would be a ko with infinite value.
    • Uncountable graphs would require an expanded definition of infinite combinatorial games.
    back
  3. In an older version of our rules, placing stones was also an unsustainable action. With that variant, isolated pairs cause a sort of score leeway. Suppose three of them exist, and one player is ahead by 10 points elsewhere on the board. Then that player can still win even if they stop placing stones and allow the opponent to place stones in the three unstable components. But if the player is only 2 points up, the game will be a draw. Thus, there's a leeway of three points, meaning that you have to be more than three points ahead elsewhere to win. To me, score leeway still seems more elegant than the score being decided by superko behavior. However, it does also mean that perfect play isn't score-independent. back