Video在线视频

所以看到这个极小极大决策算法

那么它这个函数名就命名为MINIMAX-DECISION

函数这个算法的输入呢就是当前的状态 也就是当
前的棋盘状态

因为轮到它下了 然后它的返回值就是返回一个动
作告诉这个智能体应该如何下这一步棋

那大家看到它的主体很简单的就两条语句

第一条就是因我们的调用算法的智能体是我们的
MAX

我们的MAX 所以呢当前这个状态对应的结点就是
MAX结点

所以呢它就去计算 这个MAX结点 它的这个值

也就是说极小极大值 计算这个值

所以它调用的是这个MAX-VALUE这个函数去计算
这个MAX结点的值

计算出来之后呢得到一个MAX的这个值

就像刚才这样一样得到这个值3

然后呢它就去看一下是这个状态的哪一个后续

对应着这个值 也就是说是哪一个后续结点对应着
这个值

我们看一下是这个后续结点对应这个值

那么这个后续结点是哪一个动作产生的呢

它就把这个动作 产生这个最大值的动作

返回去让智能体去执行

就像这里一样 那么是哪一个后续结点具有3呢

一看这个 是哪个动作产生了这个后续结点 是A1

所以它就把这个A1返回去让智能体去执行

所以这个程序就是这个意思

那么我们这个当前这个状态的这个值

这个MAX值是怎么计算出来的呢

然后我们来看到这里 然后它就要调用这个函数

调用计算这个MAX结点的极小极大值函数来计算

那么要计算这个MAX结点的极小极大值

它的返回值就是算出来一个效用值 就是这个

MAX结点的一个效能值 极小极大值

那么首先我们判断一下这个状态是不是一个终止
状态

如果是终止状态的话直接把它的效能函数值返回
去作为它的值 很简单的

如果不是的话 那么我们根据定义

这个结点是一个MAX结点那就要去

求它所有后续结点里面的一个最大值返回去

作为它的一个值

那么我们就定义一个临时变量v

用来储存这个值 这个max结点的效能值 极小极大
值

那么一开始给它初始化为负无穷 为什么呢

因为我们要求所有后续结点里面的最大值

所以呢它给它初始化为负无穷

然后呢就是进行for循环 就是去它所有的后续结点

也就是说它的所有的后续结点 这个就是后续的意
思

它的每一个后续结点去比较是不是比当前储存的
这个值更大

更大那么就存进来

所以整个儿子节点都比较完之后

这个v里面肯定储存的是一个所有后续结点里面的
一个最大值的

所以呢对于当前这个状态的每一个后续s

他都去看一下v里面储存的值和你这个后续的这个
值那个更大

更大的放到这个v里面去

那么这个后续s它这个值是怎么算出来的呢

因为我们max结点的后续是min结点

所以呢它的这个后续s的值的计算就要去调用另外
一个函数

另外一个函数是用来计算min结点的极小极大值

也就是说用来计算min结点的效能值的

所以呢对于它的每一个儿子

计算它的值的 效能值的时候要去调用MIN-VALUE
来计算

然后呢这个for循环结束完了之后

这个v里面就储存了所有的后续结点里面的最大值

然后这个最大值就是我们的max节点的效能函数值

也就是极小极大值 所以把他返回去

这个就是刚才的极小极大值的定义的一种实现

那么这个min结点它的效能值 它的极小极大值怎么
计算呢

它的这个函数在这里

同样这个min结点它的这个值的计算 它的输入就是

这个min结点对应的状态

然后它返回的就是这个值 它的极小极大值 或者称
为这个效能值

那么同样的首先判断一下这个状态是不是一个终
止状态

如果是的话呢 那么这个状态它是根据我们效能函
数定义

是有一个直接的值的直接返回去就行了

那么如果不是的话呢 那么它就要去找

它所有的儿子节点里面 从儿子结点的值里面找一
个最小值

作为这个极小结点的效能值的 这个是我们的定义
决定的

所以既然是要找最小 那么我们就用一个 定义一个
临时变量v

来存储这个最小值 那么这个v的初始化 用一个正
无穷来初始化

就是用一个很大值来初始化因为它要求最小值

同样的我们就去对于它的每一个儿子 都要比较 找
一遍

也就是说当前这个极小结点它的所有后续结点s

我们看一下这个s 这个节点的值和我们存储的这个
v值哪个更小

更小的话 放到这个v里面去

那么整个for循环结束之后呢

它这个v里面储存的就是所有的后续结点里面

值最小的那个值放到这里面 一个最小值放在这里
面

那么我们知道这个MIN结点的后续结点是MAX结点

所以要计算这个MIN结点的后续结点的值呢

要去调用MAX-VALUE来计算它的值

所以呢 这里面它递归的调用这个MAX-VALUE来
计算它的儿子结点的值

比较完了之后 这个for循环结束之后呢

这个v里面就储存了所有的MIN结点的后续结点里
面

具有一个最小值的后续结点的值返回去

作为这个MIN结点的效能值

那么这个就是这个极小极大决策算法的一个伪代
码

这个程序相当的简洁的 那么它理解起来也并不难

就是通过计算每个结点的效能值

也就是说一路往下走 走到这个终止状态的时候

得到这个终止状态的效能值 再一层一层返回去

得到调用这个算法的MAX结点的效能值

然后通过这个MAX的效能值呢 来选择一个

是哪一个动作得到的这个效能值

把这个动作返回去 让智能体去执行

那么这种算法其实是它的思想是什么

它的思想就是把对手MIN也想象成是一个不会犯错
误的对手

也就是说呢 如果我做A1这种行动

那么我的对手呢 是会做A11这种行动

还是会做A12这种行动还是会做A13这种行动呢

那么对手MIN它是不会犯错误的

它一定会选择使得你效能函数值最小的这个动作
来执行的

也就是说这个效能函数值越小对MIN越好的

所以MIN它一定会选择A11来执行

也就是说如果你执行 你选择A1的话 它就会选择
A11

也就是说意味着你只能得3分 你一定只能得3分

那么一样的道理如果你选择A2的话

那么MIN在这种情况下 它做这个动作A21

MAX你只能得两分 它做这个动作MAX得四分

它做这个动作MAX得6分

那么MIN结点它肯定希望MAX结点得分越少越好

所以它一定选择A21来执行

所以呢 就会使得你只能得两分

使得你这个执行A2的话只能得两分

那么同样的道理这个也是一样的

如果你选择A3进行执行动作的话

MIN的话 它选择A31你会得14分 选择A32你会得5
分

选择A33你会得两分 那么它一定会选择A33来执
行

使得你只能得两分

所以呢我们这个算法 他将对手假设成不会犯错误
的

也就是说对手也是一个在做最优决策的对手

在这种情况下它做出的决策

所以它就选择A1进行执行 因为A1会使它得到可能
的最高分3分

所以这种极小极大的决策算法在对手不会犯错误
的情况下 它能够得到一个最优的决策

也就是说它做出的这个决策不会比其他决策差的

但是如果对手不是一个完美对手

对手会犯错误的话 可能我们的算法呢就不是一个
最优的算法

就是它可能做出的决策会比其他方法更差 得到的
分更少

这个就是极小极大决策算法它的思想

就是在对手不犯错误的情况下

他选择能够得分最高的行动执行

那么来看一下这个极小极大算法的四大属性 也就
是说它的性质

首先看一下它有没有完备性

也就是说在有解的情况下它能不能找到解

那么只要搜索树是有限的 也就是说这个游戏是在
有限的步骤内能够完成的

并且这个分支数也是有限的

这种情况下 那么你一定能计算出这个结点的效能
值来

一定能够找到一个能够使得它得到这个效能值的
动作来执行的

也就是说能够计算出来的这些值

那么最优性的话怎么能够保证呢

我们刚才讲了我们的极小极大算法呢

它是把对手假想成是一个不会犯错误的对手

也就是说对手也是在做最优决策

这种情况下我搜索出的策略是最优的

它能够得到一个最大的效能值 所以它是最优的

那么对于时间复杂度来讲呢

那么我们最坏的情况下就是

整个的这个搜索树都要搜索一遍才能计算出来这
个值

所以呢它是 时间复杂度呢就是b的m次方

这个m就是我们这个搜索树的最深的层

这个b就是分支数

那么空间复杂度的话 我们采用的就是深度优先搜
索

也就是说我们在计算这个结点的效能值的时候呢

它是从最底层 也就是说要从一条路径下面的最底
层开始慢慢的回溯回去的

算出这个结点的值 所以它的空间复杂度呢是b乘以
m和我们的深度优先搜索是一样的

因为它在计算这个搜索的时候 在计算这个结点的
值的时候

采用的是这个深度优先的搜索

他是从最顶层要往前搜索一条路

往前搜索到这个终止状态的时候再返回去

返回去算出每一个结点的值来的