artificial-intelligence - 是否可以对两个以上玩家的非零和游戏使用 alpha-beta 修剪？

Question

我在某处读到，minimax 算法可以推广到两个以上的玩家。想象一下，我们有 3 个玩家，他们每个人都想最大化自己的答案。在这种情况下是否可以使用 alpha-beta 修剪？还是没用？为什么？

注意：游戏是非零和游戏。

标签： artificial-intelligenceminimaxalpha-beta-pruning

Answer 1

是的，但你必须清楚游戏机制。您给定的树首先显示蓝色移动，然后是绿色移动，红色有最终选择。

这里有两种方法，具体取决于游戏机制。如果每个玩家的唯一目的是最大化他们自己的结果，那么您需要为活跃玩家解决每个级别，只考虑相关的奖励。

在给定的示例中，假设奖励按顺序列出（蓝色、绿色、红色），那么红色对 (2-4)、(9-4)、(0-6)、(0- 2) 将是 R,L,R,R; 呈现green值 (8-5),(9-3)。从这些中，green将选择 L,L；blue获得选择 (6-8) 并将做出 R 选择，并选择 (8, 9, 6) 作为游戏价值。

---

但是，如果玩家有任何其他动机，例如最大化整体收益（我们在上面碰巧实现了）或赋予净差异价值，那么您将需要使用更复杂的决策算法；同样的逻辑也适用。

对于一个足够复杂的游戏，其中玩家是对立的，并且同时进行秘密行动，您可能必须切换到“一对多”模型，其中每个玩家都假设其他人会做出最小化选择玩家奖励的选择。这种最坏情况的计划将您带回到一个简单的极小极大过程，其中两个对手合并为一个玩家，假装游戏实际上是一个零和问题。