游戏 2048 的最佳算法是什么？

ゝ一世哀愁。 2024-03-29 15:16 68阅读 0赞

## 问： ##

我最近偶然发现了游戏 2048。您可以通过在四个方向中的任何一个方向移动相似的图块来合并相似的图块以制作“更大”的图块。每次移动后，一个新的图块会出现在随机的空白位置，其值为 2 或 4。当所有的方块都被填满并且没有可以合并图块的移动时，游戏终止，或者您创建了一个值为 2048 的图块。

一，我需要遵循一个明确的策略来达到目标。所以，我想为它写一个程序。

我目前的算法：

while (!game_over) {
        
        for each possible move:
            count_no_of_merges_for_2-tiles and 4-tiles
        choose the move with a large number of merges
    }

我正在做的是，在任何时候，我都会尝试将具有值 2 和 4 的图块合并，也就是说，我尝试使 2 和 4 图块尽可能少。如果我以这种方式尝试，所有其他图块都会自动合并，并且该策略似乎不错。

但是，当我实际使用这个算法时，我在游戏结束前只得到了大约 4000 分。 AFAIK 的最高分数略高于 20,000 分，这比我目前的分数要高得多。有没有比上面更好的算法？

## 答1: ##

> huntsbot.com洞察每一个产品背后的需求与收益，从而捕获灵感

我使用 expectimax 优化开发了一个 2048 AI，而不是 @ovolve 算法使用的极小极大搜索。 AI 简单地对所有可能的移动执行最大化，然后对所有可能的瓦片生成进行预期（由瓦片的概率加权，即 4 为 10%，2 为 90%）。据我所知，不可能修剪 expectimax 优化（除了删除极不可能的分支），因此使用的算法是经过仔细优化的蛮力搜索。

表现

默认配置（最大搜索深度为 8）中的 AI 需要 10 毫秒到 200 毫秒来执行移动，具体取决于棋盘位置的复杂性。在测试中，人工智能在整个游戏过程中达到每秒 5-10 步的平均移动速度。如果搜索深度限制为 6 次移动，则 AI 每秒可以轻松执行 20 次以上的移动，这会产生一些 interesting watching。

为了评估 AI 的得分表现，我将 AI 运行了 100 次（通过遥控器连接到浏览器游戏）。对于每个图块，以下是该图块至少获得一次的游戏比例：

2048: 100%
    4096: 100%
    8192: 100%
    16384: 94%
    32768: 36%

所有运行的最低分数为 124024；最高得分为 794076。中位得分为 387222。AI 从未失败过获得 2048 块（因此它在 100 场比赛中从未输过一次）；事实上，它在每次运行中至少达到了 8192 瓦！

这是最佳运行的屏幕截图：

https://i.stack.imgur.com/jG2CL.png

这场比赛在 96 分钟内完成了 27830 步，即平均每秒 4.8 步。

执行

我的方法将整个板（16 个条目）编码为单个 64 位整数（其中瓷砖是 nybbles，即 4 位块）。在 64 位机器上，这使得整个板子可以在单个机器寄存器中传递。

位移操作用于提取单独的行和列。单行或单列是 16 位的数量，因此大小为 65536 的表可以编码对单行或单列进行操作的转换。例如，移动被实现为对预先计算的“移动效果表”的 4 次查找，该表描述了每个移动如何影响单个行或列（例如，“向右移动”表包含条目“1122 -> 0023”，描述了如何移动第 \[2,2,4,4\] 行向右移动时变为第 \[0,0,4,8\] 行）。

评分也是使用表格查找完成的。这些表包含在所有可能的行/列上计算的启发式分数，并且板的结果分数只是每行和列的表值的总和。

这种棋盘表示以及用于移动和计分的表格查找方法允许 AI 在短时间内搜索大量游戏状态（在我 2011 年中期笔记本电脑的一个内核上每秒搜索超过 10,000,000 个游戏状态）。

expectimax 搜索本身被编码为递归搜索，它在“预期”步骤（测试所有可能的瓦片生成位置和值，并通过每种可能性的概率加权它们的优化分数）和“最大化”步骤（测试所有可能的移动）之间交替进行并选择得分最高的那个）。树搜索在它看到先前看到的位置（使用 transposition table）、达到预定义的深度限制或达到极不可能的棋盘状态时终止（例如，通过获得 6"4"从起始位置连续的瓷砖）。典型的搜索深度是 4-8 步。

启发式

几种启发式方法用于将优化算法导向有利位置。启发式的精确选择对算法的性能有巨大的影响。各种启发式方法被加权并组合成一个位置分数，它决定了一个给定的棋盘位置有多“好”。然后，优化搜索将旨在最大化所有可能棋盘位置的平均得分。游戏中显示的实际分数不用于计算棋盘分数，因为它的权重太重，有利于合并图块（延迟合并可能会产生很大的好处）。

最初，我使用了两种非常简单的启发式方法，即为开放方块授予“奖励”以及在边缘具有较大值。这些启发式算法表现得非常好，经常达到 16384，但从未达到 32768。

Petr Morávek (@xificurk) 使用了我的 AI 并添加了两个新的启发式方法。第一个启发式是对非单调行和列的惩罚，随着等级的增加而增加，确保小数字的非单调行不会强烈影响分数，但大数字的非单调行会严重损害分数。第二个启发式计算了除了开放空间之外的潜在合并（相邻相等值）的数量。这两种启发式方法将算法推向单调板（更容易合并），以及具有大量合并的板位置（鼓励它在可能的情况下对齐合并以获得更大的效果）。

此外，Petr 还使用“元优化”策略（使用称为 CMA-ES 的算法）优化了启发式权重，其中权重本身被调整以获得最高可能的平均分数。

这些变化的影响是极其显着的。算法从大约 13% 的时间达到 16384 瓦片到超过 90% 的时间达到它，并且算法开始在 1/3 的时间内达到 32768（而旧的启发式从未产生过 32768 瓦片） .

我相信启发式方法仍有改进的空间。这个算法肯定还不是“最优的”，但我觉得它已经很接近了。

AI 在超过三分之一的游戏中达到 32768 块是一个巨大的里程碑；如果有人在正式游戏中达到 32768（即不使用保存状态或撤消之类的工具），我会很惊讶。我认为65536瓷砖触手可及！

你可以自己试试人工智能。代码可在 https://github.com/nneonneo/2048-ai 获得。

`@RobL：2 出现 90% 的时间； 4 的出现率为 10%。它在 source code：var value = Math.random() < 0.9 ? 2 : 4; 中。`

`目前正在移植到 Cuda，因此 GPU 可以更快地完成工作！`

`@nneonneo 我将您的带有 emscripten 的代码移植到了 javascript，它现在运行良好in the browser！看起来很酷，无需编译和一切......在Firefox中，性能相当不错......`

`4x4 网格中的理论限制实际上是 131072 而不是 65536。但是，这需要在正确的时刻获得 4（即整个板子都充满了 4 .. 65536 每个一次 - 15 个字段被占用）并且必须在那个位置设置板子时刻，以便您实际上可以组合。`

`@nneonneo 您可能想检查一下我们的 AI，它似乎更好，在 60% 的游戏中达到 32k：github.com/aszczepanski/2048`

## 答2: ##

> 与HuntsBot一起，探索全球自由职业机会–huntsbot.com

我是其他人在此线程中提到的 AI 程序的作者。您可以在 action 中查看 AI 或阅读 source。

目前，该程序在我笔记本电脑上的浏览器中以 javascript 运行，每次移动大约需要 100 毫秒的思考时间，实现了大约 90% 的胜率，因此虽然并不完美（还没有！），但它的表现相当不错。

由于游戏是一个离散状态空间、完美信息、回合制游戏，如国际象棋和跳棋，我使用了已被证明适用于这些游戏的相同方法，即 minimax search 和 alpha-beta pruning。由于已经有很多关于该算法的信息，我将只讨论我在 static evaluation function 中使用的两个主要启发式方法，它们形式化了其他人在这里表达的许多直觉。

单调性

这种启发式尝试确保瓦片的值都沿左/右和上/下方向增加或减少。仅此启发式就捕捉到了许多其他人提到的直觉，即更高价值的瓷砖应该聚集在一个角落里。它通常会防止价值较小的瓷砖成为孤立的，并使棋盘保持井井有条，较小的瓷砖层叠并填充到较大的瓷砖中。

这是一个完美单调网格的屏幕截图。我通过运行设置了 eval 函数的算法来忽略其他启发式并只考虑单调性，从而获得了这一点。

https://i.stack.imgur.com/Oce4N.png

平滑度

仅上述启发式方法往往会创建相邻图块的值递减的结构，但当然为了合并，相邻图块需要具有相同的值。因此，平滑启发式只是测量相邻瓦片之间的值差异，试图最小化这个计数。

Hacker News 的一位评论者从图论的角度给出了an interesting formalization这个想法。

这是一个完美平滑网格的屏幕截图。

https://i.stack.imgur.com/wxgDV.png

免费瓷砖

最后，免费瓷砖太少会受到惩罚，因为当游戏板过于狭窄时，选项会很快用完。

就是这样！在优化这些标准的同时搜索游戏空间会产生非常好的性能。使用像这样的通用方法而不是明确编码的移动策略的一个优点是该算法通常可以找到有趣和意想不到的解决方案。如果你看着它运行，它通常会做出令人惊讶但有效的动作，比如突然切换它正在建造的墙壁或角落。

编辑：

这里展示了这种方法的威力。我取消了平铺值的上限（因此它在达到 2048 后一直保持不变），这是经过八次试验后的最佳结果。

https://i.stack.imgur.com/x69jZ.png

是的，这是一个 4096 和一个 2048。=）这意味着它在同一个板上三次实现了难以捉摸的 2048 瓷砖。

`您可以将放置“2”和“4”牌的计算机视为“对手”。`

`@WeiYen 当然，但是将其视为最小最大问题并不忠实于游戏逻辑，因为计算机以一定的概率随机放置图块，而不是故意将分数最小化。`

`即使 AI 随机放置瓷砖，目标也不是输。倒霉与对手为你选择最糟糕的举动是一回事。 “最小”部分意味着你尝试保守地玩，这样就不会出现让你不走运的可怕动作。`

`我有一个想法来创建一个 2048 的分叉，其中计算机而不是随机放置 2 和 4，而是使用你的 AI 来确定将值放在哪里。结果：绝对不可能。可以在这里试用：sztupy.github.io/2048-Hard`

`@SztupY 哇，这太邪恶了。让我想起了 qntm.org/hatetris Hatetris，它还试图放置最能改善你情况的部分。`

## 答3: ##

> 一个优秀的自由职业者，应该有对需求敏感和精准需求捕获的能力，而huntsbot.com提供了这个机会

我开始对这个游戏的人工智能的想法很感兴趣，它不包含硬编码的智能（即没有启发式、评分函数等）。 AI 应该只“知道”游戏规则，并“弄清楚”游戏玩法。这与大多数人工智能（如本线程中的人工智能）形成鲜明对比，其中游戏本质上是由代表人类对游戏理解的评分函数控制的蛮力。

人工智能算法

我发现了一个简单但令人惊讶的好游戏算法：为了确定给定棋盘的下一步动作，人工智能使用随机动作在内存中玩游戏，直到游戏结束。这在跟踪最终游戏得分的同时进行了多次。然后计算每个开始移动的平均结束分数。选择具有最高平均结束分数的开始移动作为下一步移动。

每次移动只需 100 次运行（即在记忆游戏中），AI 达到 80% 的次数和 4096 次的次数分别为 80% 和 50%。使用 10000 次运行可以获得 2048 瓦片 100%，4096 瓦片为 70%，8192 瓦片约为 1%。

See it in action

最佳成绩如下所示：

https://i.stack.imgur.com/zk5Pu.png

关于这个算法的一个有趣的事实是，虽然随机游戏非常糟糕，但选择最好（或最不糟糕）的棋子会导致很好的游戏玩法：典型的 AI 游戏可以达到 70000 点并持续 3000 步，然而任何给定位置的内存随机游戏在死亡前大约 40 次额外移动平均产生 340 额外点数。 （您可以通过运行 AI 并打开调试控制台亲自查看。）

该图说明了这一点：蓝线显示了每次移动后的棋盘得分。红线显示了算法在该位置的最佳随机运行结束游戏得分。本质上，红色值将蓝色值向上“拉”向它们，因为它们是算法的最佳猜测。有趣的是，红线在每个点都比蓝线略高一点，但蓝线继续增加越来越多。

https://i.stack.imgur.com/gXI6b.png

我发现该算法不需要实际预见到好的游戏玩法就可以选择产生它的动作，这让我感到非常惊讶。

后来搜索我发现这个算法可能被归类为Pure Monte Carlo Tree Search算法。

实施和链接

首先，我创建了一个可以是 seen in action here 的 JavaScript 版本。这个版本可以在适当的时间内运行 100 次。打开控制台以获取更多信息。 (source)

后来，为了玩更多，我使用了@nneonneo 高度优化的基础设施并用 C++ 实现了我的版本。这个版本允许每次移动最多 100000 次运行，如果你有耐心，甚至可以运行 1000000 次。提供建筑说明。它在控制台中运行，也有一个遥控器来播放网络版本。 (source)

结果

令人惊讶的是，增加跑步次数并没有显着改善游戏玩法。这个策略似乎有一个限制，大约 80000 点，4096 瓦和所有较小的瓦，非常接近实现 8192 瓦。将跑步次数从 100 次增加到 100000 次会增加达到这个分数限制（从 5% 到 40%）但不会突破它的几率。

运行 10000 次并在关键位置附近临时增加到 1000000 次，成功打破这一障碍的次数不到 1%，最高得分为 129892 和 8192 平铺。

改进

在实现这个算法之后，我尝试了许多改进，包括使用最小或最大分数，或者最小、最大和平均的组合。我也尝试过使用深度：我没有尝试每次移动 K 次，而是尝试了给定长度的每次移动列表（例如“上、上、左”）的 K 次移动，并选择得分最高的移动列表中的第一步。

后来我实现了一个计分树，它考虑了在给定的移动列表之后能够下移动的条件概率。

然而，与简单的第一个想法相比，这些想法都没有显示出任何真正的优势。我在 C++ 代码中将这些想法的代码注释掉了。

我确实添加了一个“深度搜索”机制，当任何一次运行意外到达下一个最高图块时，该机制会暂时将运行次数增加到 1000000。这提供了时间上的改进。

我很想知道是否有人有其他保持人工智能领域独立性的改进想法。

2048 变种和克隆

只是为了好玩，我还 implemented the AI as a bookmarklet，加入了游戏的控件。这允许 AI 与原始游戏及其许多变体一起工作。

由于 AI 的领域独立性，这是可能的。一些变体非常不同，例如六边形克隆。

`+1。作为一名 AI 学生，我发现这非常有趣。将在空闲时间更好地看看这个。`

`这真太了不起了！我只是花了几个小时优化权重以获得一个好的启发式函数 expectimax，我在 3 分钟内实现了这个，这完全粉碎了它。`

`很好地使用了蒙特卡罗模拟。`

`看这部戏是在呼唤启蒙。这打击了所有启发式方法，但它确实有效。恭喜！`

`到目前为止，最有趣的解决方案在这里。`

## 答4: ##

> huntsbot.com精选全球7大洲远程工作机会，涵盖各领域，帮助想要远程工作的数字游民们能更精准、更高效的找到对方。

编辑：这是一种幼稚的算法，对人类有意识的思维过程进行建模，与搜索所有可能性的人工智能相比，它得到的结果非常弱，因为它只向前看一个瓷砖。它是在响应时间表的早期提交的。

我已经完善了算法并击败了游戏！它可能会由于接近尾声的简单坏运气而失败（你被迫向下移动，这是你永远不应该做的，并且一个瓷砖出现在你应该最高的地方。试着保持第一行填满，所以向左移动不会打破模式），但基本上你最终有一个固定的部分和一个移动的部分可以玩。这是你的目标：

https://i.stack.imgur.com/ZBprh.png

这是我默认选择的模型。

1024 512 256 128
      8   16  32  64
      4   2   x   x
      x   x   x   x

选择的角落是任意的，你基本上从不按一个键（禁止移动），如果你这样做，你再按相反的键并尝试修复它。对于未来的图块，模型总是期望下一个随机图块是 2，并出现在当前模型的对面（虽然第一行不完整，在右下角，一旦第一行完成，在左下角角落）。

这里是算法。大约 80% 的胜利（似乎总是有可能通过更“专业”的人工智能技术获胜，不过我不确定这一点。）

initiateModel();
    
    while(!game_over)
    {
            
        checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point
    
        for each 3 possible move:
            evaluateResult()
        execute move with best score
        if no move is available, execute forbidden move and undo, recalculateModel()
     }
    
     evaluateResult() {
        
         calculatesBestCurrentModel()
         calculates distance to chosen model
         stores result
     }
    
     calculateBestCurrentModel() {
        
          (according to the current highest tile acheived and their distribution)
      }

https://i.stack.imgur.com/oe0QJ.png

由于更接近预期模型的运气，模型发生了变化。人工智能试图实现的模型是

512 256 128  x
      X   X   x   x
      X   X   x   x
      x   x   x   x

到达那里的链条变成了：

512 256  64  O
      8   16  32  O
      4   x   x   x
      x   x   x   x

O 代表禁止的空格…

所以它会向右按，然后再按一次，然后（向右或向上取决于 4 创建的位置）然后将继续完成链，直到它得到：

https://i.stack.imgur.com/FCQKU.png

所以现在模型和链又回到了：

512 256 128  64
      4   8  16   32
      X   X   x   x
      x   x   x   x

第二个指针，它运气不好，它的主要位置已经被占据了。它很可能会失败，但它仍然可以实现它：

https://i.stack.imgur.com/ERU2p.png

这里的模型和链是：

O 1024 512 256
      O   O   O  128
      8  16   32  64
      4   x   x   x

当它设法达到 128 时，它会再次获得一整行：

O 1024 512 256
      x   x  128 128
      x   x   x   x
      x   x   x   x

`execute move with best score 您如何评估可能的下一个状态中的最佳分数？`

`启发式在 evaluateResult 中定义，您基本上会尝试最接近可能的最佳方案。`

`@Daren 我正在等待您的详细信息`

`@ashu 我正在努力，意外情况让我没有时间完成它。与此同时，我改进了算法，现在它可以解决 75% 的问题。`

`我真正喜欢这个策略的地方是我可以在手动玩游戏时使用它，它让我获得了高达 37k 的积分。`

## 答5: ##

> huntsbot.com提供全网独家一站式外包任务、远程工作、创意产品分享与订阅服务!

我在此处复制 post on my blog 的内容

我提出的解决方案非常简单且易于实施。虽然，它已经达到了 131040 的分数。给出了算法性能的几个基准。

https://i.stack.imgur.com/ahJt2.png

算法

启发式评分算法

https://chart.googleapis.com/chart?cht=tx&chl=2%5E%7Bn%7D%20%5Crightarrow%202%5E%7B16%7D%20%3D%2065536

（如果需要时随机生成 4-tile 而不是 2-tile，则有可能到达 131072 tile）

下图显示了两种可能的董事会组织方式：

https://i.stack.imgur.com/pNEFG.png

为了强制以单调递减顺序排列瓷砖，分数 si 计算为板上线性化值的总和乘以公比 r<1 的几何序列的值。

https://chart.googleapis.com/chart?cht=tx&chl=p\_n%20%5Cin%20Path\_%7B0%20%5Ccdots%20N-1%7D

https://chart.googleapis.com/chart?cht=tx&chl=score%20%3D%20%5Csum\_%7Bn%3D0%7D%5E%7BN-1%7D%20value(p\_n)%20\*%20r% 5En

可以同时评估多条线性路径，最终得分将是任何路径的最大得分。

决策规则

实现的决策规则不是很聪明，Python 中的代码如下所示：

@staticmethod
    def nextMove(board,recursion_depth=3):
        m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
        return m
    
    @staticmethod
    def nextMoveRecur(board,depth,maxDepth,base=0.9):
        bestScore = -1.
        bestMove = 0
        for m in range(1,5):
            if(board.validMove(m)):
                newBoard = copy.deepcopy(board)
                newBoard.move(m,add_tile=True)
    
                score = AI.evaluate(newBoard)
                if depth != 0:
                    my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                    score += my_s*pow(base,maxDepth-depth+1)
    
                if(score > bestScore):
                    bestMove = m
                    bestScore = score
        return (bestMove,bestScore);

minmax 或 Expectiminimax 的实现肯定会改进算法。显然，一个更复杂的决策规则会减慢算法的速度，并且需要一些时间来实现。我将在不久的将来尝试一个 minimax 实现。 （敬请关注）

基准

T1 - 121 次测试 - 8 条不同的路径 - r=0.125

T2 - 122 次测试 - 8 条不同的路径 - r=0.25

T3 - 132 次测试 - 8 条不同的路径 - r=0.5

T4 - 211 次测试 - 2 条不同的路径 - r=0.125

T5 - 274 次测试 - 2 条不同的路径 - r=0.25

T6 - 211 次测试 - 2 条不同的路径 - r=0.5

https://i.stack.imgur.com/6w4qY.png

https://chart.googleapis.com/chart?cht=tx&chl=%5Csim%20

代码

该代码可以在 GiHub 上的以下链接中找到：https://github.com/Nicola17/term2048-AI 它基于 term2048，并且是用 Python 编写的。我会尽快用 C++ 实现一个更高效的版本。

`不错，你的插图给了我一个想法，将合并向量用于评估`

`你好。您确定 github 页面中提供的说明适用于您的项目吗？我想试一试，但那些似乎是原始可玩游戏的说明，而不是 AI 自动运行。你能更新那些吗？谢谢。`

## 答6: ##

> 保持自己快人一步,享受全网独家提供的一站式外包任务、远程工作、创意产品订阅服务–huntsbot.com

我的尝试像上面的其他解决方案一样使用 expectimax，但没有位板。 Nneonneo 的解决方案可以检查 1000 万次移动，这大约是 4 的深度，剩下 6 个瓷砖，可能有 4 次移动 (2*6*4)4。在我的情况下，这个深度需要太长时间来探索，我根据剩余的空闲瓦片的数量调整了 expectimax 搜索的深度：

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

棋盘的分数是用空闲块数的平方和 2D 网格的点积的加权和计算的：

[[10,8,7,6.5],
     [.5,.7,1,3],
     [-.5,-1.5,-1.8,-2],
     [-3.8,-3.7,-3.5,-3]]

这迫使从左上角的瓦片以一种蛇的形式依次排列瓦片。

github 下方或上的代码：

`不知道为什么这没有更多的赞成票。它非常简单，因为它非常有效。`

`谢谢，迟到的答案，它的表现不是很好（几乎总是在 [1024, 8192] 中），成本/统计功能需要更多的工作`

`你是如何给空白区域加权的？`

`它只是 cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid)，我们试图最大限度地提高这个成本`

`谢谢@Robusto，有一天我应该改进代码，可以简化`

## 答7: ##

> 一个优秀的自由职业者，应该有对需求敏感和精准需求捕获的能力，而huntsbot.com提供了这个机会

我是一个 2048 控制器的作者，它的得分比这个线程中提到的任何其他程序都要好。 github 上提供了控制器的有效实现。 a separate repo 中还有用于训练控制器状态评估函数的代码。 paper中描述了训练方法。

控制器使用 expectimax 搜索和状态评估函数，该函数通过时间差异学习（一种强化学习技术）的变体从头开始（无需人工 2048 专业知识）学习。状态值函数使用 n 元组网络，它基本上是在棋盘上观察到的模式的加权线性函数。它总共涉及超过 10 亿个权重。

表现

每秒 1 步：609104（平均 100 场比赛）

10 步/秒：589355（平均 300 场比赛）

在 3 层时（约 1500 次移动/秒）：511759（平均 1000 场比赛）

10次/秒的瓦片统计如下：

2048: 100%
    4096: 100%
    8192: 100%
    16384: 97%
    32768: 64%
    32768,16384,8192,4096: 10%

（最后一行表示在板上同时拥有给定的瓷砖）。

对于 3 层：

2048: 100%
    4096: 100%
    8192: 100%
    16384: 96%
    32768: 54%
    32768,16384,8192,4096: 8%

但是，我从未观察到它获得 65536 磁贴。

`相当令人印象深刻的结果。但是，您能否更新答案以解释（粗略地说，简单来说......我确信完整的细节会太长而无法在此处发布）您的程序如何实现这一目标？就像对学习算法如何工作的粗略解释一样？`

## 答8: ##

> 保持自己快人一步,享受全网独家提供的一站式外包任务、远程工作、创意产品订阅服务–huntsbot.com

我想我找到了一个运行良好的算法，因为我的分数经常超过 10000，我个人最好的分数在 16000 左右。我的解决方案不是将最大的数字放在角落里，而是让它保持在第一行。

请看下面的代码：

while( !game_over ) {
        
        move_direction=up;
        if( !move_is_possible(up) ) {
        
            if( move_is_possible(right) && move_is_possible(left) ){
        
                if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                    move_direction = left;
                else
                    move_direction = right;
            } else if ( move_is_possible(left) ){
        
                move_direction = left;
            } else if ( move_is_possible(right) ){
        
                move_direction = right;
            } else {
        
                move_direction = down;
            }
        }
        do_move(move_direction);
    }

`我运行了 100,000 场游戏来测试这个与“向上、向右、向上、向左……”的琐碎循环策略（如果必须的话，向下）。循环策略完成了 770.6 的“平均图块得分”，而这个仅获得了 396.7。你猜到为什么会这样吗？我认为它做了太多的上升，即使左边或右边会合并更多。`

`如果瓷砖没有在多个方向上移动，它们往往会以不兼容的方式堆叠。一般来说，使用循环策略会导致中心的瓷砖更大，这使得机动更加狭窄。`

## 答9: ##

> huntsbot.com全球7大洲远程工作机会，探索不一样的工作方式

此游戏 here 已经有一个 AI 实现。自述文件摘录：

该算法是迭代加深深度优先alpha-beta搜索。评估函数试图保持行和列单调（全部减少或增加），同时最小化网格上的瓦片数量。

Hacker News 上还有一个关于此算法的讨论，您可能会发现它很有用。

`这应该是最佳答案，但最好添加有关实现的更多细节：例如游戏板的建模方式（作为图表），采用的优化（最小-最大瓷砖之间的差异）等。`

`对于未来的读者：这是作者 (ovolve) 在此处的 second-topmost answer 中解释的相同程序。这个答案，以及本次讨论中对 ovolve 程序的其他提及，促使 ovolve 出现并写下了他的算法是如何工作的；这个答案现在的分数是 1200。`

## 答10: ##

> huntsbot.com洞察每一个产品背后的需求与收益，从而捕获灵感

算法

while(!game_over)
    {
        
        for each possible move:
            evaluate next state
    
        choose the maximum evaluation
    }

评估

Evaluation =
        128 (Constant)
        + (Number of Spaces x 128)
        + Sum of faces adjacent to a space {
         (1/face) x 4096 }
        + Sum of other faces {
         log(face) x 4 }
        + (Number of possible next moves x 256)
        + (Number of aligned values x 2)

评估详情

128 (Constant)

这是一个常数，用作基线和其他用途，如测试。

+ (Number of Spaces x 128)

更多的空间使状态更灵活，我们乘以 128（这是中位数），因为填充 128 个面的网格是最佳的不可能状态。

+ Sum of faces adjacent to a space {
         (1/face) x 4096 }

在这里，我们评估有可能合并的面，通过向后评估它们，图块 2 变为值 2048，而图块 2048 被评估为 2。

+ Sum of other faces {
         log(face) x 4 }

在这里，我们仍然需要检查堆叠的值，但是以一种不会中断灵活性参数的较小方式，所以我们有 \{ x in \[4,44\] \} 的总和。

+ (Number of possible next moves x 256)

如果一个状态有更多的可能转换的自由度，它就会更灵活。

+ (Number of aligned values x 2)

这是对在该状态内进行合并的可能性进行的简化检查，而无需进行前瞻。

注意：可以调整常量…

`稍后我将对其进行编辑，以添加实时代码@nitish712`

`这个算法的赢率是多少？`

`为什么需要 constant？如果您所做的只是比较分数，那会如何影响这些比较的结果？`

`@bcdan 启发式（又名比较分数）取决于比较未来状态的预期值，类似于国际象棋启发式的工作方式，除了这是一个线性启发式，因为我们没有构建一棵树来知道接下来的最佳 N 移动`

## 答11: ##

> HuntsBot周刊–不定时分享成功产品案例，学习他们如何成功建立自己的副业–huntsbot.com

这不是对 OP 问题的直接回答，这是迄今为止我尝试解决相同问题并获得了一些结果并有一些我想分享的观察结果的更多东西（实验），我很好奇我们是否可以有一些从中得到进一步的见解。

我刚刚尝试了使用 alpha-beta 修剪和 3 和 5 的搜索树深度截断的 minimax 实现。我试图解决 4x4 网格的相同问题，作为 edX 课程 ColumbiaX：CSMM.101x 人工智能（人工智能）。

我应用了几个启发式评估函数的凸组合（尝试了不同的启发式权重），主要来自直觉和上面讨论的那些：

单调性可用空间

在我的情况下，计算机播放器是完全随机的，但我仍然假设对抗设置并将 AI 播放器代理实现为最大播放器。

我有 4x4 网格来玩游戏。

观察：

如果我给第一个启发式函数或第二个启发式函数分配了过多的权重，那么这两种情况下 AI 玩家获得的分数都会很低。我对启发式函数进行了许多可能的权重分配并采用凸组合，但很少有 AI 玩家能够得分 2048。大多数时候它要么停在 1024 或 512。

我也尝试了角落启发式，但由于某种原因它使结果更糟，任何直觉为什么？

此外，我尝试将搜索深度截止值从 3 增加到 5（我不能再增加它，因为即使进行修剪，搜索空间也超过了允许的时间），并添加了一种启发式方法，它查看相邻图块的值并给出如果它们可以合并，则可以获得更多积分，但我仍然无法获得 2048。

我认为使用 Expectimax 而不是 minimax 会更好，但我仍然想只用 minimax 解决这个问题并获得高分，例如 2048 或 4096。我不确定我是否遗漏了什么。

下面的动画显示了 AI 代理与计算机玩家玩游戏的最后几个步骤：

https://i.stack.imgur.com/OhhWl.gif

任何见解都会非常有帮助，在此先感谢。 （这是我的文章链接：https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/ 和 youtube 视频：https://www.youtube.com/watch?v=VnVFilfZ0r4）

以下动画显示了游戏的最后几个步骤，其中 AI 玩家代理可以获得 2048 分，这一次也添加了绝对值启发式：

https://i.stack.imgur.com/S6QMm.gif

下图显示了玩家 AI 代理探索的博弈树，假设计算机为对手，只需一步：

https://i.stack.imgur.com/eL0wC.jpg

原文链接：[https://www.huntsbot.com/qa/MQ98/what-is-the-optimal-algorithm-for-the-game-2048?lang=zh\_CN&from=csdn][https_www.huntsbot.com_qa_MQ98_what-is-the-optimal-algorithm-for-the-game-2048_lang_zh_CN_from_csdn]

> huntsbot.com – 高效赚钱，自由工作

[https_www.huntsbot.com_qa_MQ98_what-is-the-optimal-algorithm-for-the-game-2048_lang_zh_CN_from_csdn]: https://www.huntsbot.com/qa/MQ98/what-is-the-optimal-algorithm-for-the-game-2048?lang=zh_CN&from=csdn