我最近偶然发现了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的最高分数略高于20000分,这比我目前的分数要大得多。有比上述更好的算法吗?


当前回答

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

表演

AI在其默认配置(最大搜索深度为8)中执行移动需要10毫秒到200毫秒,具体取决于板位置的复杂性。在测试中,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平铺!

以下是最佳跑步记录的截图:

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

实施

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

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

评分也使用表格查找来完成。这些表包含对所有可能的行/列计算的启发式得分,一个板的最终得分只是每行和每列的表值之和。

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

expectimax搜索本身被编码为递归搜索,它在“期望”步骤(测试所有可能的平铺生成位置和值,并根据每个可能性的概率加权其优化分数)和“最大化”步骤(检测所有可能的移动并选择具有最佳分数的移动)之间交替。当树搜索看到之前看到的位置(使用换位表)、达到预定义的深度限制或达到极不可能达到的板状态时(例如,通过从起始位置开始一行获得6“4”块而达到),树搜索终止。典型的搜索深度为4-8次移动。

启发式

使用几种启发式方法将优化算法引向有利位置。启发式算法的精确选择对算法的性能有着巨大的影响。各种启发式算法被加权并组合成一个位置得分,这决定了给定的董事会位置有多“好”。然后,优化搜索将旨在最大化所有可能董事会位置的平均得分。如游戏所示,实际得分不用于计算棋盘得分,因为它的权重太大,有利于合并瓦片(当延迟合并可能产生很大的好处时)。

最初,我使用了两种非常简单的启发式方法,即为开放正方形和边缘值较大的正方形授予“奖金”。这些启发式算法表现得很好,经常达到16384,但从未达到32768。

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

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

这些变化的影响极其显著。该算法在大约13%的时间内实现了16384个瓦片,在90%的时间内完成了它,并且该算法在1/3的时间内开始实现32768个瓦片(而旧的启发式算法从未产生过32768个)。

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


人工智能在超过三分之一的游戏中获得32768分,这是一个巨大的里程碑;我会很惊讶地听到是否有人类玩家在官方游戏中达到了32768(即不使用保存状态或撤销等工具)。我认为65536瓷砖触手可及!

你可以自己尝试人工智能。该代码位于https://github.com/nneonneo/2048-ai.

其他回答

这不是对OP问题的直接回答,这是我迄今为止试图解决同一问题的更多东西(实验),并获得了一些结果和一些我想分享的观察结果,我很好奇我们能否从中获得一些进一步的见解。

我刚刚尝试了使用alpha beta修剪的minimax实现,搜索树深度截止值为3和5。我试图解决4x4网格的相同问题,作为edX课程ColumbiaX:CSMM101x人工智能(AI)的项目作业。

我应用了两个启发式评估函数的凸组合(尝试了不同的启发式权重),主要来自直觉和上面讨论的函数:

单调性可用的可用空间

在我的情况下,电脑玩家是完全随机的,但我仍然假设了对抗性设置,并将AI玩家代理实现为最大玩家。

我有4x4网格来玩游戏。

观察结果:

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

我也尝试过拐角启发式,但出于某种原因,它会使结果更糟,凭直觉为什么?

此外,我尝试将搜索深度截止值从3增加到5(我不能再增加了,因为即使在修剪的情况下,搜索该空间也超过了允许的时间),并添加了一个启发式方法,它查看相邻平铺的值,如果它们可以合并,则会给出更多的点,但我仍然无法获得2048。

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

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

任何见解都将非常有用,提前感谢。(这是我博客文章的链接: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分,这一次还添加了绝对值启发式:

下图显示了玩家AI代理探索的游戏树,假设计算机是对手,只需一步:

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

表演

AI在其默认配置(最大搜索深度为8)中执行移动需要10毫秒到200毫秒,具体取决于板位置的复杂性。在测试中,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平铺!

以下是最佳跑步记录的截图:

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

实施

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

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

评分也使用表格查找来完成。这些表包含对所有可能的行/列计算的启发式得分,一个板的最终得分只是每行和每列的表值之和。

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

expectimax搜索本身被编码为递归搜索,它在“期望”步骤(测试所有可能的平铺生成位置和值,并根据每个可能性的概率加权其优化分数)和“最大化”步骤(检测所有可能的移动并选择具有最佳分数的移动)之间交替。当树搜索看到之前看到的位置(使用换位表)、达到预定义的深度限制或达到极不可能达到的板状态时(例如,通过从起始位置开始一行获得6“4”块而达到),树搜索终止。典型的搜索深度为4-8次移动。

启发式

使用几种启发式方法将优化算法引向有利位置。启发式算法的精确选择对算法的性能有着巨大的影响。各种启发式算法被加权并组合成一个位置得分,这决定了给定的董事会位置有多“好”。然后,优化搜索将旨在最大化所有可能董事会位置的平均得分。如游戏所示,实际得分不用于计算棋盘得分,因为它的权重太大,有利于合并瓦片(当延迟合并可能产生很大的好处时)。

最初,我使用了两种非常简单的启发式方法,即为开放正方形和边缘值较大的正方形授予“奖金”。这些启发式算法表现得很好,经常达到16384,但从未达到32768。

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

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

这些变化的影响极其显著。该算法在大约13%的时间内实现了16384个瓦片,在90%的时间内完成了它,并且该算法在1/3的时间内开始实现32768个瓦片(而旧的启发式算法从未产生过32768个)。

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


人工智能在超过三分之一的游戏中获得32768分,这是一个巨大的里程碑;我会很惊讶地听到是否有人类玩家在官方游戏中达到了32768(即不使用保存状态或撤销等工具)。我认为65536瓷砖触手可及!

你可以自己尝试人工智能。该代码位于https://github.com/nneonneo/2048-ai.

我的尝试与上面的其他解决方案一样使用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上的代码:

变量n=4,M=新矩阵变换(n);var ai={weights:[1,1],深度:1};//默认情况下,depth=1,但我们会根据空闲平铺的数量对每个预测进行调整var蛇=[[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(函数(a){return a.map(Math.exp)})初始化(ai)函数运行(ai){变量p;而((p=预测(ai))!=空){移动(p,ai);}//console.log(ai.grid,maxValue(ai.ggrid))ai.maxValue=最大值(ai.grid)控制台日志(ai)}函数初始化(ai){ai.grid=[];对于(变量i=0;i<n;i++){ai网格[i]=[]对于(变量j=0;j<n;j++){ai.grid[i][j]=0;}}兰特(ai网格)兰特(ai网格)ai.steps=0;}函数move(p,ai){//0:向上,1:向右,2:向下,3:向左var newgrid=mv(p,ai.grid);if(!equal(newgrid,ai.grid)){//console.log(stats(newgrid,ai.grid))ai.grid=新网格;尝试{兰特(ai网格)ai.步骤++;}捕获(e){控制台日志(“无房间”,e)}}}函数预测(ai){var free=freeCells(ai.grid);ai.depth=自由>7?1:(自由>4?2:3);var-root={path:[],prob:1,grid:ai.grid,childs:[]};var x=expandMove(根,ai)//console.log(“叶数”,x)//console.log(“叶数2”,countLeaves(根))if(!root.childres.length)返回nullvar values=root.childres.map(expectimax);var mx=最大值;return root.childrens[mx[1]].path[0]}函数countLeaves(节点){变量x=0;if(!node.childres.length)返回1;for(node.childs的var n)x+=叶数(n);返回x;}函数预期值(节点){if(!node.childres.length){返回node.score}其他{var values=node.childres.map(expectimax);如果(node.prob){//我们处于最大节点return Math.max.apply(空,值)}否则{//我们处于随机节点var平均值=0;对于(var i=0;i<values.length;i++)avg+=节点.子项[i].prob*值[i]返回平均值/(values.length/2)}}}函数expandRandom(节点,ai){变量x=0;对于(var i=0;i<node.grid.length;i++)对于(var j=0;j<node.grid.length;j++)if(!node.grid[i][j]){var grid2=M.copy(node.grid),grid4=M.copy(node.grid);网格2[i][j]=2;网格4[i][j]=4;var child2={grid:grid2,prob:.9,path:node.path,childs:[]};var child4={grid:grid4,prob:.1,path:node.path,childs:[]}node.childres.push(child2)node.childres.push(child4)x+=expandMove(child2,ai)x+=expandMove(child4,ai)}返回x;}函数expandMove(node,ai){//node={grid,path,score}var isLeaf=真,x=0;如果(节点路径长度小于ai深度){for(变量移动[0,1,2,3]){var grid=mv(移动,node.grid);if(!equal(grid,node.grid)){isLeaf=false;var child={grid:grid,path:node.path.contat([move]),childs:[]}node.childres.push(child)x+=expandRandom(子级,ai)}}}if(isLeaf)node.score=dot(ai.weights,stats(node.grid))return是Leaf?1:x;}var单元格=[]var table=document.querySelector(“table”);对于(变量i=0;i<n;i++){var tr=document.createElement(“tr”);单元格[i]=[];对于(变量j=0;j<n;j++){cells[i][j]=document.createElement(“td”);tr.appendChild(单元格[i][j])}table.appendChild(tr);}函数更新UI(ai){cells.forEach(函数(a,i){a.forEach(函数(el,j){el.innerHTML=ai.grid[i][j]| |“”})});}更新UI(ai);updateHint(预测(ai));函数runAI(){var p=预测(ai);如果(p!=null&&ai.running){移动(p,ai);更新UI(ai);updateHint(p);requestAnimationFrame(runAI);}}runai.onclick=函数(){if(!ai.running){this.innerHTML=“停止AI”;ai.running=真;runAI();}其他{this.innerHTML=“运行AI”;ai.running=false;updateHint(预测(ai));}}函数updateHint(dir){hintvalue.innerHTML=['↑', '→', '↓', '←'][目录]| |“”;}document.addEventListener(“keydown”,函数(事件){if(!event.target.matches('.r*'))返回;event.prpreventDefault();//避免滚动if(地图中的event.which){移动(map[event.with],ai)console.log(stats(ai.grid))更新UI(ai);updateHint(预测(ai));}})变量映射={38:0,//以上39:1,//右40:2,//向下37:3,//左};init.onclick=函数(){初始化(ai);更新UI(ai);updateHint(预测(ai));}函数统计信息(网格,previousGrid){var free=freeCells(网格);var c=dot2(网格,蛇);返回[c,free*free];}函数dist2(a,b){//2D距离的平方返回Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2)}功能点(a,b){变量r=0;对于(var i=0;i<a.length;i++)r+=a[i]*b[i];返回r}函数dot2(a,b){变量r=0;对于(var i=0;i<a.length;i++)对于(变量j=0;j<a[0].length;j++)r+=a[i][j]*b[i][j]返回r;}函数积(a){return a.reduce(函数(v,x){返回v*x}, 1)}函数maxValue(网格){return Math.max.apply(null,grid.map(函数(a){return Math.max.apply(null,a)}));}无功能单元格(网格){返回grid.reduce(函数(v,a){返回v+a.reduce(函数(t,x){返回t+(x==0)}, 0)}, 0)}函数max(arr){//返回max的[value,index]var m=[-无限,空];对于(变量i=0;i<arr.length;i++){如果(arr[i]>m[0])m=[arr[i],i];}返回m}函数min(arr){//返回min的[value,index]var m=[无限,空];对于(变量i=0;i<arr.length;i++){如果(arr[i]<m[0])m=[arr[i],i];}返回m}函数maxScore(节点){变量最小值={分数:-无限,路径:[]};for(节点的var节点){如果(node.score>min.score)min=节点;}

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


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

算法

启发式评分算法

我的算法所基于的假设相当简单:如果你想获得更高的分数,那么棋盘必须尽可能保持整洁。特别地,最优设置由瓦片值的线性和单调递减顺序给出。这种直觉也会给你一个平铺值的上限:其中n是板上平铺的数量。

(如果需要时随机生成4个图块而不是2个图块,则有可能达到131072图块)

两种可能的董事会组织方式如下图所示:

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

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

决策规则

实现的决策规则不太聪明,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或Expectimimax的实现肯定会改进算法。显然更多复杂的决策规则会降低算法的速度,并且需要一些时间来实现。我将在不久的将来尝试一个最小值实现。(敬请关注)

基准

T1-121测试-8个不同路径-r=0.125T2-122测试-8个不同路径-r=0.25T3-132测试-8个不同路径-r=0.5T4-211测试-2条不同路径-r=0.125T5-274测试-2条不同路径-r=0.25T6-211测试-2条不同路径-r=0.5

在T2的情况下,十次测试中有四次生成平均分数为42000的4096分图块

Code

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

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

我改进了算法,打败了游戏!它可能会因为临近结束时的简单厄运而失败(你被迫向下移动,这是你永远不应该做的,并且在你最高的位置会出现一个瓦片。只需保持最上面的一行填满,这样向左移动不会打破模式),但基本上你最终有一个固定的部分和一个移动的部分可以玩。这是您的目标:

这是我默认选择的模型。

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

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

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

 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创建的位置),然后继续完成链,直到它得到:

因此,现在模型和链又回到了:

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

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

这里的模型和链是:

  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