有必要为α-β修剪算法创建一棵树吗？
我在网上看到过minimax和alpha-beta修剪算法的实现。这些实现使用数组而不是树结构来生成可能的游戏动作。
有必要为这些算法创建一棵树，使用带节点的结构吗？为什么使用数组来存储游戏树？
共有1个答案
对于α-β/极小值和其他相关算法，不需要显式地创建树/将其存储在内存中。您通过递归函数调用隐式地“遍历”一棵树，但永远不会显式地创建一个，也永远不需要在这种“树”的任何节点中存储任何数据。
给定一个游戏状态，您只需要暂时使用一个数据结构来包含该状态的合法移动或后续游戏状态；类似于数组/列表的东西是最明显的数据结构。您只需要暂时使用它，这样您就可以循环使用它并运行递归函数调用，之后您可以再次丢弃它们。您将永远不必存储完整的树。
-
我不明白为什么表条目的标志被原样使用。例如，考虑具有α-β修剪和转置表的Negamax的伪代码，并集中于TT部分。 没关系。如果条目包含确切值的下限，我们尝试从左侧缩小窗口，依此类推。 而这部分我不明白。如果值太小，为什么我们设置上限标志？值位于搜索窗口的左侧 - 它小于已知的下限 - alpha。所以看起来值应该是一个下限。 从我的测试和每个人都使用那个版本的事实来看，我肯定是错的。但我不明白为
-
我做了一个Tic-Tac-Toe游戏，使用Minimax和Alpha-Beta修剪。我想为Tic-Tac-Toe（10x10）游戏制作一个计算机AI，但它的游戏树大得离谱。 我的代码是这样的，我只需要更改两个变量就可以更改一行中所需的板大小单元格。例子： 和 我希望你明白了。 所以，我把我的计划从10x10改为3x3，效果很好。 然后我改变和，使其成为（4x4）井字游戏。 现在，我认为使用Alph
-
我在为游戏筷子做一个C程序。 这是一个非常简单的游戏，总共只有625个游戏状态（如果考虑到对称性和不可到达的状态，它甚至更低）。我读过minimax和alpha-beta算法，主要是针对tic-tac-toe的，但我遇到的问题是，在tic-tac-toe中，不可能循环回到以前的状态，而这在筷子中很容易发生。因此，当运行代码时，它将以堆栈溢出结束。 我通过添加以前访问过的州的标志来解决这个问题(我不
-
我正在研究一个简单的tic-tac-toe问题，我正在努力理解Minimax算法是如何工作的。 如果我使用效用函数1表示X win，-1表示O win，0表示正在进行的游戏，那么我不明白算法如何优先考虑较短的解决方案。据我所知，它首先到达最深的节点，如果它不是最短的路径，但它会导致可能的胜利，那么它会选择它。 让我在例子中解释一下。这是电路板的状态和X转角（符号来自https://www.hack
-
我正在尝试用换位表实现增强的α-β-最小-最大修剪。我使用这个伪代码作为参考： http://people.csail.mit.edu/plaat/mtdf.html#abmem 这个算法有三个问题: > 我相信我应该在每个保存的换位表条目中存储深度（=到叶级的距离），并且仅在 entry.depth 时才使用条目 我想存储每个位置的最佳移动，以便在搜索停止后使用它进行移动排序和提取最佳移动。在纯
-
假设给定一组树ST，每棵树的每个顶点都被标记。另外还给出了另一棵树T（也有顶点标签）。问题是如何找到ST的哪些树可以从T的根开始跨越树T，从而使生成树T的顶点标签与T的顶点标签一致。请注意，T的每个顶点的子节点要么完全覆盖，要么根本不覆盖——不允许部分覆盖子节点。换句话说：给定一棵树和以下过程：选择一个顶点，删除该顶点以下的所有顶点和边（除了顶点本身）。找到ST的那些树，这样每棵树都是用一系列应用