wccanard notes

Is wccanards notes on this game available anywhere? I am specifically thinking about nim stuff which I never got around to learn.

The url is http://wccanard.wetpaint.com/

seems to be down atm

Yes I strongly recommend to read the nim stuff nim.pdf, not to boost your 5x5 D&B game, but because you will enjoy and be able to use it for any impartial game.

Other archived papers here...

If someone want to practice nim, let play this game:

- original position, heaps of 8 10 3.
- there are two phases,
1st phase:
- a player can remove as many tokens as he want from a heap, or
- decide on the rule, "player who takes last token loses" or "player who takes last token wins",
2nd phase when rule is set
- a player can remove as many tokens as he want from a heap.

Who wants to start?

Not sure I understand completely. Why don't you start, and then I'll play with you? :-)

ok nice, 8 9 3

That's fun and crazy!

Thanks.

I think I first read about this game from a Martin Gardner column, anyone has got a pointer?

It was a mistery to me for a long time until I got to know the genus theory of misère games from Thane Plambeck and then from Winning Ways for your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy.

Man, I was too confident! It's a very nice puzzle, Carroll.

Just to be clear (and not because I'm stalling for time!): if a player takes the last token in 1st phase, the other player can then decide who won?

Yes this is how I see it, saying "player that takes last token loses hence you have lost!". I think Martin Gardner had not made that clear.

So in fact it is a misere game ;)

8 9

8 7

6 7

6 5

4 5

4 3

1 3

Congrats Dushoff! Yes here the "hidden heap" value is no more *1... any explanation of this fact?

Just to finish the game:

1 2

What's harder for me is to explain why you usually _do_ want to play for *1. The two components of the game don't "add" in any obvious way, since playing in the rule component changes the nim component.

The first phase should end when a player makes a move that either has nim value 0, _or_ leaves no meaningful choices for the other player in the nim component. The latter means, effectively, a position with 1 in each pile. I just worked by observation from there. The simplest position I can be in that doesn't give you a win by calling the rule is (2 0), so that must be a win for me. The simplest position that doesn't allow you to call a rule or move to (2 0) is (3 1). The simplest position that doesn't allow you to call a rule or move to (2 0) or (3 1) is (5 4).

(5 4) has nim value *1. As did your starting position, which I assumed was winning for the second player :-). That allowed me to figure out the general rule that, since you would lose by playing nim value 0, I could always stay on nim value *1 if I wanted to. But I don't want to go to (3 2), because that would let you get to one of the anomalous winning positions. But if I _could_ go to (3 2), I could always choose either (3 1) or (2 0) instead. So that seemed good. Then there were some details I worried about in case there were three piles (I think the answer is that the full list of anomalous winning positions is (2 with an even number of ones) or (3 with an odd number of ones)), but you let me off that hook early on :-).

Maybe too much detail? Anyway, it was fun.

2 0

Sorry for my apparent textile mistake!

Yes this is a good explanation with normal Grundy numbers, but I don't think *2 is such an anomaly.

When you play misere games where lot of positions are nim heaps, you can use the genus sequences or the reduced genus numbers of form a^b, where "a" is corresponding to the normal *a value and "b" to the miserere value meaning that the outcome of the game G + *b"is a win for second player.
Here I pretend that the rule component of the game has value 1^2 with two options :
- choosing misere rule is going to *0 of genus 0^1, neutral element for game addition
- choosing normal rule is more interesting and corresponds to playing misere game with additional game of value 0^0
When you know the genus of the options of a game you get his genus by the mex rule (minimal excluded, explained in wccanard paper) on normal values (0,0) hence mex=1 and misere (0,1) mex value=2.
So by definition, if you add a nim heap of value *2 to the game component you win (what you just did). *2 has genus 2^2, there some rules for certain cases, especially when you add nim heaps, here 2^2 + 1^2 = 3^0, the misere value 0 indicates a misere win.

The genus for nim heaps are 0^1 for *0, 1^0 for *1 called fickle games; 2^2 for *2 and then on a^a for *a called firm games.
The rules for nim head addition are that if you add firm games a^a + b^b, you get a firm game of genus (a XOR b)^(a XOR b), for example *5 + *4 has genus 1^1 which is different from the heap *1 of value 1^0
When you add fickle games, *0 is neutral, and 1^0 + 1^0 is 0^1, this is why you should not leave an even number of heaps of size one.
When you add a firm a^a with 1^0, the result is a firm (a XOR 1)^(a XOR 1).
Games with firm value tend to be absorbers, for example the normal rule of value 0^0 plus a heap of size 1 of genus 1^0 yields the 1^1 game which next player can win by taking last token and getting 0^0 which is a misere win (null exponent).

The famous winning nim misers position *1 + *2 + *3 translates to (1^0 + 2^2) + 3^3 = 3^3 + 3^3 = 0^0.
Now *5+*4 is 1^1 which do not have an *2 option hence when added with 1^2 rule component, the value is 0^0, so you played the right moves. The same for any pair a, a XOR 1, except *2, *3 which has an *2 option (when you take all 3 tokens).
There is no general rule to add "wild games" of genus a^b, but you can mex the outcome with the different options when they are "tame", nim heaps or firm 0^0 game. For example 1^2 ( options 0^1,0^0) + 1^0 (option 0^1) is mex (1^2+0^1, 0^1+1^0, 0^0+1^0) = mex(1^2, 1^0, 1^1) = 0^3 so you can win by going to 0^1 ( shouting " misere rule!") + 1^0.
When I left you *1+*2 = *3 of genus 3^3 plus rule 1^2 :
3^3 (options 0^1, 1^0, 2^2) + 1^2 (options 0^1, 0^0) = mex (3^3, 3^3, 1^2, 0^3, 3^0) = 2^1 with last option to leave just *2 is winning.
When you have three or more nim heaps, you just XOR them and the game is not more complex.

Hope you enjoyed this too long post! Thanks for playing the game, *1

No I change my mind and go to 0^1...

Beware when you remove the last token from the rule component to shout the right rule ! :)

That's pretty complicated. So 0^1 means that you take both the counters, right? Because that leads to a heap that would have nim value 0 under standard rules and 1 under misere rules? If so, I call last token loses, because you just took it.

If 0^1 is a typo for (0 1), I still call lost token loses, because in that case you're about to take it!

Very interesting, thanks.

Yes I took both counters, congrats!

In this misere game where choosing the rule is like taking a token in the rule component, by choosing the rule, we could say you took the last component and so you lose! You could have chosen the 0^0 component hence the "normal" rule saying that the one taking last token wins... But this is sort of auto-referential ;)

Right, but fortunately, you specified the call in terms of "last token", not last component, or last move.

bump

isnt the rule component just *2 in disguise? it seems that way

@Christian,

If that was the case, you could find a winning move to Dushoff's 6,7 or 4,5 moves by removing 1 from the rule component, leaving e.g. *6,*7,*1. What choice of rule would give you this winning play?

Do you want to start another game?

Has anyone a link to the notes.... it seems to be "lost" in cyberspace (I only have a printed version)

Yes the archive is gone.

Maybe one could ask one of the authors of http://arxiv.org/abs/1305.2156 who knows him well, if he has a copy of the articles?

http://z5.ifrm.com/30479/151/0/f5306342/nim.pdf http://z5.ifrm.com/30479/151/0/f5306343/counting.pdf

Glad you had a copy, @Dryad, will you put a copy on http://w11.zetaboards.com/DromedaryBoard/topic/10331826/1/ too?

Sure, I also added the technotes file that diego just gave me.

Congratulations to dryad btw