点点连格棋机器博弈系统关键技术分析.ppt

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,东北大学机器博弈研究室,*,第12章,点点连格棋机器博弈系统关键技术分析,连 莲 徐心和,东北大学机器博弈研究室,2010.01,东北大学机器博弈研究室,东北大学机器博弈研究室,12.1.1 点点连格棋简介,点格棋（3，3）,东北大学机器博弈研究室,Dots and Boxes(,点格棋,),东北大学机器博弈研究室,点格棋（6，6）,东北大学机器博弈研究室,“点点连格棋”规则,棋盘,由,66,个点构成方阵，可以连成,55,个小方格子。,玩法,1,）双方轮流将邻近两点连成边，不可越点，不可重边，不连对角线；,2,）边不归属于任一方，只对格子判断归属；,3,）每个格子的,四条边被占满,时，该格子便被最后一个占边者所俘获；,4,）俘获格子后可以并必须再连一条边；,5,）格子全部围成后，博弈结束。,胜负,占领格子较多的一方为获胜方。,东北大学机器博弈研究室,点格棋棋局示意,东北大学机器博弈研究室,点点连格棋终止局面,E和D分别代表对弈双方。,双方均在自己捕获的格子内做己方的标记。,标记E的一方占格10个，标记D的一方占格15个，获胜方为标记D的一方。,东北大学机器博弈研究室,点点连格棋残局,假定游戏G是一个点点连格游戏，,b,是游戏G中的一个格子,。,参加对弈的一方开始走棋到走棋结束而换做另一方开始，我们称之为,一轮（Turn），,一轮中，每走一次棋，称之为,一步（Move）,。,东北大学机器博弈研究室,图形要素与图属性,点格棋的,棋局是由各种各样的图形组成,，于是可以定义各种棋局元素。,棋局元素包括：死格、C型格、长链、短链、环、双交等。,格的属性包括：自由度、邻居、开阔度等。,东北大学机器博弈研究室,死格，,C型格,死格(,dead box),：自由度为1的格子,C型格(C box)：由三个边构成的格子。,大C型格,C型格是特殊的死格,东北大学机器博弈研究室,自由度，邻居，开阔度,自由度(,liberties),：构成格子尚缺的边数,邻居,(neighbor),：公用边未被,占领的相邻,(adjacent),的格子,开阔度,(openess),=自由度-邻居个数,东北大学机器博弈研究室,长链，短链,链(chain)：彼此相邻的多个自由度为2的一串格子,短链(short chain)：2个格子构成的链,长链(long chain)：3个及3个以上格子构成的链,东北大学机器博弈研究室,子格，子树,子格(subbox)：接续捕获的格子。,子树(subtree)：接续捕获格子的集合。,东北大学机器博弈研究室,环,环(circle)：首尾相接的长链。多由4格构成。,东北大学机器博弈研究室,双交,双交(doublecross)：两个交互连接的C型格,东北大学机器博弈研究室,相关定义,定义1,格子,b,的,自由度,（Liberties）等于,b,未被占领的边的个数。,定义2,格子,b,被称为,C型,，当且仅当,b,的自由度为1。,定义3,格子,b,被称为,死格,（Dead Box），当且仅当,b,可由当前对弈方捕获。,也就是说当且仅当参加对弈的某一方当前存在一系列着法（Moves)，其中每个着法都捕获一个格子，这一系列格子都被称为死格。,如果画个图，每个死格作为一个节点，相邻的死格用一条边连接，则所有可贯通的节点构成了一个,死树,（Dead Tree）。,特殊的，一个没有,死邻居,的C型格也是一个死树。,所有的死树构成了一个,死森林,（Dead Forest）。,东北大学机器博弈研究室,C型格、死格与死树,1号和16号格子为,C型格,，它们的自由度为1；,1、5、10、9、8、7、12、17、16号格子均是,死格,，,1号格为一个,死树,，5、10、9、8、7、12、17、16号格子构成了另一个,死树,。,东北大学机器博弈研究室,贪婪算法（Greedy Algorithm）,定义4,一组着法被称为贪婪算法（Greedy Algorithm），当其中的每个着法都捕获一个C型格，进而该组着法最终捕获所有的死格。,所以，如前图所示的局面，如果当前走棋方选择一次性占领全部死格子，即1号和16、17、12、7、8、9、10、5号格子，那么这个策略就是贪婪算法。,定义5,坐标分别为（,i，j,）和（,k，l,）的两个格子称为是,相邻的,（Adjacent），当且仅当，并且二者的公共边（Common Edge）未被占领。,相邻的两个格子互称为邻居，当一个格子的邻居是死格时，该邻居称为,死邻居,。,前例中，19和25号格子都是24号格子的邻居。而7和9号格子都是8号格子的死邻居。,东北大学机器博弈研究室,相关定义,定义6,死格,b,的,开阔度,（Openness）大小等于,b,的自由度减去,b,的死邻居的个数，即：,O(,b,)=Lib(,b,)-DN(,b,),其中，O(,b,)代表开阔度，Lib代表自由度，DN代表死邻居的个数，易知O(,b,)的值只为0或者1。开阔度仅仅针对死格而言。,定义7,死格,b,被称作是是,开阔格,，当且仅当O(,b,)=1，否则称,b,是闭合格。开阔格不与死邻居共用的一条边称为,开阔边,。,东北大学机器博弈研究室,可见C型格是闭合格的一个特例。根据定义6和定义7，可以得到如下结论：,结论,每条死树只能含有一个或者两个C型格，当一条死树只含有一个C型格时，可以把它看做死树的起点，占格操作由起点开始，并且这条死树有且仅有一个开阔格，可以看做其终点。当一条死树含有2个C型格时，死树中不含有开阔格。,含有开阔格的死树叫做,开阔死树,（Open Dead Tree，OT），不含有开阔格的死树叫做,闭合死树,（Closed Dead Tree，CT）。,东北大学机器博弈研究室,相关定义,东北大学机器博弈研究室,长链、短链与环,21，22，23，18，13，14，15号格子构成一条,长链,，,6，11号格子构成一条,短链,，,19，20，24，25号格子构成一个,环,。,6和11号格子的两条非公共边占据后，就构成了一个,2C型,。,东北大学机器博弈研究室,12.2 点点连格棋机器博弈系统策略分析,一般点点连格棋的对弈过程中，长链和环是高频率出现的两种形状，而,对于长链和环的处理也是取胜的关键之一,。而通常，这两种形状的处理出现在残局（Final Phase）阶段。,开局是生成长链、短链和环的预备期，中局是着手生成这三种形状，,而开局和中局一般不会在链或者环里动作，偶尔会出现捕获C型格的情况。,长链的个数的奇偶性通常是决定胜负的关键,，如果条件足够宽松可以控制长链的条数的时候，我们必须掌握长链定理。,东北大学机器博弈研究室,重要定理,定理1：Dots+doublecrosses=Turns,通常情况下，最后捕获格子的一方获胜。,于是，对于先手而言，总换手次数为奇数时获胜；,对于后手而言，总换手次数为偶数时获胜。,开局记一次换手。,定理1用以计算结束前的换手次数。,东北大学机器博弈研究室,重要定理,定理2（长链法则）：,1.换手数为偶数时，先手方应力图形成偶数条长链，而后手方应力图形成奇数条长链；,2.换手数为奇数时，先手方应力图形成奇数条长链，而后手方应力图形成偶数条长链。,东北大学机器博弈研究室,重要公式,可能形成,双交,数目的计算公式,doublecrosses=longchain-1+2*circle,东北大学机器博弈研究室,长链定理,定理1,无论初始棋盘的尺寸如何，总有以下式子成立：,Dots+Doublecrosses=Turns （1）,其中，Dots指的是初始棋盘点的个数，Doublecrosses指的是棋局结束时，共形成的2C型的个数，Turns指的是棋局结束时，共经历了多少轮的走棋。,定理2被称为长链定理，它是Berlekamp对定理1的一个推论,。,定理2,如果棋盘共有奇数个点，则先手方应当形成奇数条长链以取胜，后手方应形成偶数条长链以取胜；,若棋盘共有偶数个点，则先手方应当形成偶数条长链，后手方应形成奇数条长链以取胜。,东北大学机器博弈研究室,引理1,在点点连格对弈过程中，最后一轮的走棋方是强迫对手率先进入长链或者环中走棋的一方。,对于66的点点连格棋，共有36个点，即点的个数为偶数，所以先手方应当极力形成偶数条长链，后手方应致力于形成奇数条长链。,通常一条长链或者过多的长链在实际博弈中是不易形成的，故开局时，,先手方一般考虑2条或者4条长链的情况，而后手方可以搜索利于形成3条或者5条长链的着法,。,东北大学机器博弈研究室,12.3 点点连格棋机器博弈系统数字表示,东北大学机器博弈研究室,东北大学机器博弈研究室,着法的表示,着法是填入,水平或竖直相邻两点尚未连接的边，故应该以相邻两点坐标来描述。,点阵坐标矩阵,着法表示,需要实现从点阵矩阵到棋局矩阵的映射（变换）。,东北大学机器博弈研究室,棋局各阶段的博弈策略,开局：棋盘划分，板块规划，目标是保证板块的奇偶性，符合长链定理。,注意：每个长链需要两个开口的边界,中局：以长链定理为核心，让格、短链及环配合,残局：贪婪还是让格走法的考虑。,出发点：比分差距小的叶子？,东北大学机器博弈研究室,重要着法,1：贪婪(greedy)走法,不放过每一个可以形成格子的着法。,只考虑眼前利益。,2：让格走法(loony):构成doublecross,争取最后“收秋”，故意作成双交，保证最后捕获的格子多。,东北大学机器博弈研究室,在游戏软件的编写中,提高素质！,让创新的火花,在机器博弈中迸发！,联系：,computergames,