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
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