我和我的朋友一起参加了一门人工智能方法课程，我们合作完成了期末项目，该项目是使用 C++ 和 OpenGL 编写 Othello（黑白棋）游戏及其 AI。
到目前为止，我们已经完成了棋盘和 Othello 引擎（我正在使用 MVC 类型的方法）。但最难掌握的是 AI。
我们应该编写一个 AI，它在树上使用 Alpha-Beta 剪枝来快速计算出它应该进行的下一步移动。
我们已经理解了 Alpha-Beta 剪枝的概念，以及用于检测哪些方格比其他方格更有价值的算法（就游戏而言）。
然而，我的搭档和我都没有上过数据结构课，因此我们不知道如何在 C++ 中正确创建树，甚至不知道从哪里开始。
所以我的问题是：Stack Overflow，我应该从哪里开始快速（有效地）编写和遍历用于 C++ 中 Alpha-Beta 剪枝的树，而不使用 STL。（我们的作业规定我们不允许使用 STL）。
非常感谢任何和所有的帮助！
回答：
用于 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)该函数递归地评估棋盘位置。“node” 是当前位置，其中“for each child of node” 表示生成新的棋盘位置，这些位置由当前位置的每个可能的移动产生。 depth 参数控制你想要评估树的深度，因为分析无限深度的移动可能是不切实际的。
尽管如此，如果出于教育目的，你必须在修剪之前构建一个给定深度的树，那么具有可变数量子节点的树的结构非常简单，可能如下所示：
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;}