问题标签 [minimax]

我有一个关于 Minimax 算法的简单问题：例如对于井字游戏，我如何确定每个玩家玩的效用函数？它不会自动执行此操作，是吗？我必须对游戏中的值进行硬编码，它不能自己学习它们，是吗？

我在确定空间和时间复杂性时遇到了一些麻烦。例如，如果我有一棵树，它有一个分支因子b并且最多有一个深度d，我如何计算时间和空间复杂度？我知道它们是 O(b^d) 和 O(bd)，但我的问题是如何获得这些值。

我刚开始尝试使用 minimax/negamax 算法，我想出了一个对我来说听起来不错的想法，但由于没有人使用它，这可能是一个有缺陷的逻辑。

我们为什么不这样做：

创建一个 depth=x 的三，确定要走哪一步，然后等待我们的对手。在他完成他的动作之后，我们可以只取我们已经评估过的动作的子树，并在使用旧节点的同时继续更深地构建它。我们可以使用已经评估过的节点值，并用来自新的更深节点的新值对它们进行加权。

尽管新值可能不像通常的方法那样精确，但我们可以更深入地从中获利。

我为我的错误书面和非结构化问题道歉，但我希望你能理解我的想法。

我想为九人莫里斯游戏建立一个游戏树。我想在树上应用 minimax 算法来进行节点评估。Minimax 使用 DFS 来评估节点。那么我应该先将树构建到给定的深度，然后再应用 minimax，还是可以在递归 minimax DFS 中同时进行构建树和评估的过程？

谢谢阿文德

一个学校项目让我用 C++ 编写一个日期游戏（例如http://www.cut-the-knot.org/Curriculum/Games/Date.shtml），其中计算机玩家必须使用 alpha-beta 修剪实现 Minimax 算法. 到目前为止，我理解算法背后的目标是最大化潜在收益，同时假设对手会缩小它们。

但是，我阅读的所有资源都没有帮助我理解如何设计 minimax 所基于的所有决策的评估函数。所有示例都为叶节点分配了任意数字，但是，我需要为这些节点实际分配有意义的值。

直觉告诉我，获胜叶节点的值类似于 +1，失败的叶节点为 -1，但中间节点如何评估？

非常感激任何的帮助。

我来这里是为了问一个特定的话题——我真的在网上找到了一些关于这个的信息。我正在实现 F# 版本的 Minimax 算法。我现在遇到的问题是我想比较我的树的叶子（下面的数据结构）。搜索 VS 给我的错误，我得到了这样的结果：

我曾经拥有的树类型：

以及实施 IComparable 的诱惑

最后，我只想通过其静态值（在其他函数中计算）获取 LeafP 列表的最大值（和最小值）。

上面的代码编译。但是用这个测试：

我在 GetHashCode 的覆盖中的“| :? TreeOfPosition as y -> compare (x) (y)”行中得到了 System.StackOverflowException。

我在 hubfs.net ( http://cs.hubfs.net/forums/thread/15891.aspx ) 中有一个线程，我正在讨论我的 Minimax。在这里你可以找到我最新的代码（http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm）

提前致谢，

佩德罗·杜索

好吧，我非常清楚这个想法，但我无法让它发挥作用。记住我想从叶子列表（“List.max”：P）中获取具有最大静态值的叶子，我认为实现CompareToorEquals会让 List.max 对它们起作用，对吗？我编写这样的东西：

我以这种方式安排功能的问题是：

1）模式鉴别器'LeafP'未定义（LeafP红色下划线）

2) (77,39)：错误 FS0039：未定义值或构造函数“mycompare”，当我尝试按 ALT ENTER 时，此消息出现在我的 F# Interactive 中。位置 {77,39} 对应于 mycompare 调用的开始（在 GetHashCode 中）。

我做错了什么？我能做些什么更好？

非常感谢，

佩德罗·杜索

编辑 3 - 已解决

是的！我最终管理您的工作答案！

最终代码在这里：

感谢您的反馈！

佩德罗·杜索

这个问题更像是一个语义-算法-数据结构问题，而不是一个 F# 句法问题。我有一个 Minimax 算法。极小极大算法应该从起始位置返回最佳下一步移动。为此，它计算所有下一步移动，然后计算下一个下一步移动，直到确定的深度或直到没有更多移动。它像这样构建一棵树：

我有休闲数据结构来处理树：

在上面的示例树中，P和a是分支b，c和d是叶子。下面的代码是我的极小极大算法：

这段代码返回给我一个叶子，例如，c. 当我将递归调用更改为

而这个修改让好叶子的静态值上升了。我需要返回最好的二级节点。希望有人能帮忙！佩德罗·杜索

编辑 1

感谢所有回答的家伙，他们帮助了我很多。很抱歉没有详细说明这些事情。让我们分部分进行：

1）我正在匹配我的 LeafP，LeafP(position, 0)因为当我创建我的树时，我将默认值为 0 的叶子设置为它的静态值。当我提高我的静态值时，消除叶子并使用（最小或最大）静态值制作（在分支之前）叶子我认为这样我可以防止评估前分支叶子（因为它不会有0 值）。

2）我最大的问题是让第二级（必须下的下一步）最好的位置回来。我是这样解决的：

我没有传递整个树，而是仅传递起始节点的子节点，并再次过滤结果列表（具有静态值的前分支列表，该列表对于当前级别来说是最好的）。这样我就得到了我想要的节点。

我认为 kvb 的答案很有趣，但对我来说有点复杂。我没有研究过其他的，但它们只是给了我静态值——我无法让它们为我工作:(

非常感谢所有的答案，他们都给了我很多启发。

这是我的完整代码：（http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm）

佩德罗·杜索

我已经在 Google 和 Stackoverflow 上搜索过这个问题，但我仍然不明白 minimax 函数是如何工作的。

我发现维基百科条目有一个伪代码版本的函数：

我在 Google 中找到的其他几个极小极大函数基本相同；我正在尝试在 C++ 中实现这一点，这就是我迄今为止提出的：

如您所见，我对这个极小极大函数感到很困惑。请至少给我一些提示来帮助我解决这个问题。

谢谢！:)

这是一个跳棋游戏。查看旧版本代码的修订历史。

我正在尝试使用深度 0，并且在大约一半的比赛中得分是正确的，然后突然之间它开始搞砸了。其中一名球员将开始宣称他的分数高于实际分数。为什么只能玩半场？！

只要我是一名程序员，我仍然接受过非常初级的算法教育（因为我是自学的）。也许有一本很好的关于它们的初学者书籍，您可以在回答中提出建议。