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


我最近偶然发现了这场比赛 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分,远高于我目前的分数。是否有比上述更好的算法?


1755
2018-03-12 05:37


起源


这可能有帮助! ov3y.github.io/2048-AI - cegprakash
顺便说一句,@ nitish712,你的算法是贪婪的 choose the move with large number of merges 这很快导致局部最优 - Khaled.K
@ 500-InternalServerError:如果 一世 要实现一个带有alpha-beta游戏树修剪的AI,它会假设新的块是对手放置的。这是一个最坏情况的假设,但可能有用。 - Charles
当你没有时间瞄准高分时,有趣的分心:尽量获得最低分。理论上它是2s和4s交替。 - Mark Hurd
关于这个问题的合法性的讨论可以在meta上找到: meta.stackexchange.com/questions/227266/... - Jeroen Vannevel


答案:


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

性能

默认配置中的AI(最大搜索深度为8)需要10ms到200ms才能执行移动,具体取决于电路板位置的复杂程度。在测试中,AI在整个游戏过程中实现了每秒5-10次移动的平均移动速度。如果搜索深度限制为6次移动,则AI可以轻松地执行每秒20次以上的移动,这可以实现一些 有趣的看着

为了评估AI的得分表现,我运行了100次AI(通过遥控器连接到浏览器游戏)。对于每个图块,以下是至少一次实现该图块的游戏比例:

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

所有运行的最低分数是124024;达到的最高分为794076.中位数为387222. AI从未获得2048牌(因此在100场比赛中它甚至没有输过一场比赛);事实上,它实现了 8192 每次运行至少一次!

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

32768 tile, score 794076

这场比赛在96分钟内完成了27830次移动,平均每秒4.8次移动。

履行

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

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

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

该板表示以及用于移动和评分的表查找方法允许AI在短时间内搜索大量游戏状态(在我2011年中期的笔记本电脑的一个核心上每秒超过10,000,000个游戏状态)。

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

启发式

使用几种启发法将优化算法指向有利位置。启发式的精确选择对算法的性能有很大影响。各种启发式方法被加权并组合成位置分数,该分数确定给定的板位置的“好”程度。然后,优化搜索将旨在最大化所有可能的董事会职位的平均分数。如游戏所示,实际得分是  用于计算董事会得分,因为它的权重太大而有利于合并磁贴(当延迟合并可能产生很大的好处)。

最初,我使用了两个非常简单的启发式方法,为空心方块和边缘上的大值赋予“奖励”。这些启发式表现相当不错,经常达到16384但从未达到32768。

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

此外,Petr还使用“元优化”策略(使用称为的算法)优化启发式权重 CMA-ES),调整权重本身以获得尽可能高的平均分。

这些变化的影响非常显着。该算法从大约13%的时间实现16384瓦片到90%以上的时间实现它,并且算法在1/3的时间内开始达到32768(而旧的启发式方法从未生成32768瓦片) 。

我相信启发式方法仍有改进的余地。这个算法肯定还不是“最优”,但我觉得它已经非常接近了。


人工智能在超过三分之一的游戏中实现32768瓦片是一个巨大的里程碑;如果有任何人类玩家在官方游戏中获得32768(即不使用像savestates或撤消等工具),我会感到惊讶。我认为65536瓷砖是触手可及的!

你可以亲自试试AI。代码可在 https://github.com/nneonneo/2048-ai


1132
2018-03-19 07:22



@RobL:2%出现90%的时间; 4%出现在10%的时间。它在 源代码: var value = Math.random() < 0.9 ? 2 : 4;。 - nneonneo
目前移植到Cuda,因此GPU可以提供更好的速度! - nimsson
@nneonneo我用emscripten将你的代码移植到javascript,它运行得很好 在浏览器中 现在!很酷的观看,无需编译和一切......在Firefox中,性能相当不错...... - reverse_engineer
4x4网格中的理论极限实际上是IS 131072而不是65536.但是这需要在正确的时刻获得4(即整个电路板每次填充4 .. 65536 - 占用15个字段)并且必须设置电路板这一刻让你真的可以结合起来。 - Bodo Thiesen
@nneonneo您可能想要检查我们的AI,这似乎更好,在60%的游戏中达到32k: github.com/aszczepanski/2048 - cauchy


我是其他人在这个帖子中提到的AI程序的作者。你可以在中查看AI 行动 或阅读 资源

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

由于游戏是一个离散的状态空间,完美的信息,像国际象棋和棋子这样的回合制游戏,我使用的方法已被证明适用于那些游戏,即 极小  搜索 同 alpha-beta修剪。由于那里已经有很多关于那个算法的信息,我只想谈谈我在这个算法中使用的两个主要的启发式方法。 静态评估功能 并且正式化了其他人在这里表达的许多直觉。

单调性

该启发式尝试确保瓦片的值沿左/右和上/下方向都增加或减少。这种启发式捕获了许多其他人提到的直觉,即更高价值的瓷砖应该聚集在一个角落里。它通常会阻止较小的有价值的瓷砖变得孤立,并使电路板非常有条理,较小的瓷砖层叠并填充到较大的瓷砖中。

这是一个完美单调网格的屏幕截图。我通过运行算法并使用eval函数设置忽略其他启发式算法并且仅考虑单调性来获得此结果。

A perfectly monotonic 2048 board

顺利

上述启发式单独倾向于创建其中相邻瓦片的值减小的结构,但是当然为了合并,相邻瓦片需要是相同的值。因此,平滑度启发式测量仅测量相邻图块之间的值差异,尝试最小化此计数。

黑客新闻的评论者给了 一个有趣的形式化 这个想法在图论方面。

这是一个完美平滑网格的截图,礼貌 这个优秀的模仿叉子

A perfectly smooth 2048 board

免费瓷砖

最后,由于游戏牌太过狭窄,选项很快就会耗尽,因此免费牌位太少会受到惩罚。

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

编辑:

以下是这种方法的强大功能。我打开了瓷砖值(所以它在达到2048后继续运行),这是八次试验后的最佳结果。

4096

是的,这是2048年的4096. =)这意味着它在同一块板上实现了三次难以捉摸的2048瓦片。


1224
2018-03-13 20:04



您可以将计算机放置为“2”和“4”磁贴作为“对手”。 - Wei Yen
@WeiYen当然,但是将其视为minmax问题并不忠实于游戏逻辑,因为计算机会以一定的概率随机放置磁贴,而不是故意将分数降至最低。 - koo
即使AI随机放置瓷砖,目标也不会丢失。不幸的是,对手为你选择最糟糕的举动是一回事。 “min”部分意味着你试图保守地玩,这样就没有可怕的动作让你不幸运。 - FryGuy
我有一个想法是创建一个2048的分支,其中计算机而不是放置2s和4s随机使用你的AI来确定放置值的位置。结果:完全不可能。可以在这里试用: sztupy.github.io/2048-Hard - SztupY
@SztupY哇,这是邪恶的。提醒我 qntm.org/hatetris Hatetris,也试图放置最能改善你情况的作品。 - Patashu


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

我已经改进了算法并击败了游戏!它可能会因为接近末尾的简单坏运而失败(你被迫向下移动,你永远不应该这样做,而且你的最高点应该出现在你的最高位置。只是尽量保持顶行填充,所以向左移动不会打破模式),但基本上你最终有一个固定的部分和一个移动部分来玩。这是你的目标:

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

由于更接近预期模型的运气,该模型已经改变。 AI试图实现的模型是

 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

119
2018-03-12 16:05



execute move with best score 你怎么能评估下一个州的最佳分数? - Khaled.K
启发式定义于 evaluateResult 你基本上试图最接近最好的情况。 - Daren
@Daren我在等你详细的细节 - ashu
@ashu我正在努力,意想不到的情况让我没有时间完成它。与此同时,我对算法进行了改进,现在75%的时间都可以解决这个问题。 - Daren
我真正喜欢这个策略是我能够在手动玩游戏时使用它,它让我高达37k点。 - Cephalopod


我开始对包含这个游戏的人工智能的想法感兴趣 没有硬编码的情报 (即没有启发式,评分功能等)。 AI应该 “知道” 只有游戏规则,和 “弄清楚” 游戏。这与大多数AI(如本线程中的那些)相反,其中游戏玩法基本上是由表示人类对游戏的理解的评分函数引导的强力。

AI算法

我发现了一个简单但令人惊讶的好玩法:为了确定给定棋盘的下一步动作,AI在内存中玩游戏 随机动作 直到比赛结束。这样做几次,同时跟踪最终比赛得分。然后是平均最终得分 每个开始的动作 计算。选择具有最高平均最终得分的起始移动作为下一步行动。

每次移动仅运行100次(即在记忆游戏中),AI在80%的时间内达到2048瓦,在50%的时间内达到4096瓦。使用10000次运行获得2048瓦100%,4096瓦的70%,以及8192瓦的约1%。

看到它在行动

获得的最佳成绩如下所示:

best score

关于这个算法的一个有趣的事实是,虽然随机游戏不出所料非常糟糕,选择最好(或最不好)的动作会带来非常好的游戏玩法:典型的AI游戏可以达到70000点并持续3000次移动,但是来自任何给定位置的记忆内随机游戏在死亡前的大约40次额外移动中平均产生340个额外点。 (您可以通过运行AI并打开调试控制台来自行查看。)

此图表说明了这一点:蓝线显示每次移动后的董事会得分。红线表示算法 最好 该位置的随机结束比赛得分。从本质上讲,红色值是向上“拉”蓝色值,因为它们是算法的最佳猜测。有趣的是,红线在每个点的蓝线上方稍微高一点,但蓝线继续增加越来越多。

scoring graph

我觉得非常令人惊讶的是,算法并不需要实际预见好游戏才能选择产生它的动作。

稍后搜索我发现这个算法可能被归类为a 纯蒙特卡罗树搜索 算法。

实施和链接

首先我创建了一个JavaScript版本 在这里看到了行动。这个版本可以在适当的时间运行100次运行。打开控制台以获取额外信息。 (资源

后来,为了更多地使用@nneonneo高度优化的基础设施并在C ++中实现我的版本。如果你有耐心,这个版本允许每次移动最多100000次运行甚至1000000次运行。提供建筑说明。它在控制台中运行,并且还具有远程控制以播放Web版本。 (资源

结果

令人惊讶的是,增加跑步次数并没有大幅提升比赛效果。这个策略似乎有一个限制,大约80000点,4096瓦和所有较小的瓦,非常接近实现8192瓦。将运行次数从100增加到100000会增加 可能性 达到这个分数限制(从5%到40%)但没有突破它。

在关键位置附近运行10000次运行并暂时增加到1000000,设法打破此障碍,不到1%的时间达到最大分数129892和8192瓦。

改进

实现此算法后,我尝试了许多改进,包括使用最小或最大分数,或min,max和avg的组合。我也尝试过使用深度:我没有尝试每次移动K次,而是每次移动都尝试了K次移动 名单 给定长度(例如,“向上,向上,向左”)并选择最佳得分移动列表的第一步。

后来我实施了一个评分树,该树考虑了在给定移动列表之后能够进行移动的条件概率。

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

我确实添加了一个“深度搜索”机制,当任何一次运行意外到达下一个最高的磁贴时,它会暂时将运行次数增加到1000000。这提供了时间的改善。

我很想知道是否有人有其他改进想法来保持AI的域独立性。

2048变种和克隆

只是为了好玩,我也是 将AI实现为书签,挂进游戏的控件。这允许AI与原始游戏一起工作 它的许多变种

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


114
2018-05-25 09:25



+1。作为AI学生,我发现这非常有趣。将在空闲时间更好地了解这一点。 - Isaac
这真太了不起了!我只花了几个小时来优化权重以获得expectimax的良好启发式功能,并且我在3分钟内实现了这一点,这完全打破了它。 - Brendan Annable
很好地使用蒙特卡罗模拟。 - nneonneo
观看这场比赛需要一种启蒙。这吹嘘所有的启发式,但它的工作原理。恭喜! - Stéphane Gourichon
到目前为止,这是最有趣的解决方案。 - shebaw


我在这里复制了一个内容 发布在我的博客上


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

Score

算法

启发式评分算法

我的算法所依据的假设相当简单:如果你想获得更高的分数,董事会必须保持尽可能整洁。特别地,最佳设置由瓦片值的线性和单调递减顺序给出。 这种直觉也会给你一个tile值的上限: 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的实现肯定会改进算法。显然更多 复杂的决策规则会减慢算法速度,需要一些时间才能实现。我将在不久的将来尝试实现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

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

在T2的情况下,十个中的四个测试产生4096个平铺,平均得分为 s 42000

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


88
2018-03-26 22:13



不错,你的插图给了我一个想法,将合并向量纳入评估 - Khaled.K


我尝试使用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]]

它迫使瓦片从左上方的瓦片中以一条蛇的形式下降。

代码如下或 jsbin

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



不知道为什么这没有更多的赞成。它的简单性非常有效。 - David Greydanus
谢谢,迟到的答案并且表现不太好(几乎总是在[1024,8192]),成本/统计功能需要更多的工作 - caub
你是如何为空地增加重量的? - David Greydanus
这很简单 cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid) 我们试图最大化这个成本 - caub
这需要更多的Upvotes!伟大的代码! - Smartis


我认为我找到了一个效果很好的算法,因为我经常达到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);
}

25
2018-03-12 18:57



我运行了100,000个游戏来测试这个与琐碎的循环策略“向上,向右,向上,向左,......”(如果必须的话,还有下来)。循环策略完成了“平均瓦片得分” 770.6虽然这个得到了 396.7。你有猜测为什么会这样吗?我认为它确实太多了,即使左或右会合并更多。 - Thomas Ahle
如果瓷砖没有在多个方向上移动,则瓷砖倾向于以不兼容的方式堆叠。通常,使用循环策略将导致中心较大的瓦片,这使得机动更加狭窄。 - bcdan


我是2048控制器的作者,该控制器的得分比该线程中提到的任何其他程序都要好。可以使用控制器的有效实现 github上。在 一个单独的回购 还有用于训练控制器状态评估功能的代码。训练方法在中描述

控制器使用expectimax搜索和状态评估功能,从头开始学习(没有人类2048专业知识)的变体 时差学习 (强化学习技巧)。状态值函数使用 n-tuple网络,这基本上是在电路板上观察到的模式的加权线性函数。它涉及的不仅仅是 10亿个重量, 总共。

性能

在1次/ s时: 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磁贴。


25
2017-12-21 10:49



相当令人印象深刻但是你可以更新答案来解释(粗略地,简单来说......我确定完整的细节在这里发布的时间太长了)你的程序如何实现这个目标?在粗略解释学习算法如何工作? - Cedric Mamo
@CedricMamo:github上有一个引用: arxiv.org/abs/1604.05085 - Florian Castellane


这个游戏已经有了一个AI实现: 这里。摘自README:

该算法是迭代加深深度的第一个alpha-beta搜索。评估函数尝试使行和列保持单调(全部减少或增加),同时最小化网格上的图块数量。

还有一个讨论 ycombinator 关于这个你可能觉得有用的算法。


21
2018-03-13 09:16



这应该是最好的答案,但是添加有关实现的更多细节会很好:例如:游戏板如何建模(如图),采用的优化(最小 - 最大瓦片之间的差异)等。 - Alceu Costa


算法

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)

这是对在该状态下进行合并的可能性的简化检查,而不进行预测。

注意:常量可以调整..


20
2018-03-12 20:15



我稍后会编辑它,添加一个实时代码@ nitish712 - Khaled.K
这个算法的胜率是多少? - cegprakash
你为什么需要一个 constant?如果您所做的只是比较分数,那么这会如何影响这些比较的结果? - bcdan
@bcdan启发式(又名比较得分)取决于比较未来状态的预期值,类似于象棋启发式算法如何工作,除了这是线性启发式,因为我们不构建树来了解下一个N的最佳动作 - Khaled.K
@ Khaled.K你还没有添加实时代码。 - Pragyaditya Das