A Counterexample to Khorkov's Misere Theorem 1

July 20, 2007

Khorkov's Misere Theorem 1 implies that any position containing a type 1 UT is won by the same player in normal and misere play.

But this morning Aunt Beast found a counterexample: a position which contains a type 1 UT, but is won by Left in normal play and by Right in misere play.

7+ 1(8)1[2-3] 1(9@4)8 6(10)7 7(11)7 I 7- 1(8)1[2-3] 1(9@4)8 6(10)7 7(11)7 II

This position has the nim-values 3^0.

I remember when Roman first shared this principle with me on Christmas Day, 2006 (what a fine gift!):

Khorkov's Theorem 1. Gz = (x^y + (6n+2)spots)- = (x^y + (6n+2)spots)+
Khorkov's Theorem 2. Gz = (x^y + (6n+5)spots)- = (x^y + (6n+5)spots)+

Generally speaking I always tried to play misere games by this principle. That is, I always tried to create independent 6n+2,6n+5 (as these classes of points are won by the same player both in misere and in normal games). (I never played by means of Gi.) Actually, the 2 new theorems are analogues of my principle in the language of Gi. I am very grateful to you for the help in checking these theorems by practical consideration! You did not find counterexamples?

I don't recall how hard I looked at the time, but I do know that I didn't find any counterexamples. After the recent series of games ("15-: The Empire Strikes Back"), Roman asked me to search again. "You must test T1! It's very important!". This time the search was successful.

As I wrote in April 2006, "I believe that computers will raise the standard of Sprouts play even higher than it already is, open up new vistas for human strategy and tactics, and help humans discover hidden beauty in many strange, previously-unexplored areas of the game tree."

I believe this prediction is already coming true. We have seen the strange and beautiful positions that arose in the recent series of games in 15-. Furthermore, the discovery of this counterexample is a great example of computers and people working together to invent new principles to guide human sprouts players.

Roman Khorkov has generously shared his strategies with us over the years. In that same spirit, I offer this counterexample.

Thank you, Roman, for everything you have taught us about sprouts. I hope that having a concrete counterexample will help you to further refine your marvelous algorithms.

Back to WGOSA Classic