最小化/α-β修剪如何优先考虑较短的路径？
我正在研究一个简单的tic-tac-toe问题，我正在努力理解Minimax算法是如何工作的。
如果我使用效用函数1表示X win，-1表示O win，0表示正在进行的游戏，那么我不明白算法如何优先考虑较短的解决方案。据我所知，它首先到达最深的节点，如果它不是最短的路径，但它会导致可能的胜利，那么它会选择它。
让我在例子中解释一下。这是电路板的状态和X转角（符号来自https://www.hackerrank.com/challenges/tic-tac-toe):
OX_
_X_
__O
如果我们从左上角位置搜索到右下，那么算法会发现，如果我们把X放在位置（0,2）上，导致它不可避免地赢得下一个回合：
OXX
_X_
__O
然而，更明智的选择是（2，1）和直接获胜的位置：
OX_
_X_
_XO
我看不出极小值或α-β修剪会优先考虑这种行为。
所以我的问题是我是否正确理解它，以及如何改进它。
共有1个答案
Tic-Tac-Toe的Minimax几乎没有可能的数值估值：赢、输、平。Minimax算法指定了其他玩家后续移动可以最小化玩家位置的所有方式的最大值。下一步的胜利将被赋予无限，这是一个明确的选择。否则，在Tic Tac Toe中，除少数特殊情况外，它将优先考虑平局，例如在下一步中获胜或能够创造一个叉子（导致在下一步中取得一定胜利）。
Alpha-Beta剪枝是一种优化方法，当可以证明搜索树的任何部分都会产生比已经发现的部分更糟糕的结果时，它可以避免探索搜索树的部分；例如，假设一个完整的节点探索产生了一个潜在的吸引，而另一个节点的叶子显示了损失；探索后一个节点的其他子节点是没有意义的（除非您假设其他玩家不会总是发挥他们的最佳动作）。您可能会发现此链接很有用：https://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html
-
我不明白为什么表条目的标志被原样使用。例如，考虑具有α-β修剪和转置表的Negamax的伪代码，并集中于TT部分。 没关系。如果条目包含确切值的下限，我们尝试从左侧缩小窗口，依此类推。 而这部分我不明白。如果值太小，为什么我们设置上限标志？值位于搜索窗口的左侧 - 它小于已知的下限 - alpha。所以看起来值应该是一个下限。 从我的测试和每个人都使用那个版本的事实来看，我肯定是错的。但我不明白为
-
我在为游戏筷子做一个C程序。 这是一个非常简单的游戏，总共只有625个游戏状态（如果考虑到对称性和不可到达的状态，它甚至更低）。我读过minimax和alpha-beta算法，主要是针对tic-tac-toe的，但我遇到的问题是，在tic-tac-toe中，不可能循环回到以前的状态，而这在筷子中很容易发生。因此，当运行代码时，它将以堆栈溢出结束。 我通过添加以前访问过的州的标志来解决这个问题(我不
-
我正在尝试用换位表实现增强的α-β-最小-最大修剪。我使用这个伪代码作为参考： http://people.csail.mit.edu/plaat/mtdf.html#abmem 这个算法有三个问题: > 我相信我应该在每个保存的换位表条目中存储深度（=到叶级的距离），并且仅在 entry.depth 时才使用条目 我想存储每个位置的最佳移动，以便在搜索停止后使用它进行移动排序和提取最佳移动。在纯
-
我做了一个Tic-Tac-Toe游戏，使用Minimax和Alpha-Beta修剪。我想为Tic-Tac-Toe（10x10）游戏制作一个计算机AI，但它的游戏树大得离谱。 我的代码是这样的，我只需要更改两个变量就可以更改一行中所需的板大小单元格。例子： 和 我希望你明白了。 所以，我把我的计划从10x10改为3x3，效果很好。 然后我改变和，使其成为（4x4）井字游戏。 现在，我认为使用Alph
-
例如，给定以下矩阵： 其中对于每个元组，第一个数字是食物，第二个数字是水。我需要从右下角到左上角，我只能向上或向左移动。
-
我正在使用for。对于这个我正在使用，https://github.com/vyuldashev/laravel-queue-rabbitmq. 对于正常队列和消费者，一切都很好。为了区分消息的优先级，我定义了多个队列，在队列名中使用0-3作为后缀。我通过手动计算作业总数，将作业路由到不同的队列。 使用这种方法，对于不同的任务，我需要创建更多具有名称优先级的队列。创建队列名称中包含 0-3 的队列