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