我想为以下游戏构建一个AI:
- 在一个M x N的棋盘上有两个玩家
- 每个玩家可以上下或左右移动
- 棋盘上有不同的物品
- 在尽可能多的类别中拥有比对方更多的物品的玩家获胜（在一个类别中拥有更多物品使你成为该类别的赢家，拥有更多类别的玩家赢得游戏）
- 在一个回合中，你可以拾取你所站立的物品或移动
- 玩家的移动是同时进行的
- 如果两个玩家站在同一个位置上，并且两者都尝试拾取物品，则拾取成功的几率为0.5
如果满足以下任一条件，游戏结束:
- 所有物品都被拾取
- 由于一个玩家在超过半数的类别中拥有超过半数的物品，已经有明显的赢家
我对AI一无所知，但我之前上过一门机器学习课程。
-
我该如何开始解决这样的问题？
-
这个问题是否有普遍性？
回答：
对于你提出的这种对抗性搜索游戏（称为两人零和游戏）的经典选择被称为Minimax搜索。根据维基百科，Minimax的目标是
在最坏情况（最大损失）情景下最小化可能的损失。或者，可以认为是最大化最小收益。
因此，它被称为minimax，或maximin。本质上，你构建一个由Max和Min级别组成的树，每个节点的分支因子等于每回合可能的动作数量，在你的情况下是4。每个级别对应一个玩家的回合，树一直延伸到游戏结束，允许你搜索每回合的最优选择，假设对手也在最优地玩。如果你的对手没有最优地玩，你的得分只会更好。本质上，在每个节点你模拟所有可能的游戏并为当前回合选择最佳行动。
如果生成所有可能的游戏似乎需要很长时间，你是正确的，这是一个指数复杂度的算法。从这里你会想要研究alpha-beta剪枝，它本质上允许你根据迄今发现的值消除一些你正在枚举的可能游戏，并且是对minimax的一个相当简单的修改。这种解决方案仍然是最优的。我将进一步的解释推迟到维基百科文章中。
从那里，你会想要尝试不同的启发式方法来消除节点，这可能会大大减少需要遍历的节点树的数量，但请注意，通过启发式方法消除节点可能会产生一个次优但仍然不错的解决方案，这取决于你的启发式方法。一个常见的策略是限制搜索树的深度，本质上你可能搜索前5个回合来确定当前的最佳移动，使用在5个回合后的每个玩家的分数估计。这同样是一个你可以调整的启发式方法。简单地计算游戏在那个回合结束时的分数可能就足够了，并且绝对是一个好的起点。
最后，对于涉及概率的节点，有一个对Minimax的轻微修改，称为Expectiminimax，它通过添加一个“第三”玩家来处理概率，这个玩家为你选择随机选择。这些第三玩家的节点以随机事件的期望值作为它们的价值。
