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

algorithm logic artificial-intelligence 2048


我最近偶然发现了2048游戏。您可以通过在四个方向上任意移动相似的图块来合并它们,以制作“更大”的图块。每次移动后,新的图块将出现在随机的空白位置,值为 24 。当所有盒子都装满并且没有可以合并磁贴的移动,或者您创建的值为 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
}

我正在做的是在任何时候,我都将尝试合并值 24 的图块,也就是说,我尝试将 24 的图块尽量减少。如果以这种方式尝试,所有其他磁贴将自动合并,并且该策略看起来不错。

但是,当我真正使用这种算法时,我只在游戏结束前得到4000分左右。最高分AFAIK是20000分,比我现在的分数要大得多。有没有比上面的算法更好的算法?





Answer 1 nneonneo


我使用Expectimax优化开发了2048 AI ,而不是@ovolve算法使用的minimax搜索。 AI会简单地对所有可能的移动执行最大化,然后对所有可能的图块生成进行期望(通过图块的概率加权,即4的概率为10%,2的概率为90%)。据我所知,不可能修剪Expectimax优化(除去删除极不可能的分支),因此使用的算法是经过仔细优化的蛮力搜索。

Performance

AI的默认配置(最大搜索深度为8)从10ms到200ms的任何时间执行一次移动,具体取决于电路板位置的复杂程度。在测试中,人工智能在整个游戏过程中的平均移动速率为每秒5-10次移动。如果将搜索深度限制为6个动作,则AI可以轻松地每秒执行20个以上的动作,这使您可以进行一些有趣的观看

为了评估AI的得分性能,我运行了100次(通过遥控器连接到浏览器游戏)。对于每一个瓦片,这里是该瓦片至少达到一次的游戏比例。

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

最低分数为124024;AI的最高得分是794076。中位数是387222。AI从未失败过获得2048个图块(因此,即使每100场游戏中有一次它也不会输掉游戏);实际上,它在每次运行中至少获得了8192个磁贴!

下面是极品跑的截图。

32768 tile, score 794076

这场比赛用时278330分钟,即平均每秒4.8步。

Implementation

我的方法是将整个电路板(16个条目)编码为一个64位的整数(其中tiles是nybbles,即4位块)。在64位的机器上,这使得整个电路板可以在一个机器寄存器中传递。

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

分数也是通过表格查询来进行的。表中包含了对所有可能的行和列的启发式评分,而一个板的结果就是每一行和每一列的表值之和。

这种棋盘的表现形式,再加上移动和计分的表格查询方式,使得人工智能可以在短时间内搜索到大量的游戏状态(在我2011年中的笔记本电脑的一个核心上,每秒超过1万个游戏状态)。

Expectimax搜索本身被编码为递归搜索,它在“期望”步骤(测试所有可能的瓦片生成位置和值,并通过每种可能性的概率加权其优化得分)和“最大化”步骤(测试所有可能的移动)之间交替并选择得分最高的那个)。当树搜索看到先前看到的位置(使用转置表),达到预定义的深度限制或达到极不可能的板状态(例如通过获取6个“ 4”图块达到的状态)时,树搜索终止从起始位置连续)。典型的搜索深度是4-8步。

Heuristics

使用几种启发式方法将优化算法引向有利位置。启发式算法的精确选择对算法的性能有很大的影响。权衡各种启发式方法并将其组合到位置分数中,该分数确定给定板位置的“好”程度。然后,优化搜索将旨在使所有可能的董事会职位的平均分数最大化。如游戏所示,实际得分用于计算棋盘得分,因为它过于偏重而无法合并砖块(延迟合并可能会产生很大的收益)。

最初,我使用了两个非常简单的启发式算法,对开放的方块和边缘上的大值给予 "奖励"。这两种启发式方法的表现相当不错,经常达到16384,但从未达到32768。

PetrMorávek(@xificurk)采用了我的AI,并添加了两个新的启发式方法。第一种启发式方法是对具有非单调的行和列的行列进行惩罚,该行和列随等级的增加而增加,以确保数量较少的非单调行不会严重影响得分,但数量较大的非单调行会严重损害得分。第二个启发式方法计算了除开放空间外的潜在合并数(相邻的相等值)。这两种启发式算法将算法推向单调板(更易于合并),并推向具有大量合并的板位置(鼓励它在可能的情况下对齐合并以产生更大的效果)。

此外,Petr还使用“元优化”策略(使用称为CMA-ES的算法)对启发式权重进行了优化,其中权重本身进行了调整以获得最高的平均分数。

这些变化的效果是非常显著的。算法从13%左右的时间内实现16384的瓦片,到90%以上的时间内实现,算法开始实现32768的时间超过13个(而旧的启发式算法从未产生过一次32768的瓦片)。

我相信在启发式算法上还有改进的空间。这个算法肯定还不是 "最优的",但我觉得已经很接近了。


人工智能在超过三分之一的游戏中达到32768瓦,这是一个巨大的里程碑;如果有人类玩家在官方游戏中达到了32768瓦,我会很惊讶(也就是说,没有使用savestates或撤消等工具)。我想65536的瓦片是指日可待的!

您可以自己尝试AI。该代码可从https://github.com/nneonneo/2048-ai获得




Answer 2 ovolve


我是该线程中其他人提到的AI程序的作者。您可以查看AI 行动或阅读

目前,该程序在我的笔记本电脑上以javascript在浏览器中运行时的胜率约为90%,每次移动的思考时间约为100毫秒,所以虽然还不是很完美(还没有!),但它的表现相当不错。

由于该游戏是离散的状态空间,完美的信息,基于回合的游戏(如国际象棋和西洋跳棋),因此我使用了已被证明可用于这些游戏的相同方法,即带有alpha-beta修剪的minimax 搜索。由于已经有很多关于该算法的信息,因此,我将仅讨论在静态评估函数中使用的两种主要启发式方法,这些启发式方法将其他人在这里表达的许多直觉形式化。

Monotonicity

这个启发式试图确保瓦片的值都是沿左下和右上方向增加或减少。仅仅这个启发式就抓住了许多其他人提到的直觉,即价值较高的瓷砖应该集中在一个角落里。这通常可以防止价值较小的瓦片被遗弃,并且可以使棋盘非常有条理,较小的瓦片层层叠加,填入较大的瓦片中。

这里是一个完全单调的网格的截图。我是通过运行算法的eval函数设置来忽略其他启发式,只考虑单调性,从而得到的。

A perfectly monotonic 2048 board

Smoothness

单单用上述启发式就会产生相邻瓦片价值递减的结构,当然,为了合并,相邻瓦片需要相同的价值。因此,平滑性启发式只是测量相邻瓦片之间的值差,试图将这个数值最小化。

黑客新闻的评论者从图论的角度对该概念进行了有趣的形式化

这是一个完美平滑的网格的屏幕截图,这得益于出色的模仿叉

A perfectly smooth 2048 board

免费瓷砖

最后,空闲牌太少也是有惩罚的,因为当游戏板变得太过拥挤时,选项会很快用完。

就这么简单! 在优化这些标准的同时,通过对博弈空间进行搜索,可以获得非常好的性能。使用这样的泛化方法而不是明文规定的走法策略的一个好处是,算法经常可以找到有趣的、意想不到的解决方案。如果你观察它的运行,它经常会做出一些出人意料但又有效的动作,比如突然切换到哪个墙或墙角上。

Edit:

下面是这个方法的威力展示。我取消了瓦片值的上限(所以在达到2048之后,它就一直保持着),这里是八次试验之后的最佳结果。

4096

是的,那是4096和2048旁边的4096。)这意味着,它在同一块板子上实现了三次难以捉摸的2048瓦。




Answer 3 Ronenz


我对此游戏的AI构想产生了兴趣,其中包含硬编码的智能(即,没有启发式,计分功能等)。 AI应该仅“知道”游戏规则,并“确定”游戏玩法。这与大多数AI(如该线程中的AI)相反,后者的游戏本质上是由代表人类对游戏理解的计分功能操纵的。

人工智能算法

我发现了一个简单但出乎意料的出色玩法:要确定给定棋盘的下一招,AI会使用随机招数在内存中玩游戏,直到游戏结束。在跟踪最终比赛分数的同时,完成了几次。然后计算每个开始动作的平均终点得分。选择平均终点得分最高的起点作为下一步。

每一步棋只需要100次运行(即在内存游戏中),AI就能达到2048张牌的80%,4096张牌的50%。使用10000次运行可以获得2048张牌的100%,4096张牌的70%,8192张牌的1%左右。

看看它的行动

这里显示的是最好的成绩。

best score

关于这种算法的一个有趣的事实是,虽然随机博弈的游戏不难理解,但选择最好的(或最不坏的)棋子会带来非常好的游戏效果。一个典型的AI游戏可以达到70000点,并持续3000步,然而从任何给定位置的内存中的随机博弈游戏在死亡前平均多走40步左右就能获得340点的额外积分。(你可以通过运行AI,打开调试控制台,就可以看到这一点)。

该图说明了这一点:蓝线表示每次移动后的棋盘得分。红线显示从该位置开始算法的最佳随机运行结束游戏得分。本质上,红色值是将蓝色值向上“拉”向它们,因为它们是算法的最佳猜测。有趣的是,红线在每个点上都仅比蓝线高一点,但是蓝线仍在不断增加。

scoring graph

我觉得很奇怪的是,算法不需要实际预测到好的游戏玩法,就可以选择产生算法的招式。

稍后搜索,我发现该算法可能被归类为“ 纯蒙特卡洛树搜索”算法。

执行和联系

首先,我创建了一个JavaScript版本,在这里可以看到它。该版本可以在适当的时间内运行100多次。打开控制台以获取更多信息。(来源

后来,为了玩得更多,我使用了@nneonneo高度优化的基础结构,并使用C ++实现了我的版本。如果您有足够的耐心,此版本最多可允许单次运行100000次,甚至100万次。提供了建筑说明。它运行在控制台中,还具有用于播放Web版本的遥控器。(来源

Results

令人惊讶的是,增加运行次数并不能大大改善游戏玩法。对于4096个图块和所有较小的图块,此策略似乎在80000点附近存在限制,非常接近实现8192个图块。将跑步次数从100增加到100000,增加了达到此分数限制(从5%到40%)但没有突破的几率

在临界位置附近临时增加到1000000运行10000的情况下,成功突破这一关卡的次数不足1%,达到了12892的最高分和8192的瓷砖。

Improvements

实施此算法后,我尝试了许多改进,包括使用最小或最大得分,或最小,最大和平均值的组合。我使用深度也试过:不是每移动试图ķ运行,我想每个举动K移到列表的给定长度的(“向上,向上,左”为例),并选择最好的得分移动列表的第一招。

后来我实施了一个计分树,考虑到在给定的招式列表后,有条件的概率可以出招。

然而,这些想法都没有显示出比第一个简单的想法有任何真正的优势。我把这些想法的代码留在C++代码中注释出来。

我确实添加了一个 "深度搜索 "机制,当任何一个运行的玩家不小心到达下一个最高的瓦片时,会将运行数暂时增加到1000000。这提供了一个时间上的改善。

我很想知道,如果有谁有其他的改进思路,能保持人工智能的领域独立性,我会很感兴趣。

2048种变体和克隆

只是为了好玩,我还将AI作为书签实现了,与游戏的控件挂钩。这使AI可以与原始游戏及其许多变体一起使用

这可能是由于人工智能的域无关性所致。有些变体是相当明显的,比如六边形克隆。




Answer 4 Daren


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

我已经完善了这个算法,并且打败了这个游戏! 它可能会因为简单的运气不好而失败(你被迫往下移动,这是你永远不应该做的,在你最高的地方出现了一个瓦片,你的最高的地方应该是。尽量把最高的那一排填满就好了,所以向左移动不会打破格局),但基本上你最终会有一个固定的部分和一个移动的部分来玩。这就是你的目标。

Ready to finish

这是我默认选择的模式。

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

所选的角是任意的,你基本上永远不会按一个键(禁止的动作),如果按了,就再按一次相反的键,然后再试着修复。对于未来的瓷砖,模型总是期望下一个随机瓷砖是2,并出现在当前模型的反面(当第一排未完成时,在右下角,一旦第一排完成后,在左下角)。

算法是这样的。胜率在80%左右(看来用更 "专业 "的AI技术,似乎总能赢,不过我不太清楚这一点)。

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)
  }

关于缺失步骤的几点提示。在这里。model change

由于运气好,更接近于预期的模型,所以模型发生了变化。人工智能所要实现的模型是

 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创建的地方),然后将继续完成链,直到它得到。

Chain completed

所以现在模式和链条又回到了。

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

第二个指针,它的运气不好,主要的点位已经被拿下了。很可能会失败,但还是可以实现的。

Enter image description here

这里的模式和链条是。

  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



Answer 5 Nicola Pezzotti


我在这里复制博客文章的内容


我提出的方案很简单,也很容易实现。虽然,它已经达到了131040分。提出了几种算法性能的基准。

Score

Algorithm

启发式评分算法

我的算法所依据的假设相当简单:如果想获得更高的分数,就必须尽可能地保持棋盘的整齐。具体来说,最优的设置是由瓦片值的线性和单调的递减顺序给出的。这个直觉也会给你一个瓦片值的上界。s其中n为棋盘上的瓷砖数量。

(有可能在需要的时候,如果随机生成的4分彩而不是2分彩,就有可能达到131072的瓦片)

板书的两种可能的组织方式如下图所示。

enter image description here

为了以单调递减的顺序执行图块的排序,将分数si计算为板上线性化值的总和乘以公共比率r <1的几何序列的值。

s

s

多条线性路径可以同时进行评价,最终得分将是任何路径的最高分。

决策规则

决策规则的实现不是很聪明,这里用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,肯定会改善算法。显然,更复杂的决策规则会拖慢算法的速度,而且需要一些时间来实现。(敬请关注)

Benchmark

  • 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

enter image description here enter image description here enter image description here enter image description here

在T2的情况下,10个测试中,有4个测试产生了4096张牌,平均得分为s42000

Code

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