artificial-intelligence - 可以在expectiminimax算法中实现剪枝吗？

Question

我目前正在使用 expectiminimax 算法，该算法在我目前的情况下效果很好：

max -> min -> chance -> max -> min -> chance -> (repeat)

我无论如何都做不到

max/min -> Chance -> (repeat)

由于游戏的运作方式。

如果我继续转换我的算法，我觉得好像 alpha 会不准确。

使用我当前的设置实施修剪（除了地平线效应）是否有任何副作用，或者我只是想多了？

Answer 1

我不确定您要实现哪个游戏，但听起来确实很有趣。当我们对任何节点的分支因子或游戏如何进行一无所知时，真的很难想出一个好的答案。我认为这真的取决于你的游戏。

我在五子棋游戏中尝试了不同的修剪方法，基于这个经验，我真的认为你的搜索算法的结果取决于机会节点对游戏期望的影响程度，与最小和最大节点改变期望的程度相比.

如果机会节点可以极大地改变游戏的预期（每次掷骰子的高方差），但五六招之间的选择并没有太大的改变，那么我认为你不必太担心。

但是如果相反的话，机会节点基本上只是在推动游戏前进而不影响游戏结果的预期，而游戏的动作（或动作）确实很重要，我认为获得一个好的搜索算法可以收获很多。

还要检查 *-minimax 算法。（布鲁斯·巴拉德 1983 年）

Expectiminimax 和 *-minimax 与正常的 minimax 相同。首先尝试假设的最佳移动（来自一些启发式）以创建截止，但您还应该尝试启发式排序机会节点中的机会结果。

当您开始测试时，这实际上真的很有趣，但获得好的答案的唯一方法是让您的手指弄脏并尝试一下。

祝你好运！

Answer 2

看来修剪在这种环境下仍然有效，我有严重的怀疑，但到目前为止一切都已经检查过了。也就是说，非剪枝算法和剪枝算法中的所有测试用例都在较少的节点中提供了具有相同启发式的相同移动。

我还发现，在我的情况下，我会将机会节点的控制权交给用户（如果某些事件有的话，他们可以确定可接受的损失）。如果该技能有 95% 的命中率和 5% 的命中率，用户可以认为这 5% 可以忽略不计并忽略命中率，但这并不意味着启发式被视为其值的 100%，它维持其 95%。在给定环境的情况下，使用 1 种能力可能会出现 16 种可能的结果，而我希望在这种情况下具有灵活性。

至于游戏，至少在游戏风格上会和宝可梦差不多。