xhSong's Blog

前几天看summer师弟玩Selenium感觉挺有意思。便拿着时间风靡一时的游戏“2048”来练手，写了个简单的 AI。甚是欢乐！

Selenium

啥是selenimu，简单的说——Selenium也是一个用于Web应用程序测试的工具。Selenium测试直接运行在浏览器中，就像真正的用户在操作一样。支持的浏览器包括IE、Mozilla Firefox、Mozilla Suite等(来自 http://www.51testing.com/zhuanti/selenium.html)。

selenimu这里就不多介绍了，细节请看 selenium 的 python api 文档

2048策略

2048这个游戏地球人都知道就不介绍了。主要介绍下我的AI。我的AI对于每一个方向的评估有三个方面

1. 移动导致合并的得分 score：这个就是游戏本身定义的得分，如 4和4合并得8分，128和128合并的256分
2. 移动后每一行每一列的单调性 monotone：对于每一行（每一列）如果 line[i] <= line[i+1]则mon+= line[i]+line[i+1]否则，mon-=line[i]+line[i+1]，monotone=sum(abs(mon))
3. 移动后相邻块值相同的情况 adjoin：任意两个相邻块的值相同，如cells[i][j]=cells[i+1][j]，则 adjoin+=cells[i][j]

最后的估值 estimation = score + monotone * 0.3 + adjoin。对于上下左右四个方向取estimation最大的方向操作

这种方法还可以，运气好的话，可以得到2048

程序结构

程序的源代码如下：

from selenium import webdriver
from selenium.webdriver.common.keys import Keys
import os
import time

size = 4

class Estimator:
    def estimate(self, precells, postcells, action, score):
        for i in range(size):
            score += self.__estimate_line([postcells[i][j] for j in range(size)])
            score += self.__estimate_line([postcells[j][i] for j in range(size)])
        return score

    def __estimate_line(self, line):
        monotone, adjoin = 0, 0
        for i in range(size - 1):
            if line[i + 1] > line[i]:
                monotone += line[i + 1] + line[i]
            else:
                monotone -= line[i + 1] + line[i]
            if line[i + 1] == line[i]:
                adjoin += line[i]
        return abs(monotone) * .3 + adjoin

class Auto2048:
    def __init__(self, url, estimator):
        self.browser = webdriver.Firefox()
        self.browser.get(url)
        self.estimator = estimator

    def get_cells(self):
        tiles = self.browser.find_elements_by_class_name('tile')
        self.cells = [[0 for i in range(4)] for i in range(4)]

        for tile in tiles:
            attr = tile.get_attribute('class').split()
            value = int(attr[1].split('-')[1])
            x = int(attr[2].split('-')[3]) - 1
            y = int(attr[2].split('-')[2]) - 1
            self.cells[x][y] = value

    def AI(self):

        self.get_cells()
        self.Print(self.cells)

        action, actionname = '', ''
        moveable = False
        
        strategies = [    {'fun': self.try_up, 'action': Keys.UP, 'name': 'Up'}, 
                        {'fun': self.try_down, 'action': Keys.DOWN, 'name': 'Down'}, 
                        {'fun': self.try_left, 'action': Keys.LEFT, 'name': 'Left'}, 
                        {'fun': self.try_right, 'action': Keys.RIGHT, 'name': 'Right'}]
        for strategy in strategies:
            result = strategy['fun']()
            estimation = self.estimator.estimate(self.cells, result['cells'], strategy['name'], result['score'])
            if result['moveable'] and (moveable == False or max_estimation < estimation):
                action = strategy['action']
                max_estimation = estimation
                moveable = True
                actionname = strategy['name']

        if not moveable:
            return False

        self.browser.find_element_by_class_name('grid-container').send_keys(action)
        print 'Action: ', actionname
        return True

    def move_left(self, cells):
        moveable = False
        score = 0
        for x in range(size):
            pre = 0
            for y in range(size):
                if cells[x][y]:
                    cells[x][pre] = cells[x][y]
                    if y != pre:
                        moveable = True
                        cells[x][y] = 0
                    pre += 1
            for y in range(size - 1):
                if cells[x][y] and cells[x][y] == cells[x][y + 1]:
                    cells[x][y] += cells[x][y]
                    score += cells[x][y]
                    cells[x][y + 1] = 0
                    moveable = True
            pre = 0
            for y in range(size):
                if cells[x][y]:
                    cells[x][pre] = cells[x][y]
                    if y != pre:
                        moveable = True
                        cells[x][y] = 0
                    pre += 1
        return {'moveable': moveable, 'score': score, 'cells': cells}
    
    def try_left(self):
        cells = [[self.cells[i][j] for j in range(size)] for i in range(size)]
        return self.move_left(cells)

    def try_right(self):
        cells = [[self.cells[i][size - 1 - j] for j in range(size)] for i in range(size)]
        result = self.move_left(cells)
        result['cells'] = [[result['cells'][i][size - 1 - j] for j in range(size)] for i in range(size)]
        return result

    def try_up(self):
        cells = [[self.cells[j][i] for j in range(size)] for i in range(size)]
        result = self.move_left(cells)
        result['cells'] = [[result['cells'][j][i] for j in range(size)] for i in range(size)]
        return result
    
    def try_down(self):
        cells = [[self.cells[size - 1 - j][i] for j in range(size)] for i in range(size)]
        result = self.move_left(cells)
        result['cells'] = [[result['cells'][j][size - 1 - i] for j in range(size)] for i in range(size)]
        return result

    def __del__(self):
        self.browser.close()

    def Print(self, cells):
        print 
        for x in range(size):
            for y in range(size):
                print '%5d' % cells[x][y], 
            print 

if __name__ == '__main__':
    url = 'file://' + os.path.abspath('2048/index.html')
    # url = "http://gabrielecirulli.github.io/2048/"
    auto2048 = Auto2048(url, Estimator())
    while auto2048.AI():
        time.sleep(0.2)
    time.sleep(10)

源代码中有两个类

主逻辑类 Auto2048

使用 2048的url和估值类(AI逻辑)构造。测试过程中，用 wget 将 "http://gabrielecirulli.github.io/2048/" 的所有页面抓到本地分析（由于不懂js在网页中的工作原理，使用find_elements_by_class_name找当前cells的信息找了好久）

每一次操作调一次AI()，AI() 先获取当前页面的状态保存在 self.cells 中，然后对上下左右四个方向枚举，取估值最大的方向并使用send_keys进行操作。如果能操作则AI()返回True，否则返回False

估值类 Estimator

估值类只要实现 def estimate(self, precells, postcells, action, score): 估值方法即可。其中，precells为操作前状态，postcells为操作后状态，atcion为操作['Left', 'Right', 'Up', 'Down']，score为操作得分。返回值为估值estimation，值越到越好。

虽然我的估值方法运气好的话可以得到2048，但还是很粗糙的。你要有兴趣的话，可以写一个更好的Estimator得到更高的分。

源代码地址 https://github.com/xhSong/auto2048