(Алгоритм Python NegaMax для Game of Nim) Что не так с моим кодом?
Я новый ученик ИИ. Мое задание требует, чтобы я написал программу на Python, которая оптимально играет в игру Ним (используя алгоритм NegaMax).
Если вы не знакомы с игрой, вот краткое описание:
Ним — это простая игра для двух игроков. Начнем с кучи из n спичек,
где n ≥ 3.
Два игрока, Макс и Мин, по очереди убирают k спичек из стопки, где k = 1, k = 2, or k = 3. Игрок, выигравший последнюю спичку, проигрывает.
Это то, что я уже написал:
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")
Независимо от того, сколько state я поставил, и Мин, и Макс всегда берут по 1 матчу в каждом раунде.
Я думаю, проблема в том, что оценка неверна, но я не вижу, где я ошибся. Любая помощь будет оценена по достоинству! Спасибо!
Ответы 1
Проверьте условие остановки.
Тебе нужно :
if state == 1:
return (-1,1)
И тогда все идет гладко.
Я бы также изменил сигнатуру функции для ясности, потому что ей нужно только 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")
Играет оптимально.
Вы можете наблюдать результаты при оптимальной игре, когда MAX проигрывает для состояний 1+4k (1, 5, 9, 13, 17 и т. д.) и выигрывает для всех остальных состояний.
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