项目拾取竞赛中的人工智能算法

Question

我想为以下游戏建立一个AI：

• M板上有两个玩家
• 每个玩家都可以向上/向下或左/右移动。
• 董事会上有不同的项目
• 在尽可能多的类别中拥有比其他玩家更多的项目的玩家获胜(在一个类别中拥有更多的项目将使您成为这个类别的赢家，拥有更多类别的玩家将赢得游戏)
• 在一个回合中，你可以捡起你站着的东西，也可以移动。
• 球员动作同时进行。
• 两名球员站在同一个球场上，如果双方都这样做的话，他们有0.5次的机会。

如果满足下列条件之一，游戏将结束：

• 所有的物品都被捡起来了
• 已经有一个明显的胜利者，因为有一个玩家拥有超过一半的项目，超过一半的类别。

我不知道人工智能，但不久前我上了一门机器学习课。

1. 我该如何着手解决这个问题呢？
2. 这个问题有泛化吗？

Answer 1

您提出的对抗性搜索游戏(称为两人零和游戏)的典型选择称为极小最大搜索。从维基百科来看，Minimax的目标是

将最坏情况(最大损失)的可能损失降到最低。或者，它可以被认为是最大化的最小收益。

因此，它被称为极大极小。本质上，您构建了一棵Max和Min级别的树，其中每个节点都有一个分支因子，等于每个回合中可能的操作数，在您的情况下是4个。每个级别对应于玩家的一个回合，树一直延伸到游戏结束，允许您在每个回合搜索最优选择，假设对手也是最优的。如果你的对手打得不好，你只会得分更好。本质上，在每个节点上，您模拟每个可能的游戏，并选择当前回合的最佳动作。

如果看起来生成所有可能的游戏需要很长时间，你是对的，这是一个指数复杂性算法。从这里开始，您将需要研究α-β修剪，它基本上允许您根据到目前为止找到的值来消除您正在枚举的一些可能的游戏，这是对minimax的一个相当简单的修改。这个解决方案仍然是最优。我敬请维基百科的文章作进一步解释。

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

最后，对于涉及概率的节点，有一个名为前极小极大的Minimax的轻微修改，它本质上是通过添加一个“第三个”播放器来为您选择随机选择来考虑概率。第三个玩家的节点以随机事件的期望值作为它们的值。

Answer 2

对于任何这样的问题，通常的方法是与活的对手玩游戏足够长的时间，找到一些启发式的解决方案(短期目标)，带领你走向胜利。然后在解决方案中实现这些启发式。从非常小的板(1x3)和少量的类别(1)开始，播放它们，看看会发生什么，然后前进到更复杂的情况。

在不玩游戏的情况下，我只能想象那些物品较少的类别更有价值，还有那些目前离你更近的类别，还有那些离你最远但比对手离你更近的类别。

每一个类别都有一个成本，这是获得控制权所需的移动次数，但你的成本与对手的成本不同，并且它随每一步而变化。如果你的成本接近对手的成本，但仍然低于对手的成本，类别对你有更大的价值。

每次你移动的时候，类别都会改变他们的价值，所以你必须重新计算董事会，从那里开始决定你的下一步行动。目标是最大化您的值和最小化对手的值，假设对手使用与您相同的算法。

如果你事先探索了不止一个回合，那么寻找最好的动作就会变得更加复杂，但也会更有效。在这种情况下，你必须模拟对手的移动使用相同的算法，然后选择你的移动对手有最弱的反移动。这种策略被称为极小最大。

所有这些都不是真正的人工智能，但它是一个算法的路线图。另一个答案中提到的神经网络更像人工智能，但我对它们一无所知。

Answer 3

AI的目标是始终寻求保持胜利的条件。

如果它是实用的(取决于如何存储项目位置)，在每一轮开始时，所有剩余项目的距离应由AI知道。理想情况下，这将在游戏开始时计算一次，然后根据AI移动的位置进行简单的“调整”，而不是在每一回合重新计算。如果AI不只是考虑自己的情况，那么让AI为玩家做同样的事情也是不明智的。

从这一点出发，需要确定哪些项目应作为优化考虑因素的最佳选择：

• 人工智能目前有哪些项目和项目类别？
• 玩家目前有哪些项目和项目类别？
• 哪些项目和项目类别接近人工智能？
• 玩家附近有哪些物品和物品类别？

你到底是如何做到这一点的，很大程度上取决于你想要人工智能的难度有多大。

一个简单的方法是使用一种贪婪的方法，简单地追求“当前”的最佳选择。这可以通过简单的找到最接近的项目，而不是在一个类别中，玩家目前正在赢得这么多的项目(可能是1-3)。这就产生了一个人工智能，试图赢得，但不考虑未来，这使得它相当容易预测。

允许贪婪算法检查多个前进方向将改进算法，并考虑玩家将做什么将进一步改进算法。

启发式将导致一个更现实的AI和难以击败AI。甚至可能几乎不可能被打败。