博弈与博弈树

博弈

博弈双方根据事先制定的规则，轮流交替在对应的棋局上做出自己的选择，然后根据规则判定那一方获胜。

博弈树（一种特殊的与或树）

• 目标：将当前棋局作为根节点，选出最有利于自己获胜的一步棋
• 结构

  • 节点：每一个节点代表一种棋局，总共有两种情况，一种是敌方走过，轮到我走；另外一种是我方走过，敌方进行选择。

  • 交替出现的与或节点：双方轮流走步，轮流扩展自己的节点

  • 终叶节点：

    • 我方获胜，节点可解
    • 敌方获胜，节点不可解

  • 根节点：敌方刚走过的棋局，我方根据该棋局做出自己的判断

  • 根节点的字节点：我方根据敌方走过的棋局，可以做出的选择

• 估价函数：将胜利的判定条件作为可视化，可比较的数字，通过比较估价函数值，来确定当前步是否是最有力的步骤
  • 终叶节点的估价函数：通过终叶棋局的直接计算获得
  • 父节点：
    • 子节点是或连接：选取子节点中估价函数最大的得分作为父节点的估价函数值
    • 子节点是与连接：选取子节点中估价函数最小的得分作为父节点的估价函数值

搜索方法——man-min搜索

• 基本思想：自下而上逐层回溯评估。——因为底层的终叶节点代表着棋局的最终输赢，所以要从结局开始追溯，判定某一步走的结果是输是赢。
• 与节点的子节点选择最小值最为父节点的值——敌方有若干种可能，只要有一种可能，在同等的情况下，敌方也一定会赢，所以，父节点一定是最小值。
• 或节点的子节点选择最大值作为父节点的值——我方有若干种走法，凡是我方一定选择胜率最高的步子。

图例

有当前棋局出发，根据步数4的要求，延展出对应的与或图

然后根据对应的传递规则，从下往上进行推导，直到倒数第二层，选择出胜率最高的步数。