我正在考虑为一个可能有两到四个玩家的游戏构建AI。在这个领域做了一些研究后，看起来标准的极小化极大算法都不适用，除非你构建一个“偏执”的AI，它假设所有玩家都想对付它，并且可以有效地被视为一个更大的对手，轮到它时会多走几步。

游戏的一部分问题在于棋盘非常大，通常每个玩家在任何一个回合都有数百种可用的移动。此外，某些移动可能允许玩家再次移动。这使得任何广度优先搜索都极其昂贵，除非你进行激进的剪枝。

为了提供背景，游戏大致类似于跳棋，但棋盘大约是跳棋的4倍大。

有没有适合这种游戏的算法？或者我最好的选择是使用启发式方法而不进行任何移动树搜索？

回答：

你这里提出了多个问题。

简单的问题是，“我该如何处理这个巨大的移动空间？”一个好的答案是，使用带有棋盘评估启发式的树搜索。基本概念是，由于搜索空间太大无法直接处理，你可以尽可能合理地向前搜索，在搜索结束时，使用你对游戏本身的了解来评估哪些叶节点是最好的。

例如，国际象棋中有一个粗略的规则，兵的价值为1，象和马的价值为3，车的价值为5，王后的价值为9，所以在你的搜索过程中结束时，你可能会使用一个棋盘评估函数来计算双方总分，并用它作为评估函数。（警告：这个特定的评估函数非常粗糙。好的函数将取决于棋子的位置，是否被将军等。棋盘评估函数并不是容易想出的。）

难的问题是，“我如何处理超过两个玩家的情况？”这是一个非常难的问题。一种处理方法是假设每个玩家都严格为了赢得游戏，并相应地调整搜索算法。这与假设所有对手都在合作和协调并不完全相同。我相信Russell和Norvig在《人工智能：一种现代方法》一书中关于对抗性搜索的章节中专门讨论了这个想法。不过，AIMA在这方面的讨论只是对多玩家AI的一个指引。

多玩家——也就是说，多代理——AI是一个比单代理AI复杂得多的任务。