3

我正在和我的一个朋友一起学习人工智能方法的课程，我们已经合作完成了最终项目，该项目正在使用 C++ 和 OpenGL 编写奥赛罗和人工智能。

到目前为止，我们已经有了开发板和 Othello 引擎（我使用的是 MVC 类型的方法）。但事实证明难以掌握的一件事是人工智能。

我们应该编写一个 AI，它在树上使用 Alpha-Beta 修剪来快速计算它应该采取的下一步行动。

就游戏而言，Alpha-Beta 修剪的概念，以及用于检测哪些方格比其他方格更有价值的算法。

但是，我和我的伙伴还没有学习数据结构课程，因此我们不知道如何在 C++ 中正确创建树，甚至不知道从哪里开始。

所以我的问题是，Stack Overflow 是：我从哪里开始在不使用 STL的情况下快速（有效地）编写和遍历 C++ 中的 Alpha-Beta 修剪树。（我们的作业表明我们不允许使用 STL）。

感谢您提供任何和所有帮助，谢谢！

4

1 回答 1

2

用于 alpha-beta 修剪的树通常是隐式的。这是一种防止您的 AI 搜索算法将时间浪费在错误解决方案上的方法。这是来自维基百科的伪代码：

function alphabeta(node, depth, α, β, Player)         
    if  depth = 0 or node is a terminal node
        return the heuristic value of node
    if  Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Beta cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Alpha cut-off *)
        return β 
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

该函数递归地评估棋盘位置。“节点”是当前位置，它所说的“对于节点的每个子节点”是您生成新棋盘位置的位置，这些新棋盘位置是由当前位置的每个可能移动产生的。深度参数控制您想要评估树的距离，因为分析移动到无限深度可能是不切实际的。

尽管如此，如果您必须在出于教育目的修剪之前构建一棵给定深度的树，那么具有可变数量子节点的树的结构非常简单，可能看起来像这样：

struct Node
{
    Node ** children;
    int     childCount;
    double  value;
};

Node * tree;

这children是一个带有 childCount 成员的 Node 数组。叶节点将具有childCount=0. 要构建树，您将搜索可用的板位置，如下所示：

Node * CreateTree(Board board, int depth)
{
    Node * node = new Node();
    node.childCount = board.GeAvailableMoveCount();
    node.value      = board.GetValue;
    if (depth > 0 && node.childCount > 0)
    {
        node.children = new Node * [node.childCount];
        for (int i = 0; i != node.childCount; ++i)
            node.children[i] = CreateTree(board.Move(i), depth - 1);
    }
    else
    {
        node.children = NULL;
    }
    return node;
}

void DeleteTree(Node * tree)
{
    for (int i = 0; i != tree.childCount; ++i)
        DeleteTree(tree.children[i]);
    delete [] tree.children; // deleting NULL is OK
    delete tree;
}
于 2011-08-01T07:13:44.220 回答