Hello all. I am attempting to write simple AI for a computerized opponent in a game of nim. My implementation of nim will play as follows. There are three piles of "imaginary" sticks. One player starts by removing a number of sticks from any one of the piles. The number of sticks that can be removed from a pile is limited only by the pile size. The opponent will respond in turn by removing some sticks from one of the piles. One wins by selecting sticks in a such a way that her opponent must pick up the last remaining stick. Example of a game. A, B and C represent three piles of sticks. ABC 321 Player 1 removes 2 from A 121 Player 2 removes 1 from C 12_ Player 1 removes 1 from A _2_ Player 2 removes 1 from B _1_ Player 1 is forced to remove the final stick from B, and loses. My problem is in defining decent game heuristics. Which situations are "good" for a given player, and which are bad? For example, a situation in which player 1 must pick from a single remaining pile is very good for player 1, because he can always pick one less than the total pile number and leave the remaining one for his losing opponent (obviously this is only true for pile size > 1). Is there anyone out there who has played alot of nim before? I would be grateful if you could give any examples of good or bad playing situations. The goal is to provide some basis for my AI to choose a path to play, judging on "goodness/badness" of the resulting situation. Thanks.

I hadn't heard of 'nim' before, but I have seen a flash game that played the game you describe. It beat me every time, but I could win one by playing it against itself (ie have two open and on one let it go first and on the other copy the first ones move etc).
Here is one copy of the game (I don't think that is it's home site). Perhaps you could analyze how it selects moves?

google is your friend :)
http://www.google.com/search?hl=en&q=nim+strategy

Except for trivial situations where each row has a single stick left, you can know if a situation is lost for the side to move by `xor'ing together the number of sticks in each row and checking if the result is zero.

Example: A=1, B=4, C=5. 1^4^5 = 0, so the player to move loses.

Example: A=45, B=131, C=89. 45^131^89 = 247, so the player to move wins. What is the winning move? Well, you must change one of the three numbers so the xor becomes 0. You have to pick a number that has the top bit of 247 (2^7) in its binary expression. That would be 131. Now 131^247 = 116 (this number is guaranteed to be smaller than 131 because of the top bit being the same in 131 and 247). So the winning move is taking 15 sticks from B, so you leave your oponent in the situation A=45, B=116, C=89, with 45^116^89 = 0.

Check Grundy Numbers. Optimal strategy for 3 nims is only xor of 3 grundy numbers for one nim

Thank you for your replies!

Actually I have seen this game strategy before. The problem is, if the computer uses this it will be too hard to beat. I do not want the computer to play perfectly so my intention is to build a state-space tree to a certain depth, and evaluate the best path to pick based on the states at the bottom of the tree.

I just need some way of evaluating how good or bad the situations at the bottom of the tree are, so I can make a reasonable path choice. I plan to associate weight values with situations which I know are good or bad (such as an odd number of piles with 1 element), and 0 for all other situations which do not match any of those on my list of "known situations".

btw Extrarius thanks for the link, that was a cool implementation :)