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

第12章点点连格棋机器博弈系统关键技术分析 连 莲 徐心和 东北大学机器博弈研究室 2010.01 棋盘：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，不会产生平局 点格棋棋局示意 点点连格棋终止局面 点点连格棋残局 图形要素与图属性 点格棋的棋局是由各种各样的图形组成，于是可以定义各种棋局元素。 棋局元素包括：死格、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