博弈问题的搜索解法

发表于 | 分类于 ，

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
f(局面 x) --> 面对局面x，胜利or失败?
{
    边界判断
        返回边界结果

    for (所有走法k)
    {
        走一步k-->局面y
        res = f(y)
        # 走法k会导致对方失败，说明是必胜点
        if res is 失败
            return 胜利
        回退局面-->局面x
    }
    # 所有的走法都是对方胜，说明是必败点
    return 失败
}

例如使用搜索求巴什博弈:

1
2
3
4
5
6
7
8
9
10
def searchBashGame(n, m):
    # 边界处理
    if n == 0:
        return False
    # 尝试所有的走法
    for x in range(1, m+1):
        res = searchBashGame(n-x, m)
        if res is False:
            return True
    return False

但是一旦n稍大，搜索算法就无能为力了。这是因为在搜索算法执行时有大量重复计算，因此我们可以使用打表的方式来优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
f(局面 x, 哈希表 table) --> 面对局面x，胜利or失败?
{
    # 注意这里
    if x in table:
        return table[x]
    边界判断
        返回边界结果

    for (所有走法k)
    {
        走一步k-->局面y
        res = f(y)
        # 走法k会导致对方失败，说明是必胜点
        if res is 失败
            table[x] = 胜利
            return 胜利
        回退局面-->局面x
    }
    # 所有的走法都是对方胜，说明是必败点
    table[x] = 失败
    return 失败
}