'Always Win' — general solution for the following game?

OK, I am about to describe a very simple game here that can be played just about anywhere. It is very simple, and very fun (IMO) but no matter how hard I try to analyze th damn game I can’t get it down (might help if I tried sober, but I never play the game when I’m sober).

Here is the layout:


      X
    X X X
  X X X X X
X X X X X X X

Ok, the "X"s represent objects of some kind. I usually use pennies, but in a pinch I’ve substituted peanut shells, pieces of lint, just about any discernable relatively stable object. Once the “pieces” are liad out as above the game begins.

Players take turns. We have here, luckily, Player A and Player B. A and B have already fought a duel and decided that A goes first (note: duel not necessary ;)). Now, here is the definition of a legal turn:

The player may remove any number of pieces from a horizontal row at a time, but the player must take at least one. So, A will take his turn.


      X
    X X X
  X X X X X
            X

Note there are still four rows. It is now B’s turn. He can take one from the top or bottom row (since there is only one in each) or he may take 1, 2, or 3 from the second or 1-5 from the third. Turns alternate.

Point to game: do not take the last piece.


NOW, in my opinion and from playing the game quite a few times it seems that, were the game to be played by two “perfect” players, the winner of the game would then be determined by who went first (though it might mean that whoever went first was destined to lose, of course).

Can anyone help me analyze this game and come up with something? I’ve tried to tackle it in a number of ways and though I can come up with a few “target patterns” toward the end to shoot for I cannot find any similarity between them and I cannot, from the beginning, predict what a great move would be.

Oh, and if you dont figure it out, have fun playing it. It seems so damn simple. :slight_smile:

The game you’re describing is called “Nim”, and yes, with optimal play it’s a guaranteed win for either the first player or the second player. (I don’t remember which off the top of my head, but I think it depends on the opening setup.) Check out, for example, http://www.cut-the-knot.com/nim_st.html for an analysis.

Nim is one of the most heavily analyzed games there is, because it’s one of the few non-trivial two-person zero-sum perfect-information games that can be analyzed completely. Any good book on game theory should have an analysis of it.

If you are the first player, simply pick the top one first, and then scoop up however many the person left in the row on the turn right before yours.
If you are the second player, you can win as long as the first player picks the top row last (the one with only one penny in it). All you have to do is pick up whatever is left from the row the first player just picked from, and at the end there will only be the top row left, which the first player must get.
Of course, if a person picks up a whole row, that changes things. But it works as long as only partial rows are picked up.

Well, I spent about an hour on it and finally came to the conclusion that Player B can force a win. I identified three target patterns, and the play reduces to one of them after the first move in all but a couple of cases, which work out in two or, in one case, three moves. My solution as a whole, though, is kind of ungainly. I’ll post it when I have a little more time…

The second player should always win.
Losing positions include:
Two rows with the same number markers (except 1-1).
Three rows with 1-1-1, 1-2-3, or 1-4-5.
Four rows where each row has the same number of markers as another row (except 1-1-1-1).

If your opponent takes more than one marker on the first move, you can force one of the losing positions. If he only takes one, then you should remove one from the smallest remaining row.

Hexaflexagons and Other Mathematical Diversions, by Martin Gardner, has a whole chapter on this subject. The puzzle can be generalized to one with any number of rows and counters, and there is a solution that works for all cases. The first player has a strong advantage, but either player can win by doing a binary number analysis on the number of markers in each row to determine the best move.

Wow, nice site, Math Geek. Interesting that I seemed to have the win conditions backwards. Damn, the electronics guy in me should have looked into this as a damn logic game! :stuck_out_tongue:

I will look into seeing how the winning XOR strategy changes since I’ve changed the win conditions. :cool:

My high school geometry teacher showed me the “alwaysd win” rule for this, which is binary, as stated above. Convert the number of markers in each row to binary form and add up the columns independently. If they add up to zero (in the last place of each column) you’re screwed, and you lose if the other guy plays rationally. Otherwise, play so that the tallies all come out zero in the last place and you’ll win. This strategy works for any number of markers in each row.

I played this game in my high school advanced algerba class against another guy, and we got very good at playing it intuitively – no need to go through all the math. I also learned the math of min independently when I got two copies of the game Dr. Nym as as kid – a mechanical Nim-playing computer – and analyzed the math.
Incidentally, the playing of Nim is a central point in the film Last Year at Marienbad. What irks me is that the guy who claims to be a great player and unbeatable actually plays a lousy game, and ought to be defeated by a competant player. They never do this in the film, so I don’t know if his bad playing was meant to be relevant or if the director (Resnais?) didn’t know how to play, either.

Yes, I noticed that pattern (along with others not in the format above), but that wasn’t really a general solution, more like a “try to get here.” Never did seem that the second person should always win, though, from “target shooting.”

Actually, strictly speaking I got them backwards. It occurred to me late last night that you had specified “last move loses” while the link I posted was talking about “last move wins”. I wasn’t paying close enough attention, obviously; my bad.