（Python Nim 游戏的 NegaMax 算法）我的代码有什么问题？

Question

我是人工智能的新手。我的作业要求我在 Python 中编写一个程序，以最佳方式玩 Nim 游戏（使用 NegaMax 算法）。

如果你不熟悉这个游戏，这里有一个简单的描述：

Nim 是一款简单的双人游戏。我们从一堆 n 场比赛开始，其中 n ≥ 3.

Max 和 Min 两名玩家轮流从火柴堆中移除 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，Min和Max在每一轮中总是需要1场比赛。

我觉得问题是评价不对，但是看不出哪里错了。任何帮助，将不胜感激！谢谢！

Answer 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

（Python Nim 游戏的 NegaMax 算法）我的代码有什么问题？

(Python NegaMax Algorithm for Game of Nim) What is wrong with my code?

python

artificial-intelligence

negamax