极大极小算法.pptx

博弈博弈:诸如下棋、打牌、战争等一类竞争性的智能活动。诸如下棋、打牌、战争等一类竞争性的智能活动。其中最简单的一种称为双方完备博弈其中最简单的一种称为双方完备博弈 博弈是博弈是AI研究的起源和动力之一，是启研究的起源和动力之一，是启发式算法所针对的一个重要领域发式算法所针对的一个重要领域1 1、提供了可构造的任务领域，能明确判断成功或失败、提供了可构造的任务领域，能明确判断成功或失败、提供了可构造的任务领域，能明确判断成功或失败、提供了可构造的任务领域，能明确判断成功或失败2 2、博弈问题是对、博弈问题是对、博弈问题是对、博弈问题是对AIAI研究提出了严峻的挑战。研究提出了严峻的挑战。研究提出了严峻的挑战。研究提出了严峻的挑战。如何表示博弈问题的状态、博弈的过程和博弈的知识？如何表示博弈问题的状态、博弈的过程和博弈的知识？如何表示博弈问题的状态、博弈的过程和博弈的知识？如何表示博弈问题的状态、博弈的过程和博弈的知识？极大极小搜索思想极大极小搜索思想1 1、极大极小策略、极大极小策略、极大极小策略、极大极小策略 是考虑双方对弈若干步之后，从可能的步中选一步相对好的步法是考虑双方对弈若干步之后，从可能的步中选一步相对好的步法是考虑双方对弈若干步之后，从可能的步中选一步相对好的步法是考虑双方对弈若干步之后，从可能的步中选一步相对好的步法来走，即在有限的搜索深度范围内进行求解来走，即在有限的搜索深度范围内进行求解来走，即在有限的搜索深度范围内进行求解来走，即在有限的搜索深度范围内进行求解 定义一个静态估价函数定义一个静态估价函数定义一个静态估价函数定义一个静态估价函数f,f,以便对棋局的态势作出优劣评估以便对棋局的态势作出优劣评估以便对棋局的态势作出优劣评估以便对棋局的态势作出优劣评估 规定：规定：规定：规定：MAXMAX和和和和MINMIN代表对弈双方代表对弈双方代表对弈双方代表对弈双方 P P代表一个棋局代表一个棋局代表一个棋局代表一个棋局(即一个状态）即一个状态）即一个状态）即一个状态）有利于有利于有利于有利于MAXMAX的态势，的态势，的态势，的态势，f(p)f(p)取正值取正值取正值取正值 有利于有利于有利于有利于MINMIN的态势，的态势，的态势，的态势，f(p)f(p)取负值取负值取负值取负值 态势均衡，态势均衡，态势均衡，态势均衡，f(p)f(p)取零值取零值取零值取零值2 2、MINMAXMINMAX的基本思想：的基本思想：的基本思想：的基本思想：(1)当轮到当轮到当轮到当轮到MIN MIN 走步时，走步时，走步时，走步时，MAXMAX应该考虑最坏的情况（即应该考虑最坏的情况（即应该考虑最坏的情况（即应该考虑最坏的情况（即f(p)f(p)取极小值）取极小值）取极小值）取极小值）(2)(2)当轮到当轮到当轮到当轮到MAX MAX 走步时，走步时，走步时，走步时，MAXMAX应该考虑最好的情况（即应该考虑最好的情况（即应该考虑最好的情况（即应该考虑最好的情况（即f(p)f(p)取极大值）取极大值）取极大值）取极大值）(3)(3)评价往回倒推时，相应于两位棋手的对抗策略，交替使用（评价往回倒推时，相应于两位棋手的对抗策略，交替使用（评价往回倒推时，相应于两位棋手的对抗策略，交替使用（评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1 1）和（和（和（和（2 2）两种方法传递倒推值。）两种方法传递倒推值。）两种方法传递倒推值。）两种方法传递倒推值。算法分析和举例算法分析和举例例子：一字棋（或井字棋）算法分析例子：一字棋（或井字棋）算法分析例子：一字棋（或井字棋）算法分析例子：一字棋（或井字棋）算法分析 设棋局为设棋局为设棋局为设棋局为P P，估价函数为，估价函数为，估价函数为，估价函数为e(P)e(P)。规定：规定：规定：规定：(1)(1)若若若若P P对任何一方来说都不是获胜的位置，则对任何一方来说都不是获胜的位置，则对任何一方来说都不是获胜的位置，则对任何一方来说都不是获胜的位置，则e(P)=e(e(P)=e(所有空格都放所有空格都放所有空格都放所有空格都放上上上上MAXMAX的棋子后三字成一线的总数的棋子后三字成一线的总数的棋子后三字成一线的总数的棋子后三字成一线的总数)-e()-e(所有空格都放上所有空格都放上所有空格都放上所有空格都放上MINMIN的棋的棋的棋的棋子后三字成一线的总数子后三字成一线的总数子后三字成一线的总数子后三字成一线的总数)(2)(2)若若若若P P是是是是MAXMAX必胜的棋局，则必胜的棋局，则必胜的棋局，则必胜的棋局，则e(P)e(P)+。(3)(3)若若若若P P是是是是MINMIN必胜的棋局，则必胜的棋局，则必胜的棋局，则必胜的棋局，则e(P)e(P)-。比如比如比如比如P P如右图示如右图示如右图示如右图示,则则则则e(P)=6-4=2e(P)=6-4=2叉代表叉代表叉代表叉代表MAXMAX 方，圆圈代表方，圆圈代表方，圆圈代表方，圆圈代表MINMIN方方方方 向上值的传播规则：向上值的传播规则：向上值的传播规则：向上值的传播规则：若父状态在若父状态在若父状态在若父状态在MINMIN层，那么孩子中最小值被传递上去层，那么孩子中最小值被传递上去层，那么孩子中最小值被传递上去层，那么孩子中最小值被传递上去若父状态在若父状态在若父状态在若父状态在MAXMAX层层层层,那么孩子中最大值被传递上去那么孩子中最大值被传递上去那么孩子中最大值被传递上去那么孩子中最大值被传递上去算法分析算法分析MAXMAXMINMINMAXMAX由于上图所示位置具有最大的倒推值，它应当选取为由于上图所示位置具有最大的倒推值，它应当选取为由于上图所示位置具有最大的倒推值，它应当选取为由于上图所示位置具有最大的倒推值，它应当选取为MAXMAX的第的第的第的第一步（正好是一步（正好是一步（正好是一步（正好是MAXMAX的最好的优先走步）的最好的优先走步）的最好的优先走步）的最好的优先走步）算法分析算法分析 现在图中现在图中现在图中现在图中MAXMAX有两个可能有两个可能有两个可能有两个可能“最好的最好的最好的最好的”优先走步，假设优先走步，假设优先走步，假设优先走步，假设MAXMAX走了图上指明的那一步走了图上指明的那一步走了图上指明的那一步走了图上指明的那一步 MAXMAXMINMIN算法分析算法分析MAXMIN 如上图，如上图，如上图，如上图，A A点，点，点，点，MINMIN直接获胜，其直接获胜，其直接获胜，其直接获胜，其e(P)e(P)-，MAXMAX只有选择图上的走步，获胜只有选择图上的走步，获胜只有选择图上的走步，获胜只有选择图上的走步，获胜的把握才更大。的把握才更大。的把握才更大。的把握才更大。