点点连格棋机器博弈系统关键技术分析.ppt
《点点连格棋机器博弈系统关键技术分析.ppt》由会员分享,可在线阅读,更多相关《点点连格棋机器博弈系统关键技术分析.ppt(37页珍藏版)》请在三一文库上搜索。
1、东北大学机器博弈研究室,第12章 点点连格棋机器博弈系统 关键技术分析,连 莲 徐心和 东北大学机器博弈研究室 2010.01,东北大学机器博弈研究室,东北大学机器博弈研究室,12.1.1 点点连格棋简介,点格棋(3,3),东北大学机器博弈研究室,Dots and Boxes(点格棋),东北大学机器博弈研究室,点格棋(6,6),东北大学机器博弈研究室,“点点连格棋”规则,棋盘 由66个点构成方阵,可以连成55个小方格子。 玩法 1)双方轮流将邻近两点连成边,不可越点,不可重边,不连对角线; 2)边不归属于任一方,只对格子判断归属; 3)每个格子的四条边被占满时,该格子便被最后一个占边者所俘获;
2、 4)俘获格子后可以并必须再连一条边; 5)格子全部围成后,博弈结束。 胜负 占领格子较多的一方为获胜方。,东北大学机器博弈研究室,棋盘:33,55,66,东北大学机器博弈研究室,点数 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,不会产生平局,东北大学机器博弈研究室,点格棋棋局示意,东北大学机器博弈研究室,点点连格棋终止局面,E和D分别代表对弈双方。 双方均在自己捕获的格子内做己方的标记。 标记E的一方占格10个,标记D的一方占格15个,
3、获胜方为标记D的一方。,东北大学机器博弈研究室,点点连格棋残局,假定游戏G是一个点点连格游戏,b是游戏G中的一个格子。 参加对弈的一方开始走棋到走棋结束而换做另一方开始,我们称之为一轮(Turn),一轮中,每走一次棋,称之为一步(Move)。,东北大学机器博弈研究室,图形要素与图属性,点格棋的棋局是由各种各样的图形组成,于是可以定义各种棋局元素。 棋局元素包括:死格、C型格、长链、短链、环、双交等。 格的属性包括:自由度、邻居、开阔度等。,东北大学机器博弈研究室,死格, C型格,死格(dead box) :自由度为1的格子 C型格(C box) :由三个边构成的格子。 大C型格 C型格是特殊的
4、死格,东北大学机器博弈研究室,自由度,邻居,开阔度,自由度(liberties) :构成格子尚缺的边数 邻居(neighbor) :公用边未被 占领的相邻(adjacent)的格子 开阔度 (openess) = 自由度 - 邻居个数,东北大学机器博弈研究室,长链,短链,链(chain):彼此相邻的多个自由度为2的一串格子 短链(short chain):2个格子构成的链 长链(long chain):3个及3个以上格子构成的链,东北大学机器博弈研究室,子格,子树,子格(subbox):接续捕获的格子。 子树(subtree):接续捕获格子的集合。,东北大学机器博弈研究室,环,环(circle
5、):首尾相接的长链。多由4格构成。,东北大学机器博弈研究室,双交,双交(doublecross):两个交互连接的C型格,东北大学机器博弈研究室,相关定义,定义1 格子b的自由度(Liberties)等于b未被占领的边的个数。 定义2 格子b被称为C型,当且仅当b的自由度为1。 定义3 格子b被称为死格(Dead Box),当且仅当b可由当前对弈方捕获。 也就是说当且仅当参加对弈的某一方当前存在一系列着法(Moves),其中每个着法都捕获一个格子,这一系列格子都被称为死格。 如果画个图,每个死格作为一个节点,相邻的死格用一条边连接,则所有可贯通的节点构成了一个死树(Dead Tree)。 特殊的
6、,一个没有死邻居的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型格,进而该组着法最终捕获所有的死格。 所以,如前图所示的局面,如果当前走棋方选择一次性占领全部死格子,即
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 点点 连格棋 机器 博弈 系统 关键技术 分析
链接地址:https://www.31doc.com/p-3404429.html