“Blokus”游戏的人工智能(1-4玩家)

Question

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

我是一个Java初学者，计划实现一个先进的人工智能。我们已经有一个随机AI (挑选一个随机有效移动)和一个AI与一个简单的移动评级机制。我们还需要一个AI，应该是尽可能好(或至少非常好;)。

问题是:哪种人工智能概念适合我们的目的？minimax算法似乎是一个有效的选择，但你如何使它适应一个4人游戏？像布卢库斯这样的游戏有更好的概念吗？

(谢谢:)

Answer 1

在一个4人游戏中很难实现max，因为：

• 决策树呈指数增长，因此您将被内存和/或计算时间限制为log(medMoves)=N步骤。对于一个4人的游戏，这是下降到N/4。例如，如果N是8，你将只能看到每个玩家的两个移动。
• 玩家合谋是很难解释的。在现实的游戏中，一些球员可能会互相帮助(即使他们不在同一支球队)。这将导致他们偏离他们个人的“最大”。

如果你想要Minmax，你必须做大量的修剪才能使它可行。我的建议是学习一些模式，这样AI就会知道如何做出反应。这可以通过神经网络来完成，也可以通过一些调整来强化学习。

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

Answer 2

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

Answer 3

我推荐极小极大算法。为了提高效率，你可以添加一件事(这意味着你应该能够深入到未来)，那就是α-beta剪枝。

minimax搜索的问题是，它必须检查的博弈状态的数量在树的深度上是指数的。不幸的是，我们不能消除指数，但事实证明我们可以有效地把它切成两半。

这句话来自Artificial Intelligence: A Modern Approach第三版的第5.3章，作者是斯图亚特·拉塞尔和彼得·诺维格。它支撑着我的显示器，我在大学的几节课上使用了它。我知道人们不经常参考这方面的书籍，但这是非常相关的。我已经广泛使用它，我确实推荐它，因为它是可以理解的，并且涵盖了广泛的人工智能内容。

可在亚马逊网站上找到的价格是104美元，或者是咳嗽*我相信如果你没有那么多钱买一本书，你可以在网上找到它。查找minimax算法和αbeta在线剪枝也会给您带来好的结果。

我认为，使Minimax成为一个糟糕的选择的唯一情况是，如果游戏状态对任何给定的玩家都是部分可观察的(他们不知道发生了什么)，或者如果游戏是不确定的(它有随机元素)。因为这两种情况都不是Blokus的情况，所以我认为你在Minimax上做了一个很好的选择。

人工智能领域在教科书中被称为对抗性搜索(第5章:对抗性搜索)，因此使用该术语在线查找更多信息可以获得更多有用的信息，或者帮助您找到Java实现的示例。我不认为这是一个初学者的任务，但听起来你是它的，如果你做了游戏，并可以选择随机有效的动作。保持良好的工作状态！