中国计算机博弈锦标赛新增比赛项目.ppt

东北大学机器博弈研究室,2010中国计算机博弈锦标赛 比赛项目简介,徐 心 和 东北大学机器博弈研究室 2010.01,东北大学机器博弈研究室,2010中国计算机博弈锦标赛 比赛项目,传统项目 中国象棋 围棋 九路围棋 六子棋 新增项目 点格棋（Dots and Boxes） 苏拉卡尔塔（Surakarta） 亚马逊（Amazons） 幻影围棋（ Phantom Go ） 国际机器博弈协会（ICGA）计算机奥林匹克大赛 （Computer Olympiad）项目,东北大学机器博弈研究室,中国象棋（Chinese Chess）,棋盘 910 棋子：红黑各7个兵种，16子 各兵种的行棋规则和活动范围 胜负判定准则 长将、长拖 时间约束 60步不吃子判和,东北大学机器博弈研究室,围棋（Go / I-Go）,棋盘 1919 轮流下子，谁占的地盘多谁胜。 先下手为强，贴目（5-7）。 规则最简单，计算机博弈难度最大。 当前侧重解决1/4棋盘 Go 99,东北大学机器博弈研究室,五子棋（ FIR-Five In A Row ）,起源于中国 发展在日本（连珠棋） Renju / Go-Moku 棋盘 1515 已被证明先手胜 禁手 换手 金球制改进球制,东北大学机器博弈研究室,六子棋（Connect 6）,吴毅成教授发明 棋盘 1919 6子连珠为胜 先手下一子，然后每手下两子，削减先手优势 复杂度显著提高 台湾已经盛行 欧洲也很关注,东北大学机器博弈研究室,点格棋（3，3）,东北大学机器博弈研究室,Dots and Boxes(点格棋),东北大学机器博弈研究室,点格棋（6，6）,东北大学机器博弈研究室,“点点连格棋”规则,棋盘 由66个点构成方阵，可以连成55个小方格子。 玩法 1）双方轮流将邻近两点连成边，不可越点，不可重边，不连对角线； 2）边不归属于任一方，只对格子判断归属； 3）每个格子的四条边被占满时，该格子便被最后一个占边者所俘获； 4）俘获格子后可以并必须再连一条边； 5）格子全部围成后，博弈结束。 胜负 占领格子较多的一方为获胜方。,东北大学机器博弈研究室,苏拉卡尔塔（ Surakarta）,东北大学机器博弈研究室,“苏拉卡尔塔”规则,棋盘棋子 1）横竖各6条边构成正方形棋盘，36个交叉点为棋位，各边由8段圆 弧连接，通常用2种不同颜色表示。 2）红黑双方各12枚棋子。 初始状态 棋子各方底线排成2排。 玩法 1）双方轮流走棋，每次走动一枚棋子； 2）除了吃子之外，每枚棋子只能沿着垂直或对角方向走动一格，只 能走向空位； 3）吃对方子时必须经过至少一个完整的弧线。 胜负 吃掉所有对方棋子一方获胜。,东北大学机器博弈研究室,亚马逊,棋盘表示：1010方阵 棋子：黑白各四个皇后 占格棋子（可用围棋黑棋子）80个，表示路障,东北大学机器博弈研究室,“亚马逊”规则,1. 棋盘棋子 1）棋盘是由深浅两色间隔排列的100个小方格组成的正方形。 2）双方各有4个（国际象棋）“皇后” 棋子，初始棋位如图所示。 2. 棋子走法 1）双方着法均由两部分构成：先走棋，再 “放箭”。双方轮流走棋并放箭（设障），但不吃子。 2）走棋：按照国际象棋 “皇后”的走法，即可以走到横向、竖向和斜向的任何空棋位。此棋位称之为“到达棋位”； 3）放箭（设障）：从“到达棋位”向“皇后”可行的路径上的任一棋位放置一个永久性障碍物。可以在该点放置一枚黑色的围棋子，任何棋子都不可以越过。 3. 胜负 结束标志为一方没有棋子可以移动。最后可以走动棋子的一方获胜。 考虑到白方的先手优势，一般允许黑方有n次pass（不走棋）,东北大学机器博弈研究室,走棋与放箭,东北大学机器博弈研究室,幻影围棋,幻影围棋是一项欧洲的棋类游戏，因为下棋规则是基于围棋，但又是在围棋的基础上加入了信息不完全的限制看不到对方的落子，故名幻影围棋。 棋盘：99围棋的棋盘。 棋子：黑白两种围棋棋子。 实际上有3个棋盘，黑方棋盘，白方棋盘，裁判棋盘。 本方只清楚自己的落子情况，对于对方落子情况只能判断和猜测。裁判的棋盘才给出真正的棋局。,东北大学机器博弈研究室,东北大学机器博弈研究室,幻影围棋棋规,黑白双方轮流落子，落子的基本规则与围棋一致，其中气、禁招等概念都相同； 幻影围棋中加入了信息隐藏的概念在下棋时，双方都无法看到对手棋盘上的落子，形成两个不完备信息的棋盘，完备信息的对弈棋盘是由双方的棋盘取并集而成； 由于信息隐藏，就需要一个中间裁判。裁判可以看到双方棋盘，也就是说，从裁判角度所看到的是一个完备信息的99围棋棋盘，并且根据围棋规则判断双方落子是否合法，如果合法的话返回legal，若不合法则返回illegal； 当有一方落子后出现提子情况时，裁判会向双方返回提子数目与位置信息，双方同时更改棋面； 当一方所有落子都返回illegal时即可判断该方PASS； 直至双方都无法再落子，即双方都返回PASS，此时由裁判根据所占地域多少判定胜负。,东北大学机器博弈研究室,一盘人机对弈的棋谱,黑方（B）：计算机程序，白方（W）：幻影围棋选手,东北大学机器博弈研究室,30手后的裁判棋盘,30手后的黑棋棋盘,摘自：Tristan Cazenave A Phantom Go Program,东北大学机器博弈研究室,最终棋局,领地已经分明，没有继续落子的必要了，双方pass 黑先手，落32子；白后手，落30子，其中2子被提出（H8, J7） 白棋获胜，49:32 白棋策略：先将棋盘分为