博弈树的启发式搜索

概述

博弈树是一种基于与或图的启发式搜索算法。博弈主要分为两类，一是机遇性博弈，还有就是完备性博弈。机遇性博弈中参与博弈的玩家之间信息是不完备的，并且博弈中事件的发生具有概率性，日常中大部分的博弈都是机遇性博弈。完备性博弈是指参与博弈的玩家之间都掌握着博弈对手的完整信息，基于已掌握的信息对博弈进程进行推演。完备性博弈是一种理想的博弈，通常出现在棋牌类的游戏中。

对于一种博弈的游戏，参与者可能会有多个。基于与或图的博弈树启发式搜索只能应用于双人完备信息博弈。这种搜索算法也称为Max-Min搜索（极大极小搜索）。

与或图也称为与或树，是一种特殊的树结构。与或树是多叉树，每个节点的类型要么是与节点，要么是或节点。通常可以将与或树应用于问题求解上，对于一个问题可以将其归约为许多子问题的求解。这样的一个问题归约的过程就可以用与或树进行表示。其中原命题为与或树的跟节点，分解出的子命题为与或树的孩子节点。如果分解出子命题中一个命题有解就可以导致原命题有解，就把原命题所在节点命名为或节点，反之若需要所有子命题都有解才能导致原命题有解，那么这个节点就是与节点。

极大极小搜索

双人完备信息博弈中，假设博弈一方是MAX，另一方是MIN。对于MAX来说自己可选的行动方案都是或的关系，因为主动权掌握在MAX手中。而对手MIN所作出的所有决策在MAX看来都是与的关系，因为当主动权掌握在MIN手中后，MAX不得不考虑到MIN所有可能的决策结果，这样MAX才能作出对于自己最有利的决策。

基于如上的假设与考量结合双人完备信息博弈游戏的特点，可以总结出博弈树有如下特征：

1. 博弈过程必须有立场，要么站在MAX的立场上，要么站在MIN的立场上。

2. 博弈树中与节点与或节点是逐层交替出现的，其中根节点是或极点。或节点代表MAX所面临的博弈状态（MIN决策之后的博弈状态），与节点代表MIN所面临的博弈状态（MAX决策之后的博弈状态）。