algorithm - 元素拾取竞赛的AI算法

Question

我想为以下游戏构建一个 AI:

• M x N 棋盘上有两个玩家
• 每个玩家都可以向上/向下或向左/向右移动
• 板上有不同的项目
• 在尽可能多的类别中拥有比其他玩家更多元素的玩家获胜(在一个类别中拥有更多元素使您成为该类别的赢家，拥有更多类别的玩家赢得游戏)
• 在一个回合中，你可以拿起你站立的元素或移动
• 玩家移动是同时进行的
• 站在同一个 field 上的两名玩家如果都这样做，则有 0.5 的拾取机会

如果满足以下条件之一，游戏结束:

• 所有元素都已取走
• 已经有一个明显的赢家，因为一个玩家拥有超过一半类别的一半以上的项目

我对人工智能一无所知，但我前段时间上过机器学习课。

1. 我该如何着手解决这样的问题？

2. 这个问题有泛化吗？

Answer 1

您提出的对抗性搜索游戏(称为两人零和游戏)的规范选择称为 Minimax搜索。来自维基百科，Minimax 的目标是

Minimize the possible loss for a worst case (maximum loss) scenario. Alternatively, it can be thought of as maximizing the minimum gain.

因此，它被称为 minimax 或 maximin。本质上，您构建了一个 Max 和 Min 级别的树，其中每个节点都有一个分支因子，该分支因子等于每轮可能的 Action 数，在您的例子中为 4。每个级别对应玩家的一个回合，树一直延伸到游戏结束，允许您在每个回合搜索最佳选择，假设对手正在最佳 还有。如果你的对手没有发挥最佳水平，你只会得分更高。本质上，在每个节点，您都模拟所有可能的游戏，并为当前回合选择最佳 Action 。

如果生成所有可能的游戏似乎需要很长时间，那你是对的，这是一个指数复杂度算法。从这里你会想调查alpha-beta pruning ，它实质上允许您根据到目前为止找到的值消除您正在枚举的一些可能的游戏，并且是对 minimax 的相当简单的修改。此解决方案仍将是最佳。我遵从维基百科文章进一步解释。

从那里开始，您可能想要尝试使用不同的启发式方法来消除节点，这可能会修剪大量要遍历的节点的树，但是请注意，通过启发式方法消除节点可能会产生次优的结果，但仍然是好的解决方案，具体取决于您的启发式方法。一种常见的策略是限制搜索树的深度，本质上，您可能向前搜索 5 步以确定当前最佳着法，使用每个玩家在 5 步时的得分估计值。再一次，这是一种您可以调整的启发式方法。像简单地计算游戏得分就好像它在那个回合结束一样可能就足够了，这绝对是一个很好的起点。

最后，对于涉及概率的节点，Minimax 有一个轻微的修改，称为 Expectiminimax通过添加一个为您选择随机选择的“第三”玩家，基本上可以解决概率问题。第三个玩家的节点将随机事件的期望值作为它们的值。