国际象棋negamax函数

Question

嗨!

我正在尝试为我的国际象棋引擎写一个negamax搜索算法，但是我似乎不能让它工作。我使用wikipedias伪代码作为示例，但不知何故它并没有产生预期的结果。当我用ply 2运行它时，它改变了我的棋盘数据结构，尽管它不应该改变。当函数用ply 2运行完后，所有的白色(或黑色)都取决于哪个玩家调用了这个函数。棋子从起始位置向前移动2个空间。

我的make和unmake移动函数工作得很好，因为我用一个非递归函数测试了它们，它最多可以搜索5层。然后，它完美地工作了。一定是我的negamax实现出了问题。

非常感谢您的帮助！

def negaMax(self, board, rules, ply, player):
        """ Implements a minimax algorithm. """
        if ply == 0:
            return self.positionEvaluation()

        self.max_eval = float('-infinity')

        self.move_list = board.generateMoves(rules, player)
        for self.move in self.move_list:
            board.makeMove(self.move, player)
            self.eval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player))
            board.unmakeMove(self.move, player)

            if self.eval > self.max_eval:
                self.max_eval = self.eval

        return self.max_eval

Answer 1

这里的主要问题是我认为使用对象变量而不是局部变量。

self.move是一个对象变量，每次你改变它--递归的每一层都会“看到”变化，这对于递归算法来说通常是件坏事。

递归算法应该是自包含的，如果对调用环境有任何更改，应该做最少的修改-这使得遍历算法流变得更容易。

我在这段代码中看到的两个主要问题是：

1. self.move应为局部变量(将其声明为move)。当你稍后这样做时：board.unmakeMove(self.move, player) -我怀疑棋盘正在撤销一个不同的移动，这是在递归树中设置得更深的，而不是你想要的。使用局部变量将消除这种不受欢迎的行为。
2. 递归调用的每一层都在设置self.max_eval = float('-infinity') -因此您需要不断地更改它，尽管这可能不是您想要做的。

解决方案应该是这样的：

def negaMax(self, board, rules, ply, player):
        """ Implements a minimax algorithm. """
        if ply == 0:
            return self.positionEvaluation()

        max_eval = float('-infinity')

        move_list = board.generateMoves(rules, player)
        for move in move_list:
            board.makeMove(move, player)
            currentEval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player))
            board.unmakeMove(move, player)

            if currentEval > max_eval:
                max_eval = currentEval 
        return max_eval

我不能100%确定它确实能解决代码中的所有问题(但它能解决一些问题)，但我100%确定避免使用对象变量会让你的代码更容易理解和调试。