Saechsli: 3+3小游戏自动机 - NeoAtlantis应用科学和神秘学实验室

1 前言

3+3，是一个Gamee提供的小游戏，规则类似于流行的2048游戏。

和2048不同的是，3+3需要将两个交替出现的数字加起来：1和2得到数字块3 。从数字3开始，规则和2048一样了：两个3可以合成一个6, 然后两个6合成12…… 每次整个棋盘可以往上下左右4个方向之一移动。移动的结果，是让数字窜动一个格子（而不是如2048,一直到某个边界的底部），并在移动方向的反方向边界上，随机添加一个新的数字。

在这篇文章中，我们尝试使用Python和Javascript，编写一个自动进行3+3游戏的自动机（Saechsli，源码可以从github获取）。使用这个程序并不能保证一定能获得很高的分数，故本文作为参考，着重介绍这个问题背后的各种技术方案：这种思路，同样也可以用于其他类型的网页游戏或应用。

demo

2 要解决的问题和方案

目标是设计一个3+3游戏的自动机。这里牵扯到几个基本问题：

如何得知任何时候的棋盘状态，和下一步将要放置的数字；
如何根据上一步获得的信息，分析下一步最佳的移动方向；
如何将决定的移动方向，输入给棋盘，进行实际移动。

解决这几个问题需要的技术有：

和游戏代码进行交互的脚本，其任务是：
1. 读取浏览器中的变量，获得当前的棋盘状态；
2. 将棋盘状态和下一步的数字，提交给分析模块，获得下一步移动方向的指示；
3. 将移动指示通过模拟键盘操作的方式，输入给棋盘，进行移动。
根据任何一个棋盘状态和下一步的数字，进行分析和决策的模块。

2.1 浏览器交互

分析过3+3游戏的JavaScript代码后，可以发现，运行中的代码会在浏览器中暴露一个game对象，从中可以快速获取我们需要的信息。我们只需要在网页的运行环境中添加自定义的代码，就可以完成对游戏状态的访问和控制。

具体实现这种控制的方式，有一种比较简单的方案：用户脚本。

浏览器需要事先安装Greasemonkey或者Tampermonkey等插件。这些插件允许用户导入安装一些脚本，将之注入到网页中，就能做到对特定网页的控制和修改了。这些导入的脚本，就是用户脚本（UserScript）。

这种方案，相比于一个完整的浏览器插件而言，具有开发简单、迅速的优点。

2.2 决策模块

根据棋盘状态和下一步的数字，进行决策，是一个很复杂的问题。

给定每一步的棋盘，第一步可以有最多上下左右4种移动方式。在这4种方式之中，我们最终需要作出一个决定。每次移动之后，在移动方向的反方向对应的边上，最多4个空位之中，会随机出现一个新的数字。具体数字则是确定的：从开局的1开始，1和2交替出现，即第一次移动一定会补充一个1，下一次则是一个2……以此类推。

因此，第二步的移动，就会有最多4×4=16种可能。继续增加一步，第三步相对于第一步就会有最多16×16=256种可能。

本文作者设计的方案，是希望利用计算机的速度优势，在给定某一步的棋盘后，穷举未来若干步中的所有情况，对其进行统计，获得比较有优势的走法。如果我们穷举未来5步，就需要计算16的5次方=1048576（约100万）种可能。使用程序，这应当是能在可以接受的时间内完成的。

2.3 开发方式

决策模块的逻辑比较复杂，而且需要大量的穷举。作者选择使用Python 3编写这方面的逻辑。如果使用Python中的yield，还可以在实现穷举的同时，避免大量的内存占用，这可能是比较重要的考虑，因为我们需要1M的计算。

决策模块需要和浏览器中的脚本进行通信。这就需要在Python中同时实现一个服务器，使用bottle模块可以快速完成这一步。浏览器中的脚本，使用jQuery可以发起请求，将每一步的结果传给决策模块，然后获取决策。

3 实现细节

3.1 决策模块

我们首先叙述决策模块的细节。

3.1.1 游戏规则

为了能分析每一步移动后棋盘的状态，很重要的是要了解3+3的游戏规则。

我们可以将棋盘看成一个4×4的矩阵。棋盘的上下左右4个移动方向，可以通过矩阵的旋转和镜像，化作同一种移动方式。因此这里我们统一研究棋盘向左移动的情况。这个逻辑实现之后，自然可以应用到其他方向的移动中。

棋盘向左移动时，每一行中的数字方块都是只有向左的平移和合并，行与行之间独立。因此我们首先研究每一行的移动规则，这样应用到4行，就得到了棋盘的移动规则。

显然地，我们也应当先不考虑移动后添加数字的情况。这一问题应当在棋盘移动之后处理。

行左移与合并规则

我们通过一些例子观察每一行是如何移动的，其中数字0表示一个空的块，在棋盘上不显示。

移动前:   1    0    0    1    <-- 向左平移
移动后:   1    0    1    0

移动前:   1    2    2    1    <-- 向左平移
移动后:   3    3    0    0

移动前:   6    6    0    2    <-- 向左平移
移动后:   12   0    2    0

经过多次分析、试错和对源码的研究后，可以总结出，每一行实际上是如下方式按照两步移动的：

在每一行中，从左向右，依次寻找、合并符合规则（1和2，或大于2的相同的）两个块。将合并结果放在左侧，右侧当作空位（零）。
对整个一行进行一种向左的平移：自从左向右第一个空位开始的所有块，相对位置不变，向左进行一次平移。

以上面的例子来看，具体就是：

移动前:   1    0    0    1    <-- 向左平移
步骤 1:   1    0    0    1    (没有能合二为一的2个块)
                   |_____|   (这一部分在下一步中向左平移)
步骤 2:   1    0    1         (第一个0开始，右侧的数字全部向左平移一次)
移动后:   1    0    1    0

移动前:   1    2    2    1    <-- 向左平移
步骤 1:   3    0    3    0    (相邻的1和2被合并成3放在左侧，右侧补0)
                   |____|    (标出的3和0向左平移)
步骤 2:   3    3    0
移动后:   3    3    0    0

移动前:   6    6    0    2    <-- 向左平移
步骤 1:   12   0    0    2
步骤 2:   12   0    2
移动后    12   0    2    0

需要注意的是，为了实现后续的矩阵左移规则，我们还需要知道每一行是否实际移动过。我们通过两点来判定：a）如果发生过两个块的合并，这一行一定是移动过； b）在步骤2的平移中，如果平移过程中遇到了不是0的数字，就一定是在移动。

整个矩阵的左移规则，新数字的添加

原则上说，整个矩阵向左平移，就是对每一行应用如上所述的 行左移与合并规则 。

分析3+3的游戏规则，一个矩阵能左移，是有条件的：至少有一行发生了左移，才是整个矩阵发生了左移。如果所有的行都无法左移，这个矩阵在这个方向上就无法移动，也不会被添加新数字，例如：

如果矩阵发生了左移，则游戏会在最右一列上的一个或多个空位中，随机选取一个位置，添加新的数字。例如：

左移前: 1   1   0   0
       3   2   2   1
       2   1   0   0
       1   1   1   1

左移后: 1   1   0   0(?)    (虽然这一行没有发生移动，但也可能被添加数字）
       3   2   3   0(?)
       3   0   0   0(?)
       1   1   1   1

新的数字会被随机添加在标记了(?)的3个位置之一。

3.1.2 穷举各种移动方式

我们定义一个类，叫做GameGrid，作用是储存一个给定的棋盘状态和下一步将要添加的数字，然后提供一个enumerateUserMoveResults的方法，用来列出从给定状态向某个方向移动一次后所有可能出现的新棋盘状态：

def enumerateUserMoveResults(self, direction):
    # 将存储的矩阵，根据给定的方向`direction`，旋转成向左移动的状态
    matrix = self.__getRotationNormalizedMatrix(self.state, direction)
    shiftable = False
    for each in matrix: # 依次对矩阵的每一行进行左移
        _, shifted = shift4(each) # 我们要记录下矩阵中每一行是否真的移动了
        shiftable = shiftable or shifted

    if not shiftable: # 如果矩阵不能移动，那么结果是0, 没有新的棋盘状态
        yield from ()
        return

    for i in range(0, 4): # 遍历左移后矩阵的每一行
        if matrix[i][-1] < 0:
            # shift4()函数（行左移函数）会将每行左移后最右侧新得到的0
            # 用-1代替。我们将这个-1依次用新增加的值代替，然后yield这个新的矩阵，
            # 就返回了一种新的、可能的棋盘状态。
            matrix[i][-1] = self.__next
            yield self.__reverseRotationNormalizedMatrix(matrix, direction) # yield之前，要先将矩阵转换为原始方向
            matrix[i][-1] = 0 # 恢复当前枚举的这一行的结尾为0

这样，初始化一个GameGrid，就可以通过调用enumerateUserMoveResults，获得一次平移后，新棋盘的全部可能状态（最多4种）。

接下来，我们定义一个evaluateMovement函数，目的是根据开始的棋盘输入和一个初始的移动方向，根据限定条件（最多推断的步数maxcount），对走maxcount步后棋盘的状态进行穷举。这个函数会递归调用自己，直到步数达到限定条件为止。

在这个递归的过程中，我们关心两个参数：

棋盘上能出现的最大数字块；
整个过程中能见到的自由度。

能出现的最大数字块，表明这种移动方式上是否能尽快合并相同的数字。能见到的自由度，表明在某个移动方式之后可能死局的可能性——显然，自由度越高，大概越不容易死局。这样，坚持不死局，就容易获得更高的分数。

def evaluateMovement(state, direction, movementCount=1, maxcount=3):
    retMax = max([max(l) for l in state])
    retFreedomGrade = 1 # 本级的自由度，本次移动本身是1种可能

    if movementCount <= maxcount:
        grid = GameGrid(state, movementCount)
        totalNextFreedomGrades = 0 # 下次移动的全部自由度数量
        for possibility in grid.enumerateUserMoveResults(direction):
            for nextMove in [LEFT, RIGHT, TOP, BOTTOM]:
                # 对下一步的上下左右四个方向进行枚举，注意这是递归调用
                results = evaluateMovement(
                    possibility, # 本局棋盘
                    nextMove,    # 移动方向
                    movementCount+1, # 移动步数计数
                    maxcount     # 最大步数限制
                )
                retMax = max(retMax, results[0]) # 记录最大数字块
                totalNextFreedomGrades += results[1] # 记录自由度数量    
        retFreedomGrade *= totalNextFreedomGrades

    return (retMax, retFreedomGrade)

至此，我们已经有了根据给定棋盘状态进行自动推断，并对各种推断结果给出评估参数的程序。

3.1.3 决策

这一步的目的，是根据在 3.1.2 中得到的、对4种潜在的移动方式进行的评估结果，作出决定，告诉浏览器脚本下一步的移动方向。

由于有多个评估参数，决策过程可以是比较复杂的，甚至可以做到使用AI进行辅助。我们在这里则暂不进行这样复杂的工作，仅仅应用两条规则：

最大数字块优先。如果有一个移动方向能得到更大的数字块，就用那个方向。
最多自由度优先。在各种移动方向能得到的最大数字块相同的情况下，比较能得到的最大自由度，选择最大的那个。

在后续的实际测试中，可以发现自动机根据这两条规则进行的移动和人类的方式不同。因为人类为了获得高分，倾向于将最大的数字块放在棋盘的角落，稍微小些的按照位置排序，以便“进位”。自动机的结果，却是不断调整最大数字块的位置，将之在棋盘上浮动，合并出现的其他块。这种方式虽然反直觉，但偶尔也能获得较高的得分，说明以上规则是可行的，而且似乎可以添加其他规则，诱导自动机偏好将最大数字块放在角落。

3.2 浏览器脚本

我们需要一个将浏览器上显示的游戏状态发送给决策模块，并执行其决策的程序。

由于3+3本身就是基于浏览器的程序，使用一样的技术，直接用JavaScript注入到浏览器的游戏环境中，就是一种简单方便的方案。

这种方式称为用户脚本，我们需要使用Tampermonkey或者Greasemonkey这样的浏览器插件加载脚本，但脚本本身编写起来就非常简单了。

在脚本开头，使用一种特殊的注释声明这个脚本的用途：

// ==UserScript==
// @name          3+3 game bot
// @namespace     http://github.com/neoatlantis/saechsli
// @description   Experimental study of automated 3+3 gaming.
//
// @require https://code.jquery.com/jquery-2.1.4.min.js
// @include       https://d29zfk7accxxr5.cloudfront.net/games/game-156/data/*
// @grant         unsafeWindow
// ==/UserScript==

我们使用@require要求这个脚本需要包含一个jQuery，用来实现和后台的AJAX通讯；脚本的应用范围，在@include后面给出，就是3+3的游戏实际所在的网址。最后，我们要求使用unsafeWindow特权，这是用来访问游戏页面的窗口内容所需要的。

获得游戏棋盘的当前状态 有一个很简单的方法，在unsafeWindow.game.grid这个数组中本身就存储了游戏的状态。这个数组是一维的，16个元素分别表示从左上角横向然后向下依次排列的16个数字，其中空位用0表示。

控制游戏棋盘 的方法也很简单。unsafeWindow.game.controller.buttons对象中有四个元素： left, right, up, down，每个都带有一个trigger方法。在trigger方法中传入"keydown"，就可以模拟触发相应的动作。

完整的用户脚本，可以从github找到: https://github.com/neoatlantis/saechsli/blob/master/userscript.js 这里就不再详细讨论了。

NeoAtlantis应用科学和神秘学实验室
NeoAtlantis Laboratory of Applied Science and Occultism
Labor der angewandten Wissenschaft und des Okkultismus NeoAtlantis

Saechsli: 3+3小游戏自动机
发表于 2017 年 11 月 25 日

1 前言

2 要解决的问题和方案

2.1 浏览器交互

2.2 决策模块

2.3 开发方式

3 实现细节

3.1 决策模块

3.1.1 游戏规则

行左移与合并规则

整个矩阵的左移规则，新数字的添加

3.1.2 穷举各种移动方式

3.1.3 决策

3.2 浏览器脚本

NeoAtlantis应用科学和神秘学实验室 NeoAtlantis Laboratory of Applied Science and Occultism Labor der angewandten Wissenschaft und des Okkultismus NeoAtlantis

Saechsli: 3+3小游戏自动机 发表于 2017 年 11 月 25 日

1 前言

2 要解决的问题和方案

2.1 浏览器交互

2.2 决策模块

2.3 开发方式

3 实现细节

3.1 决策模块

3.1.1 游戏规则

行左移与合并规则

整个矩阵的左移规则，新数字的添加

3.1.2 穷举各种移动方式

3.1.3 决策

3.2 浏览器脚本

NeoAtlantis应用科学和神秘学实验室
NeoAtlantis Laboratory of Applied Science and Occultism
Labor der angewandten Wissenschaft und des Okkultismus NeoAtlantis

Saechsli: 3+3小游戏自动机
发表于 2017 年 11 月 25 日