Clash of the Titans, Game 1
Analysis by Josh Jordan
Game 1 of the World Game of Sprouts Association-sponsored “2011 Clash of the Titans” match between WGOSA World Champion Roman Khorkov and me took place over email in early February, 2011. I was assisted by my computer program Aunt Beast, while Roman used only his brain. After I won the game, Roman wrote:
“This was an amazing game. Very intriguing... It added my white hair. It will be good if you make a detailed analysis. We simply have to bring it to the public!”
As requested, here is my analysis. First, though, let's have a look at these two titans.
| 
|
| Roman Khorkov | Josh Jordan |
27- (Khorkov*)
Sprouts is a two-player pencil-and-paper game invented in the 1960s by mathematicians John Conway and Michael Patterson. The game starts with a field of dots on an otherwise-empty piece of paper. The move is to add a new dot along with two lines joining it to existing dots subject to the conditions that (a) lines may not cross and (b) no dot may have more than 3 lines coming out of it. (Mathematically speaking, each move extends a plane multigraph of maximum degree 3 by adding a new vertex of degree 2.) The players alternate turns until it is no longer possible to move, at which point the game is over. Like any impartial combinatorial game, sprouts can be played with two different win conditions: (a) last player wins or (b) last player loses. The former is known as normal play, the latter as misère (pronounced something like "MEE-zair") play.
The top human players seem to be able to play normal sprouts quite accurately. For this reason, the emphasis in modern tournament sprouts has shifted to misère play. (According to the Wikipedia entry on misère games, "Perhaps the only misère combinatorial game played competitively in an organized forum is Sprouts.") However, skill in normal play does not go to waste: the main principle of human misère sprouts strategy is to to create a large component with firm nim-values (see below), in the presence of which the game's misère outcome is usually the same as its normal outcome. (A component is a minimal contiguous region of the game with the property that a move in that region does not affect the moves available in the rest of the game.)
In sprouts, one player serves, that is, determines the number of initial spots and the win condition (normal or misère), and the other player then decides who plays first.. The player who plays first is known as Left; the other is known as Right. Here Roman has served 27 spots, misère. Had he intended normal play, the serve would have been written as "27+".
27- (Jordan+Aunt Beast - Khorkov*) 1(28)2
The shape that results from connects two initial spots like this is known as an anago.
Even though 27- is thought to be a win for Right, I opt to move first, in part to show how a computer can help win a theoretically losing position. We're a long way from knowing for sure whether 27- is a win for Left or a win for Right, so in the opening phase I merely try to make the position more complex, in accordance with the Enough Rope Principle.
The diagrams here follow Winning Ways by coloring Left's move bLue and Right's move Red.
1(29)1[2,3]
Roman responds with the analogue of the correct reply in 15-. According to theory, adding a multiple of 6 spots to a region with a large number of spots doesn't change the outcome of the game, so this move should also work for 27-.
4(30)29
Continuing the standard opening for 15-, I make a *3 component in S(2). (The notation S(x) means the entire component containing spot x.) I will try to make more of these *2 and *3 components as the game continues. An identical pair of nim-heaps of size at least 2 make a component with firm nim-values 00. In misère play, when the position contains a component with firm nim-values, further identical pairs of these nim-heaps can can usually be ignored as in normal play, but not always…
It may be useful to recall some definitions and notation. A nim-heap of size x is denoted by *a. The nim-value of a position x is the size of the nim-heap that must be adjoined to x to result in a P-position, that is, a loss for the player to move. A position that is a win for the player to move is known as an N-position.
The nim-values of a position are its normal nim-value a and its misère nim-value b, written ab. A component with firm nim-values is a component with identical normal and misère nim-values. This is not the same as a firm component, which is a tame component with firm nim-values. A component x is tame whenever there exist nim-heaps a, b, …, c such that, for any impartial combinatorial game y, a+b+…+c+y has the same misère outcome as x+y. (Note that y doesn't necessarily have to follow the rules of sprouts or nim.) Most components with firm nim-values are not tame. A partially-correct table of nim-values for various common sprouts components can be found at Playing Sprouts with Misère Grundy Numbers (Peltier, 2008).
4(31)4[5-20]
Roman makes a group of 16 spots and a group of 7. If spots 30 and 31 were removed, both of these groups would be components with firm nim-values of 11.
5(32)5[6-9]
With Aunt Beast, I try to disrupt the human strategy by steering the game into positions in which the normal outcome differs from the misère outcome, even in the presence of components with firm nim-values. Playing those types of positions correctly seems to be very difficult for today's human sprouts players.
I have noticed that many of these tricky positions contain groups of four spots, so I try to create such a group here. This was almost certainly a mistake, since it allows Roman to effectively remove those four spots from the game on his next move.
5(33)32[6]
Roman simplifies. S(6) is now effectively dead (equivalent to *0).
Dead spots and components which I know to be effectively dead (equivalent to *0, either by themselves or in combination with other components) are colored gray in the diagrams. Further play in these dead components is pointless.
10(34)11
Trying again to add complexity, I fall back on the usual approach of playing an anago.
30(35)31[21,22]
I expect Roman to close off the anago with 10(35)10[11] or 10(35)10[11,12], but he surprises me by playing this move instead, splitting the rest of the position into two components with nim-values 30 and 00.
I think it's bad practice for a human player in a theoretically winning position to leave an anago exposed like this, since the opponent can use it to create complex positions that could otherwise be prevented from arising.
In the diagram, the nim-values ab of various components have been noted in boxes. When a box contains *n, the component is equivalent to a nim-heap of size n.
23(36)24
Trying to make things even more complex, I play a third anago.
21(37)35
Roman is now facing two exposed anagos, a situation in which he does not usually find himself.
10(38)10[11]
This move looks to have been a mistake on my part. Even if the 01 component were equivalent to *0, the remaining components do not make a misère P-position. If instead the 30 component is replaced by *3, the resulting position is also not a misère P-position.
My move does have a possible virtue: there are only three replies that make the normal-play nim-values sum to *0 by changing the 30 component into a 01, namely 23(39)23, 25(39)36, and 23(39)27. Each of these are subtly different from a misère perspective, and each yields a different unusual configuration in S(23). These unusual configurations are unlikely to have been well-studied by human sprouts theorists.
Instead, though, I should have played 12(38)34 or 12(38)13, both of which better accord with the Enough Rope Principle.
12(39)12[13]
Roman returns to a position in which the normal-play nim-values sum to *0. Interestingly, though, he does so by raising the nim-values of S(11) from 01 to 34.
23(40)23[25]
I have set a trap. Aunt Beast still can't figure out who wins here, but she can see that Roman loses if he moves in the 51 component. It's likely that he will, since human players can't abide positions with normal-play nim-values greater than 3.
Update (March 2011): In subsequent analysis, Aunt Beast determined that this move is not just a trap — it actually wins! How strange that *2 + *2 + 51 + 34 would yield a misere P-position. If God doesn't play dice with the universe, he must not play sprouts either, because both seem equally random.
26(41)26 N
Roman moves in the 51 component, reducing it to *3. Now Aunt Beast can see that Roman has lost. Adopting a notation from combinatorial game theory, I have appended "N" to losing moves, which stands for "next player wins".
14(42)15 P
There are six winning options here: 34(42)38, 12(42)13, 14(42)14[15-16,38], 14(42)14[15-18], 14(42)14[15-17], and 14(42)15. I like to play an anago whenever possible. Aunt Beast didn't compute the exact normal-play nim-value of the anago component during the game, but in the course of writing this article, I used Glop to determine that it is at least 5.
Adopting another notation from combinatorial game theory, I have appended "P" to winning moves, which stands for "previous player wins". In this case, the previous player is the person who just played the move, that is, me.
14(43)14[16-20] N
Looping on a tail of the anago, Roman encloses a group of 5 spots.
According to the "component with firm nim-values" heuristic, this position's nim-values 33 + *3 + *3 + *3 would seem to yield a clear 00, that is, a P-position in normal and misère play. Actually, though, it's a misère N-position — a perfect example of a case in which the heuristic goes horribly wrong.
Even though it loses, this is still an excellent move: it leaves me with only one winning reply, a reply which would be impossible to find today (early 2011) without the aid of a computer.
16(44)16[43] P
This was the only winning move. The fact that this position is P cannot be predicted by a theory that looks only at the nim-values of its components.
17(45)17[18,19] N
Roman adds an additional level of nesting to the loops and pivots in S(11). This is another excellent move that leaves me only one winning reply.
In 2006, Dan Hoey pointed out that a related class of positions containing nested pivot spots “tend to have reasonably large game complexity, since Dawson's Kayles produces nim-values up to *9.” For more on this, see these messages in the “Dawson's Sprouts” thread on sprouts-theory.
18(46)19 P
Again, this was the only winning move. Now the game's outcome and its nim-values begin to correspond: the 13 component has restive nim-values, so we can guess that the position is P if and only if *3 is equal to *3 + *2 + *2, which indeed it is.
26(47)41 N
Ordinarily, when you are winning, the answer to an anago in an otherwise-empty region is to convert it to a big loop, but doing that here via 18(47)19 allows four different winning replies, while Roman's move allows only one.
21(48)21[22] P
For the third time in a row, this was the only winning move. Game trees in which two moves in a row have unique winning replies tend to be difficult for humans to analyze, so I can only imagine what a tree with three in a row is like.
This position is clearly P on the basis of its nim-values alone.
2(49)2[3] N
This is another good move; it allows me only two winning replies.
12(50@13)39 P
This was one of only two winning moves; the other was 17(50)46, which leaves S(11) with nim-values 61.
Roman usually resigns in losing positions with such few remaining live spots. Either the normal-play nim-value of 5 is clouding his vision, or he is doing an excellent job of defending a losing position, by forcing his opponent to play very accurately.
18(51)19 N
Roman plays yet another excellent move which allows me only one winning reply.
17(52)18 P
This was the only winning move.
20(53)20[45] N
Another strong move that leaves me only two winning replies.
16(54@20)44 I P
After this move, S(17) is effectively dead and Roman concedes. This was the simpler of only two winning moves; the other was 19(54@45)46, with nim-values 50.
Josh Jordan, February, 2011
