(Алгоритм Python NegaMax для игры Нима) Что не так с моим кодом? - PullRequest
Новая
       37

(Алгоритм Python NegaMax для игры Нима) Что не так с моим кодом?

0 голосов
/ 14 мая 2019

Я новый ученик ИИ. Мое задание требует от меня написания программы на Python, которая оптимально играет в игру Ним (используя алгоритм NegaMax).

Если вы не знакомы с игрой, вот краткое описание:

Nim - простая игра для двух игроков. Начнем с кучи из 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 Ответ

0 голосов
/ 14 мая 2019

Проверьте состояние остановки.

Вам нужно: 

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
...