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

1、第第1212章章点点连格棋机器博弈系统点点连格棋机器博弈系统关键技术分析关键技术分析 连连 莲莲 徐心和徐心和东北大学机器博弈研究室东北大学机器博弈研究室2010.01东北大学机器博弈研究室东北大学机器博弈研究室12.1.1 点点连格棋简介点点连格棋简介点格棋（点格棋（3，3）东北大学机器博弈研究室 Dots and Boxes(点格棋)东北大学机器博弈研究室点格棋（点格棋（6，6）东北大学机器博弈研究室 “点点连格棋”规则1.棋盘由66个点构成方阵，可以连成55个小方格子。2.玩法 1）双方轮流将邻近两点连成边，不可越点，不可重边，不连对角线；2）边不归属于任一方，只对格子判断归属；3）每个

2、格子的四条边被占满四条边被占满时，该格子便被最后一个占边者所俘获；4）俘获格子后可以并必须再连一条边；5）格子全部围成后，博弈结束。3.胜负占领格子较多的一方为获胜方。东北大学机器博弈研究室棋盘：棋盘：33，55，66东北大学机器博弈研究室 点数点数 33 55 66 nn 点数点数 9 25 36 格数格数 22 44 55 (n-1)(n-1)格数格数 4 16 25 边数边数 223 245 256 2(n-1)n 边数边数 12 40 60 一般比赛采用一般比赛采用66，不会产生平局，不会产生平局东北大学机器博弈研究室点格棋棋局示意点格棋棋局示意东北大学机器博弈研究室点点连格棋终止局面

3、点点连格棋终止局面 E和和D分别代表对弈分别代表对弈双方。双方。双方均在自己捕获双方均在自己捕获的格子内做己方的的格子内做己方的标记。标记。标记标记E的一方占格的一方占格10个，标记个，标记D的一的一方占格方占格15个，获胜个，获胜方为标记方为标记D的一方。的一方。东北大学机器博弈研究室点点连格棋残局点点连格棋残局 假定游戏假定游戏G是一个点点是一个点点连格游戏，连格游戏，b是游戏是游戏G中中的一个格子的一个格子。参加对弈的一方开始走参加对弈的一方开始走棋到走棋结束而换做另棋到走棋结束而换做另一方开始，我们称之为一方开始，我们称之为一轮（一轮（Turn），），一轮中，一轮中，每走一次棋，称之为

4、每走一次棋，称之为一一步（步（Move）。东北大学机器博弈研究室图形要素与图属性图形要素与图属性 点格棋的点格棋的棋局是由各种各样的图形组成棋局是由各种各样的图形组成，于是，于是可以定义各种棋局元素。可以定义各种棋局元素。棋局元素包括：死格、棋局元素包括：死格、C型格、长链、短链、环、型格、长链、短链、环、双交等。双交等。格的属性包括：自由度、邻居、开阔度等。格的属性包括：自由度、邻居、开阔度等。东北大学机器博弈研究室死格，死格，C型格型格 死格死格(dead box)：自由度为：自由度为1的格子的格子 C型格型格(C box)：由三个边构成的格子。：由三个边构成的格子。大大C型格型格 C型格

5、是特殊的死格型格是特殊的死格东北大学机器博弈研究室自由度，邻居，开阔度自由度，邻居，开阔度 自由度自由度(liberties)：构成格子尚缺的边数：构成格子尚缺的边数 邻居邻居(neighbor)：公用边未被：公用边未被 占领的相邻占领的相邻(adjacent)的格子的格子 开阔度开阔度(openess)=自由度自由度-邻居个数邻居个数东北大学机器博弈研究室长链，短链长链，短链 链链(chain)：彼此相邻的多个自由度为：彼此相邻的多个自由度为2的一串格子的一串格子 短链短链(short chain)：2个格子构成的链个格子构成的链 长链长链(long chain)：3个及个及3个以上格子构成

6、的链个以上格子构成的链东北大学机器博弈研究室子格，子树子格，子树 子格子格(subbox)：接续捕获的格子。：接续捕获的格子。子树子树(subtree)：接续捕获格子的集合。：接续捕获格子的集合。东北大学机器博弈研究室环环 环环(circle)：首尾相接的长链。多由：首尾相接的长链。多由4格构成。格构成。东北大学机器博弈研究室双交双交 双交双交(doublecross)：两个交互连接的：两个交互连接的C型格型格东北大学机器博弈研究室相关定义相关定义定义定义1 格子格子b的的自由度自由度（Liberties）等于）等于b未被占领的边的个数。未被占领的边的个数。定义定义2 格子格子b被称为被称为C

7、型型，当且仅当，当且仅当b的自由度为的自由度为1。定义定义3 格子格子b被称为被称为死格死格（Dead Box），当且仅当），当且仅当b可由当前对弈方可由当前对弈方捕获。捕获。也就是说当且仅当参加对弈的某一方当前存在一系列着法（也就是说当且仅当参加对弈的某一方当前存在一系列着法（Moves)，其中每个着法都捕获一个格子，这一系列格子都被称为死格。其中每个着法都捕获一个格子，这一系列格子都被称为死格。如果画个图，每个死格作为一个节点，相邻的死格用一条边连接，则如果画个图，每个死格作为一个节点，相邻的死格用一条边连接，则所有可贯通的节点构成了一个所有可贯通的节点构成了一个死树死树（Dead Tre

8、e）。）。特殊的，一个没有特殊的，一个没有死邻居死邻居的的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 一组着法被

9、称为贪婪算法（一组着法被称为贪婪算法（Greedy Algorithm），当其中的每），当其中的每个着法都捕获一个个着法都捕获一个C型格，进而该组着法最终捕获所有的死格。型格，进而该组着法最终捕获所有的死格。所以，如前图所示的局面，如果当前走棋方选择一次性占领全部死格所以，如前图所示的局面，如果当前走棋方选择一次性占领全部死格子，即子，即1号和号和16、17、12、7、8、9、10、5号格子，那么这个策略就号格子，那么这个策略就是贪婪算法。是贪婪算法。定义定义5 坐标分别为（坐标分别为（i，j）和（）和（k，l）的两个格子称为是）的两个格子称为是相邻的相邻的（Adjacent），当且仅当，并且

10、二者的公共边（），当且仅当，并且二者的公共边（Common Edge）未）未被占领。被占领。相邻的两个格子互称为邻居，当一个格子的邻居是死格时，该邻居称相邻的两个格子互称为邻居，当一个格子的邻居是死格时，该邻居称为为死邻居死邻居。前例中，前例中，19和和25号格子都是号格子都是24号格子的邻居。而号格子的邻居。而7和和9号格子都是号格子都是8号号格子的死邻居。格子的死邻居。东北大学机器博弈研究室相关定义相关定义 定义定义6 死格死格b的的开阔度开阔度（Openness）大小等于）大小等于b的自由度的自由度减去减去b的死邻居的个数，即：的死邻居的个数，即：O(b)=Lib(b)-DN(b)其中，

11、其中，O(b)代表开阔度，代表开阔度，Lib代表自由度，代表自由度，DN代表死邻居代表死邻居的个数，易知的个数，易知O(b)的值只为的值只为0或者或者1。开阔度仅仅针对死格。开阔度仅仅针对死格而言。而言。定义定义7 死格死格b被称作是是被称作是是开阔格开阔格，当且仅当，当且仅当O(b)=1，否则，否则称称b是闭合格。开阔格不与死邻居共用的一条边称为是闭合格。开阔格不与死邻居共用的一条边称为开阔开阔边边。东北大学机器博弈研究室 可见可见C型格是闭合格的一个特例。根据定义型格是闭合格的一个特例。根据定义6和定义和定义7，可，可以得到如下结论：以得到如下结论：结论结论 每条死树只能含有一个或者两个每

12、条死树只能含有一个或者两个C型格，当一条死型格，当一条死树只含有一个树只含有一个C型格时，可以把它看做死树的起点，占格型格时，可以把它看做死树的起点，占格操作由起点开始，并且这条死树有且仅有一个开阔格，可操作由起点开始，并且这条死树有且仅有一个开阔格，可以看做其终点。当一条死树含有以看做其终点。当一条死树含有2个个C型格时，死树中不型格时，死树中不含有开阔格。含有开阔格。含有开阔格的死树叫做含有开阔格的死树叫做开阔死树开阔死树（Open Dead Tree，OT），不含有开阔格的死树叫做），不含有开阔格的死树叫做闭合死树闭合死树（Closed Dead Tree，CT）。）。东北大学机器博弈研

13、究室相关定义相关定义东北大学机器博弈研究室长链、短链与环长链、短链与环 21，22，23，18，13，14，15号格子构成一条号格子构成一条长链长链，6，11号格子构成一条号格子构成一条短链短链，19，20，24，25号格子号格子构成一个构成一个环环。6和和11号格子的两条非号格子的两条非公共边占据后，就构成公共边占据后，就构成了一个了一个2C型型。东北大学机器博弈研究室12.2 点点连格棋机器博弈系统策略分析点点连格棋机器博弈系统策略分析 一般点点连格棋的对弈过程中，长链和环是高频率出现的一般点点连格棋的对弈过程中，长链和环是高频率出现的两种形状，而两种形状，而对于长链和环的处理也是取胜的关

14、键之一对于长链和环的处理也是取胜的关键之一。而通常，这两种形状的处理出现在残局（而通常，这两种形状的处理出现在残局（Final Phase）阶）阶段。段。开局是生成长链、短链和环的预备期，中局是着手生成这开局是生成长链、短链和环的预备期，中局是着手生成这三种形状，三种形状，而开局和中局一般不会在链或者环里动作，偶而开局和中局一般不会在链或者环里动作，偶尔会出现捕获尔会出现捕获C型格的情况。型格的情况。长链的个数的奇偶性通常是决定胜负的关键长链的个数的奇偶性通常是决定胜负的关键，如果条件足，如果条件足够宽松可以控制长链的条数的时候，我们必须掌握长链定够宽松可以控制长链的条数的时候，我们必须掌握长

15、链定理。理。东北大学机器博弈研究室重要定理重要定理 定理定理1：Dots+doublecrosses=Turns 通常情况下，最后捕获格子的一方获胜。通常情况下，最后捕获格子的一方获胜。于是，对于先手而言，总换手次数为奇数时获胜；于是，对于先手而言，总换手次数为奇数时获胜；对于后手而言，总换手次数为偶数时获胜。对于后手而言，总换手次数为偶数时获胜。开局记一次换手。开局记一次换手。定理定理1用以计算结束前的换手次数。用以计算结束前的换手次数。东北大学机器博弈研究室重要定理重要定理定理定理2（长链法则）：（长链法则）：1.换手数为偶数时，先手方应力图形成偶数条长换手数为偶数时，先手方应力图形成偶数

16、条长链，而后手方应力图形成奇数条长链；链，而后手方应力图形成奇数条长链；2.换手数为奇数时，先手方应力图形成奇数条长换手数为奇数时，先手方应力图形成奇数条长链，而后手方应力图形成偶数条长链。链，而后手方应力图形成偶数条长链。东北大学机器博弈研究室重要公式重要公式 可能形成可能形成双交双交数目的计算公式数目的计算公式 doublecrosses=longchain-1+2*circle东北大学机器博弈研究室长链定理长链定理 定理定理1 无论初始棋盘的尺寸如何，总有以下式子成立：无论初始棋盘的尺寸如何，总有以下式子成立：Dots+Doublecrosses=Turns （1）其中，其中，Dots指

17、的是初始棋盘点的个数，指的是初始棋盘点的个数，Doublecrosses指的指的是棋局结束时，共形成的是棋局结束时，共形成的2C型的个数，型的个数，Turns指的是棋局指的是棋局结束时，共经历了多少轮的走棋。结束时，共经历了多少轮的走棋。定理定理2被称为长链定理，被称为长链定理，它是它是Berlekamp对定理对定理1的一个推论的一个推论。定理定理2 如果棋盘共有奇数个点，则先手方应当形成奇数如果棋盘共有奇数个点，则先手方应当形成奇数条长链以取胜，后手方应形成偶数条长链以取胜；条长链以取胜，后手方应形成偶数条长链以取胜；若棋盘若棋盘共有偶数个点，则先手方应当形成偶数条长链，后手方应共有偶数个点

18、，则先手方应当形成偶数条长链，后手方应形成奇数条长链以取胜。形成奇数条长链以取胜。东北大学机器博弈研究室 引理引理1 在点点连格对弈过程中，最后一轮的走棋方是强在点点连格对弈过程中，最后一轮的走棋方是强迫对手率先进入长链或者环中走棋的一方。迫对手率先进入长链或者环中走棋的一方。对于对于66的点点连格棋，共有的点点连格棋，共有36个点，即点的个数为偶数，个点，即点的个数为偶数，所以先手方应当极力形成偶数条长链，后手方应致力于形所以先手方应当极力形成偶数条长链，后手方应致力于形成奇数条长链。成奇数条长链。通常一条长链或者过多的长链在实际博弈中是不易形成的，通常一条长链或者过多的长链在实际博弈中是不

19、易形成的，故开局时，故开局时，先手方一般考虑先手方一般考虑2条或者条或者4条长链的情况，而后条长链的情况，而后手方可以搜索利于形成手方可以搜索利于形成3条或者条或者5条长链的着法条长链的着法。东北大学机器博弈研究室12.3 点点连格棋机器博弈系统数字表示点点连格棋机器博弈系统数字表示 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101A东北大学机器博弈研究室10101111011110112010130

20、10141101010110101101010101001010010101010110101101011110111101111011511011101110111011110111101010100101001021101011010110101bb东北大学机器博弈研究室着法的表示着法的表示 着法是填入着法是填入水平或竖直相邻两点尚未连接的边，故水平或竖直相邻两点尚未连接的边，故应该以相邻两点坐标来描述。应该以相邻两点坐标来描述。点阵坐标矩阵点阵坐标矩阵 着法表示着法表示 需要实现从点阵矩阵到棋局矩阵的映射（变换）。需要实现从点阵矩阵到棋局矩阵的映射（变换）。6,65,64,63,62,6

21、1,66,55,54,53,52,51,56,45,44,43,42,41,46,35,34,33,32,31,36,25,24,23,22,21,26,15,14,13,12,11,1POINT),1(&),()1,(&),(jijiorjiji东北大学机器博弈研究室棋局各阶段的博弈策略棋局各阶段的博弈策略开局：棋盘划分，板块规划，目标是保证板块的奇开局：棋盘划分，板块规划，目标是保证板块的奇偶性，偶性，符合长链定理。符合长链定理。注意：每个长链需要两个开口的边界注意：每个长链需要两个开口的边界中局：以长链定理为核心，让格、短链及环配合中局：以长链定理为核心，让格、短链及环配合残局：贪婪还是

22、让格走法的考虑。残局：贪婪还是让格走法的考虑。出发点：比分差距小的叶子？出发点：比分差距小的叶子？东北大学机器博弈研究室重要着法重要着法1：贪婪：贪婪(greedy)走法走法 不放过每一个可以形成格子的着法。不放过每一个可以形成格子的着法。只考虑眼前利益。只考虑眼前利益。2：让格走法：让格走法(loony):构成构成doublecross 争取最后争取最后“收秋收秋”，故意作成双交，保证最后捕，故意作成双交，保证最后捕获的格子多。获的格子多。东北大学机器博弈研究室在游戏软件的编写中在游戏软件的编写中提高素质！提高素质！让创新的火花让创新的火花在机器博弈中迸发！在机器博弈中迸发！联系：联系： http:/