Analysis of Ultimate Go

    Keywords: Rules

(There is a discussion section at the bottom: please comment there. Thanks in advance!)


Analysis of Ultimate Go

I. Abstract

Rulesets of Go are roughly divided into two flavors: “area scoring” (e.g. Chinese rules) and “territory scoring” (e.g. Japanese rules). Area-scoring rulesets tend to be quite simple, however they usually share the “dame parity” disadvantage: in very close games the result might depend on the parity of the number of neutral (or dame) points. Territory-scoring rulesets manage to dispose of the dame-parity issue (among other things), but at the cost of becoming quite involved, albeit following a clear underlying logic.

The Ultimate Go rules presented in this note aim to be simple, and at the same time solve the dame-parity issue. We take the very simple “No-pass Go with prisoner return” ruleset and add the device of ultimate prisoners, in order to solve the dame-parity issue in a way free of hypothetical play and\or a moderator. This device can be thought of as a simple and unambiguous realization of the “Taiwan Rule”.


II. Background and motivation

Go is a game with very simple rules, or so goes the common wisdom. However, the various rulesets for the game of Go are not always so simple. In particular the game has two phases (moving and counting), the latter phase involving terms like ‘score’, ‘territory’ or ‘area’, and sometimes terms like ‘alive’ and ‘seki’. These terms, albeit beautiful and logical, all stem from one common underlying logic that derives from the basic notion of ‘capture’, so it feels like they should all be implicit in the ruleset, rather than explicit.

In addition simpler rulesets, which are usually of the “area scoring” flavor (e.g. Chinese rules), share the following disadvantage: in a very close game, right before the “dame filling” phase of the endgame, the result may depend on the parity of the number of dame points. This is undesirable, as it introduces a seemingly random element to a hard-fought game.

The ruleset suggested in this note mentions none of the above terms. The only non-trivial concept is the one of capture (referred to below as removal of “surrounded” stones from the board), and all other terms are implicit from an analysis of the ruleset, including: score, territory, dame, seki, etc. The underlying logic, motivating the step back from the usual rulesets to these more fundamental rules, is best explained by considering the following question: why should players thrive for more territory? Well, because it will allow them to have a larger number of safe moves at the “counting phase” of the game, delaying the (almost) inevitable loss of one of them.

The counting phase, where players only delay the inevitable, will be implicit from the game’s analysis, not explicit in the rules. In particular players may fail to agree whether this “counting phase” has begun, and yet no harm will come to the flow of play, nor to the result. In particular no “hypothetical play” phase will be necessary, even in case of such disagreement.

The main advantage of the suggested ruleset over simple rulesets of the “area scoring” flavor is that it manages to avoid the “dame parity” issue, and it does that with only a slight complication of the rules (via the device of ultimate prisoners).


III. Rules of Ultimate Go

0. Ultimate Go is a game played between two players, Black and White. Each player has an endless supply of identical stones of her color, and a prisoner bowl.

1. The board consists of 19 horizontal and 19 vertical lines, and the stones are placed on their 19*19 intersections.

2. A stone on the board is said to be surrounded if there is no connected path along the lines from that stone to an empty intersection which avoids all opponent stones.

3. Before the game starts the board is empty, as are the prisoner bowls. Each player takes one stone from her opponent’s supply and places it next to her prisoner bowl. That stone is the ultimate prisoner of that player. Players move alternately, Black moving first.

4. A placement consists of a player placing a stone from her supply on an empty intersection, then checking which opponent stones are surrounded, and if such stones exist - removing all of them from the board to her prisoner bowl.

5. A placement is legal if the placed stone is not surrounded in the resulting board position, and furthermore that board position has not occurred in the game.

6. A delay consists of a player returning either one of her prisoners (i.e. a stone from her prisoner bowl) or her ultimate prisoner to her opponent’s supply. In the latter case this delay is called the ultimate delay.

7. A move consists of either a legal placement or a delay.

8. If a player plays her ultimate delay second (i.e. after her opponent played his ultimate delay) then she should return her ultimate prisoner next to her opponent’s supply. From now on her opponent may declare a draw by taking that stone from next to his supply and moving it into his supply.

9. At a player’s turn she must do one of the following: make a move; declare a draw, in which case the game ends with a draw; resign the game, in which case her opponent wins.

Remarks:

• In order to give a Komi of K a player should surrender K stones to her opponent’s prisoner bowl before game starts.

• In order to play with Handicap H Black should give White a Komi of H-1, and then White should delay in her first H-1 moves.

• As usual with (Go) rulesets, players may agree on anything that they deem will leave the result unchanged, e.g. removing dead stones, expediating the "counting phase" by automatic moves, automatic prisoner exchange, etc. The ruleset allows a player to prolong the game (either because of misjudging the status of the game, or intentionally), but this prolongation is usually as bad as any other ruleset allows. In a close game a loser with such prolongation intentions may harm her own position instead of resigning, and the winner might be forced to capture one of her groups (and prolong the game longer than what other rulesets allow). However, this disadvantage is more than compensated by the simplicity of the rules.

• The sole purpose of adding ultimate prisoners is for the outcome of a close game not to depend on the parity of the number of neutral intersections. This independence is true even if it’s agreed that a draw result actually leads e.g. to a White win, of course. If we omit ultimate prisoners we call the resulting ruleset Fundamental Go. This latter ruleset is actually mentioned very briefly in Sensei’s Library as No pass Go with prisoner return (see References below), as the author discovered while writing this note.

• The above rules generally favor ‘territory scoring’ over ‘area scoring’, e.g. seki eyes don’t count as territory – because you can’t play in them safely (though in some Seki-related subtleties these rules do "agree" with area scoring, e.g. a false eye in a Seki). However filling dames is part of the game (as is “counting” for that matter). The rules go one further than Japanese ones, and dictate a 2-point “group tax” on each non-Seki living group.

• There is no “pass”, so when it’s Black’s turn the number of black stones “in the game” (i.e. on the board + prisoners) equals precisely the number of white stones in the game, and when it’s White’s turn the difference is precisely 1. This is true assuming no Komi, of course.

• Every game has a finite number of moves: the number of placements is bounded by 3^(19*19) since a board position is just a function from the set of intersections to {empty, black, white}, and the number of delays is clearly bounded by the number of placements + 2. In Fundamental Go a draw is impossible, hence on every node of the game tree either Black or White has a winning strategy. This “strategy” is just a huge book containing answers to all possible future moves by the opponent.

• Rule 5 favors “positional superko” mainly for simplicity of statement, but also since “situational superko” would practically allow a “reverse delay” of surrendering one prisoner to the opponent, which seems undesirable. Since delays are always allowed (even after such a reverse delay) the same situation (board position + turn) can be repeated in the situational superko variant, making this variant even less desirable.


IV. Analysis of Fundamental Go

Our aim is to describe the optimal use of ultimate prisoners. When played correctly (which should be very easy for most Go players, at least in most games) the two ultimate delays will signal transitions between very different phases of the game - the game actually “ends” (in the usual sense of the word) after the first ultimate delay; what comes after that are “counting” moves; and these end with the second ultimate delay. In order to achieve that aim we first analyze the game without ultimate prisoners, i.e. Fundamental Go. Remember that in Fundamental Go in each node of the game tree one of the players has a winning strategy (in the sense of Game Theory).

At any stage of the game the current score is defined as follows: assume Black has a winning strategy. Clearly if White got enough “mid-game Komi”, i.e. Black surrendered enough stones to White’s prisoner bowl, White would have a winning strategy. As an extreme upper bound, if Black gave a mid-game Komi of K=360 White can win by simply delaying until board has 360 black stones and Black can’t move (assuming no initial Komi). Also the set of values K of mid-game Komi sufficing for a White win is closed upwards – if White can win with K extra prisoners, she can certainly win with more than K.

Now we define the score as follows:

score := min { K | White has a win with a mid-game Komi of K } – 0.5

If White has a winning strategy then we define similarly:

score := - min { K | Black has a win with a mid-game Komi of K } + 0.5

Clearly the score is positive when Black has a win and negative when White has a win. Its absolute value |score| is the average between the minimal mid-game Komi giving the losing player a victory, and the maximal mid-game Komi keeping the winner unchanged (this maximum might be 0).

Note that this definition is usually theoretical, but when the game nears its “end” (in the usual sense of the word) it becomes quite practical to evaluate the score. Also note that the score is a function of the complete situation, defined to include the following data: (a) whose turn is it; (b) the board position; and (c) the set of previous board positions in the game. Note that the prisoner-difference defined as #(black prisoners) - #(white prisoners) can be deduced from (a) and (b) (and the Komi, if any). The absolute number of prisoners is irrelevant – adding one prisoner to each player clearly does not affect the score, since if a player had a win before the addition she can simply wait with her extra prisoner, and use it to delay precisely after her opponent used his extra prisoner to delay.

We claim that no move by Black can increase the score (and no move by White can decrease it). Assume for contradiction Black has a move that increases the score by at least 1. After giving enough mid-game Komi to the correct player that means White had a win before Black’s move (score = -0.5), but is losing after it (score >= +0.5) – a contradiction, since a win by White means she has a winning answer to every move by Black. A move is called optimal if it keeps the score fixed. The best way to think of this is as follows: trying to play optimally means playing as if one doesn’t know the value (or direction) of the Komi. The cost of a move is the (non-negative) amount by which it changes the score. So after a Black move the score decreases by the move’s cost, and after a White move the score increases by the move’s cost.

Note that, somewhat surprisingly, at some point in the game a player might have no optimal moves (this is unlike a minimax score). In detail, this happens when a player has no prisoners, and every legal placement puts one of her own living groups in atari. In such a situation the player should resign the game, and the score (in favor of the winner) can then be usually computed as 0.5 plus the number of safe moves the winner can still make (this number might be 0).


V. Phases of a game of Fundamental Go

Assume that the player to make a move has a one-time option to play a “reverse delay”, i.e. to surrender a prisoner to the opponent. Clearly the cost of such a reverse delay equals the cost of a delay, and it’s introduced only because sometimes (when prisoner bowl is empty) no delay is possible. We call this cost of a delay \ reverse delay the current sente level - again, this is a function of the complete situation (defined above), and is purely theoretical until the endgame. This term might sound non-fitting in certain occasions, but it should again (like the term 'optimal') be thought of as the urgency of play assuming the player doesn't know the Komi.

Now the set of optimal moves can’t be empty – to see that introduce mid-game Komi so that the player to make a move has the closest win possible (i.e. |score| = 0.5), and let that player make one of her winning moves (and if a delay of a mid-game Komi stone is her only option – she can reverse delay). There are three distinct scenarios:

1. Normal play phase: the sente level is positive (i.e. the set of optimal moves consists only of placements). It’s of course very hard to play optimally, although after a strong sente move (i.e. when the cost of a delay is very high), it might be easier. Of course better players will tend to make moves with lower costs.

[Diagram]
Diagram 1: groups have no outside liberties  

2. Counting phase: the sente level equals 0, and the set of optimal moves includes moves other than the reverse delay (a delay and\or some placements). This can happen slightly before the usual counting starts, e.g. there might be an even number of neutral points, or perhaps two miai moves on board making territory boundaries not completely defined yet (like a and b in diagram 1).

The number of moves each player will make in this phase (after filling the even number of dames etc., and assuming players won't place dead stones) is roughly the “territory score” of the losing player, i.e. the number of territory points (computed with a “group tax” of two points per non-seki living shape) plus the total number of prisoners and dead stones. However, note that if players insist on playing optimally throughout the counting phase they might be forced to place dead stones - in diagram 2, after Black captures at c, White is forced to play a dead stone (unless he reaches an agreement with Black).

[Diagram]
Diagram 2  

3. You–should-resign-now phase: the sente level is 0, and the set of optimal moves includes only the reverse delay. That means the player has no prisoners, and all legal placements harm her position (i.e. all living groups are completely filled except for two eyes, all Seki situations are played out for that player, an eternal Ko was just played, etc.). That player should resign the game, and the score can then (roughly) be computed by counting how many moves the winner can safely make.


VI. Optimal use of ultimate prisoners

The above analysis applies equally well to Ultimate Go if we ignore the “declare a draw” option (clearly adding a prisoner to each player has no effect per se). Now consider the following question: when should the second ultimate delay be played? Clearly a player should do that only if it’s her unique optimal move, i.e. we’ve almost reached phase 3 above. The result will thus be either a win for her opponent (if he has at least one optimal move), or a draw (if he has none). Therefore, the second ultimate delay (if played optimally, which is trivial as noted) signals the end of the counting phase (phase 2 above). Note that the result of the game is affected by the “declare a draw” option only in the following scenario: the player who played an ultimate delay first is about to lose (if we ignore this option) by the closest possible margin (i.e. |score| = 0.5).

Given the above it’s not hard to see that the first ultimate delay should be played only if a delay is one of the player’s optimal moves (i.e. when the sente level is 0), since otherwise the cost of the ultimate delay is at least 1, and the (small) advantage of being the first to play an ultimate delay is nullified. However, on the first occasion that a delay is optimal the player usually won’t have to play the ultimate delay immediately - there might be other optimal moves after which the sente level becomes positive, e.g. filling one dame out of an even number of dames (which changes the sente level from 0 to 1). After all dames are filled (and all miai moves are played, etc.) that player will have to play an ultimate delay, lest her opponent will do just that (and gain the advantage of being able to turn a tight loss into a draw). At any rate, the first ultimate delay signals the transition from the normal play phase (phase 1 above) to the counting phase. As mentioned this transition can be slightly fuzzy, but if the player waits till not playing the ultimate delay is a mistake then it will signal the end of dame filling and the beginning of proper counting.


VII. Examples

We give two examples where the Fundamental Go score (defined above) is +0.5, but in the first example the game ends in a draw (because the Ultimate-Go-adjusted territories are equal), while in the second example Black wins (because she has more "territory"). Note that the concept of "territory" implicit in Ultimate Go is different than what most territory-scoring rulesets dictate, e.g. some seki false eyes do count as points - see Seki false eye example.

[Diagram]
Black to play, no "regular" prisoners  

In the first example each player has a territory of 2 (after deducting the 2-point group tax).

[Diagram]
Optimal play  

W4 = ultimate delay

B9 = ultimate delay

W10 = declare a draw

White could also play her ultimate delay earlier (instead of W2).

[Diagram]
Black's attempt to deny the draw  

If Black attempts to deny White the opportunity to declare a draw then she lets White fill the last dame, and of course loses:

B1 = ultimate delay

B9 = resign

[Diagram]
White to play, no "regular" prisoners  

In the second example the Fundamental Go score is also +0.5, but this time we want Black to win, since she has a territorial lead of 1 point. Indeed, the ultimate delay device does not allow White to force a draw this time.

[Diagram]
Optimal play - Black wins  

B4 = ultimate delay

W9 = ultimate delay

W11 = resign (this is a "1-point win", since White only needs 1 extra prisoner to force a draw)

[Diagram]
White's failed attempt  

If White attempts to gain by ultimate-delaying first this doesn't help of course - she actually loses by 2 points instead of 1 (i.e. she needs more extra prisoners to force a draw).

W1 = ultimate delay

W9 = resign (and this time White needs 2 extra prisoners to force a draw, so it's a "2-point win" for Black).


VIII. Recap

Rulesets of Go usually come in two flavors: “area scoring” and “territory scoring”. Area-scoring rulesets tend to be quite simple, although they also contain concepts which ought to be implicit rather than explicit. However, such rulesets share the “dame parity” disadvantage, which apart from posing an aesthetic problem can become a very practical problem in close games. Territory-scoring rulesets manage to dispose of the dame-parity issue (and other issues which are mainly a matter of taste, like “should a Seki eye be counted as territory?”), but at the cost of becoming quite involved, albeit following a clear underlying logic.

The Ultimate Go rules presented above aim to be simple, and at the same time solve the dame-parity issue. We take the “no-pass Go with prisoner return” ruleset, and add the device of ultimate prisoners in order to solve the dame-parity issue in a way free of a moderator and\or hypothetical play. This device can be thought of as a simple and unambiguous realization of the “Taiwan Rule”, of which the author learned while finishing this note (see Ikeda’s book in the References below).


IX. References

• Sensei’s Library “no pass Go” page: [ext] https://senseis.xmp.net/?NoPassGo .

• Ikeda’s book: [ext] https://gobase.org/studying/rules/ikeda/ (dame parity in section 3.5, the Taiwan Rule in section 3.6).


Yoav Yaffe


Discussion:

1.


Analysis of Ultimate Go last edited by 185.184.244.169 on May 31, 2020 - 16:51
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library