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

第12章 点点连格棋机器博弈系统 关键技术分析 连 莲 徐心和东北大学机器博弈研究室 2010.0112.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争取最后“收秋”，故意作成双交，保证最后捕获 的格子多在游戏软件的编写中提高素质！让创新的火花在机器博弈中迸发！联系：computergames@ 。