Connect-K AI 的良好启发式

Question

我正在编写一个 Connect-K 简单 AI（没有修剪，只有 4 层）。我想知道什么是可以快速计算的最佳启发式算法。

比我拥有的更好的东西：

def eval(board, player)
    connections = 0
    magnitude = 0
    for x in range(0, self.boardW(board)):
        for y in range(0, self.boardH(board)):
            if(self.get_player(board, x, y) == player): #assuming x and y are in bounds
                temp = 1
                # keep checking in this direction to find the max temp can be
                if (magnitude < temp):
                    magnitude = temp
            if(self.get_player(board, x, y) == player):
                connection += 1
        ........
    return connection**2 + magnitude**2

基本上这应该是 return 板上任何点与其相邻点的最大连接数，加上 8 个方向（向上、向下）中任意一个的连续项目数, 左, 右, 左上, 左下, ...)

我的k会大于4；因此我无法进行详尽的树搜索。

Answer 1

一个min-max search could be useful in this scenario, possibly combined with a simplified MCTS。基本上，更深层次的递归会让你达到游戏的更多结束状态。通过分析在每种情况下获胜的玩家，您可以更好地了解某步棋的价值。

最小-最大方法对于两个玩家之间的博弈非常有用，并广泛用于此类棋盘游戏。 MCTS 可能有点矫枉过正，但总体思路是用广泛的搜索换取随机的、更深入的搜索。例如，您可以随机选择 10 个分支，并使用相同的计算量进行 6-7 次递归，而不是使用 20 的分支因子和 5 级递归（20^5 = 320 万）。

在类似的项目（跳棋的 AI）中取得了良好效果的是在递归中进一步降低分支因子。通过定义最大分支（递归步骤中要探索的最大分支数），让这个数字大于顶层的典型分支，并进一步减少递归到更小的数字（5-10 相当很快，底部是 1-3）。这样，您就可以两全其美。你探索了所有即将发生的动作，但你也得到了很多关于它们如何影响游戏后期的信息。

快速回顾一下：使用 MCTS 和 min-max，您可以找到很多最终状态。如果对手赢了，给它一个很大的负分。如果你赢了，给它一个很大的正分如果两者都没有，你可以给它一个 0，或者使用你在问题中显示的函数。利用min-max算法让父游戏状态的分数取决于子游戏状态的分数。

Connect-K AI 的良好启发式

Good Heuristic for Connect-K AI

python

performance

artificial-intelligence

heuristics