如何为两人棋盘游戏创建 AI?

人工智能 深度学习 强化学习 人工智能设计 游戏-ai 组合游戏
2021-11-17 01:17:21

目标

我想创造一种人工智能来在棋盘游戏中与其他玩家竞争。

游戏说明

我有一个类似于“蛇和梯子”的棋盘游戏。你必须在你的对手之前到达最后的场地。但是这个游戏不是依靠运气(掷骰子)而是使用“食物”之类的东西。想走多远就走多远,但是搬家要花粮食(搬得越多,多出一块田地的费用就越高),而且只能在一些特殊的田地里得到粮食。而且没有任何蛇或梯子,因此您必须运行整个部分。还有一些规则,例如,您可以向后退,并且只有在您获得的“食物”少于一定数量并且有一些具有其他特殊效果的额外字段时才允许进入目标。

对于一名球员

如果只有一个玩家,因为在这个游戏中没有像“运气”这样的东西,理论上我可以计算每一种方法来找到唯一的最好的方法。实际上,我应该使用需要较少计算能力的算法。

对于两个或更多玩家

挑战来自其他玩家。我无法访问已经占用的领域。其他一些领域会根据我与其他玩家的相对位置给我​​奖金(我只会谈论两人游戏)。例如,只有当我在他身后时,那个特殊领域才会给我一些额外的食物。

我的问题

如果我有某种知道场地奖励的神经网络,我会给出我的位置、对手的位置、食物等(游戏状态),它会计算出介于 -100 之间的值,那将是理想的和 100(假设字段从 0 到 100)我应该走多少个字段(向前或向后)。

我读了一些关于 Q 学习、深度强化学习和深度神经网络的文章。这是解决我的问题的正确方法吗?如果有,你有什么更具体的想法吗?多个演员和根据无尽状态移动的无限可能性让我很难想到任何事情。还是有一种不同的、更好的方式从我身边溜走?

2个回答

假设这是一个回合制游戏,并且对于每一回合,都有一个最佳选择会导致获胜状态(零和),您基本上可以将问题简化为“我获胜的最佳移动顺序是什么,考虑到董事会提出的当前情况? ”。因此,您需要每回合都执行您的算法,因为最佳顺序会随着电路板的变化而变化。

有一种相对可靠的 AI 算法正在实施,以赢得国际象棋、西洋双陆棋等游戏。该技术称为minimax总而言之,极小极大是一种简单的搜索算法,可以最小化其他玩家的分数,同时最大化你的分数。

您将遇到的问题之一是,当我们搜索树的更深部分时,搜索树变得如此之宽,因此还必须实施alpha-beta 剪枝以减少搜索量。一般来说,alpha-beta 剪枝只是简单地消除不太可能成为最佳选择的分支(就分数而言),从而减少搜索次数以加快算法速度。

要成为 AI 对手,您需要创建一个子例程,考虑棋盘的当前状态并选择移动,就像玩家一样。

现在,这个子程序如何选择要采取的行动?您需要获取当前板并计算其值。然后考虑你可以采取的每一个可能的举动。然后考虑,对于每一个,你的对手可能做出的每一个可能的动作。迭代到最大深度。您将构建一个树结构(广度优先)。

修剪你的树。可以修剪任何保证您降低董事会价值的分支。

然后,不知何故,比较剩余的分支。您要么乐观地权衡可能的最佳结果并选择那些分支。或者根据最坏结果的可能性继续修剪。