知识卡片
零和博弈可用取负统一递归
零和游戏中当前玩家的价值等于对手价值的负数,因此每个节点可统一计算 max(−子节点值),递归时交换行动方。叶子评价必须始终采用当前行动方视角,并满足双方评分符号一致;不满足零和假设时不能直接套用。
同一深度与相同走法顺序下,不剪枝的NegMax和Minimax探索相同状态,只是表达方式不同。
212沿用Minimax的状态、合法走法、深度和最佳走法接口;叶子分数需与当前行动方视角相符。
213承接Minimax适用环境;游戏规则和评分需支持玩家间取负转换。
214的03365–03366代码以当前player评价叶子,递归交换player和opponent,撤销动作后比较−me.score。动作撤销需恢复全部状态,且终局处理应遵守游戏规则。
216的03367井字棋树与Minimax例子对照:递归中每层从当前行动方视角评分,父层对返回值取负并选最大,未剪枝时复杂度仍按分支和深度指数增长。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 零和博弈可用取负统一递归
- · 输入/输出
- · 使用环境
- · 解决方案
- · 分析
原书出处 · 5 处
- · 查看原书依据
NegMax NegMax算法不再使用Minimax的MAX和MINI层级,而是每一级都使用同样的方法。这种思想也形成了另外一种算法,AlphaBeta,我们在稍后会讨论这个算法。在Minimax中,局面状态是一直从玩家的视角来观察,然后选择走法(需要存储棋子的信息以供评价函数使用)。 此算法不再将
- · 查看原书依据
输入输出同Minimax。
- · 查看原书依据
使用环境 使用环境也同Minimax。
- · 查看原书依据
NegMax实现
- · 查看原书依据
NegMax探测的状态数目和Minimax一样,如果追寻深度为d,每个局面状态的可行走法为b个,那么数目近似于bd。 最后我们可以看到NegMax是如何处理博弈树的叶子节点的。你同样可以在例7-7的代码中看到,这些叶子状态节点都是从玩家的角度出发,也就是说双亲节点从叶子节点选择的MoveEvalua