“理治棋壮”中国象棋计算机博弈引擎程序架构设计与主要算法概述.doc

理 治 棋 壮 中 国 象 棋 计 算 机 博 弈 引 擎 程 序 架 构 设 计 与 主 要 算 法 概 述 理 治 棋 壮 中 国 象 棋 计 算 机 博 弈 引 擎 开 发 小 组 在 各 种 棋 牌 博 弈 当 中, 中 国 象 棋 是 一 种 完 全 知 识 博 弈, 即 参 与 双 方 在 任 何 时 候 都 完 全 清 楚 每 一 个 棋 子 是 否 存 在, 位 于 何 处 中 国 象 棋 规 则 简 单 明 确, 成 功 与 失 败 的 判 定 标 准 简 单, 不 包 含 任 何 机 会 或 偶 然 性, 问 题 的 状 态 在 数 学 意 义 上 是 有 限 的, 因 此 从 理 论 上 讲 易 于 用 计 算 机 人 工 智 能 方 法 实 现 但 象 棋 有 限 的 数 学 状 态 事 实 上 是 一 个 天 文 数 字, 无 法 全 部 计 算 ; 象 棋 的 经 典 开 局 与 残 局 形 式 往 往 是 人 类 经 验 的 总 结, 无 法 用 简 单 的 算 法 泛 泛 表 述, 这 又 造 成 了 计 算 机 实 现 的 不 完 备 性 和 教 条 性 总 的 来 说, 象 棋 对 弈 程 序 是 个 系 统 工 程, 它 是 以 下 几 个 系 统 的 有 机 结 合 : 棋 盘 表 示 着 法 生 成 局 面 评 估 博 弈 树 搜 索 其 它 ( 如 开 局 库 等 ) 理 治 棋 壮 中 国 象 棋 计 算 机 博 弈 引 擎 的 设 计, 参 考 国 内 人 工 智 能 领 域 一 些 较 为 成 熟 的 博 弈 理 论 和 象 棋 算 法, 理 解 并 改 进 后 进 行 计 算 机 实 现 ; 同 时 使 用 机 机 对 战 平 台 与 他 人 的 象 棋 引 擎 进 行 分 析 比 较, 寻 找 弱 点, 加 以 完 善 下 面 我 们 就 程 序 架 构 设 计 与 主 要 算 法 进 行 简 要 介 绍 一 引 擎 架 构 设 计 理 治 棋 壮 中 国 象 棋 计 算 机 博 弈 引 擎 着 法 生 成 模 块 象 棋 界 面 程 序 UCCI 通 讯 模 块 局 面 评 估 模 块 主 控 函 数 博 弈 树 搜 索 模 块 开 局 库 文 件 开 局 库 检 索 模 块 我 们 的 程 序 依 据 系 统 功 能, 可 划 分 为 如 图 所 示 的 几 个 模 块 在 编 码 时, 每 个 模 块 为 一 个 独 立 的 类, 采 用 单 件 的 设 计 模 式 其 中 UCCI 通 信 模 块 使 用 其 制 定 方 提 供 的 现 成 的 代 码 ( 遵 循 GPL 许 可 ) 各 个 模 块 之 间 松 藕 合, 便 于 算 法 替 换 局 部 优 化 和 单 元 测 试 具 体 数 据 结 构 和 接 口 将 在 基 本 数 据 结 构 与 模 块 设 计 说 明 文 档 中 阐 述 1

二 主 要 算 法 概 述 1 棋 盘 表 示 中 国 象 棋 的 棋 盘 是 一 个 9 10 的 矩 阵, 最 容 易 转 化 为 一 个 9 10 的 二 维 数 组, 用 数 组 元 素 表 示 棋 盘 每 一 个 交 叉 点 有 无 棋 子, 是 什 么 棋 子 这 种 表 示 法 清 楚 明 了, 相 关 算 法 与 正 常 象 棋 思 路 一 致, 简 单 易 写, 方 便 在 用 户 界 面 呈 现, 但 算 法 实 现 效 率 比 较 低 为 提 高 算 法 效 率, 一 些 领 域 专 家 提 出 了 比 特 棋 盘 表 示 法, 用 32( 棋 子 种 类 ) 90( 棋 盘 交 叉 点 数 ) 个 64 位 哈 希 数 表 示 每 个 棋 子 在 出 现 在 每 个 交 叉 点 上 的 情 形, 将 所 有 棋 子 的 哈 希 数 求 异 或 得 到 表 示 一 个 局 面 的 哈 希 数 这 种 表 示 法 算 法 充 分 利 用 位 运 算 的 高 效 性, 有 利 于 着 法 生 成 和 局 面 评 估, 但 实 现 的 困 难 度 较 大, 占 用 空 间 较 大, 同 时 不 利 于 局 面 向 用 户 界 面 呈 现 兼 顾 算 法 的 效 率 与 实 现 的 方 便, 我 们 采 用 的 是 目 前 流 行 的 另 一 种 16 16 棋 盘 表 示 法 ( 在 实 现 时 为 运 算 方 便, 用 长 度 为 256 的 一 维 数 组 表 示 ) 这 种 方 法 的 存 储 原 理 与 9 10 的 二 维 数 组 一 致, 但 采 用 16 16 矩 阵 的 中 间 一 块 表 示 棋 盘 这 样 做 的 好 处, 一 方 面 行 列 坐 标 增 量 分 别 为 0x10 0x01, 可 以 用 各 类 位 运 算 表 示 棋 盘 的 变 化, 比 在 9 10 的 二 维 数 组 中 做 乘 除 9 10 的 运 算 快 得 多 ; 另 一 方 面 周 围 一 圈 哨 兵 可 以 避 免 使 用 大 量 边 界 条 件 检 测, 自 动 防 止 棋 子 走 出 棋 盘 边 界 在 这 种 棋 盘 数 组 中, 用 无 符 号 单 字 节 的 整 数 元 素 表 示 有 无 棋 子, 是 什 么 棋 子 例 如 : 红 帅 红 仕 红 相 红 马 红 车 红 炮 红 兵 棋 盘 中 无 子 的 位 置 1 2 3 4 5 6 7 0 黑 将 黑 士 黑 象 黑 马 黑 车 黑 炮 黑 卒 棋 盘 外 的 点 255 254 253 252 251 250 249 99 用 255~249 表 示 黑 方 棋 子, 原 因 是 这 些 数 恰 为 -1~-7 的 8 位 二 进 制 补 码, 与 红 方 棋 子 一 一 对 应, 方 便 程 序 对 棋 子 的 判 断 2

2 着 法 生 成 我 们 需 要 通 过 一 个 局 面, 得 到 指 定 一 方 所 有 可 行 的 着 法, 以 便 分 析 评 估 其 形 成 的 局 面, 得 到 一 个 最 佳 着 法 着 法 的 生 成 过 程 是 遍 历 整 个 棋 盘, 对 所 有 棋 子 列 出 其 符 合 棋 规 的 着 法 ( 有 必 要 排 除 主 动 送 将 和 不 应 将 等 违 规 着 法 ), 记 入 一 个 着 法 表 示 类 的 数 组 所 谓 着 法 表 示 类, 记 录 了 一 种 着 法 的 起 点 终 点 吃 了 什 么 子 是 否 构 成 将 军 在 寻 找 符 合 棋 规 的 着 法 方 面, 我 们 充 分 利 用 16 16 棋 盘 表 示 法 在 计 算 方 面 的 优 势, 对 不 同 的 棋 子, 分 别 采 用 预 置 表 模 板 匹 配 奇 偶 校 验 等 多 种 位 运 算 的 方 法, 提 高 了 算 法 效 率 例 如 下 图 为 马 的 匹 配 模 板, 我 们 用 两 个 数 组 存 储 马 的 落 子 位 置 ( 所 示 ) 和 蹩 马 腿 位 置 ( 所 示 ) 相 对 于 起 始 位 置 的 偏 移 量, 将 其 与 起 始 位 置 相 加, 再 与 棋 盘 相 应 位 置 通 过 位 运 算 进 行 匹 配, 即 可 找 到 其 中 的 可 行 着 法 3 局 面 评 估 局 面 评 估 就 是 给 棋 局 打 分, 识 别 棋 局 的 好 坏, 以 便 在 博 弈 树 搜 索 时 作 为 路 径 选 择 条 件 寻 找 最 佳 着 法 可 行 的 办 法 就 是 对 局 面 进 行 量 化, 通 过 数 值 评 判 棋 局 的 好 坏 由 于 评 估 需 要 大 量 的 象 棋 知 识, 仁 者 见 仁, 智 者 见 智, 评 估 函 数 的 设 计 便 成 为 计 算 机 博 弈 中 最 为 人 性 化 的 部 分 一 般 评 估 函 数 要 综 合 考 虑 以 下 几 个 方 面 : 固 定 子 力 价 值 子 力 位 置 价 值 棋 子 灵 活 度 棋 子 威 胁 / 保 护 棋 子 配 合 作 战 将 帅 安 全 固 定 子 力 价 值 子 力 位 置 价 值 属 于 静 态 局 面 评 估, 我 们 将 其 放 在 同 一 个 函 数 中 完 成, 通 过 遍 历 棋 盘, 将 每 一 棋 子 的 评 估 值 累 加, 一 并 计 算 我 方 与 敌 方 的 评 估 值, 返 回 其 差 值 棋 子 灵 活 度 棋 子 威 胁 / 保 护 属 于 未 来 局 势 发 展 评 估 ; 棋 子 配 合 作 战 将 帅 安 全 属 于 知 识 型 评 估 它 们 也 可 通 过 静 态 局 面 评 估 获 得, 但 这 样 一 来 计 算 量 过 大, 因 此 我 们 将 这 一 块 放 在 着 法 生 成 模 块 动 态 计 算, 只 计 算 走 棋 一 方 所 走 棋 子 的 影 响 由 于 局 面 变 化 的 连 续 性, 这 种 局 部 动 态 计 算 很 大 程 度 上 可 以 反 映 某 一 着 法 对 局 面 整 体 的 影 响 4 博 弈 树 搜 索 博 弈 树 上 的 每 一 个 节 点 都 代 表 一 个 局 面, 每 一 层 的 节 点 都 是 由 其 父 节 点 的 所 有 可 行 着 法 形 成 的 奇 数 层 与 偶 数 层 节 点 分 别 表 示 双 方 的 局 面 引 擎 要 在 众 多 的 叶 子 节 点 上 挑 选 一 个 最 3

佳 的 局 面, 从 而 反 推 到 当 前 的 着 法 作 为 自 己 的 选 择 中 国 象 棋 博 弈 树 的 庞 大 是 可 以 想 象 的 如 果 按 照 每 一 步 平 均 有 45 种 可 行 着 法, 每 局 棋 平 均 走 90 步, 那 从 开 始 局 面 展 开 到 分 出 胜 负, 则 要 考 虑 的 局 面 种 数 比 地 球 上 的 原 子 数 目 还 要 多, 无 法 完 全 计 算, 因 此 只 能 对 有 限 层 次 展 开 分 析 对 由 对 弈 双 方 共 同 产 生 的 博 弈 树 搜 索 问 题, 香 农 (Claude Shannon) 教 授 早 在 1950 年 提 出 了 极 大 - 极 小 算 法 (Minimax Algorithm) 即 将 红 方 局 面 评 估 值 计 为 正, 黑 方 局 面 评 估 值 取 其 负 值, 红 黑 双 方 在 每 一 节 点 分 别 选 择 其 子 节 点 中 评 估 值 绝 对 值 最 大 的 一 个 递 归 深 度 优 先 遍 历 有 限 层 次 的 树, 找 到 使 起 始 节 点 评 估 值 绝 对 值 最 大 的 一 个 局 面, 然 后 通 知 引 擎 走 形 成 这 一 局 面 的 着 法 极 大 - 极 小 算 法 的 改 进 形 式 有 Aspiration Search Principal Variable Search Tolerance Search 等, 目 前 大 多 数 国 际 象 棋 与 中 国 象 棋 的 算 法 核 心 青 睐 速 度 快 而 不 会 出 现 错 误 剪 枝 的 Principal Variable Search, 我 们 的 搜 索 模 块 也 采 用 这 一 算 法 同 时 加 入 迭 代 深 化 搜 索 功 能, 依 局 搜 索 用 时 的 变 化 尽 量 深 化 博 弈 树 搜 索 层 数 此 外, 对 于 博 弈 树 中 的 重 复 节 点, 可 以 利 用 置 换 表 和 历 史 启 发 等 技 术 避 免 重 复 计 算, 直 接 使 用 第 一 次 的 计 算 结 果 代 入 之 后 的 重 复 节 点, 使 用 浅 层 次 的 评 估 结 果 为 深 层 次 待 搜 索 节 点 排 序, 以 节 约 运 算 时 间 5 其 它 ( 如 开 局 库 ) 中 国 象 棋 开 局 的 几 个 回 合 内, 双 方 各 自 展 开 子 力, 占 据 棋 盘 有 利 位 置 如 果 采 用 上 述 通 用 的 博 弈 树 搜 索 方 法 往 往 会 因 为 局 部 很 小 的 利 益 而 忽 视 全 局 的 发 展, 走 出 贻 笑 大 方 的 开 局 象 棋 有 着 经 过 千 锤 百 炼 的 经 典 开 局 着 法, 如 果 将 它 们 存 储 在 数 据 文 件 中, 在 开 局 时 用 查 询 取 代 局 面 评 估 和 博 弈 树 搜 索, 就 可 以 使 我 们 快 速 出 动 子 力, 占 据 有 利 位 置, 同 时 防 止 被 对 手 开 局 的 怪 着 整 昏 我 们 通 过 编 写 小 程 序, 将 从 网 上 收 集 到 的 专 人 整 理 好 的 经 典 开 局 棋 谱 转 化 格 式 作 为 我 们 的 开 局 库 在 博 弈 树 搜 索 模 块 上 挂 接 开 局 库 检 索 模 块, 在 开 局 的 几 个 回 合 内 首 先 将 局 面 交 由 4

开 局 库 检 索 模 块 判 断 如 果 是 库 中 已 存 局 面, 则 直 接 返 回 库 中 指 定 的 着 法, 否 则 才 调 用 博 弈 树 搜 索 此 外 在 残 局 阶 段, 人 类 的 象 棋 知 识 和 判 断 力 往 往 强 于 计 算 机 固 化 的 搜 索 方 式 我 们 的 目 标 是 优 势 求 胜, 下 风 谋 和, 均 势 求 机 考 虑 到 残 局 变 化 的 复 杂 性, 基 于 目 前 国 内 象 棋 残 局 库 研 究 开 发 基 本 还 是 空 白 的 实 现, 我 们 就 不 做 残 局 库 了, 而 是 采 用 迭 代 深 化 的 搜 索 方 式 加 强 对 残 局 的 分 析 能 力 参 考 文 献 : [1] 徐 心 和 王 骄, 中 国 象 棋 计 算 机 博 弈 关 键 技 术 分 析, 小 型 微 型 计 算 机 系 统,Vol.27,No.6, 2006,pp961-969 [2] 王 小 春,PC 游 戏 编 程 ( 人 机 博 弈 ), 重 庆 大 学 出 版 社,2002 [3] 黄 晨, 解 剖 大 象 的 眼 睛 中 国 象 棋 程 序 设 计 探 索, 象 棋 百 科 全 书 网 站 (http://www.elephantbase.net),2005 北 京 理 工 大 学 理 治 棋 壮 中 国 象 棋 计 算 机 博 弈 引 擎 开 发 小 组 版 权 所 有 (2006.7~2006.8) 项 目 主 管 : 林 健 ( 北 京 理 工 大 学 计 算 机 科 学 技 术 学 院 ) 指 导 教 师 : 黄 鸿 ( 北 京 理 工 大 学 信 息 科 学 技 术 学 院 自 动 控 制 系 系 统 工 程 研 究 所 ) 技 术 顾 问 : 赵 陈 翔 ( 北 京 理 工 大 学 软 件 学 院 ) 开 发 人 员 : 林 健 ( 北 京 理 工 大 学 计 算 机 科 学 技 术 学 院 ) 高 然 ( 北 京 理 工 大 学 计 算 机 科 学 技 术 学 院 ) 应 张 彬 ( 北 京 理 工 大 学 软 件 学 院 ) 武 斌 ( 北 京 理 工 大 学 软 件 学 院 ) 联 系 方 式 : lj@linjian.cn( 林 健 ) honghuang@bit.edu.cn( 黄 鸿 ) 5