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


当前回答

许多其他答案使用人工智能,对可能的未来、启发式、学习等进行计算成本高昂的搜索。这些令人印象深刻,可能是正确的前进方向,但我想提出另一个想法。

模拟游戏中优秀玩家使用的策略。

例如:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

按照上面显示的顺序读取正方形,直到下一个正方形值大于当前值。这就带来了试图将另一个具有相同值的平铺合并到此方形中的问题。

为了解决这个问题,他们有两种移动方式,没有留下或更糟,检查这两种可能性可能会立即发现更多问题,这形成了一个依赖关系列表,每个问题都需要先解决另一个问题。我认为我在决定下一步行动时,特别是在被卡住的时候,会有一条链条,或者在某些情况下,是内部的依赖树。


瓷砖需要与邻居合并,但太小:将另一个邻居与此邻居合并。

较大的平铺:增加较小的周围平铺的值。


整个方法可能比这更复杂,但并不复杂。这可能是一种机械的感觉,缺乏分数、体重、神经和对可能性的深入探索。可能性之树甚至需要足够大,完全需要分支。

其他回答

算法

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 }

在这里,我们仍然需要检查堆叠的值,但以一种较小的方式,这不会中断灵活性参数,因此我们得到了[4,44]中的{x的和}。

+ (Number of possible next moves x 256)

如果一个国家对可能的转变有更大的自由度,它就会更灵活。

+ (Number of aligned values x 2)

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

注意:常数可以调整。。

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

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

这是我默认选择的模型。

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

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

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

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


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

这不是对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代理探索的游戏树,假设计算机是对手,只需一步: