人工智能技术导论 -- 博弈树搜索
我在之前整理过一篇博客关于博弈论和纳什均衡的几个例子
https://www.cnblogs.com/wkfvawl/p/11725263.html
这里来介绍博弈树搜索.
一, 博弈树的概念
在博弈过程中, 任何一方都希望自己取得胜利. 因此, 当某一方当前有多个行动方案可供选择时, 他总是挑选对自己最为有利而对对方最为不利的那个行动方案. 此时, 如果我们站在 A 方的立场上, 则可供 A 方选择的若干行动方案之间是 "或" 关系, 因为主动权操在 A 方手里, 他或者选择这个行动方案, 或者选择另一个行动方案, 完全由 A 方自己决定. 当 A 方选取任一方案走了一步后, B 方也有若干个可供选择的行动方案, 此时这些行动方案对 A 方来说它们之间则是 "与" 关系, 因为这时主动权操在 B 方手里, 这些可供选择的行动方案中的任何一个都可能被 B 方选中, A 方必须应付每一种情况的发生.
这样, 如果站在某一方(如 A 方, 即在 A 要取胜的意义下), 把上述博弈过程用图表示出来, 则得到的是一棵 "与或树". 描述博弈过程的与或树称为博弈树, 它有如下特点:
(1) 博弈的初始格局是初始节点.
(2) 在博弈树中, "或" 节点和 "与" 节点是逐层交替出现的. 自己一方扩展的节点之间是 "或" 关系, 对方扩展的节点之间是 "与" 关系. 双方轮流地扩展节点.
(3) 所有自己一方获胜的终局都是本原问题, 相应的节点是可解节点; 所有使对方获胜的终局都是不可解节点.
二, 极小极大值分析法
在二人博弈问题中, 为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案, 就需要对当前的情况以及将要发生的情况进行分析, 从中选出最优的走步. 最常使用的分析方法是极小极大分析法. 其基本思想是:
(1) 设博弈的双方中一方为 A, 另一方为 B. 然后为其中的一方 (例如 A) 寻找一个最优行动方案.
(2) 为了找到当前的最优行动方案, 需要对各个可能的方案所产生的后果进行比较. 具体地说, 就是要考虑每一方案实施后对方可能采取的所有行动, 并计算可能的得分.
(3) 为计算得分, 需要根据问题的特性信息定义一个估价函数, 用来估算当前博弈树端节点的得分. 此时估算出来的得分称为静态估值.
(4) 当端节点的估值计算出来后, 再推算出父节点的得分, 推算的方法是: 对 "或" 节点, 选其子节点中一个最大的得分作为父节点的得分, 这是为了使自己在可供选择的方案中选一个对自己最有利的方案; 对 "与" 节点, 选其子节点中一个最小的得分作为父节点的得分, 这是为了立足于最坏的情况. 这样计算出的父节点的得分称为倒推值.
(5) 如果一个行动方案能获得较大的倒推值, 则它就是当前最好的行动方案.
倒推值的计算
在博弈问题中, 每一个格局可供选择的行动方案都有很多, 因此会生成十分庞大的博弈树. 据统计, 西洋跳棋完整的博弈树约有 1040 个节点. 试图利用完整的博弈树来进行极小极大分析是困难的. 可行的办法是只生成一定深度的博弈树, 然后进行极小极大分析, 找出当前最好的行动方案. 在此之后, 再在已选定的分支上扩展一定深度, 再选最好的行动方案. 如此进行下去, 直到取得胜败的结果为止. 至于每次生成博弈树的深度, 当然是越大越好, 但由于受到计算机存储空间的限制, 只好根据实际情况而定.
例 一字棋游戏. 设有如图 (a) 所示的九个空格, 由 A, B 二人对弈, 轮到谁走棋谁就往空格上放一只自己的棋子, 谁先使自己的棋子构成 "三子成一线" 谁就取得了胜利.
一字棋
设 A 的棋子用 "a" 表示, B 的棋子用 "b" 表示. 为了不致于生成太大的博弈树, 假设每次仅扩展两层. 估价函数定义如下:
设棋局为 P, 估价函数为 e(P).
(1) 若 P 是 A 必胜的棋局, 则 e(P)=+∞.
(2) 若 P 是 B 必胜的棋局, 则 e(P)=-∞.
(3) 若 P 是胜负未定的棋局, 则 e(P)=e(+P)-e(-P)
其中 e(+P)表示棋局 P 上有可能使 a 成为三子成一线的数目;
e(-P)表示棋局 P 上有可能使 b 成为三子成一线的数目.
例如, 对于图 (b) 所示的棋局, 则
按照棋盘上红色连线安放棋子 a 使得三子成一线, 共 6 条连线.
按照棋盘上蓝色连线安放棋子 b 使得三子成一线, 共 4 条连线.
e(P)=6-4=2
另外, 我们假定具有对称性的两个棋局算作一个棋局. 还假定 A 先走棋, 我们站在 A 的立场上.
下图给出了 A 的第一着走棋生成的博弈树. 图中节点旁的数字分别表示相应节点的静态估值或倒推值. 由图可以看出, 对于 A 来说最好的一着棋是 S3, 因为 S3 比 S1 和 S2 有较大的倒推值.
一字棋极小极大搜索
在 A 走 S3 这一着棋后, B 的最优选择是 S4, 因为这一着棋的静态估值较小, 对 A 不利. 不管 B 选择 S4 或 S5,A 都要再次运用极小极大分析法产生深度为 2 的博弈树, 以决定下一步应该如何走棋, 其过程与上面类似, 不再重复.
三,α-β剪枝技术
上述的极小极大分析法, 实际是先生成一棵博弈树, 然后再计算其倒推值. 这样做的缺点是效率较低. 于是, 人们又在极小极大分析法的基础上, 提出了α-β剪枝技术.
这一技术的基本思想是, 边生成博弈树边计算评估各节点的倒推值, 并且根据评估出的倒推值范围, 及时停止扩展那些已无必要再扩展的子节点, 即相当于剪去了博弈树上的一些分枝, 从而节约了机器开销, 提高了搜索效率. 具体的剪枝方法如下:
(1) 对于一个与节点 MIN, 若能估计出其倒推值的上确界β, 并且这个β值不大于 MIN 的父节点 (一定是或节点) 的估计倒推值的下确界α, 即α≥β, 则就不必再扩展该 MIN 节点的其余子节点了(因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了). 这一过程称为α剪枝.
(2) 对于一个或节点 MAX, 若能估计出其倒推值的下确界α, 并且这个α值不小于 MAX 的父节点 (一定是与节点) 的估计倒推值的上确界β, 即α≥β, 则就不必再扩展该 MAX 节点的其余子节点了(因为这些节点的估值对 MAX 父节点的倒推值已无任何影响了). 这一过程称为β剪枝.
认真品味上面的两句规则, 下面给出一个具体的 α-β剪枝的实例.
使用 ScreenToGif 截的 PPT 图, 关于 ScreenToGif 的使用说明参见
https://www.cnblogs.com/wkfvawl/p/11625823.html
这里来说一下剪枝过程, F 下的第一个节点是 K, 其值为 4, 这时作为 MIN 节点的 F 上确界β为 4,F 下的第二个节点 L 和第三个节点 M 的值都拿来比较, 但都大于 4, 所以 F 节点 MIN 值还是 4. 这时 MAX 节点 C 的下确界α为 4, 并将α传递给 MIN 节点 G.
G 下的第一个节点为 1, 此时作为 MIN 节点 G 的上确界β为 1, 留意到此时 G 的 α=4 ＞ β, 所以无需再探索 G 的剩余子节点, 把未探索的子节点通过α剪枝剪掉.
这里 C 的父节点 A 是一个 MIN 节点, A 的估计上确界β便是 4. 接着我们对 A 的右子树进行查找, 并将β传递下去.
对于 MIN 节点 H, 其下的第一个子节点 P 值为 5, 大于 4, 因而接着比较第二个子节点 Q 值为 8, 也大于 4, 因而 H 节点 MIN 值的上确界β便是 5,P 的父节点 D 是一个 MAX 节点, 因而此时 D 的下确界α值为 5.
由于 D 的父节点 A 是一个 MIN 节点, A 的估计倒推值的上确界β为 4, 小于 D 的下确界 5, 因而就不必去扩展 MAX 节点 D 的其他子节点了, 进行了β剪枝.
这是就可以确定节点 A 的父亲节点 S0, 其为 MAX 节点的下确界α为 4, 这就对 S0 右子树进行查找. 并直接将下确解α沿着 S0->B->E->I 传递, 深入到 I.
对于 MIN 节点 I, 其下的第一个子节点 R 值为 0, 这时作为 MIN 节点 I 的上确界β为 0, 留意到此时 I 的 α=4 ＞ β, 所以无需再探索 I 的剩余子节点, 把未探索的子节点通过α剪枝剪掉.
I 的父节点是一个 MAX 节点, 更新其父节点 E 的下确界α为 0. 将 E 的α传递给 J.
这时对于 MIN 节点 J, 其下的第一个子节点 S 值为 - 6, 这时作为 MIN 节点 I 的上确界β为 - 6, 留意到此时 J 的 α=0 ＞ β, 所以无需再探索 J 的剩余子节点, 把未探索的子节点通过α剪枝剪掉.
这时确定了 E,E 的父亲节点 B 是一个 MIN 节点, 通过 E 其上确界β更新为 0, 但 E 的父亲节点的α为 4,α=4 ＞ β, 所以无需再探索 B 的剩余子节点, 把未探索的子节点通过α剪枝剪掉.
最终确定 S0, 搜索完成.
关于α-β剪枝的过程, 还想要了解一个, 可以参考这篇博客
https://www.7forz.com/3211/
来源: https://www.cnblogs.com/wkfvawl/p/12066647.html