5
博弈树的启发式搜索
下棋、打牌、战争等一类竞争性智能活动称为博弈
(1)二人零和、全信息、非偶然博弈
对垒的A,B双方轮流采取行动，博弈的结果只有三种情况：A方胜，B方胜，双方战成平局
在对垒过程中，任何一方都了解当前的格局及过去的历史
双方都是很理智地决定自己的行动，不存在“碰运气”偶然因素
(2)博弈过程
博弈的初始格局是初始节点
在博弈树中，“或”节点和“与”节点是逐层交替出现的，自己一方扩展的节点之间是“或”关系对方扩展的节点之间是“与”关系，双方轮流地扩展节点
所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点
(3)极大极小分析法
设博奕双方中一方为A,另一方为B,极大极小分析法是为其中一方（A)寻找一个最优行动方案的方法
考虑每一方案实施后对方可能采取的所有行动，计算可能的得分
定义一个估价函数，用来估计当前博弈树端节点的得分，得分称为静态估值,由端节点估值计算父节点得分—倒推值
“或”节点：选其子节点中最大的得分作为父节点的得分，立足最好
“与”节点：选其子节点中最小的得分作为父节点的得分，立足最坏
 点击看大图
|
