河南省网站建设_网站建设公司_响应式网站_seo优化

原文：towardsdatascience.com/i-built-an-ai-human-level-game-player-31b78df8aca3

一段时间以前，我为一个游戏构建了人类级自动玩家的决策部分。

这个棋盘游戏自动玩家的实力非常强大，以至于我所知道的任何人（包括我自己）都无法持续击败它，以至于我不得不以可控的方式让它变得更简单，以便让休闲玩家感到有趣。

在这篇文章中，我解释了我是如何使用深度学习之前的 AI 标准技术来编程这个小游戏的“大脑”的。你将学习（如果你还不熟悉的话）如何构建 Minimax 树以及如何为棋盘评估开发启发式方法。Minimax 技术可以应用于任何对抗性游戏，而不管我所描述的游戏的具体细节如何。

进入 Kromate

当移动设备开始变得流行（大约在 2008 年，iPhone 发布之后），可用的棋盘游戏很少。而且有些游戏在当时的小屏幕上根本无法玩。当然，这包括象棋：你无法在 3.5 英寸的屏幕上以 320 x 480 像素的分辨率真正显示棋盘。你可以，但会累坏你的眼睛。

我的兄弟之一提出了一个想法，即一个非常小的棋盘游戏，位置少于 20 个（而不是象棋中的 64 个），只放置 6 种颜色的“棋子”（而不是象棋中的 16 个）。他想出了类似于象棋的规则，包括“将军”和“将死”。

这个游戏被称为“Kromate”，因为它使用颜色来识别棋子。

我恐怕不得不详细解释如何玩 Kromate，因为否则你将无法理解自动玩家是如何解决这个问题的。

考虑图中这个棋盘：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/917d4a22d39cc8c4b2b441f05286f8cc.png

Kromate 应用 iPhone 截图（已编辑）

棋盘上有 19 个位置用于放置 6 种颜色的棋子。两位玩家每人有 3 个棋子：一位玩家拥有“基本”颜色（红色、蓝色、黄色），另一位玩家拥有“次级”颜色（橙色、绿色、紫色）。次级颜色是通过混合两种基本颜色形成的（这或许让你想起了你小学时的岁月）。

棋盘上有 19 个位置而不是 20 个（比如），这可能看起来有些奇怪，但如果你看看图中的位置排列，它就像一个蜂巢，有行和斜线路径。

看看上面的棋盘。这个棋盘可以在小屏幕上正确显示，你不这么认为吗？即使是原始的 iPhone 也能展示出它的全部魅力。

初始时，棋子随机放置在棋盘上。这也是 Kromate 作为实体棋盘游戏不实用的一个原因（例如，你需要“扔”棋子，然后看看它们最近的空位——这根本不实用）。

但图片中的红色箭头是什么意思呢？嗯，那是 Kromate 的类似棋盘的部分：当原色代币与次级颜色代币“对齐”时，它们可以“攻击”对方，反之亦然。例如，在上面的图中，黄色和蓝色代币正在“攻击”绿色代币，因为它们与它对齐，黄色与蓝色相加得到绿色。

攻击一个次级颜色的代币需要两个原色代币，而使用两个次级颜色代币，另一名玩家可以攻击一个原色：例如，紫色和橙色代币可以攻击红色代币，因为紫色和橙色都包含红色。

代币可以在直线上移动，无论是水平还是对角线，只要它们不遇到阻挡道路的代币。然而，有一个条件是代币落下的地方没有被攻击，如上所述。

例如，在图中，绿色代币必须移动，因为它被攻击（处于“将军”状态）。它可以移动到上左方和上右方的一个或两个位置。显然，它也可以水平向右移动，但这是不允许的，因为蓝色和黄色代币也攻击那个地方。

现在你们可以玩 Kromate 了。

等等，但游戏何时结束？这就是“将死”的定义。考虑以下位置：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c9956c9a8f28475c4e691156d6cd1a45.png

Kromate iPhone 应用的截图（已编辑）

次级颜色处于“将死”状态，因为绿色代币被攻击，但它不能移动到任何未被攻击的地方。拥有原色代币的玩家获胜。

Kromate iPhone 应用

为 Kromate 构建完整的应用对我来说一个人来说有点太多（我是一名全职的人工智能研究员），所以我联系了一家专门从事 iPhone 开发的公司。那是一家非常独特的公司，

我在奥斯汀找到了一些俄罗斯开发者。他们看起来很正规，并且已经在 Apple Store 上发布了许多应用。我们通过电话协商的安排是，我会编写决策部分（决定下一步棋），他们会做其他所有事情，包括用户界面和与操作系统相关的一切，比如启动应用、给它一个图标等等。

我们从未在现实生活中见过面就签订了合同。

这种安排意味着我只需编写一个接受 Kromate 位置（以我们同意的方式编码）的程序，并返回下一步棋。

最小-最大技术

我遵循了一种名为“最小-最大树”的技术，这种技术是由一位名叫亚瑟·萨缪尔的人工智能先驱很久以前发明的。萨缪尔是 IBM 的员工，他遵循了约翰·冯·诺伊曼提出的一些想法。他为跳棋游戏开发了一个非常好的自动玩家，并引入了“启发式棋盘评估”函数的概念。让我们检查一下这个。

启发式棋盘评估函数为每个有效的棋盘位置提供一个实数，表示该位置的好坏（数值越高，越好）。一个问题是没有通用的方法来定义棋盘评估函数，你必须根据对所玩游戏的知识发挥创意。

例如，在棋类游戏中，该函数会给拥有棋子的情况加分，但并非每个棋子的价值相同（例如，车比象更有价值，等等）。"启发式"这个词是"经验法则"的简称，但听起来要好得多。简单来说，对于一个启发式棋盘评估函数，你需要找到一种方法，为好的棋局位置赋予高价值，为不好的棋局位置赋予低价值。

然后，Samuel 使用游戏树来组织对不同替代方案的搜索。

首先，你必须考虑你可以做出的合法移动。每个移动都会从"根"处产生一个"分支"。但对于这些分支中的每一个，另一方可以做出一系列的移动（除非是"将死"位置），这些也将是分支。这个分支过程可以继续，直到满足"停止"条件。

可能存在不同的停止条件；最简单的一种是考虑固定数量的树"层级"，即玩家的回合数。这是我为 Kromate 选择的，自动玩家（AI 的回合，另一方的回合，然后 AI 再次回合）只有两个回合。

虽然游戏树将不同的可能性组织在一个地方，但我们还需要用它来为顶层做出移动选择。

最后要考虑的是如何从根节点获得最佳移动。这就是 Minimax 过程发挥作用的地方。让我们假设图中的游戏树：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/e862edc37269552d6a1a4790e06de0d4.png

图片由作者提供

初始时，在根节点，我的位置是 P1（我说“我的位置”是从 AI 玩家的角度出发），我有两个可能的移动，导致 P2 和 P3；然后，轮到另一方。从位置 P2 开始，另一方可以选择一个移动导致位置 P4 或 P5，依此类推。

树的底部有一些尚未展开的叶子节点。我们必须使用上面提到的启发式函数评估这些棋盘位置。

下面，我们有了相同的图形，但加入了启发式函数的评估：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/01e25cc3678e6ea5ec3bad48c1eb0438.png

图片由作者提供

现在是 Minimax 有趣的部分：从底部向上传播评估。我们首先从某个位置下的评估中取最大值，因为轮到我下棋：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/16b2b89ae491d9e6cbdf4f7b006a0512.png

图片由作者提供

继续向上，假设另一方是理性的，它将选择给我最差评估的选项（是的，另一方希望我不好），如下所示：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8eb98ad8ac64869968f08c032eff7fcd.png

图片由作者提供

虽然我们可以将评估传播到顶部（树的根），但在这里它们不是必需的（除了查看最佳获胜概率）。现在，我们可以选择最佳移动，即从 P1 到 P2。

简而言之，Minimax 技术就像“前瞻”几步，这是优秀的棋手经常做的事情。Minimax 玩家不仅评估从你的第一步产生的结果（这意味着静态评估 P1 和 P3）并从中选择最佳选项，而是探索接下来会发生什么——在一定程度上——然后只选择导致最佳静态评估的移动。

不要认为 Minimax 就是关于树搜索的全部。在过程中提出了许多改进，例如alpha-beta 剪枝，用于从搜索树中剪掉整个分支。

Kromate 上的 Minimax

当 IBM 的 DeepBlue 在 1997 年 5 月的著名象棋比赛中击败卡斯帕罗夫时，计算机在移动之前检查了数百万个选项。但这并不是蛮力，因为它包括了如 alpha-beta 剪枝等技术来减少搜索树。

在另一端，Kromate 在搜索树的叶子处检查了不到 100 个位置。Kromate 的 Minimax 树只包含 AI 玩家的两个回合和人类玩家的一个回合，正如上面的图示所示。

Kromate 的搜索树看起来像是一种激进的简化，但出人意料地有效。使用可能的移动数量来评估位置的想法直接击中了要害。这很有道理，因为如果你有几个选择，你更接近“将死”位置——那里你有一个确切的选择。你拥有的选择越多，你离失败就越远。

初始时，我考虑将许多因素结合起来评估位置，这是一种常见的做法。然而，当我正在细化每个因素的细节时，我意识到几乎所有其他因素都比可能的移动数量要少得多。

在这个阶段，读者您可以看到，设计一个静态评估函数并不容易。这可能是一个复杂的过程，而且无法保证结果会很好。这就是为什么只有当我看到 AI 玩家的出色表现时，我才意识到静态评估函数是好的。

人类水平的 AI

我将整个 Kromate AI 玩家编程为一个 Objective C 函数，该函数返回一个 Kromate 移动，作为一对两个数字：要移动的标记和目的地位置。

坦白说，当我仅基于古老的 Minimax 树完成了自动玩家时，我并没有期望它会有超过基本性能的表现。但是，我和它玩了几场比赛，在我看来，AI 玩家似乎很强。当然，我对 AI Kromate 玩家的主观印象可能会受到它是我创造的这个事实的影响，我可能会有“宠物效应”，使我的测试变得不那么严格。

但我把游戏给每个人测试时，他们都无法击败它——在某些情况下根本无法击败；其他人可以赢几次，但大多数比赛都输了。

说实话，我没有资源对 AI Kromate 玩家与人类进行比较的系统评估，但我可以告诉你，大多数人发现它太难击败，以至于他们不再觉得游戏体验有趣。你不想连续输 10 次！

AI 玩家如此强大，以至于我不得不“简化”它，使游戏更具吸引力。

例如，我可以通过减少 Minimax 树的深度来简化 Kromate AI 玩家，但我不想对代码进行重大修改，并希望提供几个级别——包括最难级别——所以我提出了一个更简单的解决方案。

“基准”Kromate 玩家随机选择一个有效的走法。实际上，我在 AI 玩家之前就编写了这个程序。不用说，基准玩家很容易被人类玩家击败。

因此，我将 AI 玩家的走法与随机玩家的走法“混合”在一起。通过修改每个单独走法的随机或 AI 选择的概率，很容易调整每种走法的比例。

我最终提供了 5 个不同的级别，包括底部的随机基准和顶部的 AI 玩家，以及 3 个中间级别，选择 AI 玩家的概率分别为 0.25、0.5 和 0.75。

那接下来发生了什么？

非常少。我的俄罗斯同事在 2009 年底在苹果应用商店发布了 Kromate，但效果不佳。似乎很少有人愿意从头开始学习一种新的类似国际象棋的游戏（即使包括在线帮助）。然后，他们将 Kromate 包装在游戏捆绑包中，另一个捆绑包，后来完全放弃了它。

在我要求严格的大学全职工作中，我没有进一步追求 Kromate 冒险。

但我学到了一些东西。

一方面，直到你亲手处理代码的细节，你才完全理解你在说什么。在这种情况下，Minimax 方法必须被转换成一系列 Objective C 函数调用，从为每个位置中的每个标记生成可能的合法走法开始。

另一个教训是最关键的部分是定义一个好的静态位置评估函数，这在任何教科书中都没有出现。

最后的学习是，直到你把它放在实际游戏中测试，你才知道你的聪明位置评估函数是否真的有用。实际上。

我希望您觉得我进入构建人类水平 AI 玩家的谦逊之旅很有趣。也许这可以激励您在现在有了更强大的工具之后构建其他东西！

—通过我的免费通讯录，“The Skeptic AI Enthusiast”，获取我亲自挑选的 AI 新闻分析和科技解释，由一位 AI 老兵以批判性的视角审视当前的技术格局，请访问rafebrena.substack.com/