α-β剪枝实现的一字棋

南 京 大 学 计 算 机 科 学 与 技 术 系 α -β 剪 枝 实 现 的 一 字 棋 051221134 翟 晓 华 2008/5/23

目 录 一 实 验 目 的... 3 二 实 验 环 境... 3 三 实 验 原 理... 3 3.1 游 戏 规 则... 3 3.2 极 小 极 大 分 析 法... 3 3.3 α-β 剪 枝 算 法... 4 3.4 输 赢 判 断 算 法 设 计... 5 四 数 据 结 构... 5 4.1 程 序 流 程... 5 4.2 主 要 成 员 函 数... 6 4.2.1 估 值 函 数... 6 4.2.2 Alpha-Beta 剪 枝 算 法... 7 4.2.3 判 断 胜 负... 7 4.2.4 鼠 标 左 键 响 应... 8 4.2.5 Draw 系 列 函 数... 8 4.2.6 COMPUTER or PLAER 先 手... 8 五 实 验 内 容... 9 5.1 基 本 功 能 简 介... 9 5.2 流 程 图... 10 5.2.1 估 价 函 数... 10 5.2.2 Alpha-Beta 剪 枝... 10 六 实 验 小 结... 12

一 实 验 目 的 学 习 极 大 极 小 搜 索 及 α -β 剪 枝 二 实 验 环 境 (1) 硬 件 环 境 : 网 络 环 境 中 的 微 型 计 算 机 (2) 软 件 环 境 :Windows 操 作 系 统,Microsoft Visual C++ 语 言 三 实 验 原 理 3.1 游 戏 规 则 一 字 棋 游 戏 ( 又 叫 三 子 棋 或 井 字 棋 ), 是 一 款 十 分 经 典 的 益 智 小 游 戏 井 字 棋 的 棋 盘 很 简 单, 是 一 个 3 3 的 格 子, 很 像 中 国 文 字 中 的 井 字, 所 以 得 名 井 字 棋 井 字 棋 游 戏 的 规 则 与 五 子 棋 十 分 类 似, 五 子 棋 的 规 则 是 一 方 首 先 五 子 连 成 一 线 就 胜 利 ; 井 字 棋 是 一 方 首 先 三 子 连 成 一 线 就 胜 利 井 字 棋 ( 英 文 名 Tic-Tac-Toe) 井 字 棋 的 出 现 年 代 估 计 已 不 可 考, 西 方 人 认 为 这 是 由 古 罗 马 人 发 明 的 ; 但 我 们 中 国 人 认 为, 既 然 咱 们 都 发 明 了 围 棋 五 子 棋, 那 发 明 个 把 井 字 棋 自 然 是 不 在 话 下 这 些 纯 粹 是 口 舌 之 争 了, 暂 且 不 提 3.2 极 小 极 大 分 析 法 设 有 九 个 空 格, 由 MAX,MI 二 人 对 弈, 轮 到 谁 走 棋 谁 就 往 空 格 上 放 一 只 自 己 的 棋 子, 谁 先 使 自 己 的 棋 子 构 成 三 子 成 一 线 ( 同 一 行 或 列 或 对 角 线 全 是 某 人 的 棋 子 ), 谁 就 取 得 了 胜 利 用 圆 圈 表 示 MAX, 用 叉 号 代 表 MI 比 如 下 图 中 就 是 MAX 取 胜 的 棋 局 估 价 函 数 定 义 如 下 :

设 棋 局 为 P, 估 价 函 数 为 e(p) (1) 若 P 对 任 何 一 方 来 说 都 不 是 获 胜 的 位 置, 则 e(p)=e( 那 些 仍 为 MAX 空 着 的 完 全 的 行 列 或 对 角 线 的 总 数 )-e( 那 些 仍 为 MI 空 着 的 完 全 的 行 列 或 对 角 线 的 总 数 ) (2) 若 P 是 MAX 必 胜 的 棋 局, 则 e(p)=+ ( 实 际 上 赋 了 60) (3) 若 P 是 B 必 胜 的 棋 局, 则 e(p)=- ( 实 际 上 赋 了 -20) 比 如 P 如 下 图 示, 则 e(p)=5-4=1 需 要 说 明 的 是,+ 赋 60,- 赋 -20 的 原 因 是 机 器 若 赢 了, 则 不 论 玩 家 下 一 步 是 否 会 赢, 都 会 走 这 步 必 赢 棋 3.3 α -β 剪 枝 算 法 上 述 的 极 小 极 大 分 析 法, 实 际 是 先 生 成 一 棵 博 弈 树, 然 后 再 计 算 其 倒 推 值, 至 使 极 小 极 大 分 析 法 效 率 较 低 于 是 在 极 小 极 大 分 析 法 的 基 础 上 提 出 了 α-β 剪 枝 技 术 α-β 剪 枝 技 术 的 基 本 思 想 或 算 法 是, 边 生 成 博 弈 树 边 计 算 评 估 各 节 点 的 倒 推 值, 并 且 根 据 评 估 出 的 倒 推 值 范 围, 及 时 停 止 扩 展 那 些 已 无 必 要 再 扩 展 的 子 节 点, 即 相 当 于 剪 去 了 博 弈 树 上 的 一 些 分 枝, 从 而 节 约 了 机 器 开 销, 提 高 了 搜 索 效 率 具 体 的 剪 枝 方 法 如 下 : (1) 对 于 一 个 与 节 点 MI, 若 能 估 计 出 其 倒 推 值 的 上 确 界 β, 并 且 这 个 β 值 不 大 于 MI 的 父 节 点 ( 一 定 是 或 节 点 ) 的 估 计 倒 推 值 的 下 确 界 α, 即 α β, 则 就 不 必 再 扩 展 该 MI 节 点 的 其 余 子 节

点 了 ( 因 为 这 些 节 点 的 估 值 对 MI 父 节 点 的 倒 推 值 已 无 任 何 影 响 了 ) 这 一 过 程 称 为 α 剪 枝 (2) 对 于 一 个 或 节 点 MAX, 若 能 估 计 出 其 倒 推 值 的 下 确 界 α, 并 且 这 个 α 值 不 小 于 MAX 的 父 节 点 ( 一 定 是 与 节 点 ) 的 估 计 倒 推 值 的 上 确 界 β, 即 α β, 则 就 不 必 再 扩 展 该 MAX 节 点 的 其 余 子 节 点 了 ( 因 为 这 些 节 点 的 估 值 对 MAX 父 节 点 的 倒 推 值 已 无 任 何 影 响 了 ) 这 一 过 程 称 为 β 剪 枝 从 算 法 中 看 到 : (1) MAX 节 点 ( 包 括 起 始 节 点 ) 的 α 值 永 不 减 少 ; (2) MI 节 点 ( 包 括 起 始 节 点 ) 的 β 值 永 不 增 加 在 搜 索 期 间,α 和 β 值 的 计 算 如 下 : (1) 一 个 MAX 节 点 的 α 值 等 于 其 后 继 节 点 当 前 最 大 的 最 终 倒 推 值 (2) 一 个 MI 节 点 的 β 值 等 于 其 后 继 节 点 当 前 最 小 的 最 终 倒 推 值 3.4 输 赢 判 断 算 法 设 计 因 为 每 次 导 致 输 赢 的 只 会 是 当 前 放 置 的 棋 子, 输 赢 算 法 中 只 需 从 当 前 点 开 始 扫 描 判 断 是 否 已 经 形 成 五 子 对 于 这 个 子 的 八 个 方 向 判 断 是 否 已 经 形 成 五 子 如 果 有, 则 说 明 有 一 方 胜 利, 如 果 没 有 则 继 续 搜 索, 直 到 有 一 方 胜 利 或 者 搜 索 完 整 个 棋 盘 四 数 据 结 构 4.1 程 序 流 程 显 示 棋 盘 用 户 输 入 搜 索 深 度 ( 默 认 为 2) 比 赛 结 束 ( 胜 负 平 )? 调 用 AlphaBeta 函 数 计 算 下 一 步 落 子 位 置 选 择 玩 家 先 或 电 脑 先 开 始 游 戏 根 据 玩 家 鼠 标 点 击 位 置 下 棋 电 脑 先 比 赛 结 束 ( 胜 负 平 )? 比 赛 结 束, 提 示 结 果 信 息 调 用 AlphaBeta 函 数 计 算 下 一 步 落 子 位 置

4.2 主 要 成 员 函 数 类 视 图 一 览 : 选 中 部 分 均 为 主 要 函 数 4.2.1 估 值 函 数 估 价 函 数 // 完 成 功 能 : 根 据 输 入 棋 盘, 判 断 当 前 棋 盘 的 估 值, 估 价 函 数 为 课 本 P129 所 讲 : // 若 是 MAX 的 必 胜 局, 则 e = +IFIIT, 这 里 为 +60 // 若 是 MI 的 必 胜 局, 则 e = -IFIIT, 这 里 为 -20, 这 样 赋 值 的 原 因 是 机 器 若 赢 了, 则 不 考 虑 其 它 因 素 // 其 它 情 况, 棋 盘 上 能 使 CUMPUTER 成 三 子 一 线 的 数 目 为 e1 // 棋 盘 上 能 使 PLAER 成 三 子 一 线 的 数 目 为 e2, // e1-e2 作 为 最 终 权 值

// 参 数 : board: 待 评 估 棋 盘 // 返 回 : 评 估 结 果 int CTic_MFCDlg::evaluate(int board[]) 4.2.2 Alpha-Beta 剪 枝 算 法 AlphaBeta 剪 枝 主 函 数 // 完 成 功 能 : 根 据 输 入 棋 盘, 搜 索 深 度, 及 其 他 参 数, 给 出 一 个 相 应 的 最 优 解, 存 入 result 中 // 参 数 : board : 待 评 估 棋 盘 // Depth : 搜 索 深 度 // turn : 当 前 是 机 器 走 (MAX 结 点 ) 还 是 玩 家 走 (MI 结 点 ) // Alpha :alpha 值, 第 一 次 调 用 默 认 -100 // Beta :beta 值, 第 一 次 调 用 默 认 +100 // result: 输 出 结 果 // 返 回 : 若 当 前 点 为 MAX 节 点, 则 返 回 alpha 值 ; // 若 当 前 点 为 MI 节 点, 则 返 回 beta 值 int CTic_MFCDlg::AlphaBeta(int Board[], int Depth, int turn, int Alpha, int Beta, int *result) 4.2.3 判 断 胜 负 // 完 成 功 能 : 根 据 输 入 棋 盘, 判 断 当 前 棋 盘 的 结 果,COMPUTER 胜?PLAER 胜? 平 局? // 参 数 : board: 待 评 估 棋 盘 // 返 回 : -1 表 示 : 尚 未 结 束 // 0 表 示 : 平 局 // 1 表 示 :PLAER 胜

// 2 表 示 :COMPUTER 胜 int CTic_MFCDlg::isWin(int curpos) 4.2.4 鼠 标 左 键 响 应 // 完 成 功 能 : 鼠 标 左 键 相 应, 在 点 击 的 那 格 放 置 玩 家 棋 子, 之 后 再 相 应 计 算 机 走 下 一 步 void CTic_MFCDlg::OnLButtonDown(UIT nflags, CPoint point) 4.2.5 Draw 系 列 函 数 // 完 成 功 能 : 根 据 Chess 棋 盘 数 组 画 出 棋 盘 void CTic_MFCDlg::DrawBoard(CDC *pdc) // 完 成 功 能 : 在 棋 盘 上 画 一 个 O, 电 脑 void CTic_MFCDlg::DrawO(CDC *pdc, int Pos) // 完 成 功 能 : 在 棋 盘 上 画 一 个 X, 玩 家 void CTic_MFCDlg::DrawX(CDC *pdc, int Pos) 4.2.6 COMPUTER or PLAER 先 手 // 完 成 功 能 : 计 算 机 先 走

void CTic_MFCDlg::OnStartCom() // 完 成 功 能 : 玩 家 先 走 void CTic_MFCDlg::OnStartPly() 五 实 验 内 容 5.1 基 本 功 能 简 介 杨 老 师 要 求 最 好 不 要 用 Java 完 成, 因 此 这 里 采 用 C++ 的 MFC 完 成, 总 的 界 面 如 下, 有 以 下 功 能 : 搜 索 树 深 度 的 设 置 ; 机 器 先 手 或 者 玩 家 先 手 ; 游 戏 胜 负 或 者 平 局 判 断 并 且 经 测 试, 有 较 好 的 鲁 棒 性, 例 如 : 1. 鼠 标 在 游 戏 开 始 之 前 或 者 结 束 之 后 点 击 棋 盘 不 会 有 相 应, 并 会 提 示 用 户 先 开 始 游 戏 ; 2. 鼠 标 点 击 棋 盘 区 域 之 外, 不 会 有 相 应 3. 搜 索 深 度 已 经 设 置 区 域 4. 同 一 棋 盘 格 子 点 击 只 响 应 一 次 这 里 需 要 说 明 的 是, 搜 索 深 度 并 非 越 深 越 好, 局 限 于 估 值 函 数 是 根 据 能 够 成 三 子 一 线 的 数 目 决 定 的, 所 以 搜 索 到 最 后 一 层, 如 果 有 人 胜, 则 出 现, 如 果 没 人 胜, 则 三 子 一 线 数 目 为 0, 所 以 毫 无 意

义 如 果 搜 索 深 度 取 到 4 或 者 以 上, 会 发 现 电 脑 会 走 出 一 些 很 笨 的 棋, 就 是 这 个 原 因 经 测 试 发 现, 搜 索 深 度 为 2 时 效 果 最 好, 这 也 是 我 为 什 么 默 认 值 取 2 的 原 因 5.2 流 程 图 5.2.1 估 价 函 数 START 初 始 化 Result 为 0 是 否 判 断 了 每 一 种 三 子 连 线 可 能 取 下 一 种 三 子 连 线 情 况 若 机 器 未 出 现 三 子 连 珠 并 且 有 可 能 出 现 Result+=1 若 机 器 现 三 子 连 珠, 赋 60 作 无 穷 大 Result+=60 若 玩 家 未 出 现 三 子 连 珠 并 且 有 可 能 出 现 Result+=1 若 玩 家 出 现 三 子 连 珠, 赋 -20 作 无 穷 小 Result+=-20 返 回 Result ED 5.2.2 Alpha-Beta 剪 枝

START 接 收 参 数 及 初 始 化 当 前 节 点 是 极 小 值 的 节 点 还 有 可 能 的 走 法? 还 有 可 能 的 走 法? score < Beta score > Alpha 生 成 新 节 点 ( 即 放 下 一 步 棋 ) 生 成 新 节 点 ( 即 放 下 一 步 棋 ) 递 归 搜 索 子 节 点, 得 到 估 价 值 score 取 极 小 值 Beta = score 取 极 大 值 Alpha = score 递 归 搜 索 子 节 点, 得 到 估 价 值 score Alpha >= Beta Alpha >= Beta 撤 销 搜 索 过 的 节 点 ( 即 撤 销 刚 放 下 的 那 步 棋 ) 撤 销 搜 索 过 的 节 点 ( 即 撤 销 刚 放 下 的 那 步 棋 ) 剪 枝, 抛 弃 后 继 节 点 剪 枝, 抛 弃 后 继 节 点 返 回 Alpha 返 回 Beta ED

六 实 验 小 结 通 过 本 次 实 验 进 一 步 对 老 师 课 堂 上 所 讲 的 AlphaBeta 剪 枝 有 了 更 加 深 刻 的 了 解, 对 它 的 一 般 实 现 有 了 初 步 的 认 识 复 习 了 大 二 时 所 学 习 的 C++ 语 言, 并 且 对 MFC 程 序 设 计 有 了 更 深 的 了 解