“Blokus”游戏的人工智能（1-4名玩家）

Question

我们正在开发一个基于Blokus游戏的Java小游戏。Blokus手册

我是Java初学者，计划实现一个高级人工智能。我们已经有了一个随机AI(选择一个随机有效的移动)和一个带有简单移动评级机制的AI。我们也想要一个尽可能好的人工智能(或者至少非常好；) ).

问题是：哪种AI概念适合我们的目的？最小轴算法似乎是一个有效的选择，但你如何将其适应4人游戏？像blokus这样的游戏有更好的概念吗？

已经谢谢了:)

Answer 1

我会推荐minimax算法。你可以增加一件事来使它更有效(意味着你应该能够在未来走得更远)，那就是阿尔法-贝塔修剪。

极大极小搜索的问题是，它必须检查的游戏状态的数量在树的深度上是指数级的。不幸的是，我们不能消除指数，但事实证明我们可以有效地将其减半。

这句话来自Stuart Russel和Peter Norvig的《人工智能：现代方法》第三版第5.3章。它举起了我的显示器，我在大学的一些课程中使用它。我知道人们不经常参考SO的书籍，但它非常相关。我已经广泛使用了它，我确实推荐它，因为它既易于理解，又涵盖了广泛的 AI 内容。

它可以在亚马逊上以104美元的价格买到，或者*咳咳*我相信如果你没有那么多钱买一本教科书，你可以在网上找到它。在网上查找最小极大算法和阿尔法β修剪也应该会给你带来好的结果。

我认为唯一会使 Minimax 成为您糟糕选择的情况是，如果游戏状态对任何给定玩家来说只能部分观察到（他们不知道正在发生的事情的一切），或者如果游戏是不确定的（它有随机元素）。因为这些都不是Blokus的情况，我认为你对Minimax做出了很好的选择。

人工智能领域在教科书中被称为对抗性搜索(第5章:对抗性搜索)，所以用这个术语在网上查找更多信息可能会得到更多有用的信息，或者帮助你找到一个Java实现的例子。我不认为这是一个初学者的任务，但听起来你可以胜任，如果你做了这个游戏，并能随机选择有效的移动。继续努力吧！

Answer 2

从理论上讲，一个“尽可能好的AI”是一个完美的AI，它是一个在游戏中的任何时刻都完全了解游戏状态(如果人类玩家不知道完整的游戏状态)的AI。在游戏中，每个人都有完整的游戏状态知识(像Blokus)，一个尽可能好的人工智能是一个可以尝试预测最佳行动的人工智能(这里是minimax，如你所说)。你也可以谷歌一下遗传算法和模拟退火，因为它们是有效的，这取决于你想要什么。此外，你可以为2个以上的玩家使用minimax。

Answer 3

在4人游戏中很难实现Min-max，因为：

< li >决策树呈指数级增长，因此内存和/或计算时间会限制在< code>log(medMoves)=N步。对于一个4人游戏来说，这是N/4。例如，如果N是8，你只能看到每个玩家的2步棋。 < li >玩家勾结很难解释。在现实游戏中，一些玩家可能会互相帮助(即使他们不在同一个团队)。这将导致他们偏离个人的“最大值”。

如果你想要Minmax，你将不得不做大量的修剪才能使其可行。我的建议是学习一些模式，这样人工智能就会知道如何做出反应。这可以通过神经网络或强化学习来完成，只需进行一些调整。

这些模式可以是静态的(您可以手动或以编程方式创建输入场景)，也可以是动态的(创建所有有效的场景并随机选择得分最高的场景)。