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

《点点连格棋机器博弈系统关键技术分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第12章点点连格棋机器博弈系统关键技术分析连莲徐心和东北大学机器博弈研究室2010.01东北大学机器博弈研究室东北大学机器博弈研究室12.1.1点点连格棋简介点格棋（3，3）东北大学机器博弈研究室DotsandBoxes(点格棋)东北大学机器博弈研究室点格棋（6，6）东北大学机器博弈研究室“点点连格棋”规则棋盘由6×6个点构成方阵，可以连成5×5个小方格子。玩法1）双方轮流将邻近两点连成边，不可越点，不可重边，不连对角线；2）边不归属于任一方，只对格子判断归属；3）每个格子的四条边被占满时，该格子便被最后一个占边者所俘获；4）俘获格子后可以并必须再连一条边；5）格子全部围成后，博弈结束。胜负

2、占领格子较多的一方为获胜方。东北大学机器博弈研究室棋盘：3×3，5×5，6×6东北大学机器博弈研究室点数3×35×56×6n×n点数92536格数2×24×45×5(n-1)×(n-1)格数41625边数2×2×32×4×52×5×62×(n-1)×n边数124060一般比赛采用6×6，不会产生平局东北大学机器博弈研究室点格棋棋局示意东北大学机器博弈研究室点点连格棋终止局面E和D分别代表对弈双方。双方均在自己捕获的格子内做己方的标记。标记E的一方占格10个，标记D的一方占格15个，获胜方为标记D的一方。东北大学机器博弈研究室点点连格棋残局假定游戏G是一个点点连格游戏，b是游戏G中的一个格子。参

3、加对弈的一方开始走棋到走棋结束而换做另一方开始，我们称之为一轮（Turn），一轮中，每走一次棋，称之为一步（Move）。东北大学机器博弈研究室图形要素与图属性点格棋的棋局是由各种各样的图形组成，于是可以定义各种棋局元素。棋局元素包括：死格、C型格、长链、短链、环、双交等。格的属性包括：自由度、邻居、开阔度等。东北大学机器博弈研究室死格，C型格死格(deadbox)：自由度为1的格子C型格(Cbox)：由三个边构成的格子。大C型格C型格是特殊的死格东北大学机器博弈研究室自由度，邻居，开阔度自由度(liberties)：构成格子尚缺的边数邻居(neighbor)：公用边未被占领的相邻(adjace

4、nt)的格子开阔度(openess)=自由度-邻居个数东北大学机器博弈研究室长链，短链链(chain)：彼此相邻的多个自由度为2的一串格子短链(shortchain)：2个格子构成的链长链(longchain)：3个及3个以上格子构成的链东北大学机器博弈研究室子格，子树子格(subbox)：接续捕获的格子。子树(subtree)：接续捕获格子的集合。东北大学机器博弈研究室环环(circle)：首尾相接的长链。多由4格构成。东北大学机器博弈研究室双交双交(doublecross)：两个交互连接的C型格东北大学机器博弈研究室相关定义定义1格子b的自由度（Liberties）等于b未被占领的边的个数

5、。定义2格子b被称为C型，当且仅当b的自由度为1。定义3格子b被称为死格（DeadBox），当且仅当b可由当前对弈方捕获。也就是说当且仅当参加对弈的某一方当前存在一系列着法（Moves)，其中每个着法都捕获一个格子，这一系列格子都被称为死格。如果画个图，每个死格作为一个节点，相邻的死格用一条边连接，则所有可贯通的节点构成了一个死树（DeadTree）。特殊的，一个没有死邻居的C型格也是一个死树。所有的死树构成了一个死森林（DeadForest）。东北大学机器博弈研究室C型格、死格与死树1号和16号格子为C型格，它们的自由度为1；1、5、10、9、8、7、12、17、16号格子均是死格，1号格为

6、一个死树，5、10、9、8、7、12、17、16号格子构成了另一个死树。东北大学机器博弈研究室贪婪算法（GreedyAlgorithm）定义4一组着法被称为贪婪算法（GreedyAlgorithm），当其中的每个着法都捕获一个C型格，进而该组着法最终捕获所有的死格。所以，如前图所示的局面，如果当前走棋方选择一次性占领全部死格子，即1号和16、17、12、7、8、9、10、5号格子，那么这个策略就是贪婪算法。定义5坐标分别为（i，j）和（k，l）的两个格子称为是相邻的（Adjacent），当且仅当，并且二者的公共边（CommonEdge）未被占领。相邻的两个格子互称为邻居，当一个格子的邻居是死格

7、时，该邻居称为死邻居。前例中，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被称作是是开阔格