Clash of the Titans, Game 1
Analysis by Josh Jordan
Game 1 of the World Game of Sprouts Associationsponsored “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 twoplayer pencilandpaper game invented in the 1960s by mathematicians John Conway and Michael Patterson. The game starts with a field of dots on an otherwiseempty 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 "MEEzair") 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 nimvalues (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 nimheaps of size at least 2 make a component with firm nimvalues 0^{0}. In misère play, when the position contains a component with firm nimvalues, further identical pairs of these nimheaps can can usually be ignored as in normal play, but not always…
It may be useful to recall some definitions and notation. A nimheap of size x is denoted by *a. The nimvalue of a position x is the size of the nimheap that must be adjoined to x to result in a Pposition, that is, a loss for the player to move. A position that is a win for the player to move is known as an Nposition.
The nimvalues of a position are its normal nimvalue a and its misère nimvalue b, written a^{b}. A component with firm nimvalues is a component with identical normal and misère nimvalues. This is not the same as a firm component, which is a tame component with firm nimvalues. A component x is tame whenever there exist nimheaps 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 nimvalues are not tame. A partiallycorrect table of nimvalues for various common sprouts components can be found at Playing Sprouts with
Misère Grundy Numbers (Peltier, 2008).
4(31)4[520]
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 nimvalues of 1^{1}.
5(32)5[69]
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 nimvalues. 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 nimvalues 3^{0} and 0^{0}.
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 nimvalues a^{b} of various components have been noted in boxes. When a box contains *n, the component is equivalent to a nimheap 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 0^{1} component were equivalent to *0, the remaining components do not make a misère Pposition. If instead the 3^{0} component is replaced by *3, the resulting position is also not a misère Pposition.
My move does have a possible virtue: there are only three replies that make the normalplay nimvalues sum to *0 by changing the 3^{0} component into a 0^{1}, 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 wellstudied 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 normalplay nimvalues sum to *0. Interestingly, though, he does so by raising the nimvalues of S(11) from 0^{1} to 3^{4}.
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 5^{1} component. It's likely that he will, since human players can't abide positions with normalplay nimvalues 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 + 5^{1} + 3^{4} would yield a misere Pposition. 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 5^{1} 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[1516,38], 14(42)14[1518], 14(42)14[1517], and 14(42)15. I like to play an anago whenever possible. Aunt Beast didn't compute the exact normalplay nimvalue 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[1620] N
Looping on a tail of the anago, Roman encloses a group of 5 spots.
According to the "component with firm nimvalues" heuristic, this position's nimvalues 3^{3} + *3 + *3 + *3 would seem to yield a clear 0^{0}, that is, a Pposition in normal and misère play. Actually, though, it's a misère Nposition — 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 nimvalues 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 nimvalues up to *9.” For more on this, see these messages in the “Dawson's Sprouts” thread on sproutstheory.
18(46)19 P
Again, this was the only winning move. Now the game's outcome and its nimvalues begin to correspond: the 1^{3} component has restive nimvalues, 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 otherwiseempty 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 nimvalues 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 nimvalues 6^{1}.
Roman usually resigns in losing positions with such few remaining live spots. Either the normalplay nimvalue 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 nimvalues 5^{0}.