4

你好！

我正在尝试为我的国际象棋引擎编写一个 negamax 搜索算法，但我似乎无法让它工作。我以 wikipedias 伪代码为例，但不知何故它不会产生预期的结果。当我以 2 层运行它时，它会改变我的电路板数据结构，尽管它不应该。在第 2 层函数完成运行后，所有白棋（或黑棋。取决于玩家调用该函数的名称。）棋子从起始位置向前移动 2 个空格。

我的 make 和 unmake move 函数运行良好，因为我使用搜索多达 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
4

1 回答 1

4

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

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% 肯定避免使用对象变量会使您的代码更容易理解和调试。

于 2012-09-09T22:20:51.717 回答