实验5： -剪枝实现一字棋 一、实验目的 学习极大极小搜索及 - 剪枝算法实现一字棋。 二、实验原理 1.游戏规则 "一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋" 的棋盘很简单，是一个 3×3 的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 2.极小极大分析法 设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 ○ ╳ 用圆圈表示 MAX，用叉号代表 MIN ○ ○ ○ 比如左图中就是 MAX 取胜的棋局。 ╳ ╳ 估价函数定义如下设棋局为 P，估价函数为 e(P)。 (1) 若 P 对任何一方来说都不是获胜的位置，则 e(P)=e(那些仍为 MAX 空着的完全的行、列或对角线的总数)-e(那些仍为 MIN 空着的完全的行、列或对角线的总数) (2) 若 P 是 MAX 必胜的棋局，则 e(P)＝+ （实际上赋了 60）。 (3) 若 P 是 B 必胜的棋局，则 e(P)＝- （实际上赋了-20）。 比如 P 如下图示,则 e(P)=5-4=1 需要说明的是，+ 赋60，- 赋-20 的原因是机器若赢了，则不论玩家下一步是否会 赢，都会 走这 步必赢棋。 3. -剪枝算法 ○ ╳ 2 上 述 的 极 小 极 大 分 析 法 ， 实 际 是 先 生 成 一 棵 博 弈 树 ， 然 后 再 计 算 其 倒 推 值 ，至 使 极 小 极 大 分 析 法 效 率 较 低 。于 是 在 极 小 极 大 分 析 法 的 基 础 上 提 出 了 - 剪 枝技 术 。 - 剪 枝 技 术 的 基 本 思 想 或 算 法 是 ， 边 生 成 博 弈 树 边 计 算 评 估 各 节 点 的 倒推 值 ， 并 且 根 据 评 估 出 的 倒 推 值 范 围 ， 及 时 停 止 扩 展 那 些 已 无 必 要 再 扩 展 的 子 节点 ， 即 相 当 于 剪 去 了 博 弈 树 上 的 一 些 分 枝 ， 从 而 节 约 了 机 器 开 销 ， 提 高 了 搜 索 效率 。 具 体 的 剪 枝 方 法 如 下 ： (1) 对 于 一 个 与 节 点 MIN， 若 能 估 计 出 其 倒 推 值 ...
