问题求解基本原理

问题求解基本原理内容摘要：

Slide 14 定义 棋局的 评价函数 设 P 为 有界博弈树 中棋局； ｈ (P): 棋局Ｐ优劣的评价函数。 • 例 1：从当前棋局到离我方最后取胜的差距： 胜利在望 – ｈ (P)值较大， 败局显露 – ｈ (P)值较小； • 例 2：从当前棋局到到某个明显有利于我方棋局的差距： 吃掉对方一子 , 或者 “ 叫吃 ”。  ｈ (P)MAX赢 = ｈ (P)MIN输 = +∞  ｈ (P)MAX输 = ｈ (P)MIN赢 = ∞  ｈ (P)平 = 0  ｈ (P) – 任一终叶棋局Ｐ优劣的评价函数的 定义原则： 北京航空航天大学软件开发环境国家重点实验室 Slide 15 计算 棋局的 评价函数 有界博弈树中任一棋局（节点Ｐ） 评价 函数 值的 计算 ：  对于 终叶节点Ｐ ： 赋 静态评价函数值ｈ (P)。  对于 非终叶节点Ｐ ：按 极小 极大走步原则 ，采用倒推的方法， 自下而上 地由子节点 计算 父节点的 动态评价函数值ｈ (P)。 北京航空航天大学软件开发环境国家重点实验室 Slide 16 站在 MAX立场 基于 极小 极大原则 的 评价 函数 计算实例 静态 启发式评价函数值 动态 评价函数值 北京航空航天大学软件开发环境国家重点实验室 Slide 17 基于博弈搜索的搜索策略  博弈问题及博弈树  博弈搜索控制策略  有界深度搜索算法及其应用实例  博弈树的 α β 剪枝 北京航空航天大学软件开发环境国家重点实验室 Slide 18 有界深度搜索 算法 及其应用实例  针对 当前 对方 给出的棋局 s ： 按宽度优先法 自上而下地 生成 规定深度 的博弈树； 为有界深度博弈树的所有 叶节点 赋 静态评价函数估计值 根据 极小 极大走步原则 自下而上地 逐级 计算各 非终叶节点的 动态 评价函数估计值， 直至求到起始节点的 评价函数值 ｈ (s)为止。  比较我方可走的各棋局的 评价函数估计值， 从中选择 最好 的棋步走。  再根据对方走出的棋局 s，重复上述过程。 北京航空航天大学软件开发环境国家重点实验室 Slide 19 有界深度搜索算法及其 应用实例 一字棋 （站在 MAX的立场） 定义特殊棋局估计函数 h1(P)  h1(P)MAX赢 = +∞  h1(P)MAX输 = ∞  h1(P)平 =。