知识卡片

普通读书笔记卡 · 5654.d.1.f.4.n.8 · 生成模型:未记录

零和博弈可用取负统一递归

理解等级:中级

零和游戏中当前玩家的价值等于对手价值的负数,因此每个节点可统一计算 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

    参考来源

    - 位置:《算法技术手册》第7章《NegMax》(spine1617;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1580.html;u211-ch07-009)。 - 结论依据:211全文及03364伪代码图实读。 - 原始内容:NegMax NegMax算法不再使用Minimax的MAX和MINI层级,而是每一级都使用同样的方法。这种思想也形成了另外一种算法,AlphaBeta,我们在稍后会讨论这个算法。在Minimax中,局面状态是一直从玩家的视角来观察,然后选择走法(需要存储棋子的信息以供评价函数使用)。 此算法不再将 - 位置:《算法技术手册》第7章《输入/输出》(spine1617;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1580.html;u212-ch07-009)。 - 结论依据:212沿用Minimax的状态、合法走法、深度和最佳走法接口;叶子分数需与当前行动方视角相符。 - 原始内容:输入输出同Minimax。 - 位置:《算法技术手册》第7章《使用环境》(spine1618;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1581.html;u213-ch07-009)。 - 结论依据:213承接Minimax适用环境;游戏规则和评分需支持玩家间取负转换。 - 原始内容:使用环境 使用环境也同Minimax。 - 位置:《算法技术手册》第7章《解决方案》(spine1619;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1582.html;u214-ch07-009)。 - 结论依据:214的03365–03366代码以当前player评价叶子,递归交换player和opponent,撤销动作后比较−me.score。动作撤销需恢复全部状态,且终局处理应遵守游戏规则。 - 原始内容:NegMax实现 - 位置:《算法技术手册》第7章《分析》(spine1621;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1584.html;u216-ch07-009)。 - 结论依据:216的03367井字棋树与Minimax例子对照:递归中每层从当前行动方视角评分,父层对返回值取负并选最大,未剪枝时复杂度仍按分支和深度指数增长。 - 原始内容:NegMax探测的状态数目和Minimax一样,如果追寻深度为d,每个局面状态的可行走法为b个,那么数目近似于bd。 最后我们可以看到NegMax是如何处理博弈树的叶子节点的。你同样可以在例7-7的代码中看到,这些叶子状态节点都是从玩家的角度出发,也就是说双亲节点从叶子节点选择的MoveEvalua