My rules of Go, on arbitrary directed graphs

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 games¹ between two players, one for each finite² 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.

For the next conjecture, 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 those win-or-draw 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 Ω(2^N) 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.³

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