算法提高：博弈论 ｜ 最小最大问题

博弈论是二人或多人在平等的对局中各自利用对方的策略变换自己的对抗策略,达到取胜目标的理论。博弈论是研究互动决策的理论。博弈可以分析自己与对手的利弊关系,从而确立自己在博弈中的优势,因此有不少博弈理论,可以帮助对弈者分析局势,从而采取相应策略,最终达到取胜的目的。

最小最大问题

最小最大问题( minimax ):用于确定计算机玩家在诸如井字游戏、跳棋、奥赛罗和国际象棋中的哪一步。这类游戏被称为完美信息游戏,因为它可以看到所有可能的动作。拼字游戏并不是一个完美信息的游戏,因为你看不到对手的手,所以无法预测对手的动作。

可以把这个算法想象成人类的思维过程:如果我做这个动作,那么我的对手只能做两个动作,每个动作都会让我赢。所以这是正确的选择。

用博弈树数据结构表示井字游戏如图 13-1 所示。

■ 图  用博弈树数据结构表示井字游戏

如果你认为所谓最小最大就是穷举过程中找到的最差走法和最佳走法那就错了,既然是对立的概念,当然是两个对象,这里的最小最大是当前轮到 AI 走了, AI 进行穷举并选择一条对于 AI 来说最佳而对于人来说最差的走法,但是再考虑一下,机器也是有限的,对于象棋这样棋盘较大的游戏,穷举完博弈树在当前科技下不可能,因此我们的最小最大算法需要一个深度,即向前走几步,计算机就能在这个指定的比较小的整数下完成对博弈树的穷举。

当遍历若干树枝后不可能就结束了,如果在游戏没有结束的情况下我们还需要一个评价启发函数,这个函数用于判断当前策略的价值,如果使用某走法能赢,就返回一个大的正数;如果这种走法会输,就返回一个大的负值;如果走法会产生和局,就返回一个 0 左右的数;如果由于当前博弈树深度没办法判断局面,那么评价函数就会返回一个启发值。

参考程序：