有没有办法在alpha-beta修剪后进一步优化minimax算法

Question

我刚刚在 python 上完成了 connect 4 游戏的编码并向其中添加了极小极大算法，但是（我可能只是夸大了一点）花了一百万年的时间。所以，我在其中添加了 Alpha-Beta 剪枝。但是，当我在 10 分钟后写这篇文章时，它仍在加载并寻找最佳着法。post。

有什么帮助并尝试对其进行更多优化。提前致谢。

 def minimax(self, arr, a, b, depth, maximising):
    result = self.checkWin(arr)
    if result:
        d = {'R': +1, 'B': -1, 'Tie': 0}
        return d[result]
    if maximising is True:
        bestScore = -math.inf
        for i, j in self.getPossible(self.board):
            if arr[i][j] == '':
                arr[i][j] = 'R'
                score = self.minimax(arr, a, b, depth - 1, False)
                arr[i][j] = ''
                bestScore = max((score, bestScore))
                a = max((a, score))
                if b <= a:
                    break
        return bestScore
    else:
        bestScore = math.inf
        for i, j in self.getPossible(self.board):
            if arr[i][j] == '':
                arr[i][j] = 'B'
                score = self.minimax(arr, a, b, depth - 1, True)
                arr[i][j] = ''
                bestScore = min((score, bestScore))
                b = min((b, score))
                if b <= a:
                    break
        return bestScore

这是评估函数，我想我一直走到极小极大树的末端，如果我不应该这样做，那么有人能告诉我我应该为树的非终端状态分配什么值.

Answer 1

一般来说，您可以通过 3 件事来加速您的 AI：

更快地找到给定位置的所有可能走法。
更快地评估给定位置。
通过巧妙的截断使 minimax 算法更快。

首先你需要找到你的瓶颈。花了多少时间寻找所有着法，又花了多少时间评估位置？

从第 3 点开始，您已经实现了 alpha-beta，这使它更快，并且给您的结果与没有 alpha-beta.

的结果相同

您可以尝试的另一件事是转置 tables。为简化起见，您将在 table 中存储有关职位的信息以及职位的评估。因此，如果您再次遇到树中的相同位置，则不必搜索节点并对其求值，只需从转置中获取值 table.

您可以查看 chessprogramming.org 以获取有关您可以将哪些其他修剪技术应用于 connect 4 的灵感。

有没有办法在alpha-beta修剪后进一步优化minimax算法

Is there a way to optimise the minimax algorithm further after alpha-beta pruning

python

optimization

minimax

alpha-beta-pruning