《牛角棋博弈程序分析与设计.ppt》由会员分享，可在线阅读，更多相关《牛角棋博弈程序分析与设计.ppt（49页珍藏版）》请在三一文库上搜索。
1、东北大学机器博弈研究室,牛角棋博弈程序分析与设计,徐心和 徐长明 东北大学机器博弈研究室 2009.5,东北大学机器博弈研究室,主要内容,民间棋类计算机博弈 计算机该如何实现博弈过程的？ 如何存储思维信息？ 如何判断局面的胜负？ 如何展开博弈树？ 如何选择当前的着法？ 从极大极小搜索到负极大值Alpha-bete搜索 计算机引擎程序的编写（C） 用C+编写牛角棋程序 算法优化,东北大学机器博弈研究室,民间棋类计算机博弈,民间棋类的特点 规则简单，很容易入门； 不受专业知识限制； 棋盘小，棋子少，复杂度不高； 输赢容易识别，局面容易判断； 完全信息，编程相对简单； 人工智能的“果蝇”。 麻雀虽小
2、，五脏俱全 从一个实例出发牛角棋 最简单的机器博弈项目机器博弈入门课,东北大学机器博弈研究室,牛角棋,牛角棋广泛见于各地，别名较多，如憋死牛、憋死井、娃娃下山、娘子下山等。 棋盘形状及棋位数目也稍有差异。但是棋子、棋规都相同。,东北大学机器博弈研究室,牛角棋棋规,红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃； 蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃； 胜负判断：憋死憋不死？,东北大学机器博弈研究室,红先红胜 (7步),东北大学机器博弈研究室,红先蓝胜 (18步),为什么输赢？需要不断地摸索经验，试验所有的局面。,东北大学机器博弈研究室,博弈思维过程 展
3、开博弈树,红方走棋,红方走棋,蓝方走棋,红方先手,东北大学机器博弈研究室,现在要考虑的就是 计算机该如何实现这个博弈过程？,如何存储思维信息？棋盘、棋子、棋局、博弈树 如何判断局面的胜负？ 如何展开博弈树？ 如何选择当前的着法？,东北大学机器博弈研究室,如何存储思维信息？,编码 数据结构 棋盘编码（棋位编码） 棋子编码 初始局面的表示 棋位向量：(100000023) 棋子向量：(089),东北大学机器博弈研究室,棋局演化的形式化描述,状态变量 棋子向量表示 初始状态 状态演化方程 其中 为棋子i 第n+1步的着法（算子） 着法规则： 红子可上可下，可左可右，一次一步，只能走向空位，不得重合与
4、跳跃； 蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；,东北大学机器博弈研究室,着法的形式化描述,通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。,东北大学机器博弈研究室,如何判断局面的胜负？,红胜：“逃出” 蓝胜：“憋死” 和棋 局面的无限次重复,东北大学机器博弈研究室,如何展开博弈树？,东北大学机器博弈研究室,牛角棋搜索引擎程序设计 深度优先搜索,选择深度优先搜索方法，可以在搜索过程中的任何时候仅仅生成（Make move）整棵树的一小部分，搜索过的部分被立即删去（Unmake move）。显然，这个算法对内存的要求极低，往往在内存只有几千字节的机器上也可以实现。
5、并且同其他的选择相比，速度上也并不逊色。,东北大学机器博弈研究室,如何选择当前的着法？,在展开的博弈树中搜索博弈搜索引擎 基本原则：考虑到对手的存在 我们想到的内容，对手也一样能想到 对手会阻止我们达到目的 而且，对手会想尽方法使其利益最大化 如果是我方（红方）走棋，那总要找到博弈树中最好的棋局，而在考虑对方（蓝方）走棋时，就要考虑最坏的局面，因为双方都是理智的博弈者，不应该抱有任何侥幸的心理。 如果给每个棋局打分，那红方可以称得上是MAX方，蓝方便是MIN方。 基本方法：博弈树搜索（Max-Min, -, 负极大值-）,东北大学机器博弈研究室,深度为3的博弈树,深度,层数,东北大学机器博弈研
6、究室,负极大值形式的Alpha-beta搜索,Alpha的含义：当前方已经存在某个着法，其估值至少为Alpha。 Alpha为最佳着法的下界； Beta的含义：对手存在某个着法，令当前方的着法的估值无论如何也超不过Beta。 Beta为最佳着法的上界； 负极大值形式的Alpha-beta剪枝只有Beta剪枝。,东北大学机器博弈研究室,人机对弈信息流程,东北大学机器博弈研究室,Humans Move,人机界面（CHI） 界面更新，胜负判定,搜索引擎（递归BEITA-剪枝） Move Generation Make/Unmake Move Evaluation,数据结构：棋子棋盘表示 棋局序列，着
7、法列表,Root Move,牛 角 棋 软 件 结 构,软件部分,东北大学机器博弈研究室,计算引擎程序的编写,首先需要解决的算法分析与设计 然后考虑算法的实现与编程 （编程语言，设计，编码，调试） 遵照软件工程学的思想 在程序设计方法学上下功夫 学习人工智能的先进理论与技术 这是所有专业所必需的！,东北大学机器博弈研究室,东北大学机器博弈研究室,棋子的表示,#define REDSTONE 0 #define BLUESTONE1 1 #define BLUESTONE2 2,东北大学机器博弈研究室,局面的表示（一）,初始局面的表示 int board10 = REDSTONE, 0, 0,
8、0, 0, 0, 0, 0, BLUESTONE1, BLUESTONE2, ;,东北大学机器博弈研究室,局面的表示（二）,初始局面的表示 记录有子的交叉点编号 int si3 = 0, 8, 9 ; (注意off-by-one错误),东北大学机器博弈研究室,等价的局面表示,等价的初始局面 int si3 = 0, 8, 9 ; int si3 = 0, 9, 8 ;,东北大学机器博弈研究室,着法的表示,绝对着法的三个要素 Piece：哪个棋子 From：出发点编号 To： 目标点的编号,东北大学机器博弈研究室,着法的表示,相对着法更方便 Piece：哪个棋子 To： 目标点的编号 涵义：Pi
9、ece To 位： 5 4 3 2 1 0,东北大学机器博弈研究室,着法生成,着法生成是和棋类知识关系最为紧密的部分 着法生成是博弈树展开和搜索的先决条件 着法生成是博弈程序中一个相当复杂而且耗费运算时间的部分 通过良好的数据结构（棋盘表示，着法表示），可以显著地提高生成的速度 着法生成 、生成子节点(make move)、评估、选择之后，还要恢复到父节点(unmake move),东北大学机器博弈研究室,着法生成（一）,棋盘扫描法 /以红子为例，可上可下 for (each piecei) if(piecei+1=9) ,东北大学机器博弈研究室,着法生成（二）,预置表法 int preTab
10、le2105 = /*red stone moves table*/ 2, 1, INV, 2, 3, 0, INV, 4, 3, 1, 0, INV, 5, 4, 2, 1, INV, 6, 5, 3, 2, INV, 7, 6, 4, 3, INV, 8, 7, 5, 4, INV, 9, 8, 6, 5, INV, 9, 7, 6, INV, 8, 7, INV, , /*blue stone moves table*/ INV, 0, INV, 3, 1, 0, INV, 2, 1, INV, 2, 3, 5, INV, 3, 4, INV, 4, 5, 7, INV, 5, 6, I
11、NV, 6, 7, 9, INV, 7, 8, INV, , ;,东北大学机器博弈研究室,着法生成（二）,使用预置表法须注意： 根据牛角棋的规则，从预 置表中提取的着法需做如下合 法性判断： preTable color from i != si j ; ( 其中，0 = 4; j = 0, 1, 2 ) piece, from piece, to,东北大学机器博弈研究室,博弈树的展开与恢复,生成子节点局面 MakeMove ( ) 撤销子节点局面 （恢复到父节点） UnmakeMove ( ),东北大学机器博弈研究室,这是在中国象棋中标准的用深度优先策略实现的极大极小搜索算法描述。,东北大学
12、机器博弈研究室,牛角棋的搜索算法 负极大值形式的alpha-beta搜索算法,东北大学机器博弈研究室,基本搜索流程,搜 索,东北大学机器博弈研究室,13,4,15,18,-5,9,8,7,16,Ply=1,Ply=2,Ply=3,层数 Ply=0,深度 Depth=3,Depth=3,Depth=1,Depth=0,作业：试用各种算法求解下题,东北大学机器博弈研究室,各种算法至少包括,宽度优先极大极小搜索 宽度优先负极大值搜索 -搜索 负极大值形式的-搜索,东北大学机器博弈研究室,算法优化,博弈树是根在上部向下递归产生的一棵包含所有可能的对弈过程的搜索树，是完全搜索树，包含了所有可能的博弈状态
13、 但是，有些情况我们不希望重复搜索，比如重复出现的局面（状态）,东北大学机器博弈研究室,循环局面的处理,Path,搜索过程中循环局面的出现,东北大学机器博弈研究室,循环局面的处理,Path,若 i4 则无循环，注意 Pathi与Pathi-4的关系,搜索过程中循环局面的出现,东北大学机器博弈研究室,循环局面的处理,建立一个顺序表，命名为Path。 每次搜索前将唯一表示当前局面的值存入表中 若当前层为i，判断Pathi是否等于Pathi-4 若相等，表示和棋，返回；不等则继续搜索 搜索结束，将Pathi 赋值为0 较复杂棋类，如象棋，一般用hash表实现循环局面的处理。,东北大学机器博弈研究室,
14、评估（一）,胜利条件 红方胜的条件： (siREDSTONE = 8) | (siREDSTONE = 9) 蓝方胜的条件： (siREDSTONE = 0) & (siBLUESTONE1 + siBLUESTONE2) = 3),东北大学机器博弈研究室,蓝走红胜,红走蓝胜,不难看出，短兵相接，谁动谁输。 可以整理判据，放到程序当中。,棋局评估胜负提前判别,东北大学机器博弈研究室,评估（二）,总结人类博弈知识 影响胜负的重要条件 局势细微变化的条件 举例（中途判定） 1）红子突破，红胜 ( (siREDSTONE siBLUESTONE1) | (siREDSTONE siBLUESTONE
15、2) ) 2）蓝走红胜 ( (wtm = BLUE) & (siREDSTONE & 1 = 0) & (siBLUESTONE1 = siREDSTONE+1) & (siBLUESTONE2 = siREDSTONE+2) | (siBLUESTONE1 = siREDSTONE+2)& (siBLUESTONE2 = siREDSTONE+1) ),东北大学机器博弈研究室,程序运行结果统计,通过博弈树展开，考虑到分枝数不大4, 阶段数有限（10步内可以分出胜负），可以采用穷尽搜索得到对局的解。 将博弈树展开15层，如果不将无意义的循环走棋计算在内，那么 有效博弈树的总节点数为 74367
16、71个， 在叶节点上红胜为 532274个， 黑胜为 672个， 和棋为 4637870个。,东北大学机器博弈研究室,如何编写机器博弈程序？,会下棋，下好棋了解规则，懂得棋局的好坏，区分着法的好坏，如何能够克敌制胜，如何立于不败之地。 掌握计算机博弈的基本知识棋局与着法表示的数据结构，着法生成与棋局评估，博弈树，极大极小算法，最佳路径与最佳着法等。 按照软件工程编写程序需求分析，总体设计，详细设计，编码调试，设计文档，软件维护，系统优化等等。 通过反复地对战优化结构与参数对战平台，大量试验，发现问题，提高棋力。,东北大学机器博弈研究室,牛角棋是一个很好的练习,棋局表示 可行着法判别 生成着法，搏弈树展开 棋局评估胜负判别：红胜，黑胜，和棋 最佳路径的选择 当前着法 知识总结：短兵相接谁走谁输, 只好敬而远之 继续研究，你会发现问题，欢迎提出改进意见,东北大学机器博弈研究室,在游戏软件的编写中 提高素质！ 让创新的火花 在机器博弈中迸发！,联系：,