Winning Nim Against a Player who Plays Randomly
I recently wrote about my way of playing Nim against a player who doesn’t know how to play. If my move starts in an N-position, then I obviously win. If my move starts in a P-position, I would remove one token hoping that more tokens for my opponent means more opportunity for them to make a mistake. But which token to remove? Does it make a difference from which pile I choose?
Consider the position (2,4,6). If I take one token, my opponent has 11 different moves. If I choose one token from the first or the last pile, my opponent needs to get to (1,4,5) not to lose. If I choose one token from the middle pile, my opponent needs to get to (1,3,2) not to lose. But the first possibility is better, because there are more tokens left, which gives me a better chance to have a longer game in case my opponent guesses correctly.
That is the strategy I actually use: I take one token so that the only way for the opponent to win is to take one token too.
This is a good heuristic idea, but to make such a strategy precise we need to know the probability distribution of the moves of my opponent. So let us assume that s/he picks a move uniformly at random. If there are n tokens in a N-position, then there are n − 1 possible moves. At least one of them goes to a P-position. That means my best chance to get on the winning track after the first move is not more than n/(n−1).
If there are 2 or 3 heaps, then the best strategy is to go for the longest game. With this strategy my opponent always has exactly one move to get to a P-position, I win after the first turn with probability n/(n−1). I lose the game with probability 1/(n−1)!!.
Something interesting happens if there are more than three heaps. In this case it is possible to have more than one winning move from a N-position. It is not obvious that I should play the longest game. Consider position (1,3,5,7). If I remove one token, then my opponent has three winning moves to a position with 14 tokens. On the other hand, if I remove 2 tokens from the second or the fourth pile, then my opponent has one good move, though to a position with only 12 tokens. What should I do?
I leave it to my readers to calculate the optimal strategy against a random player starting from position (1,3,5,7).
Share:
Leave a comment