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

《牛角棋博弈程序分析与设计.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的博弈树,深度,层数,东北大学机器博弈研究室,负极大值形式的Alpha-beta搜索,Alpha的含义：当前方已经存在某个着法，其估

6、值至少为Alpha。Alpha为最佳着法的下界；Beta的含义：对手存在某个着法，令当前方的着法的估值无论如何也超不过Beta。Beta为最佳着法的上界；负极大值形式的Alpha-beta剪枝只有Beta剪枝。,东北大学机器博弈研究室,人机对弈信息流程,东北大学机器博弈研究室,Humans Move,人机界面（CHI）界面更新，胜负判定,搜索引擎（递归BEITA-剪枝）Move GenerationMake/Unmake MoveEvaluation,数据结构：棋子棋盘表示棋局序列，着法列表,Root Move,牛角棋软件结构,软件部分,东北大学机器博弈研究室,计算引擎程序的编写,首先需要解决

7、的算法分析与设计然后考虑算法的实现与编程（编程语言，设计，编码，调试）遵照软件工程学的思想在程序设计方法学上下功夫学习人工智能的先进理论与技术 这是所有专业所必需的！,东北大学机器博弈研究室,东北大学机器博弈研究室,棋子的表示,#define REDSTONE 0#define BLUESTONE1 1#define BLUESTONE2 2,东北大学机器博弈研究室,局面的表示（一）,初始局面的表示int board10=REDSTONE,0,0,0,0,0,0,0,BLUESTONE1,BLUESTONE2,;,东北大学机器博弈研究室,局面的表示（二）,初始局面的表示记录有子的交叉点编号in

8、t si3=0,8,9;(注意off-by-one错误),东北大学机器博弈研究室,等价的局面表示,等价的初始局面int si3=0,8,9;int si3=0,9,8;,东北大学机器博弈研究室,着法的表示,绝对着法的三个要素Piece：哪个棋子From：出发点编号To：目标点的编号,东北大学机器博弈研究室,着法的表示,相对着法更方便Piece：哪个棋子To：目标点的编号涵义：Piece To位：5 4 3 2 1 0,东北大学机器博弈研究室,着法生成,着法生成是和棋类知识关系最为紧密的部分着法生成是博弈树展开和搜索的先决条件着法生成是博弈程序中一个相当复杂而且耗费运算时间的部分通过良好的数据结

9、构（棋盘表示，着法表示），可以显著地提高生成的速度着法生成、生成子节点(make move)、评估、选择之后，还要恢复到父节点(unmake move),东北大学机器博弈研究室,着法生成（一）,棋盘扫描法/以红子为例，可上可下for(each piecei)if(piecei+1=9),东北大学机器博弈研究室,着法生成（二）,预置表法int preTable2105=/*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,

10、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,INV,6,7,9,INV,7,8,INV,;,东北大学机器博弈研究室,着法生成（二）,使用预置表法须注意：根据牛角棋的规则，从预置表中提取的着法需做如下合法性判断：preTable color from i!=si j;(其中，0=4;j=0,1,2)piece,from piece,to,东北大学机器博弈研究室,博弈树的展开与恢复,生成子节点局面MakeMove()撤销子节点局面（恢复

11、到父节点）UnmakeMove(),东北大学机器博弈研究室,这是在中国象棋中标准的用深度优先策略实现的极大极小搜索算法描述。,东北大学机器博弈研究室,牛角棋的搜索算法负极大值形式的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,作业：试用各种算法求解下题,东北大学机器博弈研究室,各种算法至少包括,宽度优先极大极小搜索宽度优先负极大值搜索-搜索负极大值形式的-搜索,东北大学机器

12、博弈研究室,算法优化,博弈树是根在上部向下递归产生的一棵包含所有可能的对弈过程的搜索树，是完全搜索树，包含了所有可能的博弈状态但是，有些情况我们不希望重复搜索，比如重复出现的局面（状态）,东北大学机器博弈研究室,循环局面的处理,Path,搜索过程中循环局面的出现,东北大学机器博弈研究室,循环局面的处理,Path,若 i4 则无循环，注意Pathi与Pathi-4的关系,搜索过程中循环局面的出现,东北大学机器博弈研究室,循环局面的处理,建立一个顺序表，命名为Path。每次搜索前将唯一表示当前局面的值存入表中若当前层为i，判断Pathi是否等于Pathi-4若相等，表示和棋，返回；不等则继续搜索搜

13、索结束，将Pathi 赋值为0较复杂棋类，如象棋，一般用hash表实现循环局面的处理。,东北大学机器博弈研究室,评估（一）,胜利条件红方胜的条件：(siREDSTONE=8)|(siREDSTONE=9)蓝方胜的条件：(siREDSTONE=0)&(siBLUESTONE1+siBLUESTONE2)=3),东北大学机器博弈研究室,蓝走红胜,红走蓝胜,不难看出，短兵相接，谁动谁输。可以整理判据，放到程序当中。,棋局评估胜负提前判别,东北大学机器博弈研究室,评估（二）,总结人类博弈知识影响胜负的重要条件局势细微变化的条件举例（中途判定）1）红子突破，红胜(siREDSTONE siBLUESTO

14、NE1)|(siREDSTONE siBLUESTONE2)2）蓝走红胜(wtm=BLUE)&(siREDSTONE&1=0)&(siBLUESTONE1=siREDSTONE+1)&(siBLUESTONE2=siREDSTONE+2)|(siBLUESTONE1=siREDSTONE+2)&(siBLUESTONE2=siREDSTONE+1),东北大学机器博弈研究室,程序运行结果统计,通过博弈树展开，考虑到分枝数不大4,阶段数有限（10步内可以分出胜负），可以采用穷尽搜索得到对局的解。将博弈树展开15层，如果不将无意义的循环走棋计算在内，那么 有效博弈树的总节点数为 7436771个，在

15、叶节点上红胜为 532274个，黑胜为 672个，和棋为 4637870个。,东北大学机器博弈研究室,如何编写机器博弈程序？,会下棋，下好棋了解规则，懂得棋局的好坏，区分着法的好坏，如何能够克敌制胜，如何立于不败之地。掌握计算机博弈的基本知识棋局与着法表示的数据结构，着法生成与棋局评估，博弈树，极大极小算法，最佳路径与最佳着法等。按照软件工程编写程序需求分析，总体设计，详细设计，编码调试，设计文档，软件维护，系统优化等等。通过反复地对战优化结构与参数对战平台，大量试验，发现问题，提高棋力。,东北大学机器博弈研究室,牛角棋是一个很好的练习,棋局表示可行着法判别生成着法，搏弈树展开棋局评估胜负判别：红胜，黑胜，和棋最佳路径的选择当前着法知识总结：短兵相接谁走谁输,只好敬而远之继续研究，你会发现问题，欢迎提出改进意见,东北大学机器博弈研究室,在游戏软件的编写中提高素质！让创新的火花在机器博弈中迸发！,联系：,