人工智能α-β剪枝实现的一字棋实验报告.pdfVIP

人工智能α-β剪枝实现的一字棋实验报告--第1页 实验 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 的原由是机器 ╳ 若赢了，则无论玩家下一步能否会赢，都会走这步必 赢棋。 人工智能α-β剪枝实现的一字棋实验报告--第1页 人工智能α-β剪枝实现的一字棋实验报告--第2页 3. - 剪枝算法 上述的极小极大剖析法，实质是先生成一棵博弈树，而后再计算其倒推值， 至使极小极大剖析法效率较低。 于是在极小极大剖析法的基础上提出了 - 剪枝技术。 - 剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推 值，而且依据评估出的倒推值范围， 实时停止扩展那些已无必需再扩展的子节点， 即相当于剪去了博弈树上的一些分枝， 进而节俭了机器开支， 提升了搜寻效率。 详细的剪枝方法以下： (1) 关于一个与节点 MIN，若能预计出其倒推值的上确界，而且这个 值不大于 MIN 的父节点 (必定是或节点 )的预计倒推值的下确界 ，即，则就不用再 扩展该 MIN 节点的其余子节点了 (由于这些节点的估值对父节点的倒推值已无任何 影响了 )。这一过程称为剪枝。 MIN (2) 关于一个或节点 MAX ，若能预计出其倒推值的下确界 ，而且这个 值不小于 MAX 的父节点 (必定是与节点 )的预计倒推值的上确界 ，即 ，则就不用再扩展该 MAX 节点的其余子节点了 (由于这些节点的估值对 MAX 父节点的倒推值已无任何影响 了)。这一过程称为 剪枝。 从算法中看到：