I am a new learner of AI. My assignment requires me to write a program in Python that plays the Game of Nim optimally (using the NegaMax algorithm).
If you're not familiar with the game, here is a brief description:
Nim is a simple two-player game. We start with a pile of n matches,
where n ≥ 3.
Two players, Max and Min, take turns to remove k matches from the pile, where k = 1, k = 2, or k = 3. The player who takes the last match loses.
This is what I have already written:
def NegaMax(state, turn, bestmove):
max = -100000000000
if state == 1:
if turn == 0:
return (-1,bestmove)
else:
return (1,bestmove)
for move in range(1, 4):
if state-move > 0:
m = NegaMax(state-move, 1-turn, bestmove)
m1 = -m[0]
if m1 > max:
max = m1
bestmove = move
return (max,bestmove)
def play_nim(state):
turn = 0
bestmove = 0
while state != 1:
[evaluation,move] = NegaMax(state, turn, bestmove)
print(str(state) + ": " + ("MAX" if not turn else "MIN") + " takes " + str(move))
state -= move
turn = 1 - turn
print("1: " + ("MAX" if not turn else "MIN") + " loses")
No matter what number of state I put in, both Min and Max always takes 1 match in every round.
I think the problem is that the evaluation is wrong, but I cannot see where I did wrong. Any help would be appreciated! Thanks!
Check your stop condition.
You need :
if state == 1:
return (-1,1)
And then everything runs smoothly.
I would also change the function signature for clarity because it only needs state :
def NegaMax(state):
max = -100000000000
if state == 1:
return (-1,1)
for move in range(1, 4):
if state-move > 0:
m = NegaMax(state-move)
m1 = -m[0]
if m1 > max:
max = m1
bestmove = move
return (max,bestmove)
def play_nim(state):
turn = 0
while state != 1:
[evaluation,move] = NegaMax(state)
print(str(state) + ": " + ("MAX" if not turn else "MIN") + " takes " + str(move))
state -= move
turn = 1 - turn
print("1: " + ("MAX" if not turn else "MIN") + " loses")
It plays optimally.
You can observe the results under optimal play, which is that MAX loses for states 1+4k (1, 5, 9, 13, 17, etc) and wins for every other states.
play_nim(5)
5: MAX takes 1
4: MIN takes 3
1: MAX loses
play_nim(11)
11: MAX takes 2
9: MIN takes 1
8: MAX takes 3
5: MIN takes 1
4: MAX takes 3
1: MIN loses