I have tried to program minimax nim game with Python. I am almost done with the codes. However, I could not solve a problem, which is so tricky. I could not reach 'best movement' of the algorithm. I started with (5, Max) position and the algorithm output should be (4, Min). My algorithm solves whole trees with utility values but could not return to the best movement.
def startposition():
return 5, 'max'
def terminalstate(state):
if state == (0, 'min') or state == (0, 'max'):
return True
else:
return False
def minimax(state):
turn,heap=state
if terminalstate(state):
return utilitystatic(state)
else:
if heap == 'min':
value = 250
for x in successorsgenerator(state):
value = min(value, minimax(x))
result = state, value
elif heap == 'max':
value = -250
for x in successorsgenerator(state):
value = max(value, minimax(x))
result = state, value
print(result)
return value
def utilitystatic(state):
turn, heap = state
assert terminalstate(state)
if state[1] == 'max':
return -100
elif state[1] == 'min':
return 100
assert False
def successorsgenerator(state):
successors = []
state = toggle(state)
newstate = decrease(state)
i = 0
while newstate[0] >= 0 and i < 3:
successors.append(newstate)
i += 1
newstate = decrease(newstate)
print('successors:', successors)
return successors
def toggle(state):
state = list(state)
state[1] = 'min' if state[1] == 'max' else 'max'
state = tuple(state)
return state
def decrease(state):
state = state[:0] + (state[0] - 1,) + state[1:2]
return state
stick = startposition()
result = minimax(stick)
print('result:', result)
In minimax(), you're currently only finding the best (min or max values depending on player) values of successor states, but not yet memorizing exactly which successor states were the best at every depth level. If you don't store that information in memory, you won't be able to tell which move was the best. So, you'll want to try something like:
def minimax(state):
turn,heap=state
if terminalstate(state):
return utilitystatic(state), _
else:
if heap == 'min':
value = 250
best_succ = None
for x in successorsgenerator(state):
val, _ = minimax(x)
if val < value:
value = val
best_succ = x
result = state, value
elif heap == 'max':
value = -250
best_succ = None
for x in successorsgenerator(state):
val, _ = minimax(x)
if val > value:
value = val
best_succ = x
result = state, value
print(result)
return value, best_succ
With a few small changes, we now store the successor x that led to the best value in best_succ, and will therefore also be able to tell exactly which successor was the best (instead of only being able to tell what its value is)