利用人工智能解决2048游戏（JAVA代码）柏拉图区块链数据智能。垂直搜索。人工智能。

使用人工智能解决2048游戏（JAVA代码）

时间戳记：7年2014月4日上午57:XNUMX

到目前为止，你们大多数人已经听过/玩过 2048游戏 由加布里埃尔·西鲁利（Gabriele Cirulli）撰写。 这是一个简单但很容易上瘾的棋盘游戏，需要您组合单元格的数量才能达到2048。正如所期望的，随着更多单元格被高值填充，游戏的难度会增加。 就我个人而言，尽管我花了很多时间玩游戏，但我始终无法达到2048。所以自然要做的是尝试用JAVA开发AI解算器来击败2048游戏。 🙂

在本文中，我将简要讨论构建2048版人工智能求解器的方法，将描述我使用的启发式方法，并提供用JAVA编写的完整代码。 该代码在GPL v3许可下是开源的，您可以从以下位置下载 Github上.

用JAVA开发2048游戏

原始游戏是用JavaScript编写的，因此我不得不从头开始用JAVA重写它。 游戏的主要思想是，您拥有一个带有Integer值的4×4网格，所有网格均为2的幂。零值单元格被认为是空的。 在游戏过程中的每个点，您都可以将值向4个方向上移，下移，右移或左移。 当您执行移动时，网格的所有值都朝该方向移动，并且它们到达网格的边界或到达具有非零值的另一个像元时都会停止。 如果该先前的单元格具有相同的值，则两个单元格将合并为一个具有双精度值的单元格。 在每次移动结束时，在一个空单元格中的一个面板中添加一个随机值，其值为2概率为0.9或4概率为0.1。 当玩家设法创建一个值为2048的单元（获胜）或没有其他举动（失败）时，游戏结束。

在游戏的原始实现中，移动合并算法有点复杂，因为它考虑了所有方向。 如果我们确定可以组合的方向并相应地旋转电路板以执行移动，则可以很好地简化算法。 莫里斯·范·德·舍 最近写了一篇有关它的文章，我认为值得检查。

所有类均带有Javadoc注释。 下面我们对实现的体系结构进行高级描述：

1.董事会班级

棋盘类包含游戏的主要代码，负责移动棋子，计算得分，验证游戏是否终止等。

2. ActionStatus和Direction枚举

ActionStatus和Direction是2个基本枚举，分别存储移动的结果及其方向。

3. ConsoleGame类

ConsoleGame是允许我们玩游戏并测试AI Solver准确性的主要类。

4. AIsolver类

AIsolver是人工智能模块的主要类别，负责评估给定特定主板的下一个最佳动作。

人工智能技术：Minimax与Alpha-beta修剪

已经发布了几种方法来自动解决此游戏。 最值得注意的是由 马特·奥弗兰。 为了解决该问题，我尝试了两种不同的方法，即使用Minimax算法和使用Alpha-beta修剪。

极小极大算法

极大极小
极大极小 是一种递归算法，可用于求解两人零和游戏。 在游戏的每个状态中，我们都关联一个值。 Minimax算法在可能的游戏状态空间中进行搜索，从而创建一棵树，将其扩展到达到特定的预定义深度为止。 一旦达到这些叶状态，就可以使用它们的值来估计中间节点中的一个。

该算法有趣的想法是，每个级别代表两个玩家之一的回合。 为了获胜，每个玩家必须选择使对手的最大收益最小化的举动。 这是minimax算法的精彩视频演示：

[嵌入的内容]

在下面，您可以看到Minimax算法的伪代码：

功能 minimax（节点，深度，最大化播放器）
    if 深度= 0 or 节点是终端节点
        回报 节点的启发式值
    if maximizingPlayer bestValue：=-∞
        每 节点val的子级：= minimax（child，depth-1，FALSE））bestValue：= max（bestValue，val）;
        回报 最超值
    其他
        bestValue：= +∞
        每 节点val的子代：= minimax（child，depth-1，TRUE））bestValue：= min（bestValue，val）;
        回报 最超值
（*最初召集玩家最大化*）
minimax（原点，深度，真）

Alpha-beta修剪

Alpha-beta修剪
Alpha-beta修剪算法 是minimax的扩展，它极大地减少（修剪）了我们必须评估/扩展的节点数。 为了实现这一点，该算法估算了两个值alpha和beta。 如果在给定节点中beta小于alpha，则可以修剪其余子树。 这是一个字母算法的视频演示：

[嵌入的内容]

在下面，您可以看到Alpha-beta修剪算法的伪代码：

功能 字母（节点，深度，α，β，maximizingPlayer）
    if 深度= 0 or 节点是终端节点
        回报 节点的启发式值
    if 最大化播放器
        每 节点α的子元素：= max（α，Alphabeta（child，depth-1，α，β，FALSE））
            if β≤α
                打破 （*β截止*）
        回报 α
    其他
        每 节点β的子元素：= min（β，Alphabeta（child，depth-1，α，β，TRUE））
            if β≤α
                打破 （*α截止*）
        回报 β
（*首次通话*）
字母（原点，深度，-∞，+∞，TRUE）

如何使用AI解决2048游戏？

为了使用上述算法，我们必须首先确定两个参与者。 第一个玩家是玩游戏的人。 第二个参与者是计算机，它在板的单元格中随机插入值。 显然，第一个玩家试图最大化其得分并实现2048合并。 另一方面，原始游戏中的计算机没有经过特别编程，可以通过为用户选择最坏的举动来阻止用户，而是在空单元格上随机插入值。

那么，为什么我们使用AI技术来解决零和游戏，并特别假设两个玩家都为他们选择了最佳移动方式？ 答案很简单； 尽管只有第一个尝试最大化其得分的玩家，但计算机的选择仍会阻止进度并阻止用户完成游戏。 通过将计算机的行为建模为矫形非随机玩家，我们确保我们的选择将是可靠的，独立于计算机的运行。

第二个重要部分是为游戏状态分配值。 这个问题相对简单，因为游戏本身给我们得分。 不幸的是，试图独自最大化分数并不是一个好方法。 原因之一是值的位置和空值单元格的数量对于赢得游戏非常重要。 例如，如果我们将较大的值分散在远程单元格中，那么对它们进行合并将非常困难。 此外，如果我们没有可用的空单元，则可能会随时失去游戏。

由于以上所有原因，几种启发式方法 有人建议 例如单调性，平滑度和木板的自由平铺度。 主要思想不是单独使用分数来评估每个游戏状态，而是构造包括上述分数的启发式综合分数。

最后，我们应该注意，即使我已经开发了Minimax算法的实现，但是大量可能的状态使该算法非常慢，因此有必要进行修剪。 因此，在JAVA实现中，我使用了Alpha-beta修剪算法的扩展。 此外，与其他实现不同的是，我不会使用任意规则来主动修剪计算机的选择，而是将所有这些规则都考虑在内，以便找到播放器的最佳移动方式。

开发启发式评分功能

为了打败游戏，我尝试了几种不同的启发式功能。 我发现最有用的是以下内容：

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

上面的功能结合了木板的实际得分，空单元/瓷砖的数量以及一个称为聚类得分的度量，我们将在后面讨论。 让我们更详细地查看每个组件：

  1. 实际分数： 出于显而易见的原因，当我们计算董事会的价值时，我们必须考虑其得分。 与分数较低的板相比，分数较高的板通常更可取。
  2. 空单元数： 正如我们前面提到的，保持很少的空单元很重要，以确保我们在接下来的步骤中不会输掉比赛。 与其他空单元较少的板状态相比，空单元较多的板状态通常更可取。 关于如何评估那些空单元的问题提出了？ 在我的解决方案中，我通过实际分数的对数对它们进行加权。 这具有以下效果：得分越低，拥有许多空单元格的重要性就越小（这是因为在游戏开始时合并单元格非常容易）。 分数越高，确保我们的游戏中有空单元格就越重要（这是因为在游戏结束时，由于缺少空单元格，更有可能丢失）。
  3. 聚类得分： 我们使用聚类得分来衡量董事会价值的分散程度。 当具有相似值的像元接近时，它们更易于合并，这意味着更难输掉比赛。 在这种情况下，聚类得分具有较低的值。 如果董事会的价值分散，那么该得分将获得非常大的价值。 从之前的两个分数中减去该分数，并表现为一种惩罚，以确保会优先使用聚类板。

在函数的最后一行，我们确保分数为非负数。 如果董事会的分数为正，则分数应严格为正，只有分数为零的分数为零。 构造max和min函数是为了获得这种效果。

最后，我们应该注意，当玩家到达终局游戏状态且不允许再进行任何移动时，我们不会使用以上得分来估计状态值。 如果游戏获胜，我们将分配最大可能的整数值，而如果游戏失败，我们将分配最低的非负值（0或1，其逻辑与上一段相似）。

有关聚类得分的更多信息

就像我们之前说的，聚类得分衡量的是董事会价值的分散程度，其作用类似于罚款。 我以这种方式构造了这个分数，以便它包含“掌握”游戏用户的提示/规则。 第一条建议的规则是，尝试使具有相似值的单元格保持关闭状态，以便更轻松地组合它们。 第二条规则是，高价值单元格应该彼此靠近，而不是出现在木板的中间，而应该出现在侧面或角落。

让我们看看如何估算聚类得分。 对于董事会的每个单元，我们估计与其相邻方（不包括空单元）的绝对差之和，然后取平均差。 之所以取平均值，是为了避免计算两次以上相邻小区的影响。 总聚类得分是所有这些平均值的总和。

聚类得分具有以下属性：

  1. 当电路板的值分散时，它的值很高；而当值相似的单元格彼此靠近时，它的值很低。
  2. 它不会超过两个相邻单元的影响。
  3. 边缘或角落的单元具有较少的邻居，因此得分较低。 结果，当高值放置在边距或拐角附近时，它们具有较小的分数，因此惩罚较小。

算法的准确性

不出所料，该算法的准确性（也就是获胜游戏的百分比）在很大程度上取决于我们使用的搜索深度。 搜索的深度越高，准确性越高，运行时间也越长。 在我的测试中，深度为3的搜索持续时间少于0.05秒，但获胜的机会为20％；深度为5的搜索持续约1秒，但获胜的机会为40％，而深度7的搜索持续了27-28秒，提供大约70-80％的获胜机会。

未来的扩展

对于那些对改进代码感兴趣的人，您可以研究以下几件事：

  1. 提高速度： 改进算法的速度将使您可以使用更大的深度，从而获得更好的精度。
  2. 创建图形： 加布里埃尔·西鲁利（Gabriele Cirulli）的执行如此出名的确有充分的理由。 很好看！ 我没有费心开发GUI，而是将结果打印在控制台上，这使得游戏难以掌握和玩。 必须创建漂亮的GUI。
  3. 音调启发法： 正如我之前提到的，一些用户提出了不同的启发式方法。 可以尝试计算分数的方式，权重和考虑到的董事会特征。 我测量聚类得分的方法应该结合其他建议，例如单调性和平滑性，但仍有改进的空间。
  4. 调整深度： 也可以根据游戏状态来尝试调整/调整搜索深度。 您也可以使用 迭代加深深度优先搜索 已知可改善alpha-beta修剪算法的算法。

不要忘记从下载Java代码 Github上 和实验。 希望您喜欢这篇文章！ 如果您这样做了，请花一点时间在Facebook和Twitter上分享该文章。 🙂

时间戳记：

更多来自 基准框