<4D F736F F D20BCC6CBE3BBFAB2A9DEC4D4ADC0EDD3EBB7BDB7A8D1A7B8C5CAF62E646F63>

Transcription

1 * 计 算 机 博 弈 原 理 与 方 法 学 概 述 徐 心 和 徐 长 明 东 北 大 学 机 器 博 弈 研 究 室, 沈 阳, 摘 要 : 计 算 机 博 弈 伴 随 着 计 算 机 的 诞 生 已 经 开 展 了 大 半 个 世 纪, 并 以 一 系 列 战 胜 人 类 天 才 而 享 誉 世 界 计 算 机 博 弈 在 国 际 上 仍 在 踏 踏 实 实 地 前 进, 然 而 在 中 国 却 难 有 作 为 究 其 原 因 则 是 缺 少 此 方 面 的 宣 传 和 基 础 知 识 的 普 及 为 此 在 研 究 了 大 量 相 关 资 料 的 基 础 上, 对 于 计 算 机 博 弈 原 理 与 方 法 学 进 行 了 概 述 从 分 析 棋 类 游 戏 属 性 和 博 弈 过 程 出 发, 总 结 了 计 算 机 博 弈 的 关 键 内 容 与 技 术, 绘 制 了 博 弈 软 件 的 基 本 结 构 图, 介 绍 了 有 关 数 据 结 构 着 法 生 成 博 弈 树 展 开 棋 局 评 估 基 本 搜 索 算 法 开 局 库 与 残 局 库 等 相 关 知 识 这 是 一 次 探 索 性 的 归 纳 与 提 升, 今 后 还 需 要 不 断 地 完 善 和 补 充 关 键 词 : 计 算 机 博 弈 原 理 与 方 法 学 数 据 结 构 博 弈 树 搜 索 算 法 Summarization of Fundamental and Methodology of Computer Games Xinhe Xu Changming Xu Research Group of Computer Games, Northeastern University Shenyang, , China xuxinhe@ise.neu.edu.cn Abstract: Computer games have developed for more than a half century since the computer emergence, and made a series of great achievements because the computers beat several human world champions. Computer games are advancing steadfastly in west world, but very hard in China. The reasons are lack of the propagation and popularization of computer games. This paper summarizes the fundamental and methodology of computer games based on studying many interrelated materials and some practice. The work starts from the analysis of game attributes and gaming progress, then sums up the main contents and key technologies, figures a basic structure diagram of computer gaming software, introduces some knowledge on data structure, move generation, expanding game tree, state evaluation, basic search algorithms, opening book, endgame database, and so on. This work is an exploration and upgrade research in the area. So it needs to do more for the consummation and perfect next. Keywords: compute games; fundamental and methodology; data structure, game tree, search algorithm 1. 引 言 计 算 机 博 弈 (Computer Games), 也 称 之 为 机 器 博 弈, 就 是 让 计 算 机 可 以 像 人 脑 一 样 进 行 思 维 活 动, 最 终 可 以 下 棋, 下 国 际 象 棋 西 洋 跳 棋 五 子 棋 中 国 象 棋 围 棋 等 等 早 在 计 算 机 诞 生 的 前 夜, 著 名 的 数 学 家 和 计 算 机 学 家 阿 伦 图 灵 (Alan Turing) 便 设 计 了 一 个 能 够 下 国 际 象 棋 的 纸 上 程 序, 并 经 过 一 步 步 的 人 为 推 演, 实 现 了 第 一 个 国 际 象 棋 的 程 序 化 博 弈 [1] 那 些 世 界 上 最 著 名 的 科 学 家, 如 计 算 机 创 始 人 冯. 诺 依 曼 (John von Neumann), 信 * 国 家 自 然 科 学 基 金 资 助 项 目, 合 同 编 号 ( )

2 息 论 创 始 人 科 劳 德. 香 农 (Claude E. Shannon) [2], 人 工 智 能 的 创 始 人 麦 卡 锡 (John McCarthy) 等 人 都 曾 涉 足 计 算 机 博 弈 领 域, 并 做 出 过 非 常 重 要 的 贡 献 从 上 世 纪 40 年 代 计 算 机 诞 生, 计 算 机 博 弈 经 过 一 代 又 一 代 学 者 的 艰 苦 奋 斗 和 坎 坷 历 程, 终 于 在 上 世 纪 的 八 九 十 年 代, 以 计 算 机 程 序 战 胜 棋 类 领 域 的 天 才 而 享 誉 世 界 其 中 最 为 著 名 的 则 是 1997 年 5 月 IBM 深 蓝 战 胜 世 界 棋 王 卡 斯 帕 罗 夫, 成 为 计 算 机 科 学 史 上 一 个 不 朽 的 丰 碑 在 这 之 后, 计 算 机 博 弈 一 天 也 没 有 停 息 过 拼 搏 由 Science 杂 志 评 选 的 2007 年 十 大 科 技 突 破 中, 就 还 包 括 了 加 拿 大 阿 尔 波 特 大 学 的 科 研 成 果 解 决 了 西 洋 跳 棋 (Checker) 博 弈 问 题 [3], 也 就 是 说, 在 西 洋 跳 棋 的 博 弈 中 计 算 机 将 永 远 立 于 不 败 之 地 正 当 世 界 的 目 光 开 始 将 计 算 机 博 弈 的 方 向 聚 焦 在 中 国 象 棋 日 本 将 棋 和 围 棋 博 弈 系 统 的 研 究 与 开 发 的 时 候, 在 中 国 计 算 机 博 弈 却 成 了 被 爱 情 遗 忘 的 角 落 寥 寥 无 几 的 参 与 者, 匮 乏 的 参 考 文 献, 沉 寂 的 计 算 机 博 弈 氛 围, 使 得 计 算 机 博 弈 在 中 国 大 陆 难 有 大 的 作 为 其 中 很 重 要 的 原 因 则 是 缺 少 计 算 机 博 弈 方 面 得 宣 传 和 基 础 知 识 的 普 及, 甚 至 难 以 找 到 论 述 计 算 机 博 弈 原 理 与 方 法 学 的 书 籍 与 资 料 既 然 提 到 原 理 与 方 法 学 的 高 度, 那 就 是 要 研 究 带 有 普 遍 性 的 最 基 本 的 可 以 作 为 其 它 规 律 基 础 的 规 律, 具 有 普 遍 意 义 的 道 理, 研 究 在 计 算 机 博 弈 学 科 上 所 采 用 的 研 究 方 式 方 法 的 综 合 本 文 所 探 讨 的 计 算 机 博 弈 还 仅 仅 是 局 限 于 完 全 信 息 的 棋 类 博 弈 由 于 棋 类 游 戏 为 广 大 群 众 所 喜 爱, 种 类 与 玩 法 十 分 丰 富 这 里 在 归 纳 棋 类 主 要 属 性 和 类 别 ( 第 2 节 ) 的 基 础 上, 第 3 4 节 分 别 给 出 了 计 算 机 博 弈 的 基 本 原 理 与 基 本 方 法, 接 着 ( 第 5 节 ) 介 绍 了 计 算 机 博 弈 的 重 要 组 成 部 分 开 局 库 和 残 局 库, 在 结 语 一 节 还 论 述 了 计 算 机 博 弈 的 学 科 性 质 应 该 看 到 这 是 一 次 探 索 性 的 归 纳 与 提 升, 肯 定 还 有 不 少 缺 陷 与 不 足, 今 后 还 需 要 不 断 地 完 善 和 补 充 2. 棋 类 游 戏 的 分 类 棋 类 游 戏 十 分 丰 富, 有 些 在 国 际 上 广 为 流 行, 也 有 些 是 仅 限 于 地 区 的 民 间 棋 类 而 且 总 会 有 新 的 棋 类 和 新 的 玩 法 在 推 出 因 此 在 研 究 普 遍 的 博 弈 原 理 之 前 有 必 要 对 于 棋 类 的 属 性 和 分 类 进 行 介 绍 2.1 按 参 与 人 数 分 类 (Player): 单 人 游 戏, 如 华 容 道 等 滑 块 类 游 戏 ; 双 人 游 戏, 如 象 棋 围 棋 五 子 棋 等 在 棋 类 中 双 人 参 与 的 棋 类 占 绝 大 多 数 ; 多 人 游 戏, 如 跳 棋 一 般 说 来, 参 与 人 数 越 多, 对 手 就 越 多, 情 况 就 越 发 复 杂 2.2 按 兵 种 多 少 分 类 (Piece-kind) 单 一 兵 种, 如 围 棋 五 子 棋 苏 拉 卡 尔 塔 (Surakarta) 亚 马 逊 (Amazons) 等 ; 多 兵 种, 如 国 际 象 棋 中 国 象 棋 日 本 将 棋 等 兵 种 的 增 加, 意 味 着 着 法 的 复 杂 程 度 增 加, 掌 握 起 来 更 加 困 难 2.3 按 着 法 分 类 (Move) 走 子 类 : 开 局 前 双 方 摆 好, 开 局 后 轮 流 走 动 棋 子 如 象 棋 国 际 象 棋 跳 棋 等 ; 添 子 类 : 开 局 前 盘 面 无 子, 开 局 后 轮 流 放 入 棋 子 如 围 棋 五 子 棋 六 子 棋 等 ; 吃 子 类 : 对 局 过 程 中 可 以 吃 掉 对 方 的 棋 子 如 象 棋 国 际 象 棋 围 棋 等 ; 混 合 类 : 在 填 子 的 过 程 中 可 以 吃 子 ( 围 棋 ); 在 走 子 过 程 中 可 以 吃 子, 还 可 以 填 子 ( 日 本 将 棋 ) 通 常 情 况 弈 棋 双 方 轮 流 施 着 ( 招 ), 各 走 ( 下 ) 一 步 但 是 有 的 棋 类 在 一 定 条 件 下 一 方 是 可 以 连 续 施 着 的, 即 连 续 走 多 步, 可 成 为 轮 (Turn) 如 跳 棋 西 洋 跳 棋 黑 白 棋 (Reversi, Othello) 点 格 棋 (Dots and Boxes) 等

3 2. 4 按 判 决 胜 负 方 式 分 类 (Win-Lose-Draw) 擒 获 首 领 : 象 棋 国 际 象 棋 等 ; 摆 成 形 状 : 连 珠 类 井 字 棋 五 子 棋 六 子 棋 等 ; 占 领 地 域 : 围 棋 点 格 棋 等 ; 剩 余 子 粒 : 黑 白 棋 苏 拉 卡 尔 塔 等 ; 活 动 余 地 : 亚 马 逊 等 ; [4] 到 目 标 地 : 跳 棋 一 字 棋 牛 角 棋 等 3. 计 算 机 博 弈 的 基 本 原 理 3.1 弈 棋 过 程 分 析 为 了 深 入 探 讨 计 算 机 博 弈 的 原 理 与 方 法 学 问 题, 有 必 要 分 析 二 人 对 弈 的 演 化 过 程, 建 立 相 应 的 数 学 模 型 图 3-1 给 出 了 博 弈 状 态 演 化 过 程 图 [5] 图 中 表 明 棋 局 状 态 是 在 着 法 算 子 作 用 下 进 行 演 化 的, 其 对 应 的 状 态 转 移 方 程 可 以 写 成 S n + 1 = S n qn+ 1, S0 = S(0) (3-1) 式 中 S 0 为 棋 局 的 初 始 局 面, q n+ 1 为 第 n+1 步 的 着 法 算 子, 而 S n+ 1 为 下 完 第 n+1 步 后 的 棋 局 于 是, 不 难 写 出 S F = 0 S0 q1 q2... qf = S Q (3-2) 式 中 S 为 终 局, 或 红 胜, 或 黑 胜, 或 和 棋 显 然, 着 法 序 列 Q { q q q... } F 弈 过 程 的 棋 谱 = 便 是 记 载 博 q F 红 方 S 0 q 1 S 1 q 2 S 2 S 2n q 2n+2 q 2n+1 S 2n+1 S F 黑 方 图 3-1 二 人 博 弈 状 态 演 化 过 程 图 弈 棋 的 过 程 是 双 方 轮 流 给 出 着 法, 使 棋 局 向 着 对 本 方 有 利 的 方 向 发 展, 直 至 最 后 的 胜 利 而 弈 棋 的 核 心 是 如 何 给 出 着 法 这 是 一 个 复 杂 的 思 维 过 程, 简 单 说 来 就 是 : 用 着 法 推 演 局 面, 从 有 利 的 局 面 中 选 择 当 前 的 着 法 显 然 如 何 正 确 地 评 估 推 演 出 来 的 局 面 则 是 选 手 棋 力 的 重 要 体 现 3.2 如 何 让 计 算 机 下 棋? 为 了 让 计 算 机 能 够 下 棋, 首 要 的 任 务 就 是 通 过 恰 当 的 数 据 结 构 使 棋 类 要 素 数 字 化, 这 里 包 括 : 棋 盘 棋 子 棋 规 ( 着 法 规 则, 胜 负 规 则 ) 等 为 了 用 着 法 推 演 局 面 和 展 开 博 弈 树, 就 需 要 具 有 着 法 生 成 器, 用 以 生 成 该 局 面 图 3-2 用 着 法 推 演 局 面

4 下 全 部 ( 或 部 分 感 兴 趣 ) 的 着 法 图 3-2 给 出 了 博 弈 者 思 维 过 程 的 机 器 实 现 过 程 框 图 从 而 可 以 产 生 如 图 3-3 所 示 的 博 弈 树 (Game Tree) 节 点 为 局 面, 树 枝 为 着 法, 根 节 点 为 当 前 局 面, 叶 节 点 为 展 开 相 应 深 度 的 终 点 局 面 双 方 轮 流 出 手, 偶 数 层 节 点 属 于 本 方 ( 方 块 表 示 ), 奇 数 层 节 点 属 于 对 方 ( 圆 圈 表 示 ) 如 果 叶 节 点 还 不 是 能 够 给 出 胜 - 负 - 和 的 最 终 局 面, 则 要 对 叶 节 点 进 行 评 估 图 3-3 展 开 深 度 为 4 的 博 弈 树 (Evaluation) 以 便 从 有 利 局 面 选 择 当 前 着 法 这 便 是 博 弈 搜 索 的 职 能 搜 索 引 擎 根 据 极 大 - 极 小 的 搜 索 算 法, 找 到 对 于 本 方 而 言 最 好 的 结 局 和 导 致 最 好 结 局 的 最 佳 路 径 (Principal Variation 主 要 变 例 ), 从 而 找 到 相 应 的 根 着 法 (Root Move) 即 是 本 轮 搜 索 所 寻 求 的 最 佳 着 法 [5] 不 难 看 出, 评 估 和 搜 索 将 成 为 博 弈 软 件 的 重 要 部 分 3.3 计 算 机 博 弈 软 件 的 构 成 根 据 以 上 的 分 析, 可 以 给 出 计 算 机 博 弈 软 件 的 结 构 图 如 图 3-4 所 示 由 于 实 际 的 博 弈 软 件 经 常 是 采 用 递 归 或 迭 代 算 法 实 现 博 弈 树 的 展 开 评 估 与 搜 索 过 程, 图 3-4 只 是 给 出 了 各 功 能 部 件 之 间 的 关 系 甲 方 ( 本 方 ) 博 弈 系 统 得 到 当 前 局 面 的 信 息 之 后, 通 过 复 杂 的 计 算 过 程 便 可 以 给 出 甲 方 当 前 的 着 法 乙 方 ( 对 方 ) 可 以 是 人, 也 可 以 是 另 外 一 个 计 算 机 博 弈 系 统 双 方 通 过 对 战 平 台 实 现 弈 棋 过 程 图 3-4 计 算 机 博 弈 软 件 结 构 图 3.4 棋 局 要 素 的 数 据 结 构 计 算 机 博 弈 数 据 结 构 研 究 的 内 容 所 有 的 棋 局 元 素, 包 括 棋 盘 棋 子 棋 局 着 法 规 则 知 识 等 通 过 数 字 化 ( 编 码 ) 成 为 数 据 元 素, 而 各 种 数 据 元 素 又 以 特 定 的 关 系 构 成 相 应 的 数 据 结 构 进 行 存 储 和 处 理 以 最 为 简 单 的 牛 角 棋 为 例, 见 图 3-5(a) 棋 盘 似 牛 角, 也 像 座 小 山 一 枚 红 子 可 上 可 下, 力 图 突 破 黑 方 的 堵 截, 走 到 山 下 而 两 枚 黑 方 棋 子, 只 上 不 下 ( 可 以 横 走 ), 力 图 将 红 子 堵 回 山 顶 双 方 轮 流 走 棋, 一 方 一 步 此 棋 也 称 之 为 娃 娃 下 山 图 3-5 牛 角 棋 编 码 或 娘 子 下 山, 在 我 国 田 间 地 头 广 为 流 传

5 设 计 牛 角 棋 的 棋 盘 和 棋 子 编 码 如 图 3-5(b) 所 示 10 个 棋 位 编 码 0-9, 红 子 1, 黑 子 2 3 这 样 初 始 棋 局 便 可 有 两 种 形 式 的 表 示 : (1) 棋 位 向 量 (1,0,0,0,0,0,0,0,2,3); (2) 棋 子 向 量 (0,8,9) 如 果 用 p1,p2,p3 表 示 红 黑 3 枚 棋 子 当 前 的 棋 位, 则 p1>p2 或 者 p1>p3 意 味 红 方 获 胜 ; 而 棋 子 向 量 为 (0,1,2) 或 (0,2,1) 则 意 味 黑 方 获 胜 [6] 计 算 机 博 弈 数 字 化 原 则 与 意 义 数 据 结 构 问 题 在 计 算 机 博 弈 中 的 重 要 性 是 不 言 而 喻 的 在 展 开 和 搜 索 博 弈 树 期 间, 数 以 千 百 万 计 的 着 法 和 棋 局 被 生 成 存 储 撤 销, 合 理 的 数 据 结 构 可 以 显 著 地 提 高 搜 索 速 度 和 深 度, 节 省 内 存 空 间, 改 进 博 弈 效 果 数 据 结 构 还 对 编 程 有 着 直 接 的 影 响 以 图 3-5(b) 为 例, 如 果 将 左 右 两 侧 节 点 编 码 互 换, 则 要 给 编 程 带 来 很 大 的 麻 烦 在 采 用 宽 度 优 先 的 搜 索 算 法 中, 新 被 扩 展 的 节 点 应 该 采 用 队 列 结 构 ; 而 在 深 度 优 先 的 搜 索 算 法 中, 则 应 该 采 用 栈 结 构 显 然 编 码 问 题 要 面 向 棋 种 面 向 算 法 面 向 编 程 许 多 情 况 下 适 当 的 冗 余 是 必 要 的 比 如 牛 角 棋 棋 局 的 棋 位 向 量 和 棋 子 向 量 同 时 存 在, 避 免 频 繁 的 相 互 的 转 换, 会 对 棋 局 评 估 和 着 法 生 成 带 来 许 多 的 便 利 哈 希 技 术 与 哈 希 表 在 博 弈 过 程 中 是 经 常 需 要 比 较 两 个 局 面 是 否 相 同 如 果 是 比 较 每 个 棋 子 的 位 置, 或 许 不 需 要 花 很 多 时 间, 但 是 实 战 中 常 常 需 要 比 较 的 局 面 多 得 惊 人 ( 数 以 十 万 百 万 计 ), 如 在 开 局 库 中 寻 找 对 应 的 局 面 于 是 这 一 操 作 的 时 间 和 空 间 开 销 便 成 为 博 弈 搜 索 的 瓶 颈 众 多 棋 类 的 成 功 经 验 表 明, 棋 局 的 存 储 最 好 是 采 用 Zobrist 哈 希 技 术 加 以 实 现 [7], 该 技 术 能 很 容 易 地 将 棋 局 映 射 为 哈 希 数 (Hash Number) 它 的 基 本 原 理 是 先 将 各 个 棋 子 的 代 码 及 其 坐 标 位 置 分 别 映 射 为 一 个 大 的 ( 如 64 位 或 32 位 等 ) 伪 随 机 数, 再 将 棋 盘 上 全 部 棋 子 所 对 应 的 随 机 数 进 行 异 或 求 和 运 算, 最 终 得 到 的 哈 希 数 便 作 为 该 棋 局 的 索 引 值 (Zobrist 键 值 ), 用 作 棋 局 的 存 储 与 查 询 Zobrist 哈 希 数 的 最 大 优 点 就 在 于 它 可 以 增 量 计 算 在 着 法 的 作 用 下, 棋 局 中 的 增 子 减 子 或 挪 子 操 作, 都 能 统 一 地 用 棋 子 变 化 所 对 应 的 哈 希 数 和 表 示 局 面 的 哈 希 数 做 简 单 的 异 或 运 算 来 完 成 博 弈 树 展 开 过 程 中, 会 产 生 大 量 的 因 不 同 着 法 顺 序 而 导 致 的 相 同 局 面 ( 重 复 节 点 ) 要 避 免 不 必 要 的 重 复 计 算, 就 要 把 搜 索 过 的 节 点 随 时 存 储 起 来, 这 就 需 要 一 种 称 为 置 换 表 (Transposition Table) 的 数 据 结 构, 一 般 实 现 为 一 个 哈 希 表 (Hash Tables) 通 常 哈 希 表 可 以 避 免 重 复 节 点 的 重 复 展 开 此 外, 哈 希 表 还 常 保 存 一 些 和 局 面 密 切 相 关 的 重 要 信 息, 例 如, 最 佳 着 法 是 否 受 到 严 重 的 威 胁 等 即 或 需 要 对 该 节 点 重 复 搜 索 时, 存 储 在 哈 希 表 中 的 相 关 信 息 还 会 对 展 开 的 子 树 有 良 好 的 启 发 功 能 [8] 比 特 棋 盘 (Bit Board) 在 着 法 生 成 和 棋 局 评 估 的 过 程 中, 时 常 仅 仅 关 心 一 些 棋 子 的 分 布, 这 时 可 以 用 比 特 棋 盘 ( 亦 称 位 棋 盘 ) 表 示 棋 子 的 某 种 状 态, 它 其 实 是 棋 子 状 态 条 件 的 布 尔 表 示 如 棋 盘 中 哪 些 棋 位 上 有 红 子? 哪 些 棋 位 上 有 黑 车 等 等 比 特 棋 盘 的 定 义 为 B [ b i j ] m n =,, b i, j 式 中 s, 为 棋 位 (i,j) 的 布 尔 条 件 i j [9] 3.5 棋 局 评 估 1 = 0 s s i, j i, j = true = false (3-3)

6 如 果 在 叶 子 节 点 不 能 给 出 胜 - 负 - 和 的 结 果, 那 么 评 价 这 样 的 局 面 对 我 有 利 还 是 不 利, 以 及 有 利 或 不 利 的 程 度, 则 只 能 依 靠 评 估 函 数 了 通 常 设 计 局 面 的 评 估 函 数 需 要 考 虑 如 下 不 同 类 型 的 知 识, 并 通 过 量 化 后 加 权 组 合 而 成 子 力 (Material) 在 象 棋 和 国 际 象 棋 中, 它 是 所 有 子 力 价 值 的 和 在 围 棋 或 黑 白 棋 中, 通 常 计 算 双 方 棋 盘 上 棋 子 的 数 量 但 是 黑 白 棋 有 个 有 趣 的 反 例 : 棋 局 只 由 最 后 的 子 数 决 定, 而 在 中 局 根 据 子 力 来 评 价 却 是 很 差 的 思 路, 因 为 好 的 局 势 下 子 数 通 常 很 少 其 他 像 五 子 棋 一 样 的 游 戏, 子 力 是 没 有 作 用 的, 因 为 局 面 好 坏 仅 仅 取 决 于 棋 子 在 棋 盘 上 的 相 互 位 置, 看 它 是 否 能 够 发 挥 作 用 位 置 (Position) 棋 子 落 于 不 同 的 棋 位 其 作 用 可 能 差 别 很 大 象 棋 中 的 车 占 中 路, 兵 过 河, 马 卧 槽 都 是 具 有 威 胁 性 的 位 置 相 反 如 果 马 窝 心, 兵 下 底 又 都 不 甚 理 想 围 棋 中 的 星 位 也 是 兵 家 必 争 之 地 于 是 不 同 的 位 置 给 予 不 同 的 分 值, 以 表 示 不 同 的 价 值 空 间 (Space) 在 某 些 棋 类 中, 棋 盘 可 以 分 为 本 方 控 制 的 区 域 和 对 方 控 制 的 区 域, 以 及 有 争 议 的 区 域 在 围 棋 中, 这 个 思 想 被 充 分 体 现 而 包 括 象 棋 在 内 的 一 些 棋 类 也 具 有 这 种 概 念, 本 方 的 区 域 包 括 一 些 棋 位, 它 被 本 方 的 棋 子 攻 击 或 保 护, 而 不 被 对 方 棋 子 攻 击 或 保 护 在 黑 白 棋 中, 如 果 一 块 相 连 的 棋 子 占 据 一 个 角, 那 么 这 些 棋 子 就 吃 不 掉 了, 成 为 该 方 的 领 地 空 间 的 评 价 就 是 简 单 地 把 这 些 区 域 加 起 来 如 果 所 含 棋 位 的 重 要 程 度 存 在 差 别, 那 就 在 区 域 的 计 算 上 增 加 棋 位 重 要 性 的 因 素 机 动 性 (Mobility) 各 个 棋 子 的 机 动 性 如 何, 关 系 到 棋 子 可 行 着 法 的 多 少 如 象 棋 中 的 马 是 可 以 马 踏 八 方 的, 但 是 贴 边 或 被 憋 腿, 其 活 动 余 地 大 减 显 然 机 动 性 越 好, 可 行 着 法 越 多, 选 择 有 利 局 势 的 机 会 也 越 多 拍 节 (Tempo) 某 些 情 况 下 起 决 定 作 用 的 不 是 着 法 的 多 少, 而 是 出 招 的 拍 节 和 数 量 的 奇 偶 性 等 以 一 数 学 游 戏 为 例 : 有 两 堆 石 子, 双 方 轮 流 从 石 堆 中 拿 去 几 颗, 每 次 只 能 从 一 堆 石 子 中 拿 走 至 少 一 颗 石 子, 拿 完 最 后 一 堆 者 获 胜 这 个 游 戏 的 诀 窍 是 : 始 终 让 对 方 面 临 两 堆 石 子 一 样 多 的 窘 境 面 向 这 样 的 问 题 时, 先 手 方 只 要 头 一 步 让 两 堆 石 子 数 目 一 样 多 就 可 以 了 然 后 对 手 从 某 一 堆 取 走 几 颗, 先 手 方 便 在 另 一 堆 取 走 同 样 数 量 的 石 子 在 黑 白 棋 和 象 棋 中 都 会 遇 到 这 样 的 问 题 而 对 于 一 字 棋 和 点 格 棋 这 着 则 是 制 胜 的 法 宝 威 胁 (Threat) 威 胁 的 思 想 是 步 步 紧 逼, 或 要 取 胜, 或 要 吃 子, 使 对 方 仅 有 招 架 之 功, 而 无 还 手 之 力 在 五 子 棋 六 子 棋 中 常 常 采 用 基 于 威 胁 的 搜 索, 即 不 断 地 摆 出 强 迫 对 方 防 守 的 棋 型, 成 为 取 胜 的 必 由 之 路 形 状 (Shape) 形 状 的 好 坏 对 于 局 面 的 影 响 一 般 是 长 远 的, 在 浅 层 的 搜 索 中 不 易 发 现 在 象 棋 中, 对 手 的 空 头 跑, 单 车 栓 车 马, 就 都 是 不 好 的 形 状, 最 终 使 本 方 处 于 被 动 的 局 面 对 于 连 珠 棋 一 类 通 过 摆 成 形 状 而 决 定 胜 负 的 棋 类 则 要 计 算 各 种 棋 型 的 数 量, 于 是 形 状 就 成 为 评 估 的 焦 点 图 案 (Motif) 一 些 常 见 的 具 有 鲜 明 特 点 的 图 案, 蕴 涵 着 特 殊 的 意 义 许 多 图 案 在 围 棋 中 称 之 为 模 式, 如 3 3 上 下 文 模 式, 通 过 对 大 量 高 手 对 局 中 的 模 式 提 取 和 出 现 频 率 的 统 计, 构 造 模 式 库, 便 可 以 由 此 提 供 下 一 手 落 子 的 最 佳 位 置 棋 局 性 能 评 估 从 表 面 上 看, 棋 局 评 估 的 越 全 面 越 准 确, 棋 力 性 能 就 会 越 高 其 实 不 然 一 般 说 来,

7 棋 力 性 能 = 知 识 速 度, 时 间 作 为 约 束 条 件 评 估 中 考 虑 的 问 题 越 多 越 细 致, 耗 费 的 时 间 则 越 多, 必 然 影 响 到 单 位 时 间 内 搜 索 节 点 的 数 目, 影 响 到 搜 索 的 速 度 和 深 度 在 博 弈 软 件 的 设 计 中 通 常 存 在 重 知 识 ( 评 估 ) 和 重 速 度 ( 搜 索 深 度 ) 两 种 倾 向, 并 且 都 有 成 功 的 范 例 当 然 能 够 权 衡 利 弊, 将 两 者 有 机 结 合 则 是 最 为 理 想 的 方 案 这 也 是 目 前 共 同 努 力 的 方 向 3.6 博 弈 树 展 开 与 分 析 博 弈 树 是 由 树 枝 和 节 点 构 成 单 向 无 环 图 树 枝 是 着 法, 节 点 是 由 该 着 法 生 成 的 局 面 因 此 博 弈 树 展 开 的 过 程 就 是 着 法 生 成 的 过 程 [8] 着 法 生 成 的 不 同 策 略 (1) 选 择 生 成 根 据 当 前 的 棋 局, 只 生 成 部 分 可 行 的 着 法, 而 不 去 考 虑 其 它 可 行 着 法 比 如 象 棋 在 被 将 军 的 局 面 下, 仅 需 要 考 虑 避 将 着 法, 即 摆 脱 被 将 军 状 态 的 着 法 ; (2) 渐 进 生 成 先 产 生 一 些 着 法, 并 沿 着 某 个 着 法 延 伸 下 去, 直 到 证 明 这 条 路 线 坏 到 足 以 中 止 搜 索 的 程 度, 再 去 生 成 和 搜 索 其 它 的 着 法 比 如 象 棋 中 先 生 成 吃 子 着 法, 然 后 再 考 虑 非 吃 子 着 法 ; (3) 完 全 生 成 一 次 产 生 所 有 的 着 法 显 然 这 是 一 种 稳 妥 而 保 守 的 做 法 [5] 走 子 类 着 法 生 成 方 法 (1) 棋 盘 扫 描 法 ( 含 射 线 法 ) 根 据 棋 规, 在 当 前 棋 局 中 逐 一 找 到 棋 子 可 行 的 落 址 该 方 法 最 为 直 观, 编 程 也 很 简 单 但 是 由 于 需 要 反 复 在 棋 盘 上 扫 瞄, 时 间 开 销 巨 大, 一 般 缺 少 实 战 意 义 (2) 模 板 匹 配 法 对 于 有 特 殊 要 求 的 走 子 类 棋 子, 如 象 棋 中 的 马 和 象, 将 根 据 走 子 规 则 绘 制 的 模 板 套 在 棋 子 当 前 的 位 置 上, 通 过 模 板 找 到 可 行 的 落 址, 形 成 可 行 着 法 (3) 预 置 表 法 这 是 一 种 用 空 间 换 时 间 的 生 成 策 略 将 全 部 棋 子 在 所 有 棋 位 上 的 着 法 都 预 先 放 在 表 中 开 局 时 自 动 生 成, 放 入 内 存 弈 棋 过 程 中 直 接 查 找 以 牛 角 棋 为 例, 红 黑 棋 子 的 全 部 着 法 存 放 在 3 维 的 预 置 表 int pretable 中, 见 图 3-6 第 1 维 区 分 红 黑 棋 子, 第 2 维 对 应 10 个 棋 位, 第 3 维 给 出 在 该 棋 位 上 的 可 能 着 法 落 址,INV 为 着 法 队 列 结 束 符 这 样 就 可 以 根 据 棋 子 当 前 所 在 的 位 置 直 接 查 出 全 部 可 能 的 着 法 当 然 还 要 检 查 该 落 址 是 否 是 空 位 int pretable[2][10][5] = { { /*red stone moves table*/ {2, 1, INV},{2, 3, 0, INV}, {4, 3, 1, 0, INV},{5, 4, 2, 1, INV}, {6, 5, 3, 2, INV}, {7, 6, 4, 3, INV},{8, 7, 5, 4, INV}, {9, 8, 6, 5, INV}, {9, 7, 6, INV},{8, 7, INV}, }, { /*black stone moves table*/ {INV},{0, INV},{3, 1, 0, INV},{2, 1, INV}, {2, 3, 5, INV}, {3, 4, INV}, {4, 5, 7, INV}, {5, 6, INV},{6, 7, 9, INV},{7, 8, INV}, }, }; 图 3-6 牛 角 棋 着 法 预 置 表 [10] 添 子 类 着 法 生 成 方 法 一 般 说 来, 添 子 类 的 着 法 生 成 比 较 直 观, 即 盘 面 上 的 合 法 空 位 便 可 以 落 子 其 中 五 子 棋 和 六 子 棋 最 为 简 单, 下 完 的 棋 子 不 再 会 改 变 黑 白 棋 稍 复 杂 些, 下 完 的 棋 子 可 能 会 被 后 续 着 法 所 变 换 黑 白, 但 每 下 一 子 棋 盘 上 就 多 一 子 围 棋 是 最 复 杂 的, 由 于 存 在 提 子 的 着 法, 所 以 局 势 是 可 逆 的, 对 于 打 劫 这 样 的 着 法 还 需 要 更 为 复 杂 的 处 理 过 程 博 弈 树 展 开 与 分 析 一 颗 完 整 博 弈 树 的 规 模 是 相 当 可 观 的 天 文 数 字 中 国 象 棋 完 整 博 弈 树 的 节 点 数 高 达 , 据 说 地 球 上 全 部 原 子 的 数 目 也 才 有 显 然 是 无 法 全 部 展 开 和 进 行 遍 历 搜 索 即

8 使 选 用 搜 索 速 率 为 1M 节 点 /s 的 计 算 机 系 统, 日 夜 不 停 地 搜 索 100 年, 也 才 只 能 搜 索 9 层 还 达 不 到 一 般 象 棋 大 师 的 水 平 即 或 是 最 简 单 的 牛 角 棋, 如 果 将 博 弈 树 展 开 15 层, 还 不 将 无 意 义 的 循 环 走 棋 的 节 点 计 算 在 内, 那 有 效 博 弈 树 的 总 节 点 数 还 接 近 750 万 个 需 要 特 别 注 意 的 是 博 弈 树 不 同 于 一 般 的 搜 索 树, 它 是 由 对 弈 双 方 共 同 产 生 的 一 种 变 性 搜 索 树 在 图 3-3 中, 本 方 走 棋 时, 它 在 偶 数 层 的 着 法 选 择 是 要 在 其 全 部 子 节 点 中 找 到 评 估 值 最 大 的 一 个, 即 实 行 Max 搜 索 而 其 应 对 方 在 奇 数 层 的 着 法 选 择 则 是 在 其 全 部 子 节 点 中 要 找 到 评 估 值 最 小 的 一 个, 即 实 行 Min 搜 索 如 果 没 有 特 殊 的 搜 索 方 法 那 将 是 非 常 棘 手 的 问 题 幸 好 香 农 (Claude Shannon) 教 授 早 在 1950 年 就 提 出 了 极 大 - 极 小 算 法 (Minimax Algorithm) [2], 从 而 奠 定 了 计 算 机 博 弈 的 理 论 基 础 4. 计 算 机 博 弈 求 解 的 基 本 搜 索 方 法 4.1 优 化 搜 索 与 博 弈 搜 索 搜 索 是 一 个 非 常 宽 泛 的 概 念, 也 是 有 着 广 泛 应 用 领 域 的 技 术 在 各 种 规 划 问 题 中, 如 线 性 规 划 非 线 性 规 划 整 数 规 划 等 ; 在 许 多 优 化 问 题 中, 如 旅 行 商 问 题 计 划 调 度 问 题 等, 在 无 法 得 到 解 析 解 ( 含 数 值 方 法 求 解 ) 的 情 况 下, 便 会 采 取 各 种 启 发 式 搜 索 算 法 如 爬 山 法 分 支 定 界 法 禁 忌 搜 索 模 拟 退 火 遗 传 算 法 蚁 群 算 法 等 等 虽 然 目 前 求 解 此 类 优 化 问 题 的 搜 索 算 法 很 多, 但 是 他 们 有 着 如 下 共 同 的 特 点 : (1) 单 一 决 策 主 体, 即 统 一 的 性 能 指 标 函 数 ; (2) 明 确 的 目 标 函 数 和 约 束 条 件, 通 常 可 以 用 数 学 模 型 来 描 述 ; (3) 基 本 为 静 态 规 划 和 优 化 问 题, 亦 即 单 步 决 策 问 题 计 算 机 博 弈 属 于 博 弈 和 对 策 的 范 畴, 是 由 两 个 非 合 作 主 体 构 成 的 多 步 的 动 态 博 弈 问 题, 对 弈 双 方 有 着 对 立 的 二 人 零 和 的 决 策 目 标, 其 目 标 函 数 难 以 用 数 学 模 型 来 描 述 目 前 能 够 用 以 描 述 的 主 要 是 博 弈 树 而 普 遍 采 用 的 求 解 方 法 就 是 在 博 弈 树 中 搜 索 博 弈 搜 索 的 目 标 就 是 搜 索 最 佳 路 径, 搜 索 当 前 的 最 佳 着 法 ( 根 着 法 ), 并 且 亦 步 亦 趋 地 进 行 下 去 博 弈 搜 索 从 搜 索 方 向 上 可 以 分 为 宽 度 优 先 搜 索 (Breadth-first search) 和 深 度 优 先 搜 索 (Depth-first search) 前 者 能 够 保 证 在 搜 索 树 中 找 到 一 条 通 向 目 标 节 点 的 最 短 途 径 但 是 巨 大 的 时 间 和 空 间 开 销 使 得 它 在 计 算 机 博 弈 中 很 少 采 用 深 度 优 先 搜 索 的 最 大 特 点 就 是 可 以 节 省 大 量 的 节 点 存 储 空 间 因 为 它 通 常 是 采 用 递 归 过 程 来 遍 历 搜 索 树, 即 后 序 遍 历, 得 到 一 个 节 点 值, 就 对 其 子 节 点 做 递 归, 然 后 根 据 他 们 的 返 回 值 来 决 定 自 身 的 返 回 值, 搜 索 过 的 底 层 节 点 也 随 即 撤 销, 因 此 它 所 占 用 的 动 态 空 间 十 分 有 限 Alpha-Beta 剪 枝 和 置 换 表 相 结 合 的 算 法 更 使 得 博 弈 树 的 规 模 被 数 量 级 地 减 少 在 最 好 的 情 况 下, 它 处 理 的 节 点 数 是 纯 粹 的 最 小 - 最 大 搜 索 (Min-Max Search, 亦 称 极 大 - 极 小 搜 索 ) 的 平 方 根 的 两 倍, 可 以 从 15,000,000 个 减 少 到 7,800 个 [10] [11] 4.2 基 于 Alpha-Beta 剪 枝 的 搜 索 目 前 以 国 际 象 棋 为 代 表 的 绝 大 多 数 博 弈 程 序 的 搜 索 算 法 都 是 在 带 置 换 表 的 启 发 式 Alpha-Beta 搜 索 基 础 上 发 展 起 来 的, 这 就 涵 盖 了 极 大 - 极 小 搜 索 Alpha-Beta 搜 索 迭 代 加 深 和 置 换 表 四 方 面 内 容 有 关 置 换 表 (TT) 的 概 念 已 经 在 哈 希 技 术 与 哈 希 表 (3.4.3 节 ) 做 了 简 单 的 介 绍 这 里 仅 对 剪 枝 算 法 和 基 本 搜 索 的 概 念 进 行 必 要 的 阐 述 极 大 - 极 小 搜 索 (Min-Max Search) 由 于 对 弈 双 方 都 很 理 智, 都 想 赢 棋, 在 考 虑 着 法 的 时 候 都 尽 量 想 让 棋 局 朝 着 自 己 的 方 面 转 化, 所 以 在 同 一 颗 博 弈 树 上 ( 图 3-3), 在 不 同 的 层 面 (Ply) 上 就 要 有 不 同 的 选 择 标 准 这 也 就 是 称 之 为 变 性 搜 索 树 原 由 在 偶 数 层 节 点 的 着 法 选 择 是 要 在 其 全 部 子 节 点 中 找 到 评 估 值 最 大 的 一 个, 即 实 行 Max 搜 索 而 在 奇 数 层 节 点 的 着 法 选 择 则 是 在 其 全 部 子 节 点 中 要 找 到 评 估 值 最 小 的 一 个, 即 实 行 Min 搜 索

9 在 进 行 极 大 - 极 小 搜 索 的 时 候, 首 先 要 在 有 限 深 度 内 展 开 全 部 叶 子 节 点, 并 进 行 评 估 然 后 自 下 而 上 地 进 行 搜 索 计 算, 奇 数 层 节 点 取 其 子 节 点 估 值 的 极 小 值, 偶 数 层 节 点 取 其 子 节 点 估 值 的 极 大 值, 一 直 反 推 算 到 根 节 点 在 反 推 的 过 程 中 始 终 要 记 住 算 出 该 值 的 子 节 点 是 谁, 这 样 就 可 以 得 到 一 个 从 根 节 点 到 叶 子 节 点 的 一 条 路 径, 这 就 是 最 佳 路 径, 它 是 双 方 表 现 最 佳 的 对 弈 着 法 序 列 文 献 中 称 其 为 主 要 变 例 (PV) 而 主 要 变 例 的 根 着 法 便 是 本 方 当 前 应 该 选 择 的 着 法 Alpha-Beta 搜 索 (Alpha-Beta Search) Alpha-Beta 搜 索 是 基 于 深 度 优 先 的 搜 索 考 虑 到 极 大 - 极 小 搜 索 的 特 殊 性, 引 进 了 Alpha-Beta 剪 枝 技 术, 使 得 搜 索 的 效 率 显 著 提 高 如 果 博 弈 树 的 局 部 为 偶 层 - 奇 层 - 偶 层 的 关 系, 如 图 4-1 例 题 所 示, 在 搜 完 左 边 一 枝 之 后, 图 4-1 Alpha 剪 枝 示 意 图 父 节 点 得 到 一 个 值 4, 可 以 称 之 为 Alpha 值 ; 如 果 在 接 续 支 路 的 叶 子 节 点 上 发 现 了 一 个 小 于 Alpha 的 节 点, 则 整 个 支 路 便 可 以 剪 掉, 即 没 有 必 要 再 搜 下 去 因 为 根 据 极 小 - 极 大 的 运 算 关 系, 这 一 枝 不 可 能 对 局 面 有 更 好 的 贡 献 不 难 看 出,Alpha 值 始 终 是 本 方 最 佳 着 法 的 下 界 Beta 剪 枝 出 现 在 奇 层 - 偶 层 - 奇 层 的 子 树 部 图 4-2 Beta 剪 枝 示 意 图 分 如 图 4-2 例 题 所 示, 在 搜 完 左 边 一 枝 之 后, 父 节 点 得 到 一 个 值 7, 可 以 称 之 为 Beta 值 ; 如 果 在 接 续 支 路 的 叶 子 节 点 上 发 现 了 一 个 大 于 Beta 的 节 点, 则 整 个 支 路 便 可 以 剪 掉, 即 没 有 必 要 再 搜 下 去 因 为 根 据 极 大 - 极 小 的 运 算 关 系, 这 一 枝 不 可 能 对 局 面 有 更 好 的 贡 献 不 难 看 出,Beta 值 始 终 是 本 方 最 佳 着 法 的 上 界 同 时 也 是 对 手 所 能 承 受 的 最 坏 的 结 果, 因 为 在 对 手 看 来, 他 总 是 会 找 到 一 个 对 策 不 比 Beta 更 坏 的 于 是 由 Alpha-Beta 值 构 成 的 窗 口 便 成 为 最 佳 着 法 的 取 值 范 围, 称 其 为 Alpha-Beta 窗 口 负 极 大 值 算 法 (NegaMax Algorithm) 前 面 谈 到 博 弈 树 的 搜 索 是 一 种 变 性 搜 索 在 偶 数 层 进 行 Max 搜 索, 而 在 奇 数 层 进 行 Min 搜 索 这 无 疑 给 算 法 的 实 现 带 来 一 大 堆 麻 烦 Knuth 和 Moore 充 分 利 用 了 变 性 搜 索 的 内 在 规 律, 在 1975 年 提 出 了 意 义 重 大 的 负 极 大 值 算 法 [12] 它 的 思 想 是 : 父 节 点 的 值 是 各 子 节 点 值 的 变 号 极 大 值, 从 而 避 免 奇 数 层 取 极 小 而 偶 数 层 取 极 大 的 尴 尬 局 面 F v) = max{ F( v ), F( v ),, F( v )} (4-1) ( 1 2 n 其 中 F ( ) 为 节 点 估 值, v, v, 2, vn 为 节 点 v 的 子 节 点 1 此 时 需 要 特 别 注 意 的 则 是, 如 果 叶 节 点 是 红 方 ( 本 方 ) 走 棋, 评 估 函 数 返 回 RedValue-BlackValue, 如 果 是 黑 方 ( 对 方 ) 走 棋, 则 返 回 BlackValue -RedValue 另 外, 由 于 负 极 大 值 计 算 等 价 于 Min 搜 索, 所 以 这 里 仅 进 行 Beta 剪 枝, 不 再 有 Alpha 剪 枝 迭 代 加 深 搜 索 (Iterative deepening search) [13] 在 对 alpha-beta 剪 枝 算 法 进 行 深 入 研 究 之 后, 就 会 发 现 剪 枝 效 果 是 和 着 法 排 序 密 切 相 关 如 果 一 开 始 就 能 从 最 佳 路 径 (PV) 展 开 搜 索, 一 定 会 得 到 一 颗 最 小 的 博 弈 树 显 然 这 是 不 可 能 的, 因 为 搜 索 的 目 标 才 是 最 佳 路 径 但 是 不 难 想 像, 深 度 为 D-1 层 的 PV D-1, 最 有 可

10 能 成 为 深 度 为 D 层 博 弈 树 的 PV 于 是 人 们 便 提 出 了 迭 代 加 深 的 搜 索 算 法 先 搜 索 1 层, 找 到 最 佳 着 法, 再 搜 2 层 的 博 弈 树, 找 到 2 层 的 PV 2 ; 进 而 搜 索 3 层 博 弈 树, 得 到 PV 3 ; 逐 渐 加 深, 直 到 PV D-1 ; 最 后 实 现 对 于 D 层 博 弈 树 的 搜 索 迭 代 加 深 搜 索 的 优 点 在 于 : (1) 在 时 间 受 限 的 情 况 下, 不 知 道 可 能 搜 索 多 深, 此 策 略 可 在 时 限 到 达 时 即 刻 结 束 搜 索, 并 能 给 出 较 好 的 结 果 ; (2) 显 著 提 高 剪 枝 效 果 表 面 上 看, 迭 代 增 加 了 搜 索 的 遍 数, 浪 费 了 一 些 时 间 但 是 有 效 的 剪 枝 可 以 显 著 地 减 少 分 支 因 子, 从 而 提 高 了 搜 索 效 率 图 4-3 给 出 了 迭 代 加 深 搜 索 程 序 流 程 图 其 中 历 史 表 记 载 着 相 应 局 面 下 的 最 佳 走 法 [8] 4.3 基 于 蒙 特 卡 洛 模 拟 的 博 弈 树 搜 索 蒙 特 卡 洛 树 搜 索 (Monte-Carlo Tree Search, MCTS) 是 一 种 最 佳 优 先 搜 索 (Bestfirst search) 算 法, 更 适 合 于 分 支 因 子 很 大 的 博 弈 树 搜 索 比 如 围 棋 分 支 因 子 常 常 大 于 100, 而 亚 马 逊 棋 的 分 子 因 子 可 以 大 于 1000, 采 用 前 述 的 Alpha-Beta 搜 索 算 法 只 能 搜 索 很 浅 的 几 层, 导 致 棋 力 水 平 难 以 提 高 自 从 Bernd Brugmann 等 首 先 将 蒙 特 卡 洛 模 拟 技 术 用 于 围 棋 的 动 态 评 估 [14], 进 而 出 现 把 UCB1(Upper [15] Confidence Bound) 算 法 扩 展 到 树 搜 索 的 UCT(UCB applied to Tree) 算 法 [16], 使 得 在 短 短 的 几 年 中, 九 路 围 棋 的 计 算 机 程 序 已 经 可 以 和 围 棋 高 手 对 弈 了 蒙 特 卡 洛 模 拟 对 局 就 是 从 某 一 棋 局 出 发, 随 机 走 棋 有 人 形 象 地 比 喻, 让 两 个 傻 子 下 棋, 他 们 只 懂 得 棋 规, 不 懂 得 策 略, 最 终 总 是 可 以 决 出 胜 负 这 个 胜 负 是 有 偶 然 性 的 但 是 如 果 让 成 千 上 万 对 傻 子 下 这 盘 棋, 那 么 结 果 的 统 计 还 是 可 以 给 出 该 棋 局 的 固 有 胜 率 和 胜 率 最 高 的 着 法 蒙 特 卡 洛 树 搜 索 通 过 迭 代 来 一 步 步 地 扩 展 博 弈 树 的 规 模,UCT 树 是 不 对 称 生 长 的, 其 生 长 顺 序 也 是 不 能 预 知 的 它 是 根 据 子 节 图 4-3 迭 代 加 深 程 序 流 程 图 点 的 性 能 指 标 导 引 扩 展 的 方 向, 这 一 性 能 指 标 便 是 UCB 值 ( 公 式 4-2) 它 表 示 在 搜 索 过 程 中 既 要 充 分 利 用 已 有 的 知 识, 给 胜 率 高 的 节 点 更 多 的 机 会, 又 要 考 虑 探 索 那 些 暂 时 胜 率 不 高 的 兄 弟 节 点, 这 种 对 于 利 用 (Exploitation) 和 探 索 (Exploration) 进 行 权 衡 的 关 系 便 体 现 在 UCT 着 法 选 择 函 数 的 定 义 上, 即 子 节 点 N i 的 UCB 值 按 如 下 公 式 计 算 lnt( N) X i + C (4-2) t( N ) i 式 中 N 为 给 定 节 点,N i 为 其 子 节 点,t(N) 为 对 N 节 点 的 模 拟 次 数,t(N i ) 为 N i 节 点 被 选 中 的 模 拟 次 数,C 为 加 权 系 数 X i 为 子 节 点 N i 的 收 益 平 均 值 可 见 UCB 公 式 由 两 部 分 组 成, 其

11 中 前 一 部 分 就 是 对 已 有 知 识 的 利 用, 而 后 一 部 分 则 是 对 未 充 分 模 拟 节 点 的 探 索 C 小 偏 重 利 用 ; 而 C 大 则 重 视 探 索 需 要 通 过 实 验 设 定 参 数 来 控 制 访 问 节 点 的 次 数 和 扩 展 节 点 的 阈 值 蒙 特 卡 洛 树 搜 索 (MCTS) 仅 展 开 根 据 UCB 公 式 所 计 算 过 的 节 点, 并 且 会 采 用 一 种 自 动 的 方 式 对 性 能 指 标 好 的 节 点 进 行 更 多 的 搜 索 具 体 步 骤 概 括 如 下 : 1. 由 当 前 局 面 建 立 根 节 点, 生 成 根 节 点 的 全 部 子 节 点, 分 别 进 行 模 拟 对 局 ; 2. 从 根 节 点 开 始, 进 行 最 佳 优 先 搜 索 ; 3. 利 用 UCB 公 式 计 算 每 个 子 节 点 的 UCB 值, 选 择 最 大 值 的 子 节 点 ; 4. 若 此 节 点 不 是 叶 节 点, 则 以 此 节 点 作 为 根 节 点, 重 复 2 5. 直 到 遇 到 叶 节 点, 如 果 叶 节 点 未 曾 经 被 模 拟 对 局 过, 对 这 个 叶 节 点 模 拟 对 局 ; 否 则 为 这 个 叶 节 点 随 机 生 成 子 节 点, 并 进 行 模 拟 对 局 ; 6. 将 模 拟 对 局 的 收 益 ( 一 般 胜 为 1 负 为 0) 按 对 应 颜 色 更 新 该 节 点 及 各 级 祖 先 节 点, 同 时 增 加 该 节 点 以 上 所 有 节 点 的 访 问 次 数 ; 7. 回 到 2, 除 非 此 轮 搜 索 时 间 结 束 或 者 达 到 预 设 循 环 次 数 ; 8. 从 当 前 局 面 的 子 节 点 中 挑 选 平 均 收 益 最 高 的 给 出 最 佳 着 法 由 此 可 见 UCT 算 法 就 是 在 设 定 的 时 间 内 不 断 完 成 从 根 节 点 按 照 UCB 的 指 引 最 终 走 到 某 一 个 叶 节 点 的 过 程 而 算 法 的 基 本 流 程 包 括 了 选 择 好 的 分 支 (Selection) 在 叶 子 节 点 上 扩 展 一 层 (Expansion) 模 拟 对 局 (Simulation) 和 结 果 回 馈 (Backpropagation) 这 样 四 个 部 分 [17] UCT 树 搜 索 还 有 一 个 显 著 优 点 就 是 可 以 随 时 结 束 搜 索 并 返 回 结 果, 在 每 一 时 刻, 对 UCT 树 来 说 都 有 一 个 相 对 最 优 的 结 果 对 于 围 棋 一 类 十 分 复 杂 的 搜 索 对 象, 即 或 进 行 数 百 万 次 的 模 拟 对 局 也 只 能 覆 盖 整 个 博 弈 树 的 很 小 一 部 分 因 此 完 全 随 机 地 选 择 子 节 点 将 会 延 缓 最 优 解 的 收 敛 速 度, 需 要 在 子 节 点 的 随 机 选 择 的 过 程 中 加 入 基 于 围 棋 知 识 的 各 种 策 略, 也 就 是 根 据 这 些 策 略 不 同 的 重 要 程 度 赋 予 不 同 的 随 机 性, 从 而 可 以 得 到 更 高 的 搜 索 效 率 和 和 更 好 的 结 果 这 里 同 样 也 存 在 如 何 权 衡 知 识 与 速 度 之 间 的 矛 盾 问 题 5. 开 局 库 与 残 局 库 5.1 开 局 库 开 局 库 几 乎 是 每 个 棋 类 博 弈 程 序 必 备 的 部 件, 它 的 好 处 在 于 : 即 使 是 再 笨 的 程 序, 开 局 库 能 使 得 它 在 开 局 阶 段 看 上 去 不 那 么 业 余 既 能 防 止 因 为 复 杂 的 搜 索 而 浪 费 大 量 时 间, 也 能 防 止 在 开 局 阶 段 犯 下 战 略 性 的 错 误 [8] 开 局 库 是 将 高 手 开 局 时 的 棋 谱 记 载 下 来, 仿 照 执 行 由 于 开 局 形 式 多 种 多 样, 局 面 常 常 数 以 千 万 计 此 时 必 须 应 用 哈 希 技 术 才 能 方 便 存 储 和 查 找 对 应 于 同 一 局 面 常 常 可 以 有 多 种 着 法, 此 时 应 该 统 计 各 种 着 法 的 胜 率, 作 为 随 机 选 择 时 的 依 据 开 局 库 还 应 该 具 有 自 学 习 的 功 能, 可 以 随 着 程 序 见 识 的 增 长, 补 充 新 鲜 的 定 式, 或 调 整 已 有 着 法 的 胜 率 参 数 5.2 残 局 库 残 局 库 却 不 一 定 是 博 弈 程 序 必 备 的 部 件 只 有 对 于 吃 子 类 棋 类, 当 盘 面 剩 余 子 力 不 多 进 入 残 局 时, 仍 然 按 照 中 局 的 搜 索 算 法 难 以 取 得 良 好 的 效 果 原 因 在 于 : (1) 评 价 指 标 发 生 变 化 多 数 中 局 的 目 标 是 谋 取 优 势, 那 在 残 局 阶 段 则 应 该 是 : 优 势 谋 胜, 劣 势 谋 和, 均 势 谋 机 因 此 如 何 谋 胜 谋 和 的 策 略 显 得 十 分 重 要 于 是 评 价 体 系 需 要 调 整 ; (2) 许 多 局 面 致 胜 的 途 径 十 分 特 殊 和 单 一, 没 有 足 够 深 度 的 搜 索 是 难 以 发 现 的 因 此 如 何 通 过 学 习 算 法 将 博 弈 大 师 丰 富 的 残 局 知 识 存 放 到 博 弈 系 统 中 去, 还 是 很 有

12 挑 战 性 的 研 究 课 题 目 前 国 际 象 棋 根 据 回 溯 算 法 推 演 出 子 数 有 限 的 残 局 库, 但 对 于 中 国 象 棋 [18, 19] 而 言 还 有 许 多 工 作 要 做 6. 结 语 计 算 机 博 弈 原 理 与 方 法 学 既 涉 及 到 博 弈 论 ( 对 策 论 ) 搜 索 原 理 等 理 论 内 容, 又 更 多 地 涉 及 到 数 据 结 构 软 件 工 程 程 序 设 计 方 法 学 等 方 面 的 知 识 计 算 机 博 弈 属 于 计 算 机 科 学 与 应 用 学 科 的 研 究 方 向 之 一, 又 是 人 工 智 能 领 域 的 重 要 研 究 方 向, 应 该 属 于 智 能 科 学 与 技 术 学 科 的 一 个 分 支 虽 然 这 一 方 向 的 研 究 工 作 取 得 了 举 世 瞩 目 的 成 果, 但 是 相 关 的 理 论 与 应 用 技 术 的 归 纳 与 提 升 还 有 很 多 工 作 要 做 这 也 是 把 计 算 机 博 弈 技 术 应 用 到 其 它 领 域 所 不 可 或 缺 的 基 础 性 工 作 本 文 尚 属 一 种 尝 试 性 的 阶 段 性 成 果, 今 后 还 需 要 不 断 充 实 与 完 善 致 谢 : 象 棋 百 科 全 书 网 站 站 长 黄 晨 先 生 提 供 了 丰 富 的 资 料, 不 仅 给 本 文 的 研 究 以 很 大 的 帮 助, 在 中 国 计 算 机 博 弈 领 域 的 影 响 也 是 有 目 共 睹 的, 在 此 一 并 表 示 感 谢 参 考 文 献 [1] Frederic Friedel, michael 译 注. 电 脑 国 际 象 棋 简 史. computerchess/c_briefhistory.htm [2] Shannon, Claude E., Programming a computer for playing chess[j], Philosophical Magazine, Vol. 41: , [3] Science-10-Breakthrough of the Year2007, Dec [4] 罗 鉴 江, 民 间 棋 类 游 戏 [M]. 北 京 : 农 村 读 物 出 版 社 [5] 徐 心 和, 王 骄. 中 国 象 棋 计 算 机 博 弈 关 键 技 术 分 析 [J]. 小 型 微 型 计 算 机 系 统,2006,27(6): [6] 徐 心 和, 王 浩, 孔 凡 禹. 事 件 对 策 理 论 及 在 棋 类 游 戏 中 的 应 用 [J] 年 中 国 智 能 自 动 化 会 议 论 文 集, , 兰 州, 中 南 大 学 学 报 ( 增 刊 ),24-27 [7] Zobrist A. A new Hashing Method with application for game playing[r]. Technical Report88, Computer Science Department, University of Wisconsin, Madison [8] 黄 晨. 电 脑 象 棋 循 序 渐 进. [9] David Eppsten, 黄 晨 译 注. 对 弈 程 序 基 本 技 术 评 价 函 数. computer/evalue_intro1.htm [10] François Dominic Laramée, 黄 晨 译 注. 国 际 象 棋 程 序 设 计. computer/basic_started.htm [11] 王 小 春,PC 游 戏 编 程 [M]. 重 庆 : 重 庆 大 学 出 版 社, 2002 [12] D.E Knuth and R.N Moore,An analyze of Alpha-Beta pruning[j], Artificial Intelligence, Vol,6,1975, pp [13] R E Korf, Depth-first iterative-deepening: An optimal admissible tree search [J]. Artificial Intelligence, 1985, 27(1): [14] Bernd Brugmann, Fohringer Ring 6. Monte Carlo Go. MonteCarloGo.pdf [15] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem [J]. Machine Learning, 47(2/3): , [16] L. Kocsis and C. Szepesvari. Bandit based monte-carlo planning[c]. In 15th European Conference on Machine Learning (ECML), , [17] Guillaume Chaslot, Sander Bakkes, Istvan Szita and Pieter Spronck. Monte-Carlo tree search: A new framework for game AI[C]. Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference [18] Wu R, Beal D F. A memory efficient retrograde algorithm and its application to Chinese chess endgames [J]. More Games of No Chance MSRI Publications Volume 42,2002,

13 [19] H.-r. Fang, T.-s. Hsu, S.-c. Hsu, Construction of Chinese Chess endgame databases by retrograde analysis[c], in: T.A. Marsland, I. Frank (Eds.), Computers and Games 2000, Lecture Notes in Computer Science, Vol. 2063, Springer, New York, 2001,