我试着用Python编写minimax nim游戏。代码我快写完了。然而,我无法解决一个问题,这是如此棘手。我无法达到算法的“最佳运动”。我从(5,Max)位置开始,算法输出应该是(4,Min)。我的算法用效用值求解整棵树,但不能返回到最佳运动。你知道吗
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)
如果你不想在内存中存储整个移动序列(这通常是/通常是不必要的),只需从生成当前游戏状态的可能子级开始。不要在你当前的状态下运行minimax,只要找到可能的下一步行动。让我们想象一下从你现在的位置有3种可能的移动(A,B,C)。现在在A上运行minimax算法,并将结果与移动A的描述一起存储。对B和C重复此操作。现在应该有如下结果:
记住,这些并不是游戏状态的启发值,而这些启发值是通过采取这些行动立即产生的。从最大化玩家的角度来看,它们代表了当当前玩家选择移动时,另一个玩家可以强制当前玩家在未来接受的最小值。你知道吗
在这个例子中,移动A对于最大化的玩家是最好的,移动C对于最小化的玩家是最好的。你知道吗
相关问题 更多 >
编程相关推荐