Figure 1: Game Tree 为 了 方 便 讨 论, 我 们 这 里 设 这 里 讨 论 的 博 弈 树 是 一 棵 有 限 树, 设 有 两 个 棋 手 甲 与 乙 进 行 这 场 博 弈, 这 样, 博 弈 树 分 为 三 类 结 点 : 1. 奇 数 层 的 非 叶 子 结 点 :

从 极 大 极 小 算 法 到 主 要 变 例 搜 索 孙 锴 1 综 述 人 机 对 弈 在 计 算 机 诞 生 前 就 开 始 了 发 展, 时 至 今 日, 人 机 对 弈 领 域 提 出 的 搜 索 算 法 数 目 已 经 非 常 之 多, 但 从 根 本 上 看, 许 多 搜 索 算 法 之 间 的 内 在 的 核 心 思 想 是 一 致 的 本 文 介 绍 将 从 极 大 极 小 搜 索 开 始, 讲 解 其 一 步 步 推 广 到 Alpha-Beta 搜 索, 以 至 于 最 终 推 广 到 实 际 应 用 中 主 要 变 例 搜 索 中 的 推 广 过 程 本 文 结 构 安 排 如 下 : 第 2 节 介 绍 博 弈 树 ; 第 3 节 介 绍 极 大 极 小 搜 索 ; 第 4 节 介 绍 负 值 最 大 搜 索 ; 第 5 节 介 绍 Alpha-Beta 剪 枝 ; 第 6 节 介 绍 窗 口 ; 第 7 节 介 绍 主 要 变 例 搜 索 ; 最 后 于 第 8 总 结 全 文 本 文 中 的 两 张 图 片 分 别 来 自 [2]( 有 修 改 ) 与 [1], 另 外 本 文 的 行 文 及 伪 代 码 参 考 了 [2] 2 博 弈 树 (Game Tree) 任 何 博 弈 类 游 戏 都 可 定 义 出 一 棵 有 根 树, 树 的 每 个 结 点 代 表 一 个 局 面, 结 点 的 子 结 点 是 该 结 点 所 代 表 的 局 面 走 一 步 可 以 到 达 的 局 面, 特 别 的, 树 的 根 节 点 是 初 始 的 局 面 例 如 图 1 是 井 字 棋 (Tic-tac-toe) 的 博 弈 树 ( 这 棵 树 中 我 们 借 助 对 称 性 质 去 掉 了 部 分 结 点, 例 如 如 果 不 考 虑 对 称, 那 么 根 节 点 应 有 9 个 子 结 点 ) 1

Figure 1: Game Tree 为 了 方 便 讨 论, 我 们 这 里 设 这 里 讨 论 的 博 弈 树 是 一 棵 有 限 树, 设 有 两 个 棋 手 甲 与 乙 进 行 这 场 博 弈, 这 样, 博 弈 树 分 为 三 类 结 点 : 1. 奇 数 层 的 非 叶 子 结 点 : 棋 手 甲 要 走 的 局 面 2. 偶 数 层 的 非 叶 子 结 点 : 棋 手 乙 要 走 的 局 面 3. 叶 子 节 点 : 对 局 的 结 果 ( 甲 胜, 乙 胜 或 平 局 ) 对 于 叶 子 结 点, 我 们 是 知 道 它 对 应 局 面 的 对 局 结 果 的 假 设 某 个 非 叶 子 结 点 的 所 有 子 结 点 都 是 叶 子 结 点, 那 么 棋 局 必 然 会 在 一 回 合 内 结 束, 我 们 假 定 棋 手 会 挑 选 对 自 己 最 有 利 的 着 法 那 么 如 果 存 在 某 个 子 结 点 对 应 的 局 面 是 该 棋 手 胜, 则 该 棋 手 必 定 会 选 择 到 达 这 类 胜 利 局 面 所 对 应 的 着 法 ; 如 果 没 有 子 结 点 对 应 的 局 面 是 该 棋 手 胜, 但 是 存 在 某 个 子 结 点 对 应 的 局 面 是 平 局, 则 该 棋 手 必 定 会 选 择 到 达 这 类 平 局 局 面 所 对 应 的 着 法 ; 如 果 所 有 子 结 点 对 应 的 局 面 都 是 该 棋 手 输, 则 该 棋 手 无 论 选 择 什 么 着 法, 他 都 会 输 因 此, 对 于 这 类 结 点 ( 所 有 子 结 点 都 是 叶 子 结 点 的 非 叶 子 结 点 ) 我 们 也 是 可 以 知 道 局 面 的 对 局 结 果 的 我 们 可 以 采 用 同 样 的 方 式 继 续 向 更 靠 近 根 的 非 叶 子 结 点 处 推 演, 于 是 最 终 对 于 博 弈 树 中 每 个 点, 我 们 都 可 以 知 道 其 对 应 局 面 的 对 局 结 果 对 于 井 字 棋, 由 于 可 能 的 局 面 数 量 很 小, 所 以 我 们 可 以 将 博 弈 树 穷 举 出 来, 在 此 基 础 上, 对 于 任 意 局 面, 我 们 都 可 以 由 博 弈 树 直 接 得 到 该 局 面 在 双 方 都 采 取 最 优 策 略 下 的 对 局 结 果, 以 及 在 该 局 面 中 的 最 优 着 法 3 极 大 极 小 搜 索 (Minimax Search) 然 而 在 更 复 杂 的 情 况 中 ( 例 如 国 际 象 棋 ), 由 于 可 能 的 局 面 数 巨 大, 而 计 算 能 力 有 限, 我 们 无 法 穷 举 整 棵 博 弈 树, 因 此 我 们 不 再 能 通 过 穷 举 博 弈 树 获 得 对 任 意 局 面 的 评 价 信 息 ( 对 局 结 果 ) 于 2

是, 此 时 我 们 推 广 之 前 对 博 弈 树 的 定 义, 将 博 弈 树 的 树 根 对 应 于 我 们 希 望 获 得 其 评 价 信 息 的 局 面, 将 我 们 能 够 由 此 树 根 穷 举 出 的 前 若 干 层 博 弈 树 作 为 我 们 实 际 讨 论 的 博 弈 树 由 于 此 时 的 博 弈 树 的 叶 子 节 点 并 不 一 定 对 应 着 对 局 的 结 果 ( 即 甲 胜 乙 胜 或 平 局 ), 所 以 我 们 设 计 一 个 局 面 评 估 的 函 数, 对 每 个 叶 子 结 点 赋 予 一 个 整 数 ( 也 可 以 是 实 数, 不 过 为 了 方 便 在 计 算 机 中 表 示 以 及 下 文 的 讨 论, 我 们 这 里 限 定 为 整 数 ), 整 数 的 大 小 代 表 着 我 们 对 对 应 局 势 偏 向 于 甲 或 乙 的 估 计 ( 局 面 评 分 ) 为 了 方 面 讨 论, 我 们 设 整 数 越 大 对 甲 越 有 利,+ 对 应 甲 胜, 整 数 越 小 对 乙 越 有 利, - 对 应 乙 胜 对 于 叶 子 结 点, 我 们 是 知 道 它 对 应 局 面 的 局 面 评 分 的 现 在, 我 们 用 类 似 前 文 的 分 析 方 法 分 析 非 叶 子 结 点 假 设 某 个 非 叶 子 结 点 的 所 有 子 结 点 都 是 叶 子 结 点, 我 们 假 定 棋 手 会 挑 选 对 自 己 最 有 利 的 着 法 如 果 该 非 叶 子 结 点 是 奇 数 层 非 叶 子 结 点 ( 对 应 棋 手 甲 要 走 的 局 面 ), 则 棋 手 必 定 会 选 择 到 达 局 面 评 分 最 大 的 子 结 点 所 对 应 的 着 法, 从 而 该 结 点 所 对 应 局 面 的 优 劣 可 以 由 其 所 有 子 结 点 局 面 评 分 的 最 大 值 来 衡 量, 这 个 值 即 可 成 为 该 结 点 所 对 应 局 面 的 局 面 评 分 如 果 该 非 叶 子 结 点 是 偶 数 层 非 叶 子 结 点 ( 对 应 棋 手 乙 要 走 的 局 面 ), 则 棋 手 必 定 会 选 择 到 达 局 面 评 分 最 小 的 子 结 点 所 对 应 的 着 法, 从 而 该 结 点 所 对 应 局 面 的 优 劣 可 以 由 其 所 有 子 结 点 局 面 评 分 的 最 小 值 来 衡 量, 这 个 值 即 可 成 为 该 结 点 所 对 应 局 面 的 局 面 评 分 因 此, 对 于 这 类 结 点 ( 所 有 子 结 点 都 是 叶 子 结 点 的 非 叶 子 结 点 ) 我 们 也 是 可 以 知 道 局 面 的 局 面 评 分 的 我 们 可 以 采 用 同 样 的 方 式 继 续 向 更 靠 近 根 的 非 叶 子 结 点 处 推 演, 于 是 最 终 对 于 博 弈 树 中 每 个 点, 我 们 都 可 以 知 道 其 对 应 局 面 的 局 面 评 分, 根 结 点 对 应 局 面 的 局 面 评 分 就 是 我 们 希 望 获 得 的 信 息 实 际 上 以 上 这 段 话 所 介 绍 的 推 演 过 程 就 是 极 大 极 小 搜 索 伪 代 码 描 述 如 下 : int MinMax(int depth) { if (SideToMove() == JIA) { // 甲 方 return Max(depth); else { // 乙 方 return Min(depth); int Max(int depth) { // 甲 方 int best = -INFINITY; if (depth <= 0) { // 如 果 是 叶 子 val = Min(depth - 1); // 取 子 结 点 评 分 的 最 大 值 if (val > best) { best = val; return best; int Min(int depth) { // 乙 方 int best = INFINITY; // 注 意 这 里 不 同 if (depth <= 0) { val = Max(depth - 1); // 取 子 结 点 评 分 的 最 小 值 3

if (val < best) { // 注 意 这 里 不 同 best = val; return best; 4 负 值 最 大 搜 索 (Negamax) 观 察 前 面 给 出 的 极 大 极 小 搜 索 的 伪 代 码, 不 难 看 出 过 程 Max 和 过 程 Min 具 有 很 高 的 相 似 度, 我 们 可 以 通 过 一 个 巧 妙 的 变 换 将 Max 与 Min 以 及 调 用 它 们 的 MinMax 合 并 重 写 为 一 个 过 程 这 一 变 换 的 核 心 思 想 源 于 对 局 面 评 分 定 义 的 巧 妙 修 改 我 们 将 整 数 越 大 对 甲 越 有 利,+ 对 应 甲 胜, 整 数 越 小 对 乙 越 有 利, - 对 应 乙 胜 修 改 为 整 数 越 大 对 当 前 局 面 将 落 子 方 越 有 利,+ 对 应 当 前 局 面 将 落 子 方 胜, 整 数 越 小 对 当 前 局 面 将 落 子 方 越 不 利, - 对 应 当 前 局 面 将 落 子 方 败 这 一 修 改 仅 仅 是 换 了 一 种 表 示 方 法 ( 即 将 极 大 极 小 搜 索 的 博 弈 树 中 奇 数 层 的 局 面 评 价 值 取 其 相 反 数, 偶 数 层 局 面 评 价 值 不 变 ), 并 没 有 改 变 局 面 评 分 和 极 大 极 小 搜 索 的 工 作 原 理, 却 使 得 奇 偶 层 结 点 局 面 评 分 的 计 算 方 法 由 过 去 的 不 同 变 为 了 相 同, 更 具 体 地 说, 现 在 所 有 非 叶 子 结 点 对 应 局 面 的 局 面 评 分 都 等 于 其 子 结 点 对 应 局 面 的 局 面 评 分 的 相 反 数 的 最 大 值 我 们 称 这 种 修 改 后 的 搜 索 为 负 值 最 大 搜 索, 其 伪 代 码 如 下 : int NegaMax(int depth) { int best = -INFINITY; if (depth <= 0) { val = -NegaMax(depth - 1); // 注 意 这 里 有 个 负 号 if (val > best) { best = val; return best; 易 见 极 大 极 小 搜 索 与 负 值 最 大 搜 索 是 完 全 等 价 的 ( 遍 历 结 点 的 顺 序, 返 回 值 均 相 同 ), 然 而 后 者 代 码 短 了 很 多, 这 极 大 地 方 便 了 代 码 的 维 护, 减 少 了 出 错 的 可 能 4

5 Alpha-Beta 剪 枝 (Alpha-Beta Pruning) Figure 2: Alpha-Beta Pruning 如 果 我 们 对 极 大 极 小 搜 索 的 搜 索 过 程 进 行 进 一 步 的 分 析, 会 发 现 对 于 搜 索 过 程 中 的 一 些 结 点, 即 使 不 计 算 ( 或 者 说 不 知 道 ) 其 局 面 评 分, 我 们 也 可 以 通 过 推 理 知 道 它 不 会 影 响 对 博 弈 树 根 的 局 面 评 分 的 计 算 例 如 图 2 所 示 的 博 弈 树 中, 如 果 我 们 的 搜 索 顺 序 是 从 左 到 右, 那 么 实 际 上 我 们 可 以 忽 略 所 有 灰 颜 色 的 结 点 的 局 面 评 分 的 计 算 举 个 更 具 体 的 例 子, 因 为 A 结 点 的 局 面 评 分 是 B 结 点 的 局 面 评 分 与 C 结 点 的 局 面 评 分 的 最 大 值, 而 C 结 点 的 局 面 评 分 是 它 所 有 子 结 点 局 面 评 分 的 最 小 值, 所 以 在 完 成 C 的 第 二 个 子 结 点 的 搜 索 后, 我 们 就 知 道 了 C 的 局 面 评 分 不 会 超 过 4, 因 此 此 时 我 们 就 知 道 A 结 点 的 值 不 会 受 以 C 结 点 为 根 的 子 树 的 影 响, 于 是 对 于 最 左 侧 的 局 面 评 分 为 5 的 灰 色 结 点, 我 们 完 全 可 以 不 对 其 进 行 搜 索 以 上 就 是 Alpha-Beta 剪 枝 的 思 想 当 然 我 们 可 以 在 前 面 给 出 的 Minimax 的 代 码 中 将 上 述 思 想 直 译 实 现, 然 而 我 们 可 以 做 得 更 好 下 面 我 们 介 绍 在 Negamax 上 优 雅 地 实 现 上 述 思 想 的 方 法 我 们 在 搜 索 中 传 递 两 个 值, 第 一 个 值 是 已 搜 索 到 的 对 自 己 的 最 好 值, 我 们 称 它 为 Alpha, 由 于 在 Negamax 中 我 们 是 求 子 结 点 局 面 评 分 的 相 反 数 的 最 大 值, 所 以 任 何 比 Alpha 小 的 值 都 不 会 改 善 我 们 的 搜 索 结 果 第 二 个 值 是 已 确 定 的 对 于 对 手 来 说 最 坏 的 值, 我 们 称 它 为 Beta 这 是 对 手 所 能 承 受 的 最 坏 的 结 果, 我 们 知 道 在 对 手 看 来, 无 论 我 们 做 如 何 的 决 策, 他 总 可 以 找 到 一 个 对 策 不 比 Beta 更 坏 我 们 先 不 讨 论 如 何 确 定 Alpha 与 Beta 值, 而 是 首 先 分 析 一 下 是 裁 剪 是 如 何 发 生 的 如 果 搜 索 过 程 中 我 们 获 得 Beta 或 比 Beta 更 好 的 值, 对 于 我 们 来 说 是 足 够 好 的 事 情, 因 为 此 时 由 Beta 的 定 义 可 知 对 手 一 定 不 会 让 我 们 有 机 会 采 取 某 种 策 略 到 达 当 前 搜 索 过 程 的 局 面, 于 是 我 们 就 可 以 停 止 当 前 结 点 后 续 的 搜 索 (Beta 截 断 ) 注 意 到 上 面 对 裁 剪 的 讨 论 并 没 有 涉 及 到 Alpha, 那 为 什 么 需 要 Alpha 呢? 对 于 给 定 局 面, 如 果 当 前 局 面 在 当 前 搜 索 过 程 中 的 Alpha 和 Beta 值 为 α 与 β, 那 么 仔 细 想 一 下 Alpha 与 Beta 的 定 义 就 会 发 现, 对 于 搜 索 过 程 中 即 将 搜 索 的 该 局 面 的 下 一 个 着 法 所 对 应 的 子 局 面, 它 的 Alpha 和 Beta 值 应 为 -β 与 -α 正 因 如 此, 我 们 同 时 需 要 Alpha 与 Beta 两 个 值, 用 Beta 值 完 成 当 前 局 面 的 剪 枝, 用 Alpha 值 确 定 子 局 面 的 Beta 值 最 后 我 们 讨 论 Alpha 与 Beta 的 确 定 由 上 述 讨 论 我 们 知 道, 一 个 非 根 结 点 的 局 面 的 Alpha 与 Beta 值 初 始 值 可 由 其 父 局 面 的 Alpha 与 Beta 值 确 定, 对 于 根 结 点, 其 Alpha 与 Beta 的 初 始 值 由 定 义 可 知 为 - 与 + 初 始 化 后, 我 们 对 每 一 个 着 法 进 行 搜 索, 并 在 完 成 每 一 次 子 结 点 的 搜 索 后 都 考 虑 对 Alpha 与 Beta 值 的 更 新 由 Alpha 的 定 义 可 知, 如 果 某 个 着 法 的 结 果 小 于 或 等 于 Alpha, 那 么 它 就 是 很 差 的 着 法, 因 此 可 以 抛 弃, 同 时 我 们 对 Alpha 和 Beta 不 做 变 动 如 果 某 个 着 法 的 结 果 大 于 或 等 Beta, 那 么 整 个 结 点 就 作 废 了, 因 为 对 手 不 希 望 走 到 这 个 局 面, 而 它 有 别 的 着 法 可 以 避 免 到 达 这 个 局 面, 因 此 我 们 也 无 需 变 动 Alpha 和 Beta, 直 接 退 出 当 前 结 点 的 搜 索 如 果 某 个 着 法 5

的 结 果 大 于 Alpha 但 小 于 Beta, 那 么 这 个 着 法 就 是 走 棋 一 方 可 以 考 虑 走 的, 除 非 以 后 有 所 变 化, 由 Alpha 的 定 义, 我 们 将 Alpha 值 改 为 这 个 着 法 的 结 果,Beta 值 不 变 下 面 给 出 伪 代 码, 其 中 星 号 (***) 指 示 了 在 负 值 最 大 搜 索 伪 代 码 上 的 改 动 int AlphaBeta(int depth, int alpha, int beta) { // *** if (depth == 0) { val = -AlphaBeta(depth - 1, -beta, -alpha); // *** if (val >= beta) { // *** return beta; // *** // *** if (val > alpha) { alpha = val; return alpha; 与 调 用 Negamax 函 数 不 同 的 是, 调 用 AlphaBeta 函 数 时 需 要 两 个 额 外 的 参 数, 前 面 的 内 容 告 诉 我 们 这 两 个 额 外 的 参 数 是 - 与 +, 例 如 我 们 要 用 以 上 函 数 完 成 一 个 6 层 的 搜 索, 那 么 我 们 应 该 这 样 调 用 这 个 函 数 : val = AlphaBeta(6, -INFINITY, INFINITY); 这 样 val 就 可 获 得 由 6 层 搜 索 得 到 的 对 当 前 局 面 的 局 面 评 分 我 们 称 上 述 代 码 描 述 的 搜 索 为 Alpha-Beta 搜 索 以 上 代 码 是 所 有 基 于 Alpha-Beta 剪 枝 的 搜 索 的 主 框 架 显 然 在 相 同 层 数 的 搜 索 中,Alpha-Beta 搜 索 遍 历 的 结 点 数 不 会 超 过 极 大 极 小 搜 索, 严 格 的 数 学 分 析 可 以 证 明 在 最 好 情 况 下 Alpha-Beta 搜 索 遍 历 的 结 点 数 只 有 极 大 极 小 搜 索 遍 历 结 点 数 的 平 方 根 那 么 多 实 际 运 行 中,Alpha-Beta 搜 索 的 效 率 极 大 地 依 赖 搜 索 结 点 的 顺 序, 最 坏 情 况 下, 如 果 你 总 是 先 去 搜 索 最 坏 的 着 法, 那 么 Beta 截 断 就 不 会 发 生,Alpha-Beta 搜 索 就 如 同 极 大 极 小 搜 索 一 样, 效 率 非 常 低 因 此 在 实 际 应 用 中, 我 们 会 采 用 一 系 列 技 术 优 化 Alpha-Beta 搜 索 的 搜 索 顺 序, 由 于 这 部 分 问 题 不 是 本 文 讨 论 的 主 题, 这 里 不 做 进 一 步 介 绍 6 窗 口 (Window) 很 多 对 Alpha-Beta 搜 索 的 进 一 步 优 化 的 技 术, 如 许 多 裁 剪 方 法, 期 望 窗 口, 主 要 变 例 搜 索,MTD(f) 等 均 涉 及 到 一 个 共 同 的 概 念 窗 口 简 单 地 说, 窗 口 就 是 指 一 对 Alpha 与 Beta 值 所 表 示 的 一 个 区 间, 这 个 区 间 代 表 了 局 面 评 分 可 能 的 范 围 为 了 记 号 上 的 方 便, 我 们 通 常 用 一 个 二 元 组 (Alpha, Beta) 来 表 示 一 个 窗 口 窗 口 这 个 概 念 有 什 么 用 呢? 下 面 给 出 一 个 例 子 对 于 某 个 给 定 的 局 面 执 行 val= AlphaBeta(6, 1, 4); 并 假 设 执 行 后 变 量 val 的 值 为 3, 注 意 到 1 3 4, 通 过 对 AlphaBeta 函 数 的 定 义 进 行 分 析 后 不 难 推 知, 对 相 同 的 局 面 执 行 val = AlphaBeta(6, -INFINITY, INFINITY); 后 变 量 val 的 值 也 必 定 为 3 我 们 可 以 推 广 观 察 得 到 如 下 一 般 性 的 结 论 : 假 设 我 们 用 窗 口 (Alpha, Beta) 搜 索 获 得 了 评 分 val (1) 如 果 Alpha val Beta, 那 么 该 局 面 的 局 面 评 分 ( 即 用 窗 口 (-INFINITY,INFINITY) 搜 索 获 得 的 评 分 ) 就 是 val (2) 如 果 val Alpha, 那 么 该 局 面 的 局 面 评 分 必 然 小 于 等 于 Alpha (3) 如 果 val Beta, 那 么 该 局 面 的 局 面 评 分 必 然 大 于 等 于 Beta 6

对 于 同 一 个 局 面 的 两 个 不 同 窗 口 的 搜 索 (Alpha1,Beta1) 与 (Alpha2,Beta2), 如 果 Alpha1 Alpha2 Beta2 Beta1, 那 么 使 用 较 小 的 窗 口 (Alpha2,Beta2) 进 行 搜 索 相 比 较 大 的 窗 口 (Alpha1,Beta1) 更 容 易 发 生 Beta 截 断, 从 而 小 窗 口 的 搜 索 遍 历 的 结 点 数 小 于 等 于 大 窗 口 的 搜 索 遍 历 的 结 点 数 尽 管 由 前 面 的 分 析 用 小 窗 口 获 得 的 信 息 不 会 超 过 大 窗 口 获 得 的 信 息, 但 是 同 时 我 们 知 道 小 窗 口 的 搜 索 代 价 也 不 会 超 过 大 窗 口 这 给 了 我 们 一 些 启 发 : 是 否 可 以 通 过 合 理 的 运 用 窗 口, 来 优 化 Alpha-Beta 搜 索 呢? 7 主 要 变 例 搜 索 (Principle Variation Search) 本 节 讨 论 主 要 变 例 搜 索 是 对 Alpha-Beta 搜 索 众 多 改 进 中 最 优 秀 的 之 一 在 Alpha-Beta 剪 枝 一 节 我 们 提 到 过 搜 索 顺 序 对 Alpha-Beta 搜 索 效 率 的 影 响 是 巨 大 的, 而 主 要 变 例 搜 索 对 搜 索 顺 序 更 为 敏 感, 因 为 主 要 变 例 搜 索 的 所 做 的 假 设 就 是 着 法 排 序 是 优 秀 的, 好 的 着 法 排 得 靠 前 因 此 我 们 在 讨 论 主 要 变 例 搜 索 前, 先 假 定 我 们 已 经 在 优 化 搜 索 顺 序 上 做 了 一 些 的 努 力, 获 得 了 比 较 优 秀 着 法 顺 序 的 排 序 我 们 将 Alpha-Beta 搜 索 中 的 结 点 分 为 以 下 三 类, 并 且 任 何 结 点 都 只 属 于 这 三 类 之 一 : 1. Alpha 结 点 每 个 着 法 搜 索 都 会 得 到 一 个 小 于 或 等 于 Alpha 的 值 2. Beta 结 点 至 少 一 个 着 法 会 返 回 大 于 或 等 于 Beta 的 值 3. 主 要 变 例 结 点 (PV 结 点 ) 有 一 个 或 多 个 着 法 会 返 回 大 于 或 等 于 Alpha 的 值 ( 即 PV 着 法 ), 但 是 没 有 着 法 会 返 回 大 于 或 等 于 Beta 的 值 主 要 变 例 搜 索 的 思 想 是 做 出 如 下 假 设 : 当 前 搜 索 结 点 的 着 法 排 序 足 够 好, 以 至 于 如 果 发 现 当 前 搜 索 结 点 的 第 一 个 着 法 的 是 PV 着 法, 那 么 当 前 搜 索 的 结 点 是 PV 结 点, 且 剩 余 的 着 法 均 不 比 这 一 着 法 好 当 然 这 一 假 设 在 实 际 中 不 必 ( 也 很 难 ) 被 满 足, 只 需 要 在 多 数 情 况 下 成 立 就 可 以 ( 即 便 假 设 在 所 有 情 况 下 都 不 成 立, 算 法 的 正 确 性 也 可 以 得 到 保 证, 只 是 此 时 算 法 的 效 率 是 低 下 的 ) 于 是, 主 要 变 例 搜 索 在 当 前 搜 索 结 点 中 如 果 发 现 一 个 PV 着 法, 那 么 对 剩 余 着 法 所 做 的 是 证 明 它 们 都 不 如 所 发 现 的 那 个 PV 着 法 证 明 一 个 着 法 足 够 坏 相 比 计 算 一 个 着 法 的 准 确 值 的 代 价 要 小 很 多, 而 做 出 这 类 证 明 的 方 法 就 是 利 用 窗 口 的 技 巧 当 然, 如 果 主 要 变 例 搜 索 发 现 无 法 给 出 证 明 ( 即 对 于 当 前 局 面 它 的 假 设 是 错 的, 在 剩 余 着 法 中 存 在 比 那 个 PV 着 法 更 好 的 着 法 ), 那 么 它 会 对 这 个 更 好 的 着 法 重 新 进 行 搜 索, 这 次 搜 索 改 为 计 算 其 准 确 的 值, 而 不 再 是 证 明 其 足 够 坏 当 然, 在 这 种 情 况 下, 相 比 Alpha-Beta 搜 索, 我 们 就 会 浪 费 先 前 对 这 个 更 好 的 着 法 是 足 够 坏 的 所 用 的 证 明 时 间 下 面 给 出 伪 代 码, 其 中 星 号 (***) 指 示 了 在 Alpha-Beta 搜 索 上 的 改 动 int AlphaBeta(int depth, int alpha, int beta) { BOOL ffoundpv = FALSE; // *** if (depth == 0) { if (ffoundpv) { // *** val = -AlphaBeta(depth - 1, -alpha - 1, -alpha); // *** if ((val > alpha) && (val < beta)) { // 检 查 失 败 *** val = -AlphaBeta(depth - 1, -beta, -alpha); // *** // *** else // *** val = -AlphaBeta(depth - 1, -beta, -alpha); 7

if (val >= beta) { return beta; if (val > alpha) { alpha = val; ffoundpv = TRUE; // *** return alpha; 算 法 的 核 心 部 分 就 是 函 数 中 间 星 号 (***)if 块 中 的 内 容 如 果 没 有 找 到 PV 结 点, AlphaBeta() 函 数 就 正 常 调 用, 如 果 找 到 了 一 个, 那 么 情 况 就 变 了 不 是 用 常 规 的 窗 口 (Alpha, Beta) 求 着 法 的 准 确 值, 而 是 用 (Alpha, Alpha+1) 来 证 明 它 足 够 坏 如 果 搜 索 返 回 小 于 或 等 于 Alpha 的 值, 便 说 明 我 们 的 假 设 是 正 确 的, 否 则, 即 若 返 回 值 是 Alpha+1 或 更 高, 那 么 搜 索 必 须 用 常 规 窗 口 重 做 8 总 结 从 极 大 极 小 搜 索 开 始, 通 过 一 步 步 改 进 我 们 最 终 获 得 了 主 要 变 例 搜 索, 尽 管 中 间 涉 及 到 了 不 少 的 概 念 分 析 与 思 考, 然 而 最 终 我 们 获 得 的 主 要 变 例 搜 索 是 一 段 优 雅 的 短 代 码, 它 被 用 在 了 成 百 上 千 的 弈 棋 程 序 中, 成 为 这 些 程 序 的 核 心 驱 动 实 际 上, 在 人 际 对 弈 领 域 中, 有 很 多 类 似 的 优 美 的 结 果, 值 得 去 品 味 与 欣 赏 References [1] www.wikipedia.org. [2] www.xqbase.com. 8