之前看到Coding 4 Fun的博客，使用Qt+BlueStack实现自动天天爱消除。哇塞，好牛逼！写程序来开挂，这么高科技的玩法勾的我跃跃欲试了。

考察一下技术方案，原文提到的Qt+BlueStack我都没有接触过，还是首选Python来的比较快。游戏选择另外一款曾经火热过的小游戏1024。其实早在1024还火的时期，就有人做出了直接写在JS中的AI来自动玩游戏并获得高分。但是这里我希望也是做成基于图形识别的自动机框架。这样以后遇到别的游戏，图形识别和控制指令部分也能借用相同的代码。

第一步 图形抓取

搜索一番发现可以使用Pillow的ImageGrab。但是Windows使用正常，mac却需要使用一个修改过的版本，下载以后直接导入。

import ImageGrab
# initial graphic settings
BOX = (55,545,1055,1545)
WIDTH = 214
INTERVAL = 28
# position checking
im_t = np.asarray(ImageGrab.grab(BOX))
imshow(im_t)
# get origin_x, origin_y
origin_x, origin_y = getOrigin(im_t)
print 'origin =', origin_x, origin_y
origin = 27 23

在屏幕上合适的位置取一个区域BOX，作为每次取屏的区域。这里不用特别准确，保证游戏区都在其中就可以了。getOrigin方法取得游戏区的准确位置，帮助校准，后面定位每个块的位置就方便了。我提前测量了游戏区域的尺寸数据，得知每个块的边长大概是214px，块间距是28px。

第二步 数字识别

获得图形以后怎么识别里面的数字呢。简单想想，事先把1，2，4等的对应图形都存起来。识别的时候只需要一一比对就可以了。

但是实力不济，1024以后的图形就没法获得了。。。再观察发现貌似新出的块只可能是1，2，4。如果自己维护一个棋盘，每一步之后的状态自己计算，那就只需要识别随机出现的新块在哪个位置，数字是1还是2还是4就可以了。

但是眼残，貌似之前测量的有误差，实验的时候发现取的块不能完全重合，也就是不能用像素值全等来判断异同。。。估计有一两个像素的误差，想来也是人之常情。。。特别是图形特别复杂的时候，难以获得准备定位。第一考虑是用图形匹配算法，比如OpenCV的cv2.matchTemplate()。但是之前没有用过，不知道开销如何，我这里的问题实质又非常简单，无非是偏移了一点点位置。后来做了个实验，简单的把2D图形拉成1D链表，然后两个链表做PearsonCorrelation。结果效果非常好，阳性值都是0.99，阴性值0.3的样子。再后来为了提高速度，只取块中间50*50的区域，识别这几个简单图形仍然又快又好。

第三步 模拟游戏

既然是自动机，我们需要自己维护一个游戏模型。棋盘用一个4*4的矩阵就可以表达。

# initial board
board = np.zeros((4,4), dtype=np.int)
for x in range(4):
    for y in range(4):
        board[x][y] = getNumber(im_t,x,y) or 0
print board
[[0 0 0 0]
 [0 0 0 1]
 [0 0 0 1]
 [0 0 0 0]]

游戏允许做上下左右四种操作，所有的块都会按照方向移动到底，相同数字的块合并。编码的时候我只实现了moveLeft，而其他三种操控可以通过矩阵旋转和moveLeft来间接实现。比如moveUp,我们只需要逆时针旋转90度，做moveLeft，再旋转270即可。

def moveRight(board):
    board = np.fliplr(board)
    moveLeft(board)
    board = np.fliplr(board)
def moveUp(board):
    board = np.rot90 (board)
    moveLeft(board)
    board = np.rot90 (board,3)
def moveDown(board):
    board = np.rot90 (board,3)
    moveLeft(board)
    board = np.rot90 (board)

玩家完成一次操作之后会随机在空位生成一个新块，这时候我们在棋盘对应为0的所有位置进行识别，找到新块，并赋值在我们的矩阵中。

Gamve Over的判定：

获取新块之后，如果棋盘中没有0，则可以进行胜负判定。如果所有块的四个相邻块都不能与其合并，则判定游戏结束。

第四步 AI算法

有了一套游戏机制以后可以考虑如何做AI来获取高分了。对抗游戏常用的MiniMax Algorithm这里并不适用。那就先试试普通的DFS。每一步都让程序去试试，每一步的每下一步也让程序去试试。如果试5步，就是对5步以后的4的5次方1024种不同结果进行了评估。评估就是给结果打打分，一般叫score function，优化问题中叫heuristic funciton。

    if np.array_equal(lastBoard,board):
        return -1000
    rst = 0
    rst += 5 * len(filter(lambda x: x ==0, board.flatten()))
    rst += 10 * math.log(maxValue(board),2)
    temp = np.log2(board+1)
    for x in range(4):
        for y in range(4):
            if y+1 < 4:
                rst -= abs(temp[x][y] - temp[x][y+1])
            if x+1 < 4:
                rst -= abs(temp[x][y] - temp[x+1][y])
            rst += temp[x][y]*temp[x][y]
    return rst

这里有几个简单的考虑，一是空块越多越好（鼓励优先合并），二是最大块越大越好（毕竟想突破1024，2048嘛），三是相邻块的差越小越好（这样以后相邻块有更大合并的可能）。最后算出来的得分越高，就越是我们希望得到的结果。

但是游戏中还有一大变数，使得这个理想算法不一定那么管用。每一步以后，会随机产生一个新块。而这个变量大大增加了计算的复杂度。尤其在游戏初期，每一步以后就不只是4种可能，而是数十种可能，如果要基于概率来算分，DFS这样的就不用考虑了。。。最后实际中，为了方便快捷（懒），我选择了只考虑一步。。。

在notebook的最后，我给出了virtual game的运行代码。

第五步 与游戏交互

AI帮忙算出了每一步走哪个方向好，我们要把这个决定用指令发送给游戏。

Windows下用ctypes.windll.user32.SendInput很简单，mac上又麻烦了一些。首先搜到的居然是让我用PyObjC调用ObjC来生成按键事件。。。太绕了，打死不从，我们按键的频率又不高。后来找到了用Apple Script的方法，简单直观了不少。

def pressKey(key):
    left = 'osascript -e \'tell application "System Events" to key code 123\''
    right = 'osascript -e \'tell application "System Events" to key code 124\''
    up = 'osascript -e \'tell application "System Events" to key code 126\''
    down = 'osascript -e \'tell application "System Events" to key code 125\''
    if key == 0:
        os.system(left)
    if key == 1:
        os.system(right)
    if key == 2:
        os.system(up)
    if key == 3:
        os.system(down)

第六步 测试

终于完成了整个流程，摆好浏览器的位置，$python 1024.py，我们来跑一跑。

流泪！！！毕竟亲生的，有点bug也懒得搞了。。。

github地址