Mathematical Analysis of 2048, The Game论文分享

0 摘要

游戏 2048 席卷了互联网，产生了无数的盗版。 世界各地的人们倾注了数百万小时试图创造 2048 棋子。 除了令人上瘾的游戏外，该游戏还提供了探索数学的有趣机会。 本文试图通过数学归纳法、数论、模糊论和拓扑学对博弈进行数学分析，在此过程中也试图找到确保胜利的最优策略。
关键词：数学分析，2048，帕斯卡三角 (Pascals Triangle)，优化

1 引言

2048 是由Gabriele Cirulli 开发的滑块益智游戏。 这是一个在 4x4 网格上玩的游戏，棋子编号为 $2^n$，其中“n”代表自然数。 游戏的目标是将相同编号的棋子组合在一起，最终形成数字 2048。用户可以在四个基本方向上移动，每次移动后，网格中随机生成一个新的棋子，编号为 2 或 4 概率约为 0.10。 如果至少一个棋子可以滑入一个空白点，或者如果棋子可以在所选方向上组合，则移动是合法的。 当用户没有任何合法移动时，游戏结束。 不禁要问一个问题，既然游戏是基于数学的，是否可以通过应用不同的数学概念来优化移动以提高我们的分数。

2 数学归纳法

在游戏开始时，我们会在随机位置获得两块棋子。 棋子可以用前面讨论的概率编号为 2 或 4。 通过观察，可以看出网格只能包含 $2^n$ 形式的数字。 我们也可以通过使用数学归纳法在数学上证明这一点。
第一步：一开始给出的棋子都是2，2和4，或者都是4。 总共有 2!2! -1 = 3 例。 这里的数字可以用 $2^n$ 的形式表示。
第二步：假设经过k步后，网格中的数字可以用 $2^n$ 的形式表示。
第三步：在第（k+1）步，出现以下情况
I. 我们把棋子滑到一个空的地方，没有棋子相互结合
II. 我们将两个或多个现有的棋子相互组合
III. 案例 1 和 2 的组合
在所有这三种情况下，都会随机生成一个新棋子，编号为 2 或 4，默认情况下可以表示为 2 的幂。

在第一种情况下，除了第 k 步的数字之外，我们只有一个新数字，它都可以用 2 的幂表示。在另一种情况下，由于编号为 $2^r$ 的棋子将组合成编号为 $2^{r+1}$ 的棋子， 所有的棋子仍然可以用 2 的幂来表示。

所以我们可以说，在任何时候，网格都只有可以用 $2^n$ 表示的数字。

3 最大棋子

从前面的讨论中，我们知道所有的棋子都是 $2^n$ 的形式，所以最大的棋子也将是相同的形式。
让我们假设 $2^r$ 是 $r\in N$ 的最大棋子。
要创建此棋子，需要 2 个 $2^{r?1}$ 的棋子，要创建$2^{r?1}$ 的图块，需要 2 个 $2^{r?2}$ 的图块，依此类推。
棋子的数量受网格上的空间限制，即 16 个空间，这意味着 $r=16$。
因此，如果我们最后得到 2，则 $2^{16}=65536$ 是最大的棋子。
假设我们很幸运，最后得到编号为 4 的棋子； $2^{r+1}$ 将是最大的棋子。
所以 $2^{17}=131072$ 将是最大的棋子。

4 最大可能总和 (Sn)

所有的棋子都是 $2^n$ 的形式。 假设最好的情况是没有两个相同编号的棋子，并且我们在网格中拥有最高编号的棋子，可以很容易地看到它们将形成一个几何级数（GP）。 此外，由于我们正在考虑最佳情况，我们可以将最小的数字设为 4 而不是 2。总和 Sn 将由下式给出：
$$\begin{array}{rl}{\mathrm{S}}_{\mathrm{n}}& =2^2+2^3+2^4+\dots \dots \dots +2^{17}\\ & =2\left(2^{17}?1\right)/(2?1)?2^1\\ & =262142?2\\ & =262140\end{array}$$
如果 最后一块是 2 而不是 4，那么总和将是：
$$\begin{array}{rl}{\mathrm{S}}_{{\mathrm{n}}^{\prime }}& =2^1+2^3+2^4+\dots \dots \dots +2^{17}\\ & =2\left(2^{17}?1\right)/(2?1)?2^2\\ & =262142?4\\ & =262138\end{array}$$
或者我们可以做：
$$\begin{array}{rl}{\mathrm{S}}_{{\mathrm{n}}^{\prime }}& =262140?2\\ & =262138\end{array}$$

5 最少获胜回合数 ($T_{min}$)

通过创建 2048 棋子来赢得游戏（尽管可以选择继续玩，直到没有更多的合法移动）。由于棋子是随机生成的； 2 的概率为 0.9 ($P_2=0.9$) 和 4 的概率为 0.1 ($P_4=0.1$)； 我们无法给出 $T_{min}$ 的确切数字，但我们可以给出一个范围。

1. 假设最好的情况是我们得到的所有棋子都是 4 号，并且我们所做的每一步都会导致 2 个棋子合并为 1 个棋子。
   现在，要制作 2048，我们至少需要 512 个棋子（$512\times 4=2048$）。 但是我们从 2 个棋子开始，这意味着我们需要 512-2=510 圈才能获得所有需要的棋子。 我们得到的最后一个棋子必须组合成 8，然后将 8s 组合成 16，将 16s 组合成 32，依此类推，直到我们将 1024s 组合成 2048。
   所以我们得到，
   $$\begin{array}{rl}{\mathrm{T}}_{\min }& =512?2+9\\ & =519\text{ turns }\end{array}$$
   得到所有编号为4的棋子的概率是$0.1^{519}=10^{?519}$。

2. 考虑一个例子，我们得到所有编号为 2 而不是 4 的棋子。如上所述，我们需要 1024 个棋子来生成 2048，然后将我们得到的最后一个棋子与另一个编号为 2 的棋子组合起来，最终得到 2048。
   同理：
   $$\begin{array}{rl}{\mathrm{T}}_{\min }& =1024?2+10\\ & =1032\text{ turns }\end{array}$$
   得到所有 2 个编号的棋子的概率是：$0.9^{1032}?6.0\times 10^{?48}$。
   因此，假设我们玩一场完美的游戏，赢得游戏所需的最少回合数在 [519, 1032]。