用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, 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上,如下所示:

“用python编写1024游戏(4)”的4个回复

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据