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!mmarusenet@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 ...)
judith@proper.UUCP (Judith Abrahms) (09/22/85)
Before I quibble about a non-net.puzzle-related point, I want to thank everyone who sent me mail explaining Nim strategy. I'd also like to ask Bob Cralle (sp.?), who offered me an article he'd written about it, to get in touch with me, since mail I sent to him bounced & I'd love to see his discussion. Special thanks to Mitchell Marks for his article, especially the "combinations" discussed at the end. I will now take issue with him about the Nim games in the film, so anyone not interested in literary speculation should press 'n'. In article <> mmar@sphinx.UChicago.UUCP (Mitchell Marks) writes: > >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. The character who always won announced, at least once, "I always win." Yet at several points in the games, he made moves that produced "unsafe" configurations. It seemed clear that up to the point at which anyone could "read out" all the possible moves to the end, the moves made by the two players (the invariable winner & loser) were pretty much random. If the winner was portrayed as not knowing the method, then he was portrayed as having some supernatural (or at least super-logical) power, for as he predicted, and despite his blunders (and even when he played first!) he never lost a game. > 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. This sounds very Marienbadish indeed, and I wish I could accept it. However, the loser showed a tremendous desire to win, and appeared thunderstruck every time he lost. And if the winner wasn't intended to be trying to win, why have him announce that he always wins? The two main players (I think there may have been other challenger/losers) were rivals outside the game. The man who invariably lost was trying to seduce the wife of the man who invariably won. It seemed pretty clear that the repeated Nim scenes were intended as some sort of commentary on the real-world situation, in which the seducer moves slowly but monotonically toward a win (he takes off with the wife at the end). I'm sure the husband's invincibility at Nim is meant to be connected with his knowledge of the seducer's campaign, which he makes no serious attempt to block. (I think he even stays out of the way deliberately on the night they're to leave -- the wife hangs back, expressing some hope he'll appear & try to stop her. He does show up, but not till she's gone.) I don't think it possible to assign a meaning to this motif -- man always wins Nim games against man to whom he loses wife -- but these two characters seemed deadly serious when they played. They didn't act or speak as if they were making random moves. Yet that's what they were doing. Judith Abrahms {ucbvax,ihnp4}!dual!proper!judith