牛角棋博弈程序分析与设计.ppt

东北大学机器博弈研究室 牛角棋博弈程序分析与设计 徐心和 徐长明 东北大学机器博弈研究室 2009.5 东北大学机器博弈研究室 主要内容 民间棋类计算机博弈 计算机该如何实现博弈过程的？ 如何存储思维信息？ 如何判断局面的胜负？ 如何展开博弈树？ 如何选择当前的着法？ 从极大极小搜索到负极大值alpha-bete搜索 计算机引擎程序的编写（c） 用c+编写牛角棋程序 算法优化 东北大学机器博弈研究室 民间棋类计算机博弈 民间棋类的特点 规则简单，很容易入门； 不受专业知识限制； 棋盘小，棋子少，复杂度不高； 输赢容易识别，局面容易判断； 完全信息，编程相对简单； 人工智能的“果蝇”。 麻雀虽小，五脏俱全 从一个实例出发牛角棋 最简单的机器博弈项目机器博弈入门课 东北大学机器博弈研究室 牛角棋 牛角棋广泛见于各地，别名较 多，如憋死牛、憋死井、娃娃 下山、娘子下山等。 棋盘形状及棋位数目也稍有差 异。但是棋子、棋规都相同。 东北大学机器博弈研究室 牛角棋棋规 红子可上可下，可左可右，一次 一步，只能走向空位，不得重合 与跳跃； 蓝子只上不下，可左可右，一次 一步，只能走向空位，不得重合 与跳跃； 胜负判断：憋死憋不死？ 东北大学机器博弈研究室 红先红胜 (7步) 东北大学机器博弈研究室 红先蓝胜 (18步) 为什么输赢？需要不断地摸索经验，试验所有的局面。 东北大学机器博弈研究室 博弈思维过程 展开博弈树 红方走棋 红方走棋 蓝方走棋 红方先手 东北大学机器博弈研究室 现在要考虑的就是 计算机该如何实现这个博弈过程？ 如何存储思维信息？棋盘、棋子、棋局、博弈树 如何判断局面的胜负？ 如何展开博弈树？ 如何选择当前的着法？ 东北大学机器博弈研究室 如何存储思维信息？ 编码 数据结构 棋盘编码（棋位编码） 棋子编码 初始局面的表示 棋位向量：(100000023) 棋子向量：(089) 2 0 3 45 67 89 1 东北大学机器博弈研究室 棋局演化的形式化描述 状态变量 棋子向量表示 初始状态 状态演化方程 其中 为棋子i 第n+1步的着法（算子） 着法规则： 红子可上可下，可左可右，一次一步，只能走向空位 ，不得重合与跳跃； 蓝子只上不下，可左可右，一次一步，只能走向空位 ，不得重合与跳跃； 东北大学机器博弈研究室 着法的形式化描述 通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。 2 0 3 4 5 67 89 1 东北大学机器博弈研究室 如何判断局面的胜负？ 红胜：“逃出” 蓝胜：“憋死” 和棋 局面的无限次重复 2 0 3 4 5 67 89 1 东北大学机器博弈研究室 如何展开博弈树？ 红方走棋 红方走 棋 蓝方走 棋 红方先手 东北大学机器博弈研究室 牛角棋搜索引擎程序设计 深度优先搜索 选择深度优先搜索方法，可以在搜索过程中的任何时候仅 仅生成（make move）整棵树的一小部分，搜索过的部分 被立即删去（unmake move）。显然，这个算法对内存的 要求极低，往往在内存只有几千字节的机器上也可以实现 。并且同其他的选择相比，速度上也并不逊色。 东北大学机器博弈研究室 如何选择当前的着法？ 在展开的博弈树中搜索博弈搜索引擎 基本原则：考虑到对手的存在 我们想到的内容，对手也一样能想到 对手会阻止我们达到目的 而且，对手会想尽方法使其利益最大化 如果是我方（红方）走棋，那总要找到博弈树中最好的棋局，而 在考虑对方（蓝方）走棋时，就要考虑最坏的局面，因为双方都 是理智的博弈者，不应该抱有任何侥幸的心理。 如果给每个棋局打分，那红方可以称得上是max方，蓝方便是 min方。 基本方法：博弈树搜索（max-min, -, 负负极大值值-） 东北大学机器博弈研究室 深度为3的博弈树 局面（取极大值）局面（取极小值） 着法 root root moves leaves ply = 0 ply = 1 ply = 2 ply = 3 depth = 3 depth = 2 depth = 1 depth = 0 图例： 深度层数 东北大学机器博弈研究室 负极大值形式的alpha-beta搜索 alpha的含义：当前方已经存在某个着法，其估值至 少为alpha。 alpha为为最佳着法的下界； beta的含义：对手存在某个着法，令当前方的着法 的估值无论如何也超不过beta。 beta为为最佳着法的上界； 负极大值形式的alpha-beta剪枝只有beta剪枝。 东北大学机器博弈研究室 人 机 对 弈 信 息 流 程 棋 局 演 化 棋手界面引擎 着法 着法 着法 着法 局面 局面 局面 局面 思 考 思 考 思 考 计 算 计 算 着法局面 计 算 东北大学机器博弈研究室 humans move 人机界面（chi） 界面更新，胜负判定 搜索引擎（递归beita-剪枝） move generation make/unmake move evaluation 数据结构：棋子棋盘表示 棋局序列，着法列表 root move 牛 角 棋 软 件 结 构 软件部分 东北大学机器博弈研究室 计算引擎程序的编写 首先需要解决的算法分析与设计 然后考虑算法的实现与编程 （编程语言，设计，编码，调试） 遵照软件工程学的思想 在程序设计方法学上下功夫 学习人工智能的先进理论与技术 这是所有专业所必需的！ 东北大学机器博弈研究室 东北大学机器博弈研究室 棋子的表示 #define redstone 0 #define bluestone1 1 #define bluestone2 2 2 0 3 45 67 89 1 0 12 东北大学机器博弈研究室 局面的表示（一） 初始局面的表示 int board10 = redstone, 0, 0, 0, 0, 0, 0, 0, bluestone1, bluestone2, ; 2 0 3 45 67 89 1 0 12 东北大学机器博弈研究室 局面的表示（二） 初始局面的表示 记录有子的交叉点编号 int si3 = 0, 8, 9 ; (注意off-by-one错误) 2 0 3 45 67 89 1 0 12 东北大学机器博弈研究室 等价的局面表示 等价的初始局面 int si3 = 0, 8, 9 ; int si3 = 0, 9, 8 ; 2 0 3 45 67 89 1 0 12 东北大学机器博弈研究室 着法的表示 绝对着法的三个要素 piece：哪个棋子 from：出发点编号 to： 目标点的编号 2 0 3 45 6 7 89 1 0 1 2 东北大学机器博弈研究室 着法的表示 相对着法更方便 piece：哪个棋子 to： 目标点的编号 涵义：piece to 位： 5 4 3 2 1 0 2 0 3 45 6 7 89 1 0 1 2 东北大学机器博弈研究室 着法生成 着法生成是和棋类知识关系最为紧密的部分 着法生成是博弈树展开和搜索的先决条件 着法生成是博弈程序中一个相当复杂而且耗费运算时间 的部分 通过良好的数据结构（棋盘表示，着法表示），可以显 著地提高生成的速度 着法生成 、生成子节点(make move)、评估、选择之后 ，还要恢复到父节点(unmake move) 东北大学机器博弈研究室 着法生成（一） 棋盘扫描法 /以红子为例，可上可下 for (each piecei) if(piecei+1 sibluestone1) | (siredstone sibluestone2) ) 2）蓝走红胜 ( (wtm = blue) & (siredstone & 1 = 0) & (sibluestone1 = siredstone+1) & (sibluestone2 = siredstone+2) | (sibluestone1 = siredstone+2)& (sibluestone2 = siredstone+1) ) 东北大学机器博弈研究室 程序运行结果统计 通过博弈树展开，考虑到分枝数不大4, 阶段数有限（10步内 可以分出胜负），可以采用穷尽搜索得到对局的解。 将博弈树展开15层，如果不将无意义的循环走棋计算在内， 那么 有效博弈树的总节点数为 7436771个， 在叶节点上红胜为 532274个， 黑胜为 672个， 和棋为 4637870个。 东北大学机器博弈研究室 如何编写机器博弈程序？ 会下棋，下好棋了解规则，懂得棋局的好坏，区分 着法的好坏，如何能够克敌制胜，如何立于不败之地。 掌握计算机博弈的基本知识棋局与着法表示的数据 结构，着法生成与棋局评估，博弈树，极大极小算法， 最佳路径与最佳着法等。 按照软件工程编写程序需求分析，总体设计，详细 设计，编码调试，设计文档，软件维护，系统优化等等 。 通过反复地对战优化结构与参数对战平台，大量试 验，发现问题，提高棋力。 东北