研讨班_牛角棋.ppt

牛角棋博弈程序分析与设计 徐心和 徐长明东北大学信息科学与工程学院 2009-01-24东北大学机器博弈研究室民间棋类计算机博弈l最简单的机器博弈项目——机器博弈入门课l麻雀虽小，五脏俱全l从一个实例出发——牛角棋东北大学机器博弈研究室民间棋类的特点l规则简单，很容易入门；l不受专业知识限制；l棋盘小，棋子少，复杂度不高；l输赢容易识别，局面容易判断；l完全信息，编程相对简单；l人工智能的“果蝇”东北大学机器博弈研究室牛角棋 l牛角棋广泛见于各地， 别名较多，如憋死牛、 憋死井、娃娃下山、娘 子下山等l棋盘形状及棋位数目也 稍有差异但是棋子、 棋规都相同东北大学机器博弈研究室牛角棋棋规l红子可上可下，可左可右 ，一次一步，只能走向空 位，不得重合与跳跃；l蓝子只上不下，可左可右 ，一次一步，只能走向空 位，不得重合与跳跃；l胜负判断：憋死憋不死？东北大学机器博弈研究室红先红胜 (7步)东北大学机器博弈研究室红先蓝胜 (18步)为什么输赢？需要不断地摸索经验，试验所有的局面东北大学机器博弈研究室博弈思维过程展开博弈树红方走棋红方走棋蓝方走棋红方先手东北大学机器博弈研究室计算机是如何实现博弈过程的？计算机如何进行博弈思维？如何编写机器博弈程序？东北大学机器博弈研究室计算机如何进行博弈思维？l如何存储思维信息？棋盘、棋子、棋 局、博弈树l如何判断局面的胜负？l如何展开博弈树？l如何选择当前的着法？l如何编写程序？l如何总结博弈的规律？ 东北大学机器博弈研究室如何存储思维信息？l 编码 —— 数据结构l 棋盘编码（棋位编码）l 棋子编码l 初始局面的表示l 棋位向量： (100000023)l 棋子向量：(089)2034567891１２３东北大学机器博弈研究室棋局演化的形式化描述l 状态变量 棋子向量 表示l 初始状态l 状态演化方程l 其中 为棋子i 第n+1步的着法（算子 ）l着法规则：红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃； 蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；东北大学机器博弈研究室着法的形式化描述通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。

203 45 67 891东北大学机器博弈研究室如何判断局面的胜负？l红胜：“逃出”—— l蓝胜：“憋死” —— l和棋——局面的无限次重复203 45 67 891东北大学机器博弈研究室如何展开博弈树？红方走棋红方走 棋蓝方走 棋红方先手东北大学机器博弈研究室如何表示博弈树？东北大学机器博弈研究室两种不同的展开方式广度 优先东北大学机器博弈研究室两种不同的展开方式深度 优先东北大学机器博弈研究室广度优先的展开与存储东北大学机器博弈研究室深度优先的展开与存储东北大学机器博弈研究室如何选择当前的着法？l 在展开的博弈树中搜索——博弈搜索 引擎l 如果红方走棋，他总要找到博弈树中 最好的棋局，而在考虑对方（蓝方） 走棋时，就要考虑最坏的局面，因为 双方都是理智的博弈者，不应该抱有 任何侥幸的心理l 如果给每个棋局打分，那红方可以称 得上是MAX方，蓝方便是MIN方东北大学机器博弈研究室深度为3的博弈树局面（取极大值）局面（取极小值）着法RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3Depth = 3Depth = 2Depth = 1Depth = 0图例：深度层数东北大学机器博弈研究室MAXMAXMIN1298765433213极大极小搜索找到最佳路径与最佳着法东北大学机器博弈研究室MAXMAXMIN1298765433213从极大极小搜索到负极大值搜索Current best PV and best move-3-2-1NegaMaxNegaMax东北大学机器博弈研究室MAXMAXMIN45682434Alpha剪枝α=4找到最佳路径与最佳着法东北大学机器博弈研究室β-剪枝（1）174298MAXMINMIN77由此产生最佳路径和最佳着法β =7东北大学机器博弈研究室β-剪枝（2）835791MAXMINMIN8426由此产生最佳路径和最佳着法448β =4东北大学机器博弈研究室负极大值形式的Alpha-beta搜索lAlpha的含义：当前方已经存在某个着法 ，其估值至少为alpha；lBeta的含义：对手存在着某个着法，令 当前方的着法的估值无论如何也超不过 beta。

l负极大值形式的alpha-beta剪枝只有beta 剪枝东北大学机器博弈研究室（alpha，beta）窗口A1A2A3An…（alpha，beta）Value = -Search()If (Value = beta)A1A2A3An…（alpha，beta）Value = -Search()An（alpha，beta）窗口东北大学机器博弈研究室博弈树搜索过程Move Generation Make MoveMove GenerationMake Move10Evaluation1010UnMake Move1010 121210 12121210 12121210 12121212101212121061212612106121261210613121261210613Cut off121213121061312121312106131212131210613121213121061312121312106131812121312106131818121213121210613181812121312121061318181212131212106131818129998Cut off1212131212106131818129998Best PV东北大学机器博弈研究室人 机 对 弈 信 息 流 程人 机 对 弈 信 息 流 程棋 局 演 化棋手界面引擎着法着法着法着法局面局面局面局面思 考思 考思 考 计 算计 算着法局面 计 算东北大学机器博弈研究室红方先行。

人选红方，输入着法；人选蓝方，输入go东北大学机器博弈研究室Human’s Move人机界面（CHI） 界面更新，胜负判定搜索引擎（递归BEITA-剪枝） Move Generation Make/Unmake Move Evaluation数据结构：棋子棋盘表示 棋局系列，着法列表Root Move牛 角 棋 软 件 结 构东北大学机器博弈研究室棋子的表示#define REDSTONE 0#define BLUESTONE1 1#define BLUESTONE2 22034567891１２３东北大学机器博弈研究室局面的表示（一）l初始局面的表示int board[10] = { REDSTONE,0, 0, 0, 0,0, 0, 0, BLUESTONE1,BLUESTONE2, }; 2034567891１２３东北大学机器博弈研究室局面的表示（二）l初始局面的表示记录有子的交叉点编号 （stone Intersection---si）int si[3] = { 0, 8, 9 };(注意off-by-one错误)2034567891１２３东北大学机器博弈研究室等价的局面表示l等价的初始局面int si[3] = { 0, 8, 9 };int si[3] = { 0, 9, 8 };2034567891１２３东北大学机器博弈研究室着法的表示绝对着法的三个要素Piece：哪个棋子 From：出发点编号 To： 目标点的编号2034567891１２３东北大学机器博弈研究室着法的表示相对着法更方便Piece：哪个棋子 To： 目标点的编号2034567891１２３东北大学机器博弈研究室着法生成l着法生成是和棋类知识关系最为紧密的部分l着法生成是博弈树展开和搜索的先决条件l着法生成是博弈程序中一个相当复杂而且耗 费运算时间的部分l通过良好的数据结构（棋盘表示，着法表示 ），可以显著地提高生成的速度l着法生成 、实现(make move)、评估、选择 之后，还要恢复到父节点(unmake move)东北大学机器博弈研究室着法生成（一）棋盘扫描法//以红子为例 for (each intersection i  ChessBoard) { if((piecei+1 si[BLUESTONE1]) || (si[REDSTONE] > si[BLUESTONE2]) )2）蓝走红胜 ( (wtm == BLUE) &&((si[REDSTONE] & 1 == 0) && ((si[BLUESTONE1] == si[REDSTONE]+1) && (si[BLUESTONE2] == si[REDSTONE]+2) || (si[BLUESTONE1] == si[REDSTONE]+2)&& (si[BLUESTONE2] == si[REDSTONE]+1))) )东北大学机器博弈研究室如何编写机器博弈程序？ l 会下棋，下好棋——了解规则，懂得棋局的好 坏，区分着法的好坏，如何能够克敌制胜，如 何立于不败之地。

l掌握计算机博弈的基本知识——棋局与着法表 示的数据结构，着法生成与棋局评估，博弈树 ，极大极小算法，最佳路径与最佳着法等l按照软件工程编写程序——需求分析，总体设 计，详细设计，编码调试，设计文档，软件维 护，系统优化等等东北大学机器博弈研究室如何总结博弈的规律？l通过博弈树展开，考虑到分枝数不大4, 阶段数有限 （ 15步内可以分出胜负），可以采用穷尽搜索得到 对局的解l将博弈树展开15层，如果不将无意义的循环走棋计 算在内，那么有效博弈树的总节点数为 7436771个，在叶节点上红胜为 532274个，蓝胜为 672个，和棋为 4637870个东北大学机器博弈研究室牛角棋是一个很好的练习l棋局表示l可行着法判别l生成着法，搏弈树展开l棋局评估——胜负判别：红胜，黑胜，和棋l最佳路径的选择l当前着法l知识总结：短兵相接的后果l继续研究：什么情况是和棋？先后手的差别东北大学机器博弈研究室机器博弈的技术构成l信息编码和数据结构l着法生成l棋局评估l基本搜索算法l高级搜索算法——启发式搜索l表、库结构的应用l并行程序设计l引擎控制l人机界面l通信协议东北大学机器博弈研究室机器博弈的技术内涵 l编程语言l程序设计方法学l数据结构l软件工程l搜索原理——AI重要求解方法l模式识别l最优化方法l机器学习与知识挖掘l博弈论（对策论）l ……获取机器博弈知识的主要途径l外文文献l经典的论文和书籍l互联网——wiki、google等l开源代码l如象棋中的Crafty、Fruit等l围棋中的GNU GO等l参加竞赛、学术研讨会等交流lICGA一年一度的赛事和研讨会lCCGC一年一度的赛事和研讨会谢谢！联系：computergames@ 。