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的最高分数略高于20000分，这比我目前的分数要大得多。有比上述更好的算法吗？

当前回答

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

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

这是我默认选择的模型。

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

2014-03-12 16:05:34

其他回答

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

我提出的解决方案非常简单，易于实施。虽然，它已经达到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++实现一个更高效的版本。

2014-03-26 22:13:01

该算法对于赢得游戏来说不是最佳的，但就性能和所需代码量而言，它是相当最佳的：

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }

2014-03-14 21:53:56

我的尝试与上面的其他解决方案一样使用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=节点；}

2015-03-03 05:35:00