I’m having trouble understanding how to apply the ko rule. For instance, in the description in Wikipedia, there is an example where the ko rule can potentially apply. But suppose there were two, or three, or four such scenarios on the board. Does one really have to keep track of all the past states of the board? Would you just keep going round-and-round, and whoever created the last original board configuration wins those points?
The theoretical answer depends whose rules you are using, because different countries use different rules, and have different ways of dealing with the multi-ko1 situation you describe.
In practice this almost never arises, and keeping track is usually easy, as something else happens to change the whole-board state, such as a move on a previously unoccupied point – note that the rule applies to the state of the entire board. It therefore also usually makes no difference which rules you use. Also, though it is common to end a game with many half-point kos2, there is no advantage to fighting more than one of them: correct play is to leave them all till there are no other points to be made, then connect if you can, take if you can’t and only fight the very last one.
Rules currently in use
All bodies forbid immediate recapture. The main approaches to complex repetitive positions are:
- Superko: You are not allowed to recreate a whole-board position that has already occurred in the game. Different bodies forbid this in different circumstances:
- Positional Superko (China, in theory): always.
- Chinese Superko (China, in practice): as a result of immediate recapture or “Sending two, returning one” (and I do not know what they do otherwise).
- Situational Superko (US, NZ): if it leaves the same player to move.
- Natural Situational Superko (UK): as the result of a move (not a pass) by the same player.
- No result (Japan, Korea): If a position is repeated, the game has “no result” and must usually be replayed.
- Long cycle rule (Computer Olympiad): If a position is repeated, the game stops and the result is purely determined by the number of captures by both sides since it first occurred.
- The currently accepted answer (by GendoIkari) is a misleading, because it only deals with the “basic ko rule” (forbidding immediate recapture), on which all bodies agree, and its tactical consequences.
- Brian Tyler’s answer explains how computer programmes detect repetitions with Zobrist hashing.
(As of 2020-04-08) Wikipedia gives more details in the article Rules of Go than at the link you gave, but for a comprehensive discussion you are better off with the article Superko in Sensei’s Library. For the correct order of play in half-point kos at the end of the game, see the article. Half-point Ko (also Sensei’s Library).
It is a shame you could not share with us the game with your son where this arose, which would have been interesting.
1 A “ko” refers here to a single position where capture-recapture would be possible if not forbidden.
2 A half-point ko is one where all that is at stake is the capture itself. This excludes kos for the life of a group or just to decide whether a point of territory has to be filled.
3 “Sending two, returning one” is a situation (usually part of a seki) in which one side can sacrifice two stones, and then recapture, recreating the previous position. This could be used to prolong the game indefinitely, though each cycle costs one point if territory scoring is used.
Ko only prevents a player from making a move that would have the effect of returning the board to the position that it was in just before his opponent's last move only. So the only thing you ever need to keep track of is what the board was like just before your opponent made his last move; you cannot move such that it would recreate that position.
All the further description in the wiki is explaining what a player will do if the move they want to make it prevented by ko. They make a move somewhere else on the board that forces black to respond to it; thus freeing them to make the play that they couldn't have played the previous turn due to ko.
Super Ko can be detected efficiently using Zobrist hashing.
The idea is to pick a random 64-bit integer to represent each of the
2x19x19 = 722 positions on the board. The empty board has a hash value of 0. When you add a stone to the board you
XOR the current hash of the board by the hash value that represents the stone at that position. You do the same for removal (
XOR being self inverse). Now you have compressed the game state into a single 64-bit integer and you simply check to see if you have seen this integer before.
The assumption is that there are no hash collisions. This is clearly not true because there are
3^361 board states (although many will be illegal) and your hash is
< 64^2. However, the assumption is that in your game of a few hundred moves, the chances of getting a collision is so small that it isn't worth worrying about. If you get a collision, you could check it if you store the full state, but it is so unlikely that you would find anything but a perfect match, that you may as well not bother.
You need something like three kos to do this.
But let's say that there are two players, X and Y. Player X takes the first ko. Player Y takes a second ko as a "ko threat." Player X takes a third ko in response. Player Y re-takes the first ko. Etc.
The ko rule serves to prevent repetition between one or two kos. But if there are enough kos so that you can take them in a "round robin," then the game could go on endlessly.