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

第第1212章章点点点点连格棋机器博弈系格棋机器博弈系统关关键技技术分析分析 连连 莲莲 徐心和徐心和东北大学机器博弈研究室东北大学机器博弈研究室12.1.1 点点点点连格棋格棋简介介点格棋（点格棋（3，，3）） Dots and Boxes(点格棋)点格棋（点格棋（6，，6））￿￿￿￿￿￿￿￿￿￿“点点连格棋”规则1.棋盘由6×6个点构成方阵，可以连成5×5个小方格子2.玩法￿￿￿1）双方轮流将邻近两点连成边，不可越点，不可重边，不连对角线；￿￿￿2）边不归属于任一方，只对格子判断归属；￿￿￿3）每个格子的四条边被占满四条边被占满时，该格子便被最后一个占边者所俘获；￿￿￿4）俘获格子后可以并必须再连一条边；￿￿￿5）格子全部围成后，博弈结束3.胜负占领格子较多的一方为获胜方棋盘：棋盘：3×3，，5×5，，6×6•点数点数 3×3 5×5 6×6 n×n•点数点数 9 25 36•格数格数 2×2 4×4 5×5 (n-1)×(n-1)•格数格数 4 16 25•边数边数 2×2×3 2×4×5 2×5×6 2×(n-1)×n •边数边数 12 40 60 •一般比赛采用一般比赛采用6×6，不会产生平局，不会产生平局点格棋棋局示意点格棋棋局示意点点点点连格棋格棋终止局面止局面 •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 在点点连格对弈过程中，最后一轮的走棋方是强迫在点点连格对弈过程中，最后一轮的走棋方是强迫对手率先进入长链或者环中走棋的一方对手率先进入长链或者环中走棋的一方•对于对于6×6的点点连格棋，共有的点点连格棋，共有36个点，即点的个数为偶数，个点，即点的个数为偶数，所以先手方应当极力形成偶数条长链，后手方应致力于形所以先手方应当极力形成偶数条长链，后手方应致力于形成奇数条长链成奇数条长链•通常一条长链或者过多的长链在实际博弈中是不易形成的，通常一条长链或者过多的长链在实际博弈中是不易形成的，故开局时，故开局时，先手方一般考虑先手方一般考虑2条或者条或者4条长链的情况，而后条长链的情况，而后手方可以搜索利于形成手方可以搜索利于形成3条或者条或者5条长链的着法条长链的着法12.3 点点点点连格棋机器博弈系格棋机器博弈系统数字表示数字表示 着法的表示着法的表示•着法是填入着法是填入水平或竖直相邻两点尚未连接的边，故应水平或竖直相邻两点尚未连接的边，故应该以相邻两点坐标来描述该以相邻两点坐标来描述•点阵坐标矩阵点阵坐标矩阵•着法表示着法表示 •需要实现从点阵矩阵到棋局矩阵的映射（变换）。

需要实现从点阵矩阵到棋局矩阵的映射（变换） 棋局各阶段的博弈策略棋局各阶段的博弈策略开局：棋盘划分，板块规划，目标是保证板块的奇开局：棋盘划分，板块规划，目标是保证板块的奇偶性，偶性， 符合长链定理符合长链定理 注意：每个长链需要两个开口的边界注意：每个长链需要两个开口的边界中局：以长链定理为核心，让格、短链及环配合中局：以长链定理为核心，让格、短链及环配合残局：贪婪还是让格走法的考虑残局：贪婪还是让格走法的考虑 出发点：比分差距小的叶子？出发点：比分差距小的叶子？重要着法重要着法1：贪婪：贪婪(greedy)走法走法 不放过每一个可以形成格子的着法不放过每一个可以形成格子的着法 只考虑眼前利益只考虑眼前利益2：让格走法：让格走法(loony): 构成构成doublecross 争取最后争取最后“收秋收秋”，故意作成双交，保证最后捕，故意作成双交，保证最后捕获的格子多获的格子多在游戏软件的编写中在游戏软件的编写中提高素质！提高素质！让创新的火花让创新的火花在机器博弈中迸发！在机器博弈中迸发！联系：联系： http:/// 。