如果你在2010年代上过网，你可能对这款令人上瘾的游戏2048并不陌生。让我们借助机器学习的力量，看看能取得多高的分数。

游戏机制

游戏运行机制如下。棋盘初始时随机生成2个方块。 每个随机方块有90%的概率为2，10%的概率为4。

共有4种可能的移动方向：上、下、左、右。每次移动对应棋盘上的“滑动”动作，所有方块会朝该方向移动，直到与另一个方块碰撞。如果两个方块的值为相同的 $N$，它们会合并为一个值为 $2N$的更高方块。每次合并时，我们的分数会增加 $2N$。

这真的有那么难吗？

是的，确实如此。至少要达到任意高的分数是相当困难的。为了理解这一点，假设你已经达到了1024分。那么，你已经使用了16个方格作为“草稿纸”来获得这个分数。然而，要得到2048分，你必须用 $16-1=15$个方格作为草稿纸再生成另一个1024分。要得到4096分，你需要用14个方格来完成，以此类推。因此，实际上存在一个 理论上的最高分数3,932,156分 ， 这个分数仅从空间限制的角度就可以计算出来。我们今天不会达到这个目标，但我们会尝试超越最好的人类玩家。

方法

我们将使用两类方法：基于搜索的和基于学习的。基于搜索的方法尝试探索多种可能的游戏状态，并根据最有可能导致期望结果的走法做出猜测。基于学习的方法则定义一个玩家模型，并通过模拟大量游戏来学习其参数。

随机玩家

这是我们的基线。它的表现相当糟糕。

蒙特卡洛方法

该方法的工作原理如下：

• 我们有一个主棋盘，只在此棋盘上执行最优移动
• 对于每一个可能的移动 $m$，复制棋盘，并在复制的棋盘上执行移动 $m$
• 然后，让一个随机玩家在该棋盘上进行移动，直到游戏失败。然后，保存最终棋盘上所有格子的总和。这将作为我们的得分。
• 重复上述过程 $N$ 次， $N$ 越大意味着探索的游戏越多。
• 选择平均得分最高的移动作为最优移动。

以下是伪代码：

def choose_best_move(board):
    scores = [] # 平均格子总和的列表
    moves = [UP, DOWN, LEFT, RIGHT]
    for move in moves:
        # 复制棋盘
        board_copy = copy(board)
        # 执行移动（包括生成新格子）
        board_copy.make_move(move)
        tile_sums = []
        # 在此移动的基础上，让一个随机玩家
        # 进行游戏直到失败。然后，记录
        # 最终棋盘上格子的平均总和。
        for n in range(num_games):
            board_copy2 = copy(board_copy)
            # 让一个随机代理进行游戏直到失败
            board_copy2.random_game()
            sums.append(board_copy2.tile_sum())
        # 保存失败配置下的平均格子总和
        scores.append(sum(tile_sums) / len(tile_sums))
    return moves[argmax(scores)]

N元组网络

N元组网络，最初构想为RAMnets ，已被发现在使用时间差分学习训练时，非常擅长玩2048游戏。它们有效地定义了一个函数 $F$，该函数将某种以二进制编码的特征映射到一个分数，该分数表示该特定特征的优劣。

与大多数现代神经网络不同，这个函数不是计算出来的，而是存储在一个数组中，数组的每个元素代表与其索引对应的特征的分数。

为了理解我们将如何索引到数组中，让我们看一下游戏板的实现。

棋盘实现

struct Board {
    raw: u64,
}

没错，我们将整个棋盘压缩进了一个64位无符号整数中。我们通过以下观察实现了这一点：

1. 每个格子的值要么为空，要么为 $2^n$，其中 $n\ge 1$。
2. 根据经验，我们可能不会得到 $2^{16}=65536$的格子。

这导致了 $1\le n\le 15$的界限。因此，每个格子有 $15+1$种可能的值，这意味着我们可以将其压缩为 $4$位。为了恢复格子的实际值，我们使用：

架构

我们使用的网络是一个 $4\times 6$ 元组网络，包含 4 个特征，每个特征代表棋盘上 $6$ 个格子的配置。由于每个格子占用 $4$ 位，每个特征将使用 $6\times 4=24$ 位。

由于我们的网络是从特征 $\to$ 分数的映射，我们使用一个大小为 $2^{4\times 6}=\text{16,777,216}$ 的 32 位浮点数数组来存储每个特征。由于每个浮点数占用 4 字节，这使得我们的网络大小达到 $4\times 4\times \text{16,777,216}=\text{268,435,456}$ 字节。

我们可以做一个方便的观察：特征的值不应因其在棋盘上的位置而改变。例如，一行包含 $(512,1024,2048,4096)$ 的格子，无论它位于棋盘的顶部、底部、左侧还是右侧，其价值都是相同的。事实上，即使我们将其顺序反转，它的价值也依然相同。这意味着我们可以重用相同的权重来计算特征在所有方向或对称性下的分数。一个正方形有 8 种这样的对称性 ，我们在下面展示了这些对称性。