Going First

Introduction


Games for two players differ widely according to the received wisdom on the advantage of first play. In chess, starting is a major boost for an expert, but in shogi (Japanese chess) that isn't true. In mathematically analysed games, such as Nim or Gomoku, first play should be decisive. In the mancala game Oware, a proof has been announced that best play leads to a draw.

Here are some links to the games mentioned

Shogi
Nim
Gomoku
Mancala
Oware

In Hex, which is known to be a first-player win but for which the winning strategy isn't understood, the so-called 'pie method' is applied to give interesting games. The player who starts must give the second player the choice of changing sides after the first move. It's a version of 'I cut, you choose'. Naturally this depends on there being opening plays which are indifferent: only about half as useful as the best ones.

The system for Go is to add to the second player's score a number of points, in compensation for the first player's starting advantage. Some mathematics of parity lies behind that, in a well-concealed way.


How much is starting worth in Go?

The game of Go has been introduced in two previous articles on this site (' Behind the Rules ' and ' Sufficient but not Necessary '). Go is a game that is scored at the end, which means that in principle we could get a definite answer to the question, how much is it worth to play first? With best play on both sides, the winning margin might be, say, 8 points for the player who starts; and therefore we should compensate the second player by giving her or him an extra 8 points of score.

Put that way, it doesn't sound very sensible: the game should always be a draw, and so hardly worth playing competitively. Of course, we are a very long way from knowing so much about Go, except when it is played on tiny boards (up to about 5x5 in size, where 19x19 is the regulation grid). Tournaments everywhere use the principle of compensating the second player. Since by convention it is Black who starts, White is awarded a certain number of points to add to the final score. These extra points, called komi in Japanese, or dum if you're in Korea which is a hotbed of the game, are now set at a level of 6.5. The half-integer value prevents draws, which is a big plus in itself: we know that the correct value will be an integer, so in a sense what this tells you is that the belief is "it's 6 or 7 but we're not sure which".

Perhaps if you haven't played Go this sounds vague and unsatisfactory. What lies behind this number? How could one come up with such an estimate of the advantage of starting? Can one even prove mathematically that the first player has any advantage? (The answer to that one is that "passing" is allowed, so that if there were any reason to believe the opposite the game would never get properly started; but that's not a scenario with much connection to the real world.)

Most of the interesting and significant questions about Go have answers that come in terms of its rich and varied history in the countries of East Asia. The short answer in this case is that in Japan, komi has been the general system since about 50 years ago, as newspapers sponsored more tournaments and long, specially-arranged, matches between top players died out. At that point komi was usually 4.5 points; the higher value 5.5 came in a generation ago, and 6.5 was introduced in Japan only in 2002. The statistics have always pointed to an advantage for Black, the first player, with the lower values of komi; and professional players have over time adapted to playing with komi by using more aggressive strategies when starting. The process, resembling an 'arms race' in which opening theories for Black and White are the weapons, may not yet have reached its conclusion.

Naturally I'm not going to try here to give a compressed version of half a century of Go opening theory. The mathematics in this article will go back to the fundamentals of scoring, to explain a matter that is often discussed by players. It relates to the fact that there are two ways of performing scoring in Go, which give results that are almost identical - but not quite. Firstly I want to explain why this isn't a matter of much concern for players who take up Go for fun - which would be almost everyone. And then I'll reveal what a little piece of number theory has to do with the difficulty of answering the question I'm sure is on your lips - "is komi 6.5 now in China, too?" The correct Chinese term is in fact tiemu.



This is a typical end-position in a game, on a small 7x7 board to keep things simple. There are some of Black's stones hopelessly cut off in White's area: three of them, in the lower right.

The first method of scoring is called area scoring . This is the method sketched in the 'Behind the Rules' article. There are 49 intersections on the board, and controlling half of them would give a target area of 25. Black's area consists of the top two rows of seven points, six in the third row, two in the fourth row and one in the fifth row: for a grand total of 23. Bad luck: that means White controls 26. The three stranded stones are disregarded - in fact White could easily have just taken them off the board right at the end of the game. Players with any experience simply take as read that these pieces contribute nothing to Black's score, and their removal is part of the 'mopping-up' talked about in 'Behind the Rules'.

The second method of scoring is called territory scoring . It involves smaller numbers, but two for each player: a count of empty territory, and the number of the opponent's stones taken. In fact in this game Black had taken three of White's stones; and White had taken two of Black's, to which we add the three hopeless stones in the diagram for a total of five.



Territory refers to empty points surrounded: we see eight points of territory, marked 'x', in this diagram, belonging to Black. White can be seen to have ten points of territory. Adding up, Black has 8+3 = 11 and White has 10+5 = 15. Again White wins, this time by four rather than three.

The area method is often called 'Chinese', and the territory method 'Japanese', because of the official rules used in those countries. Since Taiwan uses area counting and Korean players territory counting, it is better to have more abstract names. What is the relationship between these ways of scoring? Here both do give the game to White, without even introducing any compensation; but it isn't so clear what is going on.

A few basic equations will help. Each player's area is made up of empty territory plus the number of points occupied by safe stones: say we write

Area(Black) = Territory(Black) + Safe(Black)

and the same for White. Also each stone played by Black will end up either as a safe stone or a captured stone (let's leave out the possible complication of seki, mentioned in the 'Sufficient but not Necessary' article). So we have a further pair of equations like

Stones(Black) = Safe(Black) + Captured(Black) .

The difference

Area(Black) - Area(White)

is the margin in the game measured by the area scoring method. By rearranging what we have so far we can get this:

Area(Black) - Area(White) = (Territory(Black) + Captured(White)) - (Territory(White) + Captured(Black)) - (Stones(Black) - Stones(White)).

What this says is that any difference between the margins as measured by the area and territory methods is to be attributed solely to the players having played different numbers of stones. In a normal game Black starts and the players don't pass until the end. Therefore the term

Stones(Black) - Stones(White))

is expected to be 0 or 1, depending on whether Black or White plays the final stone in the game. The small board example above did have Black playing last, with a total of 20 plays against White's 19 (as you can work out from the data already given). The one-point discrepancy (margin of three with area scoring against four with territory scoring) is thereby explained.

In most cases this doesn't change the result of the game: only if the final point of area taken by Black makes all the difference. You would need to be quite skilful to notice the effect.

There is something further, though. We will have another equation.

Area(Black) + Area(White) = Area of the board.

That's because the game will go on until every point is claimed or controlled by someone: we are leaving aside the seki positions that would impede this happening. The size of board is always chosen odd, in order to rule out simple imitative play of the 180 degree-rotation kind. Therefore the board area is an odd number: and one of the players' areas will be an even number, one odd.

In area scoring one compensates the second player by saying that Black, the first player, needs not only to have more area, for example 181 points out of the 361 on a 19x19 board, but slightly in excess of that, for example 184. If an area score split as 184/177 or better is a win for Black, but 183/178 or worse a win for White, how does that translate into territory terms?

The fact is that 184 - 177 = 7 while 183 - 178 = 5, and we can't have difference 6: this is how the parity effect of a board of odd size manifests itself. By setting 185 as the target score for Black, recently, the Chinese authorities have in fact made a larger step than the Japanese authorities did in changing komi from 5.5 to 6.5.

Conclusion

The two methods of scoring lead to very slightly different games. It is hard, though, to imagine human players strong enough to be able to exploit the distinction: games theorists led by Professor Elwyn Berlekamp at Berkeley have worked very hard on the issue of who gets the last scoring point. To most players it looks more like a random bonus to the first player. To say that area scoring, which is more easily founded purely mathematically speaking, is somehow better, is to miss important aspects.