人工智能极大极小算法.doc

人工智能(极大极小算法)
第六讲 博弈与启发式及极大极小思想
博弈: 博弈
诸如下棋、打牌、战争等一类竞争性的智能活动。 诸如下棋、打牌、战争等一类竞争性的智能活动。 诸如下棋 ?其中最简单的一种称为双方完备博弈 其中最简单的一种称为双方完备博弈
博弈是AI研究的起源和动力之一， 博弈是AI研究的起源和动力之一，是启 研究的起源和动力之一 发式算法所针对的一个重要领域
1、提供了可构造的任务领域，能明确判断成功或失败 提供了可构造的任务领域， 2、博弈问题是对AI研究提出了严峻的挑战。 博弈问题是对AI研究提出了严峻的挑战 研究提出了严峻的挑战。
如何表示博弈问题的状态、博弈的过程和博弈的知识, 如何表示博弈问题的状态、博弈的过程和博弈的知识,
博弈过程
博弈是二人博弈、全信息、非偶然博弈、博弈双方利益完全对立，过程: 博弈是二人博弈、全信息、非偶然博弈、博弈双方利益完全对立，过程: (1)对垒双方MAX和MIN 轮流采取行动。结果:MAX胜、MIN败;MAX 对垒双方MAX和 轮流采取行动。结果:MAX胜 MIN败 MIN胜 和局。 败，MIN胜;和局。 (2)对垒过程中，任何一方都了解当前的格局和过去的历史 对垒过程中， (3)任何一方在采取行动前都要根据当前实际情况，进行得失分析，选自 任何一方在采取行动前都要根据当前实际情况，进行得失分析， 对己最有利而对对方最不利的对策，不存在碰运气成分。 对己最有利而对对方最不利的对策，不存在碰运气成分。
博弈树
博弈树
当某一方当前有多个行动方案可供选择时， 当某一方当前有多个行动方案可供选择时，他总是选择对 自己最为有利而对对方最为不利的那个行动方案。 自己最为有利而对对方最为不利的那个行动方案。
当轮到A方走棋时，则可供A 当轮到A方走棋时，则可供A方选择的若干个行动方案之间 的关系。轮到B方走棋时， 是“或”的关系。轮到B方走棋时，B方也有若干个可供选 择的行动方案，但此时这些行动方案对A 择的行动方案，但此时这些行动方案对A方来说它们之间是 的关系。 “与”的关系。
1. 使用与或图(与或树)来表示博弈过程，叫做博弈树。 使用与或图(与或树)来表示博弈过程，叫做博弈树。
博弈树
博弈树的特点
? 博弈的初始格局是初始节点。 博弈的初始格局是初始节点。 ? 在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方 在博弈树中， 节点和“ 节点是逐层交替出现的。
扩展的节点之间是“ 扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。 关系，对方扩展的节点之间是“ 关系。 双方轮流扩展节点。 双方轮流扩展节点。
示例
例子:假设有,枚硬币，任一选手只能将已分好的, 例子:假设有,枚硬币，任一选手只能将已分好的,堆钱币分成两堆
个数不等的钱币，,位选搜轮流进行，直到每一堆都只有,枚或,枚钱币， 个数不等的钱币， 位选搜轮流进行，直到每一堆都只有,枚或,枚钱币，
不能再分为止，哪个选手遇到不能再分的情况，则为输。 不能再分为止，哪个选手遇到
不能再分的情况，则为输。
示例分析
每种状态把钱币分成一堆或多堆. 每一层根据根据这一步由谁来执行,标上 每种状态把钱币分成一堆或多堆. 每一层根据根据这一步由谁来执行, MAX/MIN。 MAX/MIN。如下图 MIN 7表示只有1个7枚钱币的堆，由MIN来选择划分。 7表示只有 表示只有1 枚钱币的堆， MIN来选择划分 来选择划分。 每个叶子节点有一个1 的值，代表MAX 获胜还是MIN 每个叶子节点有一个1 或0的值，代表MAX 获胜还是MIN 获胜 MIN MAX MIN 6,1 5,1,1 0 1 7 1
5,2
1
4,3 3,2,2
1
4,2,1 1
0
3,3,1
1
MAX MIN MAX
4,1,1,1
0
3,2,1,1
1
2,2,2,1
0
3,1,1,1,1
0
2,2,1,1,1
1
2,1,1,1,1,1
0
(1)如果父状态是 如果父状态是MAX 节点， 节点， 如果父状态是 将孩子中最大的值赋给它 (2)如果父状态是 如果父状态是MIN 节点， 节点， 如果父状态是 将孩子中最小的值赋给它
极大极小搜索思想
1、极大极小策略 是考虑双方对弈若干步之后， 是考虑双方对弈若干步之后，从可能的步中选一步相对好的步法 来走， 来走，即在有限的搜索深度范围内进行求解 ? 定义一个静态估价函数f ,以便对棋局的态势作出优劣评估 定义一个静态估价函数f ,以便对