研讨班_牛角棋.ppt

《研讨班_牛角棋.ppt》由会员分享，可在线阅读，更多相关《研讨班_牛角棋.ppt（64页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、牛角棋博弈程序分析与设计 徐心和徐心和 徐长明徐长明东北大学信息科学与工程学院东北大学信息科学与工程学院 2009-01-242009-01-24东北大学机器博弈研究室东北大学机器博弈研究室民间棋类计算机博弈l最简单的机器博弈项目 机器博弈入门课l麻雀虽小，五脏俱全l从一个实例出发牛角棋东北大学机器博弈研究室东北大学机器博弈研究室民间棋类的特点l规则简单，很容易入门；l不受专业知识限制；l棋盘小，棋子少，复杂度不高；l输赢容易识别，局面容易判断；l完全信息，编程相对简单；l人工智能的“果蝇”。东北大学机器博弈研究室东北大学机器博弈研究室牛角棋 l牛角棋广泛见于各地，别名较多，如憋死牛、憋死井、

2、娃娃下山、娘子下山等。l棋盘形状及棋位数目也稍有差异。但是棋子、棋规都相同。东北大学机器博弈研究室东北大学机器博弈研究室牛角棋棋规l红子红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃；l蓝子蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；l胜负判断胜负判断：憋死憋不死？东北大学机器博弈研究室东北大学机器博弈研究室红先红胜红先红胜 (7步步)东北大学机器博弈研究室东北大学机器博弈研究室红先蓝胜红先蓝胜(18步步)为什么输赢？需要不断地摸索经验，试验所有的局面。为什么输赢？需要不断地摸索经验，试验所有的局面。东北大学机器博弈研究室东北大学机器博弈研究室博弈思维过程展

3、开博弈树红红方方走走棋棋红红方方走走棋棋蓝蓝方方走走棋棋红方先手红方先手东北大学机器博弈研究室东北大学机器博弈研究室计算机是如何实现博弈过程的？计算机如何进行博弈思维？如何编写机器博弈程序？东北大学机器博弈研究室东北大学机器博弈研究室计算机如何进行博弈思维？l如何存储思维信息？棋盘、棋子、棋局、博弈树l如何判断局面的胜负？l如何展开博弈树？l如何选择当前的着法？l如何编写程序？l如何总结博弈的规律？东北大学机器博弈研究室东北大学机器博弈研究室如何存储思维信息？l 编码 数据结构l 棋盘编码（棋位编码）l 棋子编码l 初始局面的表示l 棋位向量：(100000023)l 棋子向量：(089)20

4、34567891东北大学机器博弈研究室东北大学机器博弈研究室棋局演化的形式化描述l 状态变量 棋子向量表示l 初始状态l 状态演化方程l 其中 为棋子i 第n+1步的着法（算子）l着法规则：红子可上可下红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃；，可左可右，一次一步，只能走向空位，不得重合与跳跃；蓝子只上不下蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；，可左可右，一次一步，只能走向空位，不得重合与跳跃；东北大学机器博弈研究室东北大学机器博弈研究室着法的形式化描述通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。2034567891东北大学机器博弈研

5、究室东北大学机器博弈研究室如何判断局面的胜负？l红胜：“逃出”l蓝胜：“憋死”l和棋 局面的无限次重复2034567891东北大学机器博弈研究室东北大学机器博弈研究室如何展开博弈树？红红方方走走棋棋红红方方走走棋棋蓝蓝方方走走棋棋红方先手红方先手东北大学机器博弈研究室东北大学机器博弈研究室如何表示博弈树？东北大学机器博弈研究室东北大学机器博弈研究室两种不同的展开方式广广度度优先优先东北大学机器博弈研究室东北大学机器博弈研究室两种不同的展开方式深深度度优先优先东北大学机器博弈研究室东北大学机器博弈研究室广广度优先的展开与存储东北大学机器博弈研究室东北大学机器博弈研究室深度优先的展开与存储东北大学

6、机器博弈研究室东北大学机器博弈研究室如何选择当前的着法？l 在展开的博弈树中搜索博弈搜索引擎l 如果红方走棋，他总要找到博弈树中最好的棋局，而在考虑对方（蓝方蓝方）走棋时，就要考虑最坏的局面，因为双方都是理智的博弈者，不应该抱有任何侥幸的心理。l 如果给每个棋局打分，那红方可以称得上是MAX方，蓝方便是MIN方。东北大学机器博弈研究室东北大学机器博弈研究室深度为3的博弈树局面（取极大值）局面（取极大值）局面（取极小值）局面（取极小值）着法着法RootRoot MovesLeavesPly=0Ply=1Ply=2Ply=3Depth=3Depth=2Depth=1Depth=0图例：图例：深度深

7、度层数层数东北大学机器博弈研究室东北大学机器博弈研究室MAXMAXMIN1298765433213极大极小搜索找到最佳路径与最佳着法东北大学机器博弈研究室东北大学机器博弈研究室MAXMAXMIN1298765433213从极大极小搜索到负极大值搜索Current best PV and best move-3-2-1NegaMaxNegaMax东北大学机器博弈研究室东北大学机器博弈研究室MAXMAXMIN45682434Alpha剪枝=4找到最佳路径与最佳着法东北大学机器博弈研究室东北大学机器博弈研究室-剪枝（1）174298MAXMINMIN77由此产生最佳路径和最佳着法由此产生最佳路径和最

8、佳着法=7东北大学机器博弈研究室东北大学机器博弈研究室-剪枝（2）835791MAXMINMIN8426由此产生最佳路径和最佳着法由此产生最佳路径和最佳着法448=4东北大学机器博弈研究室东北大学机器博弈研究室负极大值形式的Alpha-beta搜索lAlpha的含义：当前方已经存在某个着法，其估值至少为alpha；lBeta的含义：对手存在着某个着法，令当前方的着法的估值无论如何也超不过beta。l负极大值形式的alpha-beta剪枝只有beta剪枝。东北大学机器博弈研究室东北大学机器博弈研究室（alpha，beta）窗口A1A2A3An（alpha，beta）Value=-Search()

9、If(Value=beta)A1A2A3An（alpha，beta）Value=-Search()An（alpha，beta）窗口东北大学机器博弈研究室东北大学机器博弈研究室博弈树搜索过程Move GenerationMake MoveMove GenerationMake Move10Evaluation1010UnMake Move1010 121210 12121210 12121210 12121212101212121061212612106121261210613121261210613Cut off12121312106131212131210613121213121061312

10、1213121061312121312106131812121312106131818121213121210613181812121312121061318181212131212106131818129998Cut off1212131212106131818129998Best PV东北大学机器博弈研究室东北大学机器博弈研究室人机对弈信息流程人机对弈信息流程棋棋 局局 演演 化化棋手棋手界面界面引擎引擎着法着法着法着法着法着法着法着法局面局面局面局面局面局面局面局面思思考考思思考考思思考考计计算算计计算算着法着法局面局面计计算算东北大学机器博弈研究室东北大学机器博弈研究室红方先行。红方先

11、行。人选红方，输入着法；人选蓝方，输入人选红方，输入着法；人选蓝方，输入go东北大学机器博弈研究室东北大学机器博弈研究室Humans Move人机界面（人机界面（CHI）界面更新，胜负判定界面更新，胜负判定搜索引擎（递归搜索引擎（递归BEITA-剪枝）剪枝）Move GenerationMake/Unmake MoveEvaluation数据结构：棋子棋盘表示数据结构：棋子棋盘表示棋局系列，着法列表棋局系列，着法列表Root Move牛牛角角棋棋软软件件结结构构东北大学机器博弈研究室东北大学机器博弈研究室棋子的表示#define REDSTONE 0#define BLUESTONE1 1#d

12、efine BLUESTONE2 22034567891东北大学机器博弈研究室东北大学机器博弈研究室局面的表示（一）l初始局面的表示int board10 =REDSTONE,0,0,0,0,0,0,0,BLUESTONE1,BLUESTONE2,;2034567891东北大学机器博弈研究室东北大学机器博弈研究室局面的表示（二）l初始局面的表示记录有子的交叉点编号（stone Intersection-si）int si3 =0,8,9;(注意off-by-one错误)2034567891东北大学机器博弈研究室东北大学机器博弈研究室等价的局面表示l等价的初始局面int si3 =0,8,9;i

13、nt si3 =0,9,8;2034567891东北大学机器博弈研究室东北大学机器博弈研究室着法的表示绝对着法的三个要素 Piece：哪个棋子From：出发点编号To：目标点的编号2034567891东北大学机器博弈研究室东北大学机器博弈研究室着法的表示相对着法更方便Piece：哪个棋子To：目标点的编号2034567891东北大学机器博弈研究室东北大学机器博弈研究室着法生成l着法生成是和棋类知识关系最为紧密的部分l着法生成是博弈树展开和搜索的先决条件l着法生成是博弈程序中一个相当复杂而且耗费运算时间的部分l通过良好的数据结构（棋盘表示，着法表示），可以显著地提高生成的速度l着法生成、实现(m

14、ake move)、评估、选择之后，还要恢复到父节点(unmake move)东北大学机器博弈研究室东北大学机器博弈研究室着法生成（一）棋盘扫描法/以红子为例for(each intersection i ChessBoard)if(piecei+1=9)&NoStoneAt(piecei+1)Add i into MoveList;if(0=piecei1)&NoStoneAt(piecei 1)Add i into MoveList;2034567891东北大学机器博弈研究室东北大学机器博弈研究室着法生成（二）预置表法int preTable2105=/*red stone moves t

15、able*/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,INV,6,7,9,INV,7,8,INV,;2034567891着法生成（二）预置表的使用i=0；while(1)if(preTable colorfromi!=INV)Add i into Mov

16、eList;else break;+i;东北大学机器博弈研究室东北大学机器博弈研究室着法生成（二）使用预置表法须注意：根据牛角棋的规则，从预置表中提取的着法需做如下合法性判断：preTable color from i !=si to;(其中，0=4)color:动子的颜色；from:动子的提址；to:动子的落址。2034567891局面评估l红胜 win=200l红负 lose=-200l 和 draw=0l不同层间的胜负区别 win-ply lose+plyl同为胜局，选择浅层取胜的着法。东北大学机器博弈研究室东北大学机器博弈研究室东北大学机器博弈研究室东北大学机器博弈研究室博弈树的展开与

17、恢复生成子节点局面MakeMove()撤销子节点局面（恢复到父节点）UnmakeMove()2034567891东北大学机器博弈研究室东北大学机器博弈研究室牛角棋的搜索算法负极大值形式的负极大值形式的min-max搜索算法搜索算法东北大学机器博弈研究室东北大学机器博弈研究室牛角棋的搜索算法负极大值形式的负极大值形式的alpha-beta搜索算法搜索算法东北大学机器博弈研究室东北大学机器博弈研究室基本搜索流程东北大学机器博弈研究室东北大学机器博弈研究室算法优化l博弈树是根在上部向下递归产生的一棵包含所有可能的对弈过程的搜索树，是完全搜索树，包含了所有可能的博弈状态l但是，可以及早结束有些分枝的搜

18、索，比如重复出现的局面（状态）东北大学机器博弈研究室东北大学机器博弈研究室循环局面的处理2034567891169 269 279 179 169 269 279 179 000123645789Path搜索过程中循环局面的出现搜索过程中循环局面的出现东北大学机器博弈研究室东北大学机器博弈研究室循环局面的处理2034567891169 269 279 179 169 269 279 179 000123645789Path若若i siBLUESTONE1)|(siREDSTONE siBLUESTONE2)2）蓝走红胜(wtm=BLUE)&(siREDSTONE&1=0)&(siBLUESTO

19、NE1=siREDSTONE+1)&(siBLUESTONE2=siREDSTONE+2)|(siBLUESTONE1=siREDSTONE+2)&(siBLUESTONE2=siREDSTONE+1)东北大学机器博弈研究室东北大学机器博弈研究室如何编写机器博弈程序？l 会下棋，下好棋了解规则，懂得棋局的好坏，区分着法的好坏，如何能够克敌制胜，如何立于不败之地。l掌握计算机博弈的基本知识棋局与着法表示的数据结构，着法生成与棋局评估，博弈树，极大极小算法，最佳路径与最佳着法等。l按照软件工程编写程序需求分析，总体设计，详细设计，编码调试，设计文档，软件维护，系统优化等等。东北大学机器博弈研究室东

20、北大学机器博弈研究室如何总结博弈的规律？l通过博弈树展开，考虑到分枝数不大4,阶段数有限（15步内可以分出胜负），可以采用穷尽搜索得到对局的解。l将博弈树展开15层，如果不将无意义的循环走棋计算在内，那么 有效博弈树的总节点数为 7436771个，在叶节点上红胜为 532274个，蓝胜为 672个，和棋为 4637870个。东北大学机器博弈研究室东北大学机器博弈研究室牛角棋是一个很好的练习l棋局表示l可行着法判别l生成着法，搏弈树展开l棋局评估胜负判别：红胜，黑胜，和棋l最佳路径的选择l当前着法l知识总结：短兵相接的后果l继续研究：什么情况是和棋？先后手的差别东北大学机器博弈研究室东北大学机器

21、博弈研究室机器博弈的技术构成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一年一度的赛事和研讨会谢谢！谢谢！联系：联系： http:/