一个"Blokus"游戏的人工智能（1-4人玩）

Question

我们正在制作一款基于Blokus游戏的Java小游戏。这里是游戏规则链接：Blokus-Manual。

我是初学Java的人，并计划实现一个高级的人工智能。我们已经有了一种随机AI(选择一个随机有效移动)和一种带有简单移动评估机制的AI。我们还希望有一种尽可能好的AI（或者至少非常好;））。

问题是：哪种AI概念适合我们的目的？Minimax算法似乎是一个合理的选择，但是如何将它适应于4个玩家的游戏？在像Blokus这样的游戏中，是否有更好的概念？

谢谢 :)

- Xyarvius

---

这里有一篇有趣的论文：http://www.aaai.org/Papers/AAAI/2000/AAAI00-031.pdf - FarK

Answer 1

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

• 决策树呈指数级增长，所以你会受到内存和/或计算时间的限制，只能进行log(medMoves)=N个步骤。对于4人游戏，这将降至N/4。例如，如果N为8，则每个玩家只能看到2步。
• 玩家勾结很难考虑到。在现实游戏中，一些玩家可能会互相帮助（即使他们不在同一个团队）。这将导致他们偏离自己的个人“最大值”。

如果你想要Minmax，你需要进行大量修剪才能使其可行。我建议学习一些模式，让AI知道如何反应。这可以通过神经网络或强化学习进行一些调整来完成。

这些模式可以是静态的（可以手动或程序创建输入场景），也可以是动态的（创建所有有效场景并随机移动选择得分最高的场景）。

- Razvan Manolescu

Answer 2

理论上来说，一个“尽可能好的AI”是一个完美的AI，在游戏中任何时刻都具有对游戏状态的完全了解（如果人类玩家不知道完整的游戏状态）。在每个人都知道完整游戏状态的游戏（如Blokus）中，尽可能好的AI是一种可以尝试预测最佳移动的AI（这里使用minimax算法，正如您所说）。您也可以搜索遗传算法和模拟退火算法，它们是有效的，具体取决于您想要什么。此外，您可以将minimax用于超过2个玩家的情况。

- Miguel Cunha

Answer 3

我建议使用极小化极大算法。为了使其更有效率（也就是说，您应该能够深入未来几步），可以添加一些东西，如阿尔法贝塔剪枝。

引用来自Stuart Russel和Peter Norvig的《人工智能：一种现代方法》第三版的第5.3章节。它曾经支撑过我的显示器，并在我大学的几个课程中使用过。我知道人们不经常在SO上引用书籍，但它非常相关。我已经广泛使用它，并真正推荐它既易于理解，又涵盖了广泛的AI内容。

您可以在亚马逊上以104美元的价格购买，或者 *咳咳*如果您没有那种购买教材的费用，我相信您可以在网上找到它。在网上查找极小化极大算法和阿尔法贝塔剪枝也可以获得良好的结果。

我认为唯一会使Minimax成为您的不良选择的情况是游戏状态只对任何一个玩家部分可见（他们不知道正在发生的一切），或者游戏是非确定性的（它具有随机元素）。因为这两种情况都不适用于Blokus，所以我认为您选择Minimax是一个很好的选择。

AI领域称为对抗搜索（在教科书中第5章：对抗搜索），因此使用该术语在网上查找更多信息可能会为您提供更有帮助的信息或帮助您找到示例Java实现。我不认为这是初学者的任务，但如果您制作了游戏并可以选择随机有效移动，则听起来您已经做到了。继续保持良好的工作！

- Dan

Answer 4

2011年发布了一个名为Pentobi的程序，经过多次更新后，它成为了一个非常强大的Blokus游戏程序。

事实上，到目前为止，这是唯一一个表现良好的程序，并且完全超越了其他所有程序。它能打败很多优秀的人类玩家，甚至对最强的玩家也构成了一定的威胁。

该程序的主要算法是蒙特卡洛搜索树，同时也使用了一本开局书和一些启发式方法。

您可以在http://pentobi.sourceforge.net/找到文档和下载信息。

- T G

Answer 5

我发现使用一个非常简单的启发式算法，即使只使用1步先行搜索，也可以提供相当智能的玩家。我实现了我所谓的“空间启发式算法”，它接受棋盘状态并通过将所有与每个放置的棋子相邻的方块涂上该棋子的颜色来淹没它。然后，在淹没终止时计算着色方块的总数。空间启发式算法给出了一个大致估计，即一次游戏占据或占用了多少棋盘空间，并且远远优于随机游戏。也可以与极小化搜索或蒙特卡罗树搜索相结合，以获得更强的表现。

- DerekG