用python编写1024游戏(4)

续上一篇blog，我们来用python实现ai版1024游戏。

---

如前文所述，关键在于 获得最优滑动方向 这一步。整理一下思路：

def 获得最优滑动方向:
    for 方向 in 当前有意义的滑动方向:
        执行滑动
        方向.评估值 = 评估当前局面
    return 最大评估值的方向

此方法会调用一个用递归实现的深度优先搜索：

def 评估当前局面:
    if 无需继续搜索:
        return 当前局面的评估函数值

    累计值 = 0
    for 随机数字 in 当前剩余的空格: # 注意循环嵌套的顺序
        for 方向 in 当前有意义的滑动方向:
            执行滑动，局面改变
            累计值 += 评估当前局面
    return 累计值

直接将其翻译成python代码：

def evaluate(board, depth):
    if depth <= 0 \
        or (board.num_of_empty == 0 and not combinable(board)):
        return evaluation_func(board)

    sum_of_ev = 0
    for x, y in get_left_empty(board):
        for p in [2, 4]:
            board.set(x, y, p)
            for swap_dir in get_vaild_dirs(board):
                board_copy = board.copy()
                _, moved = apply_swap(board_copy, swap_dir)
                if moved:
                    ev = evaluate(board_copy, depth - 1)
                    if p == 2:  
                        sum_of_ev += ev * 0.95
                    else:
                        sum_of_ev += ev * 0.05
            board.set(x 
antibiotika-online.com
 , y, 0)
    return sum_of_ev

def best_dir(board):
    max_value = -sys.maxint
    best = SwapDir.DOWN
    for swap_dir in get_vaild_dirs(board):
        board_copy = board.copy()
        _, moved = apply_swap(board_copy, swap_dir)
        if moved:
            cur_value = evaluate(board_copy, depth=2)
            if cur_value >= max_value:
                max_value = cur_value
                best = swap_dir
    return best

其中 evaluation_func 是关键。如何定义这个函数呢？前文提到：

H(x) = aA(x) + bB(x) + cC(x) + ...

其中 H(x) 是评估函数。我们要思考究竟是什么因素影响了当前的局面，什么才算对自己有利。

从这里和这里的讨论可以总结出以下两点：

• 最大值尽量靠在边角
• 尽可能地沿着某个方向呈等比数列排列

于是我们可以这样设计：

def evaluation_func(board):
    o = order_weight(board)
    c = corner(board)*10
    m = monotonicity(board)
    e = empty_weight(board)*10
    x = max_value_weight(board)
    return o + m + c + e + x

各种因子的实现为：

---

def corner(board): # 最大值是否在角落
    if board.get(0, 0) == board.max_value:
        return board.get(0, 0)
    else:
        return 0

---

POS_WEIGHT_TEMPLATE = [[4,3,2,1], # 位置权重
                        [3,2,1,1],
                        [2,1,1,1],
                        [1,1,1,1]]
def order_weight(board): # 根据权重矩阵计算当前局面的“方向性”
    global POS_WEIGHT_TEMPLATE
    m = 0
    for i in range(board.length):
        for j in range(board.length):
            if board.get(i, j) != 0:
                m += board.get(i,j)*POS_WEIGHT_TEMPLATE[i][j]
    return m 

---

def monotonicity(board): # 尽量使第一行按顺序排列
    value = 0
    for i in range(board.length - 1):
        if not board.get(0, i) > board.get(0, i + 1):
            return 0
        else:
            value += (board.length - i)*board.get(0, i)
    return value + board.get(0, board.length -1)

---

def empty_weight(board): # 空格数
    return board.num_of_empty

def max_value_weight(board): # 尽量凑最大值
    return board.max_value

---

递归深度为2时，运行一次大概要4-5min。当我设置递归深度为1时，进行了n次实验(n>50)，胜率大概在50%左右。跟这里提及的算法效果比起来简直一个天上一个地下。

如何设计更好的评估函数呢？如何制定更完善的搜索策略呢？这有点超出我目前的能力范围了。。。

完整代码我放到Gist上，如下所示：