民间棋类计算机博弈11.ppt

1、民间棋类计算机博弈,文中华 2010年3月,主要内容,什么是计算机博弈（机器博弈）？ 机器博弈的艰苦历程与辉煌成果 民间棋类计算机博弈 机器博弈的入门课 计算机是如何实现博弈过程的？ 机器博弈的技术构成与内涵 开展机器博弈活动的意义与展望,什么是计算机博弈？,计算机博弈, 机器博弈 Computer Games主要是指计算机下棋、玩牌 像人一样的思维 最先提出的就是计算机下 国际象棋、西洋跳棋等各种棋类,机器博弈是一个特殊的研究领域,它是非常实际的计算机科学与技术的研究课题 它是非常富于挑战性的人工智能领域的研究方向 它来不得任何理想化和虚假成分 它是现代博弈论所不能解决的动态博弈技术 它是需

2、求牵引的典型课题，具有很强的泛化能力 因为它是人工智能的基本问题 它具有广阔的应用前景对策问题 （控制、决策、对策）,机器博弈的艰苦历程与辉煌成果,国际象棋 最先提出的计算机应用课题之一 计算机前辈所关注的研究课题 半个世纪的艰苦拼搏 IBM深蓝的辉煌业绩 继续向新的高峰攀登,追寻历史的踪迹,1946年第一台电子计算机问世于美国。 冯.诺依曼 数学家，博弈论的创始人 计算机之父 提出极大极小定理 为验证机器的正确性和性能，首先为它编写了象棋程序,Programming a computer for playing chess, Shannon,1950 “用极大极小值算法可以找到想下的棋， 但

3、由于这个游戏的变化太多，不可能搜索 到终结点，所以就要寻找一种合适的方法 只搜索部分节点，然后就可以判断该走哪 步棋，进而走棋 ” 现代计算机博弈的理论基础,许多人在努力,他们来自于何方？,Canada、America、England、China、Japan、Holland、Mexico,University of Alberta, University of Wisconsin, University of Maryland, MIT, University of Tokyo, University of Albama, University of California, Erasmus U

4、niversity, Cambrige University,世纪之战,许峰雄 深蓝之父 1997年深蓝战胜卡斯帕罗夫,电脑棋手：永不停歇的挑战！,2001年“更弗里茨” 击败了除了克拉姆尼克之外的所有排名世界前十位的棋手。 2002年10月“更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。 2003年1至2月“更年少者”与卡斯帕罗夫在纽约较量，3比3战平。,克拉姆尼科最新赛事(2006.11),须知：深弗里茨比当年“深蓝”运算能力快2个数量级,连续三届奥林匹克冠军 Kramnik 2 - 4 Deep Fritz,棋类机器博弈的发展,机器博弈涉及的范围： Othello 奥塞罗

5、Checkers 西洋跳棋 Go-moku五子棋 Chess国际象棋 Chinese chess中国象棋 Shigo日本将棋 Go围棋 领域在延伸 Poker纸牌游戏 SokobanLines of action Hex Awari Amatons Rosambo Domineering ,机器博弈的艰苦历程与辉煌成果,中国象棋 机器博弈工作者新的挑战 可喜的初战胜利 还有很长的路要走 围棋的机器博弈水平还很低,台湾电脑象棋之父,前台湾大学 资讯工程系教授 许舜钦 80年代开始 机器博弈研究 “Elephant” 现在台南长荣大学,中国电脑围棋的骄傲,中山大学化学系 陈志行教授 “手谈” 汇编

6、语言 1995,1996,1997 连续3年 6项世界冠军 ,棋天大圣 勇夺 全国冠军 2006.8.8,浪潮杯首届中国计算机博弈锦标赛,左起： 卜凤波 徐天红 柳大华 张 强 汪 洋,浪潮杯首届中国象棋人机大战对阵5位象棋大师,2006年8月9日,国家奥林匹克中心综合馆,人机大战终极 PK（2006.8.15）,中国象棋第一人 许银川 vs 棋天大圣,民间棋类计算机博弈,最简单的机器博弈项目 机器博弈入门课 麻雀虽小，五脏俱全 从一个实例出发牛角棋,民间棋类的特点,规则简单，很容易入门； 不受专业知识限制； 棋盘小，棋子少，复杂度不高； 输赢容易识别，局面容易判断； 完全信息，编程相对简单；

7、 人工智能的“果蝇”。,牛角棋,牛角棋广泛见于各地，别名较多，如憋死牛、憋死井、娃娃下山、娘子下山等。 棋盘形状及棋位数目也稍有差异。但是棋子、棋规都相同。,牛角棋棋规,红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃； 蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃； 胜负判断：憋死憋不死？,红先红胜 (7步),红先蓝胜 (18步),为什么输赢？需要不断地摸索经验，试验所有的局面。,博弈思维过程展开博弈树,红方走棋,红方走棋,蓝方走棋,红方先手,计算机是如何实现博弈过程的？,计算机如何进行博弈思维？ 如何编写机器博弈程序？,计算机如何进行博弈思维？,如何存储思维

8、信息？棋盘、棋子、棋局、博弈树 如何判断局面的胜负？ 如何展开博弈树？ 如何选择当前的着法？ 如何编写程序？ 如何总结博弈的规律？,如何存储思维信息？,编码 数据结构 棋盘编码（棋位编码） 棋子编码 初始局面的表示 棋位向量：(1000000023) 棋子向量：(089),棋局演化的形式化描述,状态变量 棋子向量表示 初始状态 状态演化方程 其中 为棋子i 第n+1步的着法（算子） 着法规则：,红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃； 蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；,着法的形式化描述,通过扫描棋盘，如果“落址”为空位，便是合法着法（算子

9、）。,如何判断局面的胜负？,红胜：“逃出” 蓝胜：“憋死” 和棋 局面的无限次重复,如何展开博弈树？,如何表示博弈树？,两种不同的展开方式,广度优先,室,两种不同的展开方式,深度优先,广度优先的展开与存储,深度优先的展开与存储,如何选择当前的着法？,在展开的博弈树中搜索博弈搜索引擎 如果红方走棋，他总要找到博弈树中最好的棋局，而在考虑对方（蓝方）走棋时，就要考虑最坏的局面，因为双方都是理智的博弈者，不应该抱有任何侥幸的心理。 如果给每个棋局打分，那红方可以称得上是MAX方，蓝方便是MIN方。,深度为3的博弈树,深度,层数,MAX,MAX,MIN,3,极大极小搜索,找到最佳路径与最佳着法,MAX

10、,MAX,MIN,3,从极大极小搜索到负极大值搜索,Current best PV and best move,NegaMax,NegaMax,MAX,MAX,MIN,4,4,Alpha剪枝,=4,找到最佳路径与最佳着法,-剪枝（1）,MAX,MIN,MIN,7,7,由此产生最佳路径和最佳着法, =7,-剪枝（2）,MAX,MIN,MIN,8,由此产生最佳路径和最佳着法,4,4,8, =4,负极大值形式的Alpha-beta搜索,Alpha的含义：当前方已经存在某个着法，其估值至少为alpha； Beta的含义：对手存在着某个着法，令当前方的着法的估值无论如何也超不过beta。 负极大值形式的

11、alpha-beta剪枝只有beta剪枝。,（alpha，beta）窗口,A1,A2,A3,An,（alpha，beta）,Value = -Search(),If (Value = alpha),A1,A2,A3,An,（alpha，beta）,Value = -Search(),负极大值条件下的（alpha，beta）窗口,A1,A2,A3,An,return value,If (Value = beta),A1,A2,A3,An,（alpha，beta）,Value = -Search(),An,（alpha，beta）窗口,博弈树搜索过程,人机对弈信息流程,红方先行。 人选红方，输入着

12、法；人选蓝方，输入go,牛角棋软件结构,棋子的表示,#define REDSTONE 0 #define BLUESTONE1 1 #define BLUESTONE2 2,局面的表示（一）,初始局面的表示 int board10 = REDSTONE, 0, 0, 0, 0, 0, 0, 0, BLUESTONE1, BLUESTONE2, ;,局面的表示（二）,初始局面的表示 记录有子的交叉点编号 （stone Intersection-si） int si3 = 0, 8, 9 ; (注意off-by-one错误),等价的局面表示,等价的初始局面 int si3 = 0, 8, 9 ;

13、int si3 = 0, 9, 8 ;,着法的表示,绝对着法的三个要素 Piece：哪个棋子 From：出发点编号 To： 目标点的编号,2,0,3,4,5,6,7,8,9,1,着法的表示,相对着法更方便 Piece：哪个棋子 To： 目标点的编号 涵义：Piece To 位： 5 4 3 2 1 0,着法生成,着法生成是和棋类知识关系最为紧密的部分 着法生成是博弈树展开和搜索的先决条件 着法生成是博弈程序中一个相当复杂而且耗费运算时间的部分 通过良好的数据结构（棋盘表示，着法表示），可以显著地提高生成的速度 着法生成 、实现(make move)、评估、选择之后，还要恢复到父节点(unmak

14、e 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, 9, 7, 6, INV,8, 7, INV, , /*blue stone moves table*/ INV

15、,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,局面评估,红胜 win=200 红负 lose=-200 和 draw=0 不同层间的胜负区别 win-ply lose

16、+ply 同为胜局，选择浅层取胜的着法。,博弈树的展开与恢复,生成子节点局面 MakeMove ( ) 撤销子节点局面 （恢复到父节点） UnmakeMove ( ),牛角棋的搜索算法 负极大值形式的alpha-beta搜索算法,基本搜索流程,算法优化,博弈树是根在上部向下递归产生的一棵包含所有可能的对弈过程的搜索树，是完全搜索树，包含了所有可能的博弈状态 但是，有些情况我们不希望重复搜索，比如重复出现的局面（状态）,循环局面的处理,Path,搜索过程中循环局面的出现,循环局面的处理,2,0,3,4,5,6,7,8,9,1,Path,若i4则无循环，注意 Pathi与Pathi-4的关系,搜索

17、过程中循环局面的出现,循环局面的处理,建立一个顺序表，命名为Path。 每次搜索前将唯一表示当前局面的值存入表中 若当前层为i，判断Pathi是否等于Pathi-4 若相等，则剪枝，不等则继续搜索 搜索结束，将Pathi 赋值为0 较复杂棋类，如象棋，一般用hash表实现循环局面的处理。,评估（一）,胜利条件 红方胜的条件： (siREDSTONE = 8) | (siREDSTONE = 9) 蓝方胜的条件： (siREDSTONE = 0) & (siBLUESTONE1 + siBLUESTONE2) = 3),棋局评估胜负提前判别,蓝走红胜,红走蓝胜,不难看出，短兵相接，谁动谁输。 可

18、以整理判据，放到程序当中。,评估（二）,其它人类知识 影响胜负的重要条件 局势细微变化的条件 举例 1）红子突破，红胜 ( (siREDSTONE siBLUESTONE1) | (siREDSTONE siBLUESTONE2) ) 2）蓝走红胜 ( (wtm = BLUE) & (siREDSTONE & 1 = 0) & (siBLUESTONE1 = siREDSTONE+1) & (siBLUESTONE2 = siREDSTONE+2) | (siBLUESTONE1 = siREDSTONE+2)& (siBLUESTONE2 = siREDSTONE+1) ),辅助软件模块,差错与容错功能 输入的合法性检查 着法的合法性检查 局面的合法性检查 计时功能 保存棋谱功能与复盘功能 ,如何编写机器博弈程序？,会下棋，下好棋了解规则，懂得棋局的好坏，区分着法的好坏，如何能够克敌制胜，如何立于不败之地。 掌握计算机博弈的基本知识棋局与着法表示的数据结构，着法生成与棋局评估，博弈树，极大极小算法，最佳路径与最佳着法等。 按照软