[net.math] Nim Game in Marienbad * SPOILER *

mmar@sphinx.UChicago.UUCP (Mitchell Marks) (09/13/85)

Before getting down to the solution, some miscellaneous points:

1.  It's not really fair to say that the makers of _Marienbad_ (the two 
Alains) "didn't know" the method.  You could as easily say that the
character was portrayed as not knowing the method.  Or, given the way the
film accepts a confused version of reality, perhaps the characters were
obeying all the rules but the fundamental one: try to reach a win.

2.  The game is very old, but I don't know what the traditional layout
was.  Rows of 3 each makes for a trivial game; and even the _Marienbad_
layout is not very challenging -- i.e., even without the general method
you can try out enough variations from this position to memorize a
winning strategy.

3.  In the standard game, the last player to take a counter wins.  It can
also be played in a reverse or mis`ere version, in which the player forced
to take the last counter loses.  It turns out that the same general analysis
applies, with differences only near the end.  The analysis below is in
terms of the standard game.


Okay.  The general idea of the analysis applies to many other two-person
games.  All possible board positions can be divided into two exhaustive
and disjoint sets, consisting of the "safe-leave positions" and the
"unsafe-leave positions".  [I will omit `-leave' hereafter.]  Here is
a recursive definition:

1.  A WINNING position is a SAFE position.
2.  A position which can be converted into a safe position in a single
    move, is an UNSAFE position.
3.  A position such that all possible next single moves leave unsafe
    positions, is itself a SAFE position.

From a safe position, any move gets you to an unsafe position.  From an
unsafe position, some moves might leave you in an unsafe position but
there is at least one move that will get you to a safe position.  So, once
a player reaches a safe position, s/he has a winning strategy: suppose A
reaches a safe position.  Now any move by B MUST leave an unsafe position.
This in turn means that A MUST have a move to a safe position.  Etc.

(Of course it's possible for a player to have a safe position, but blow
it on a later move by not finding the right move, and going from the
opponent's unsafe leave to another unsafe.  But there *was* a correct
move available.)

Clearly, not every game can be analysed in these terms; it just happens
that the structure of Nim allows it.


So, the problem is to find a definition of the safe and unsafe positions.
The solution for Nim is rather unintuitive, but it can nonetheless be
used in mental or finger calculation.  (If you really want to use it,
it's a good idea to supplement the general method with some heuristics
about certain common patterns that can be removed from the calculations.)

Express the number of counters in each row in binary, and write them with
the correct digit columns aligned.  Count the ones in each column, and
note for each column whether that number is even or odd.  (Equivalently,
take the bitwise XOR of all the rows.)  THE SAFE POSITIONS ARE ALL AND
ONLY THOSE IN WHICH ALL THE COLUMN ONE'S-COUNTS ARE EVEN (all bits in
the XOR are zero).

In play, you examine the position left by your opponent, hoping of 
course that it was unsafe.  (If it happens to be safe, make a minimal
move or a confusing move, and hope that your opponent stumbles into an
unsafe leave sooner or later.)  Finding an unsafe position, look for a
way to get rid of all the 1 columns.  If there is a row with all those
bits as 1, just take that many counters; e.g. the XOR came to 10010, and
there is a row with 22 counters (10110) ; your move should be to take 18
from that row leaving 4.  If there is not such a row, find a row with a
1-bit in the column of the highest 1-bit of the XOR row; remove from
that row the difference between the value of that bit and the sum of
the values of the bits where the XOR has 1 and the chosen row has 0.
E.g., the XOR row has 1001, and there is a row with 26 counters
(11010).  Take 8-1 = 7 counters from that row, leaving 19
(10011).  That switches the 8's bit and the 1's bit, as desired.


Example with a full board:
(The _Marienbad_ layout)

	1	  1
	3	 11
	5	101
	7	111
		___
		000

This is a safe position; so the layout is a win for the second player
if s/he plays correctly.  The first player makes some move, which will
give an unsafe leave, say, taking the row of 3:

	1	  1
	5	101
	7	111
		___
		011

Your move should be to take 3 from the row of 7:

	1	  1
	5	101
	4	100
		___
		000

Now your opponent takes 1 from the row of 4:

	1	  1
	5	101
	3	 11
		___
		111

You move clearly has to involve the row of 5, to get rid of the high bit.
You also want to wipe off the low bit, but "put back" the 2's bit.  So you
take 3 and leave 2:

	1	  1
	2	 10
	3	 11
		___
		 00

From here, the tree is fairly small and you can establish even without
the binary method that this is a winning position.

Here are a couple heuristics:

	Two equal rows cancel -- ignore them in your calculations.
	If the opponent takes counters from one of them, you take the
	same number from the other, to restore them in balance.

	A threesome of rows cancels when one is 1, and the other two
	are successive numbers with the low one even, e.g. 1-2-3, 1-4-5
	as seen above.
	If the opponent takes the singleton, you take one from the odd
	row to convert it into a matched pair.  If the opponent takes from
	one of the longer rows of the triplet, leaving more than one counter,
	you take from the other one and restore the even-odd sequence.  If
	the opponent takes from one of the longer rows leaving none or one,
	you take from the other leaving one or none respectively (in other
	words, the two moves together leave only one counter from the two
	longer rows of the triplet).

These are not really *instead of* the method; they directly derive from
it.  Be careful with the heuristics: don't trip yourself up if the game
gets down to a lot of singleton rows.

-- 

            -- Mitch Marks @ UChicago 
               ...ihnp4!gargoyle!sphinx!mmar

usenet@ucbvax.ARPA (USENET News Administration) (09/16/85)

This game is a special case of "Green Hackenbush" which
is completely solved in "Winning Ways" by Berlekamp, Conway
and Guy . (I took a marvelous course in game theory from
Berlekamp some years ago ... it's a nice game if your
opponent doesn't know the theory and you do ...)