Need help explaining a Khorkov misere rule-of-thumb

29 views
Skip to first unread message

Josh Purinton

unread,
Dec 12, 2008, 2:55:02 AM12/12/08
to sprouts...@googlegroups.com
(I sent this bout 30 minutes ago, but it didn't go through. Hope it doesn't show up twice.)

Consider the position that results from:
 
15- 1(16)2 6(17)6[1-5] 7(18)8 6(19)17[7-10] 10(20)18 11(21)12 7(22)8 22(23@10)8 15(24)15[19] 13(25)14 10(26)20[9] 10(27@9)2615- 1(16)2 6(17)6[1-5] 7(18)8 6(19)17[7-10] 10(20)18 11(21)12 7(22)8 22(23@10)8 15(24)15[19] 13(25)14
 
(See attached figure.)
 
Roman wrote: "Let Y be the area which contains points 1,2,16,3,4,5. Let Z be the area which contains all other points 11,7... If you find a move which creates a normal-play G0 in region Z, then you have won. But this G0 in region Z must obey the following constraints:
G0 <> Gx+Gx+...+Gx=2n*(Gx) (x>1)
G0 = G1+G1+...+G1=2n*(G1) or G0=G0+G0+...+G0
or G0=2n*(G1)+G0+G0+...+G0"
 
The area Y is A5 (anago 5). I think Roman is saying: "If Z = Z_1 + Z_2 + ... + Z_n, G+(Z) = 0, and G+(Z_i) < 2  (for 1 <= i <= n), then o-(A5 + Z) = P".
 
 
Though I think I understand the content of Roman's heuristic, I don't understand the reason behind it. Can anyone explain why it is true?
game.png

Yper Cube

unread,
Dec 12, 2008, 3:06:14 AM12/12/08
to sprouts...@googlegroups.com
The Y region (the also called A5) is a 3^0. (normal grundy value:3, misere:0 )

If therefore you find a child of the Z region with value *0 you are sure to win in misere as
3^0 + *0 = 3^0
You can possibly do the same with a 0^1 as
(usually) 3^0 + 0^1 = 3^0

But if the child is found that is G0 in normal play but not a 0^1
lets say a *2+*2 or a *3+*3) therefore a  0^0

then (usually) 3^0 +0^0 = 3^3 , which is not a misere win for the player that plays this child.
(Note: A5=3^0 but in this case 3^0+0^0 = A5 + (*2+*2) = 3^2 (still not a misere win for the player that plays this).

In conclusion, you are correct, finding a G0 is not enough.
One has to find a child which is normal G0 and misere G1. (and stiil not be sure to win unless it's a confirmed *0)

One better look for moves from region Z with normal value G0 which either keep the region in one piece or separate it into two but the G0 comes from G0+G0 or G1+G1.


Roman's terminology is quite cumbersome and I can only guess that in the situation discussed, we need a G0 that comes from (normal values)
G0=G1+G1+...+G1=2n*(G1)+G0+G0+...+G0

But, that's not enough either!
Because sometimes, while in normal G0=G0+G0 or G0=G1+G1
the misere value of this (normal) G0 is still 0.

Example: 0^0 + 0^1= 0^0
or  1^1 + 1^0 = 0^0

What is enough, is a
G0=G1+G1+...+G1=2n*(G1)+G0+G0...+G0

where all children and children of children and children of children of children and ... (you get the point)
have normal values of 0 or 1.

Then, as nowhere a *2 or a *3 or a *n (with n>1) occurs, we are sure that the above G0 has a misere value of 1. (therefore it behaves as a *0 or it is one)

So, it can be added to 3^0 yielding a misere win for the previous player.

ypercube

Josh Purinton

unread,
Dec 12, 2008, 3:22:48 AM12/12/08
to sprouts...@googlegroups.com
On Fri, Dec 12, 2008 at 3:06 AM, Yper Cube <yper...@gmail.com> wrote:
The Y region (the also called A5) is a 3^0. (normal grundy value:3, misere:0 )

If therefore you find a child of the Z region with value *0 you are sure to win in misere as
3^0 + *0 = 3^0
 
What does "with value *0" mean? Does it mean just that G+(Z) = 0 and G-(Z) = 1? Or are there further conditions?
 

You can possibly do the same with a 0^1 as
(usually) 3^0 + 0^1 = 3^0

But if the child is found that is G0 in normal play but not a 0^1
lets say a *2+*2 or a *3+*3) therefore a  0^0

then (usually) 3^0 +0^0 = 3^3 , which is not a misere win for the player that plays this child.
(Note: A5=3^0 but in this case 3^0+0^0 = A5 + (*2+*2) = 3^2 (still not a misere win for the player that plays this).

In conclusion, you are correct, finding a G0 is not enough.
One has to find a child which is normal G0 and misere G1. (and stiil not be sure to win unless it's a confirmed *0)
 
Fascinating. I'm starting to understand how the normal-play outcome class can be a guide to finding the right move in misere.
 

Josh Purinton

unread,
Dec 12, 2008, 3:30:45 AM12/12/08
to sprouts...@googlegroups.com
On Fri, Dec 12, 2008 at 3:22 AM, Josh Purinton <josh.p...@gmail.com> wrote:
On Fri, Dec 12, 2008 at 3:06 AM, Yper Cube <yper...@gmail.com> wrote:
The Y region (the also called A5) is a 3^0. (normal grundy value:3, misere:0 )

If therefore you find a child of the Z region with value *0 you are sure to win in misere as
3^0 + *0 = 3^0
 
What does "with value *0" mean? Does it mean just that G+(Z) = 0 and G-(Z) = 1? Or are there further conditions?
 
 
I suppose "has value *0" means "is equivalent to the empty nim-heap in every way", which implies that the component can be ignored for the purposes of calculating the outcome of any game of which which it is a part. So yes, since G-(A5) = 0, then G-(A5+*0) = 0.

danny purvis

unread,
Dec 12, 2008, 7:46:23 AM12/12/08
to sprouts...@googlegroups.com
In terms of my formative "zovichean theory," I think Roman's winning move would be one that makes Z a "shallow even," in other words a biosphere sure to yield an even number of survivors. (A "deep" biosphere eventually gives one or the other player a choice of an even or odd number of survivors.) Y is probably what I call a "pseudoswitch." The mover can probably produce his choice of an even or odd number of survivors from Y, but only when this toggle also toggles Y's depth. If Y is a pseudoswitch then the person moving to Y has some choice, but not as much choice as might first appear. So I'm theorizing that his choice in would be to convert Y to either a shallow odd or to a deep even. (Now, this would be plenty of options if Z is deep. But if Z is shallow, either both options are good or both options are bad, depending on Z's survivor parity.) 
 
The given position has an odd number of cannibals. The mover needs a total deep even or a total shallow odd. If he now finds a move that leaves Z a shallow even, then if Y is, as I suspect, a "deep even / shallow odd" pseudoswitch, the mover has won. He will have left the total position a "deep even/ shallow odd" pseudoswitch.
 
Y looks very complicated, but please note two key lines:
 
(Starting with the given position for covenience)
 
1(26)1[3-5] shallow odd
 
1(26)1[3,4] deep even   


From: Josh Purinton <josh.p...@gmail.com>
To: sprouts...@googlegroups.com
Sent: Friday, December 12, 2008 2:55:02 AM
Subject: Need help explaining a Khorkov misere rule-of-thumb

Josh Purinton

unread,
Dec 12, 2008, 7:51:40 AM12/12/08
to sprouts...@googlegroups.com
On Fri, Dec 12, 2008 at 7:46 AM, danny purvis <wgosa_...@yahoo.com> wrote:
I'm theorizing that his choice in would be to convert Y to either a shallow odd or to a deep even. (Now, this would be plenty of options if Z is deep. But if Z is shallow, either both options are good or both options are bad, depending on Z's survivor parity.) [...] Note two key lines:
 
1(26)1[3-5] shallow odd
1(26)1[3,4] deep even   
 
According to Aunt Beast, both options are bad. What can we infer about the position from that?

danny purvis

unread,
Dec 12, 2008, 8:37:56 AM12/12/08
to sprouts...@googlegroups.com
Suppose Y is indeed a de/so (deep even / shallow odd) pseudoswitch. Either immediate option would be bad if Z is a true switch or if Z is an odd quasiswitch. The options of a true switch are either de/do or se/so. The options of an odd quasiswitch are do/so.
Sent: Friday, December 12, 2008 7:51:40 AM
Subject: Re: Need help explaining a Khorkov misere rule-of-thumb

Josh Purinton

unread,
Dec 12, 2008, 8:41:18 AM12/12/08
to sprouts...@googlegroups.com
"do/se/do" indeed -- no one can deny that you are brilliant! Now, what promising moves, specifically, does this information about Z suggest?
 

danny purvis

unread,
Dec 12, 2008, 9:04:13 AM12/12/08
to sprouts...@googlegroups.com
No, just the opposite.
 
Now it looks to me like I miscounted cannibals in the original position! I began my analysis in confusion and probably should leave it in the same state.

Sent: Friday, December 12, 2008 8:41:18 AM

Subject: Re: Need help explaining a Khorkov misere rule-of-thumb

danny purvis

unread,
Dec 12, 2008, 9:30:04 AM12/12/08
to sprouts...@googlegroups.com
My current Three Stooges count of the given position is 12 cannibals, an even number. So the mover needs a total se/do. By the theory that Y is a de/so, the mover would love to convert Z to a shallow odd. A try would be 15(26@19)24, hoping that the sphere S(11) will prove to be a shallow even.


From: danny purvis <wgosa_...@yahoo.com>
To: sprouts...@googlegroups.com
Sent: Friday, December 12, 2008 9:04:13 AM

Subject: Re: Need help explaining a Khorkov misere rule-of-thumb

Josh Purinton

unread,
Jan 4, 2009, 6:08:08 PM1/4/09
to sprouts...@googlegroups.com
After 15- 1(16)2 6(17)6[1-5] 7(18)8 6(19)17[7-10] 10(20)18 11(21)12
7(22)8 22(23@10)8 15(24)15[19] 13(25)14, Left has about 72 different
possible moves. Only one of them wins.

In rot13, the winning move is: gjragl gjraglfvk frira rapybfvat gjraglguerr.

> Roman wrote: "Let Y be the area which contains points 1,2,16,3,4,5. Let Z be
> the area which contains all other points 11,7... If you find a move which
> creates a normal-play G0 in region Z, then you have won."

For what it's worth, the winning move leaves the sphere Z with a
normal-play Grundy number of 3.

Reply all
Reply to author
Forward
0 new messages