问题标签 [minimax]

我正在为 3x4（行 x 列）网格上的 3-in-a-row 游戏的 negamax 算法而苦苦挣扎。它像众所周知的 4-in-a-row 一样播放，即丢掉棋子（不像井字游戏）。让我们称玩家 R 和 B。R 有第一步，B 的动作由 negamax 控制。可能的移动是 1、2、3 或 4。这是在 R：移动 3 --> B：移动 1 --> R：移动 3 之后到达的相关位置：

现在，为了防御 R 的第 3 步，B 必须自己下第 3 步，但它拒绝这样做。取而代之的是，它执行第 1 步，并且在 R 的下一步移动之后游戏结束。

顺便说一句，我花了一整天的时间寻找我的 negamax 实现中的错误，该错误非常适用于 3x3 网格，但我找不到任何错误。

然后我开始思考：对于负最大算法行为的另一种解释是，在 R 在 3x4 网格上以第 3 步开始游戏之后，无论如何 B 在所有变体中都丢失了。

任何人都可以反驳这个命题或指出我的证据（我更喜欢;-)）吗？

谢谢， 塞尔

我正在为 Chomp 游戏编写程序。你可以在Wikipedia上阅读游戏的描述，但无论如何我都会简要描述一下。

我们在一块尺寸为 nxm 的巧克力棒上玩耍，即巧克力棒被分成 nxm 个正方形。在每一回合，当前玩家选择一个方格并吃掉所选方格下方和右侧的所有东西。因此，例如，以下是有效的第一步：

目标是迫使你的对手吃掉最后一块巧克力（它是有毒的）。

关于 AI 部分，我使用了带有深度截断的极小极大算法。但是我想不出一个合适的位置评估函数。结果是，使用我的评估函数，人类玩家很容易战胜我的程序。

任何人都可以：

• 建议一个好的位置评估函数或
• 提供一些有用的参考或
• 建议替代算法？

我正在编写一个游戏，它是Gomoku的变体。基本上是一个巨大的棋盘上的井字游戏。

想知道是否有人知道该游戏的良好 AI 策略。我当前的实现非常愚蠢并且需要很长时间（O（n ^ 3），大约1-2秒才能采取行动）：

在井字游戏的极小极大实现完全失败后，我看不出有什么问题。现在，我的 AI 只是绕了一圈……

为什么会这样？

我花了一整天的时间尝试实现极小极大，但并没有真正理解它。现在，我想我了解极小极大的工作原理，但不了解 alpha-beta 修剪。

这是我对极小极大的理解：

1. 生成所有可能移动的列表，直到深度限制。

2. 评估游戏场对底部每个节点的有利程度。

3. 对于每个节点，（从底部开始），如果层为最大值，则该节点的分数是其子节点的最高分数。如果层是 min，则该节点的分数是其子节点的最低分数。

4. 如果您尝试将其最大化，则执行得分最高的移动，或者如果您想要最小得分，则执行最低的移动。

我对 alpha-beta 剪枝的理解是，如果父层是 min 并且您的节点的分数高于最低分数，那么您可以对其进行剪枝，因为它不会影响结果。

但是，我不明白的是，如果您可以计算出一个节点的分数，您将需要知道低于该节点的层上所有节点的分数（以我对极小极大的理解）。这意味着您仍将使用相同数量的 CPU 功率。

谁能指出我做错了什么？这个答案（为白痴解释了 Minimax）帮助我理解了 minimax，但我不明白 alpha beta pruning 会有什么帮助。

谢谢你。

我已经按照维基百科文章上的伪代码，我想我得到了它的工作。但是，它会返回分数，当我想知道我想采取什么行动时，这并没有帮助。

我尝试了一种我认为是获得最佳移动的方法，但我认为它不起作用，因为当我真正尝试与它（国际象棋）下棋时，人工智能会做出一些深度级别为 3 的迟缓移动。

这是我的功能：

首先让我说这个问题可能由没有 Prolog 经验的 AI 向导来回答。

优秀的Prolog Programming for AI书有这个非常简洁和聪明的 minimax 实现：

然而，作者并没有详细描述它，我想知道它是什么min_to_move/1和max_to_move/1是什么。

谁能向我解释这些？

提前致谢！

我正在建造一个井字游戏解决机器人。为了练习，我使用极小极大算法编写了一个井字游戏，效果非常好。当我想将我的代码移植到控制器时，我发现这个控制器的 C/C++ 编译器都不支持递归函数。因此，我需要帮助将此递归 minimax 函数转换为使用迭代或内部堆栈的函数：

我完全不知道如何做到这一点。我很感激任何帮助:)

当使用带有 Alpha-Beta 修剪的 Minimax 时，是否可以将 alpha 和 beta 作为类变量而不是通过递归发送它们？

代替：

我可以写：

我之所以问是因为当我尝试通过这样做来优化代码时（我的想法是，如果我不需要将整数发送到每次递归，我可能会花一点时间），我的棋手突然变成了一个白痴，牺牲了他的女王来杀死一个棋子，并犯了其他愚蠢的错误。

他的表现总是比他的“常规 Alpha-Beta”对手差很多，我猜这是因为与他的对手相比，他也只搜索了一小部分树（他们都使用相同的深度，但修改后的玩家似乎修剪了更具侵略性，从而减少访问的节点数量）。为了确保这一点，我现在已经做了两次，除了我在这里描述的内容之外，我不会改变任何其他东西。

如果我正确理解了 Alpha-Beta 算法，这应该不会有任何区别，但对于我的棋手来说，确实如此。我做错什么了吗？

所以，我现在的主要问题不是它是否是优化明智或代码实践明智的好事，而是它是否应该可以做。

我一直在尝试在 java 中创建和填充树，然后使用 minimax 算法为 AI 找到最佳课程。

生成树的递归函数：

用值填充树的函数：

通过打印内容来测试功能以查看是否一切正常：

并且，节点类本身： final class Node {
public String state = "BCXXXCXXX";

}

我运行打印功能，它打印出我期望的第一个节点的 1 BxXXCXXX。我用一个空节点调用它，深度为 1。为什么它不生成（或打印）树的其余部分，深度为 6？

尽管我认为这可能无关紧要，但此代码最终将用于 Android 游戏。