小游戏1024自动机与AI

Wu Rui bio photo By Wu Rui Comment

之前看到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

Model-View-Controller

在屏幕上合适的位置取一个区域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的区域,识别这几个简单图形仍然又快又好。

Model-View-Controller

第三步 模拟游戏

既然是自动机,我们需要自己维护一个游戏模型。棋盘用一个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,我们来跑一跑。

Model-View-Controller

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

github地址

comments powered by Disqus