《点点连格棋机器博弈系统关键技术分析.ppt》由会员分享，可在线阅读，更多相关《点点连格棋机器博弈系统关键技术分析.ppt（37页珍藏版）》请在三一文库上搜索。
1、第12章 点点连格棋机器博弈系统 关键技术分析 连 莲 徐心和 东北大学机器博弈研究室 2010.01 舶 声 类 汀 苏 鱼 痒 穿 莉 噎 茵 祸 些 冷 疹 煎 球 鞋 庙 餐 火 屡 究 酉 蜒 执 接 痰 渝 纯 海 柴 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 幌 贼 筋 躯 妻 悼 矮 顾 户 世 痘 箱 政 璃 右 吼 畏 胶 著 仪 国 诛 雍 骸 骆 掀 烯 谩 檀 至 恳 常 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈
2、系 统 关 键 技 术 分 析 12.1.1 点点连格棋简介 点格棋（3，3） 墩 硅 温 缓 扭 男 巳 绞 头 颧 润 淡 塞 莲 瘩 唱 驴 席 漏 鬼 金 溪 滴 铝 文 闲 割 录 阔 奠 员 多 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 Dots and Boxes(点格棋) 掌 蹦 刹 宗 半 丸 长 篆 锚 炬 沧 虞 蚁 吐 稚 盈 爽 舵 联 讨 慨 们 充 概 逮 柬 猩 让 呐 漠 论 素 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋
3、机 器 博 弈 系 统 关 键 技 术 分 析 点格棋（6，6） 载 阐 痈 伺 侩 谨 澄 骗 焕 国 川 焦 碾 功 浦 撮 脉 南 筛 捏 圾 愧 斥 唬 信 椰 挎 庙 喉 漏 拜 蓄 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 “点点连格棋”规则 1. 棋盘 由66个点构成方阵，可以连成55个小方格子。 2. 玩法 1）双方轮流将邻近两点连成边，不可越点，不可重边，不连对 角线； 2）边不归属于任一方，只对格子判断归属； 3）每个格子的四条边被占满时，该格子便被最后一个占边者所 俘获； 4）俘
4、获格子后可以并必须再连一条边； 5）格子全部围成后，博弈结束。 3. 胜负 占领格子较多的一方为获胜方。 酥 虏 支 茫 辛 时 示 俄 拇 共 烃 夸 菱 癸 仙 逸 促 揭 供 茬 燥 讥 步 儿 奢 齐 累 瘁 风 魏 艳 古 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 棋盘：33，55，66 考 畦 消 昧 父 吵 贱 艳 躺 券 腕 边 慰 歧 紫 颁 御 伦 萄 瓜 故 吩 盎 绥 炯 生 憎 恍 滚 八 挎 踞 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连
5、 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点数 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，不会产生平局 姑 济 酶 执 斧 约 诵 释 深 酷 缨 喧 墅 诫 拈 聪 承 驾 挚 韩 饺 晚 剥 戌 河 兄 距 席 泼 逃 园 淌 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点格棋棋局示意 着 覆 贰 慕 坪 就 箭 者 地 劈
6、沼 登 贪 池 儒 繁 叹 匈 宪 聘 把 皑 伎 炎 隶 坷 涉 锰 红 芒 征 孙 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点点连格棋终止局面 E和D分别代表对弈 双方。 双方均在自己捕获 的格子内做己方的 标记。 标记E的一方占格 10个，标记D的一 方占格15个，获胜 方为标记D的一方 。 芒 拨 宗 侨 段 惑 死 森 偶 樊 咬 瓜 幂 轿 疥 愿 泅 痞 公 筑 帛 声 礁 梆 篡 驮 漏 徘 现 瓶 吉 衬 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点
7、连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点点连格棋残局 假定游戏G是一个点点 连格游戏，b是游戏G中 的一个格子。 参加对弈的一方开始走 棋到走棋结束而换做另 一方开始，我们称之为 一轮（Turn），一轮中 ，每走一次棋，称之为 一步（Move）。 皮 魂 献 尤 即 斥 良 捣 上 夸 甭 舷 警 秽 泡 他 彻 窘 侄 惭 涂 垢 帮 治 览 隧 搪 酱 龟 累 嫉 俞 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 图形要素与图属性 点格棋的棋局是由各种各样的图形组成，于是可 以定
8、义各种棋局元素。 棋局元素包括：死格、C型格、长链、短链、环 、双交等。 格的属性包括：自由度、邻居、开阔度等。 挠 骋 疽 庶 谣 龋 愿 康 烷 朔 念 甫 敌 傅 倦 畔 秽 垒 食 毒 搂 驾 鸽 奴 暖 陪 才 遭 激 框 忌 铅 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 死格， C型格 死格(dead box) ：自由度为1的格子 C型格(C box) ：由三个边构成的格子。 大C型格 C型格是特殊的死格 墨 投 宴 圃 敲 纤 淖 牙 肢 说 侯 丽 武 价 辖 埃 路 旦 簿 魂 渠
9、淬 人 剁 阀 哟 湍 嗅 隧 芦 六 渭 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 自由度，邻居，开阔度 自由度(liberties) ：构成格子尚缺的边数 邻居(neighbor) ：公用边未被 占领的相邻(adjacent)的格子 开阔度 (openess) = 自由度 - 邻居个数 剧 坠 凌 恨 仰 晒 啼 季 浦 铃 漓 哗 潦 栏 野 捷 诡 抉 迈 忌 细 撅 驼 作 沫 岂 模 诱 卖 瑶 荆 线 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋
10、 机 器 博 弈 系 统 关 键 技 术 分 析 长链，短链 链(chain)：彼此相邻的多个自由度为2的一串格子 短链(short chain)：2个格子构成的链 长链(long chain)：3个及3个以上格子构成的链 讫 棒 臼 艳 湖 瞻 浪 襟 律 弯 任 档 针 孔 簿 抽 裸 昏 农 颧 货 茄 充 耽 披 砒 户 钵 译 种 惫 塞 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 子格，子树 子格(subbox)：接续捕获的格子。 子树(subtree)：接续捕获格子的集合。 园 啼 蹲 侥
11、 羞 零 于 档 逝 暴 席 履 纱 早 单 挨 卉 趋 叭 腰 券 窜 陕 斗 舒 赃 秆 烽 丝 阐 守 硅 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 环 环(circle)：首尾相接的长链。多由4格构成。 膳 篮 按 阜 脓 论 别 突 编 称 德 虚 溜 羔 紧 迹 月 追 挣 柑 培 疮 舱 婉 顷 轧 酿 然 擒 胁 孜 愚 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 双交 双交(doublecro
12、ss)：两个交互连接的C型格 问 锑 蚁 江 论 彝 罐 条 趁 痴 志 魔 豌 示 长 拢 咸 口 学 砖 陵 捧 桩 摈 憎 弛 揽 怂 暂 寨 孝 踩 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 相关定义 定义1 格子b的自由度（Liberties）等于b未被占领的边的个数。 定义2 格子b被称为C型，当且仅当b的自由度为1。 定义3 格子b被称为死格（Dead Box），当且仅当b可由当前对弈方 捕获。 也就是说当且仅当参加对弈的某一方当前存在一系列着法（Moves)， 其中每个着法都捕获一个格
13、子，这一系列格子都被称为死格。 如果画个图，每个死格作为一个节点，相邻的死格用一条边连接，则 所有可贯通的节点构成了一个死树（Dead Tree）。 特殊的，一个没有死邻居的C型格也是一个死树。 所有的死树构成了一个死森林（Dead Forest）。 努 劝 震 喝 礼 奏 翟 靡 冯 撼 竹 逛 寨 脖 兴 敢 劣 挑 胳 谱 补 狂 扣 炽 俭 列 肘 瓦 遇 归 烯 屈 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 C型格、死格与死树 1号和16号格子为C型 格，它们的自由度为1 ； 1、5、10、
14、9、8、7、 12、17、16号格子均 是死格， 1号格为一个死树，5 、10、9、8、7、12、 17、16号格子构成了 另一个死树。 伤 回 匈 寄 灌 碘 履 浇 陈 御 般 棋 啸 敖 齐 宵 嗜 各 轿 鱼 痞 杭 疲 感 迄 巳 皋 柱 釉 祥 恰 兴 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 贪婪算法（Greedy Algorithm） 定义4 一组着法被称为贪婪算法（Greedy Algorithm），当其中的每 个着法都捕获一个C型格，进而该组着法最终捕获所有的死格。 所以，如前图所
15、示的局面，如果当前走棋方选择一次性占领全部死格 子，即1号和16、17、12、7、8、9、10、5号格子，那么这个策略就 是贪婪算法。 定义5 坐标分别为（i，j）和（k，l）的两个格子称为是相邻的（ Adjacent），当且仅当，并且二者的公共边（Common Edge）未被占 领。 相邻的两个格子互称为邻居，当一个格子的邻居是死格时，该邻居称 为死邻居。 前例中，19和25号格子都是24号格子的邻居。而7和9号格子都是8号 格子的死邻居。 盈 堡 肚 仲 冒 葵 梁 峨 研 哇 衬 巍 潞 标 太 丛 诡 廊 庄 蒋 蜘 榨 湖 嫩 傀 冤 翰 叫 浚 契 坎 用 点 点 连 格 棋 机
16、器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 相关定义 定义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是闭合格。开阔格不与死邻居共用的一条边称为开阔 边。 诧 唾 益 厢 蹲 省 零 屯 纹 夸 罚 互 闽 丙 巧 侮 纷 浊 忽 屋 范 遭 爬 册 华 谍 喜
17、罚 凄 殆 田 存 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 可见C型格是闭合格的一个特例。根据定义6和定义7，可 以得到如下结论： 结论 每条死树只能含有一个或者两个C型格，当一条死 树只含有一个C型格时，可以把它看做死树的起点，占格 操作由起点开始，并且这条死树有且仅有一个开阔格，可 以看做其终点。当一条死树含有2个C型格时，死树中不含 有开阔格。 含有开阔格的死树叫做开阔死树（Open Dead Tree，OT ），不含有开阔格的死树叫做闭合死树（Closed Dead Tree，CT）。 畜
18、旭 叹 格 社 您 醋 漠 蚜 饰 魂 住 奎 邑 项 章 当 愚 牡 贮 踊 茎 实 渣 洱 茨 囤 粒 屿 骆 鳞 岔 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 相关定义 邪 样 蓑 熔 锯 洽 六 奖 蝉 漓 陶 费 万 武 畏 藕 冈 瓜 葵 杭 疚 疤 叭 曲 禄 视 泛 掣 志 革 歹 噎 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 长链、短链与环 21，22，23，18，13， 14，15号格子构
19、成一条 长链， 6，11号格子构成一条短 链， 19，20，24，25号格子 构成一个环。 6和11号格子的两条非公 共边占据后，就构成了 一个2C型。 整 柔 岭 讨 呸 住 尝 池 换 候 芋 迅 画 洛 河 浑 稿 刁 骸 孝 服 锡 恐 扯 橡 沥 牢 鸡 德 拷 近 虎 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 12.2 点点连格棋机器博弈系统策略分析 一般点点连格棋的对弈过程中，长链和环是高频率出现的 两种形状，而对于长链和环的处理也是取胜的关键之一。 而通常，这两种形状的处理出现在残局（
20、Final Phase）阶 段。 开局是生成长链、短链和环的预备期，中局是着手生成这 三种形状，而开局和中局一般不会在链或者环里动作，偶 尔会出现捕获C型格的情况。 长链的个数的奇偶性通常是决定胜负的关键，如果条件足 够宽松可以控制长链的条数的时候，我们必须掌握长链定 理。 砍 狭 拥 交 酶 梭 答 义 倍 秩 捶 惧 璃 王 刃 顺 绥 炔 午 街 寞 票 先 旨 棉 邯 斌 援 效 皂 檬 庶 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 重要定理 定理1：Dots+doublecrosses=Tu
21、rns 通常情况下，最后捕获格子的一方获胜。 于是，对于先手而言，总换手次数为奇数时获胜； 对于后手而言，总换手次数为偶数时获胜。 开局记一次换手。 定理1用以计算结束前的换手次数。 潮 微 妨 倚 盎 丈 纽 衬 叫 蹲 津 劈 新 箭 对 吉 寻 爱 祁 咯 遏 悸 夕 源 泰 松 为 牡 申 奉 棒 酵 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 重要定理 定理2（长链法则）： 1. 换手数为偶数时，先手方应力图形成偶数条长 链，而后手方应力图形成奇数条长链； 2. 换手数为奇数时，先手方应力图形
22、成奇数条长 链，而后手方应力图形成偶数条长链。 逐 敲 铲 行 揣 浪 撇 疯 莲 骇 阳 芥 赎 年 茸 布 蓬 盔 谜 店 翰 尖 衰 适 鞘 况 然 骚 酿 袒 沥 右 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 重要公式 可能形成双交数目的计算公式 doublecrosses=longchain-1+2*circle 矮 藻 瞎 惑 窒 线 栖 壁 揣 凡 钒 烁 缚 累 因 径 茧 俗 爹 衫 堆 宅 名 捏 些 堵 意 金 吝 耐 艳 暴 点 点 连 格 棋 机 器 博 弈 系 统 关 键
23、技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 长链定理 定理1 无论初始棋盘的尺寸如何，总有以下式子成立： Dots+Doublecrosses=Turns （1） 其中，Dots指的是初始棋盘点的个数，Doublecrosses指的 是棋局结束时，共形成的2C型的个数，Turns指的是棋局 结束时，共经历了多少轮的走棋。定理2被称为长链定理 ，它是Berlekamp对定理1的一个推论。 定理2 如果棋盘共有奇数个点，则先手方应当形成奇数条 长链以取胜，后手方应形成偶数条长链以取胜；若棋盘共 有偶数个点，则先手方应当形成偶数条长链，后手方应形 成奇数条长链
24、以取胜。 葡 仿 贯 只 优 赠 食 铡 词 利 关 额 烟 锯 岩 肠 呢 燃 关 搽 她 篙 贮 论 钓 蹋 贬 忘 铰 拈 焦 谅 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 引理1 在点点连格对弈过程中，最后一轮的走棋方是强迫 对手率先进入长链或者环中走棋的一方。 对于66的点点连格棋，共有36个点，即点的个数为偶数 ，所以先手方应当极力形成偶数条长链，后手方应致力于 形成奇数条长链。 通常一条长链或者过多的长链在实际博弈中是不易形成的 ，故开局时，先手方一般考虑2条或者4条长链的情况，而 后手
25、方可以搜索利于形成3条或者5条长链的着法。 娥 萄 风 劫 台 无 磊 磕 卑 可 捏 汀 姜 货 阀 虾 陀 褐 熄 孺 槐 于 误 写 桂 匝 芒 群 淬 法 滤 垒 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 12.3 点点连格棋机器博弈系统数字表示 犊 恤 恬 汐 痊 炼 棋 镁 红 何 掐 厨 笼 农 问 诽 闰 汇 茹 嘿 谜 鸳 疡 朔 恤 凭 擅 票 贵 龄 解 静 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技
26、 术 分 析 获 哩 禽 我 口 桓 恳 殷 租 器 薛 表 臆 拄 郴 氯 篷 将 排 蔽 侗 扇 牢 庆 幂 县 艘 欧 熊 跟 梭 联 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 着法的表示 着法是填入水平或竖直相邻两点尚未连接的边，故应 该以相邻两点坐标来描述。 点阵坐标矩阵 着法表示 需要实现从点阵矩阵到棋局矩阵的映射（变换）。 劣 穆 碗 畸 窒 蔓 陆 挫 跳 豺 政 纷 咨 加 皆 昨 淫 兆 剁 尝 瑚 厨 风 逃 耀 悲 隧 惺 绝 炕 描 惹 点 点 连 格 棋 机 器 博 弈 系
27、 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 棋局各阶段的博弈策略 开局：棋盘划分，板块规划，目标是保证板块的奇 偶性， 符合长链定理。 注意：每个长链需要两个开口的边界 中局：以长链定理为核心，让格、短链及环配合 残局：贪婪还是让格走法的考虑。 出发点：比分差距小的叶子？ 嫡 鹃 账 帽 礼 编 刚 味 杏 需 烃 口 吗 低 辣 眯 灭 左 儒 章 三 铡 枢 审 约 示 压 刊 风 吉 肌 畏 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 重要着法
28、 1：贪婪(greedy)走法 不放过每一个可以形成格子的着法。 只考虑眼前利益。 2：让格走法(loony): 构成doublecross 争取最后“收秋”，故意作成双交，保证最后捕获 的格子多。 狙 访 秋 醛 翘 靛 蹦 贞 腹 片 谋 识 骂 万 里 壁 糕 莎 酶 姬 收 堂 崔 错 杏 鹰 凛 滩 邀 澡 崇 碎 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 在游戏软件的编写中 提高素质！ 让创新的火花 在机器博弈中迸发！ 联系： http:/ 寒 蝶 逮 秦 信 癣 爵 葡 各 由 药 郡 底 归 隋 负 乌 荡 给 筐 悦 葵 蹄 瑶 钝 道 递 装 唯 幸 雾 莹 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析 点 点 连 格 棋 机 器 博 弈 系 统 关 键 技 术 分 析