java - 为黑白棋/黑白棋游戏创建 negamax/minimax 节点

Question

我为黑白棋游戏编写了 AI 播放器，我决定使用 NegaMax 或 MiniMax 来实现。伪代码:

function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
    else
        foreach child of node
            val := -negamax(child, depth-1, -β, -α, -color)
            {the following if statement constitutes alpha-beta pruning}
            if val≥β
                return val
            if val≥α
                α:=val
        return α

但是我需要将 Node 发送到这个函数，我该如何创建这个节点？就像创建具有所有可能的状态移动的节点，然后为节点中每个可能的移动创建子节点？

如果您可以帮助确定 α、β 值...

Answer 1

节点可能意味着代表一个状态。在游戏中，这是棋盘的状态(对于奥赛罗来说，棋子的位置、棋子的走法等等)。一般来说，在使用 alpha/beta 剪枝的游戏中，生成所有接下来的状态是可能的，但生成所有可能位置的所有状态是不可能的。

如果您使用 Java，则 Node 对象可能有一个方法 getChildren() 来生成该状态下所有可能的移动，它们本身就是 Node 对象。

至于α、β值，它们被初始化为Integer.MIN_VALUE和Integer.MAX_VALUE