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

2010中国计算机博弈锦标赛中国计算机博弈锦标赛比赛项目简介比赛项目简介徐徐 心心 和和2010.012010中国计算机博弈锦标赛中国计算机博弈锦标赛比赛项目比赛项目•传统项目传统项目—— 中国象棋中国象棋 围棋围棋 九路围棋九路围棋 六子棋六子棋•新增项目新增项目——点格棋（点格棋（Dots and Boxes））苏拉卡尔塔（苏拉卡尔塔（Surakarta））亚马逊（亚马逊（Amazons））幻影围棋（幻影围棋（ Phantom Go ）） ——国际机器博弈协会（国际机器博弈协会（ICGA）计算机奥林匹克大赛）计算机奥林匹克大赛 （（Computer Olympiad）项目）项目东北大学机器博弈研究室中国象棋（中国象棋（Chinese Chess））•棋盘棋盘 9×10•棋子：红黑各棋子：红黑各7个个兵种，兵种，16子子•各兵种的行棋规各兵种的行棋规则和活动范围则和活动范围•胜负判定准则胜负判定准则•长将、长拖长将、长拖…•时间约束时间约束•60步不吃子判和步不吃子判和东北大学机器博弈研究室围棋（围棋（Go / I-Go））•棋盘棋盘 19×19•轮流下子，谁占轮流下子，谁占的地盘多谁胜。

的地盘多谁胜•先下手为强，贴先下手为强，贴目（目（5-7）•规则最简单，计规则最简单，计算机博弈难度最算机博弈难度最大•当前侧重解决当前侧重解决1/4棋盘棋盘 Go 9×9东北大学机器博弈研究室五子棋（五子棋（ FIR-Five In A Row ））•起源于中国起源于中国•发展在日本（连珠棋）发展在日本（连珠棋）•Renju / Go-Moku•棋盘棋盘 15×15•已被证明先手胜已被证明先手胜•禁手禁手•换手换手•金球制改进球制金球制改进球制东北大学机器博弈研究室六子棋（六子棋（Connect 6））•吴毅成教授发明吴毅成教授发明•棋盘棋盘 19×19•6子连珠为胜子连珠为胜•先手下一子，然后每手先手下一子，然后每手下两子，削减先手优势下两子，削减先手优势•复杂度显著提高复杂度显著提高•台湾已经盛行台湾已经盛行•欧洲也很关注欧洲也很关注东北大学机器博弈研究室点格棋（点格棋（3，，3））东北大学机器博弈研究室Dots and Boxes(点格棋)东北大学机器博弈研究室点格棋（点格棋（6，，6））东北大学机器博弈研究室“点点连格棋”规则1.棋盘由6×6个点构成方阵，可以连成5×5个小方格子。

2.玩法 1）双方轮流将邻近两点连成边，不可越点，不可重边，不连对角线； 2）边不归属于任一方，只对格子判断归属； 3）每个格子的四条边被占满四条边被占满时，该格子便被最后一个占边者所俘获； 4）俘获格子后可以并必须再连一条边； 5）格子全部围成后，博弈结束3.胜负占领格子较多的一方为获胜方东北大学机器博弈研究室苏拉卡尔塔（（ Surakarta））东北大学机器博弈研究室“苏拉卡尔塔”规则1.棋盘棋子1）横竖各6条边构成正方形棋盘，36个交叉点为棋位，各边由8段圆弧连接，通常用2种不同颜色表示2）红黑双方各12枚棋子2.初始状态棋子各方底线排成2排3.玩法 1）双方轮流走棋，每次走动一枚棋子； 2）除了吃子之外，每枚棋子只能沿着垂直或对角方向走动一格，只能走向空位； 3）吃对方子时必须经过至少一个完整的弧线4.胜负吃掉所有对方棋子一方获胜东北大学机器博弈研究室亚马逊亚马逊•棋盘表示：棋盘表示：10×10方阵方阵•棋子：黑白各四个皇后棋子：黑白各四个皇后•占格棋子（可用围棋黑占格棋子（可用围棋黑棋子）棋子）80个，表示路障个，表示路障东北大学机器博弈研究室“亚马逊亚马逊”规则规则1. 棋盘棋子棋盘棋子1）棋盘是由深浅两色间隔排列的）棋盘是由深浅两色间隔排列的100个小方格组成的正方形。

个小方格组成的正方形2）双方各有）双方各有4个（国际象棋）个（国际象棋）“皇后皇后” 棋子，初始棋位如图所示棋子，初始棋位如图所示2. 棋子走法棋子走法 1）双方着法均由两部分构成：先走棋，再）双方着法均由两部分构成：先走棋，再 “放箭放箭”双方轮流走棋并双方轮流走棋并放箭（设障），但不吃子放箭（设障），但不吃子 2）走棋：按照国际象棋）走棋：按照国际象棋 “皇后皇后”的走法，即可以走到横向、竖向和斜的走法，即可以走到横向、竖向和斜向的任何空棋位此棋位称之为向的任何空棋位此棋位称之为“到达棋位到达棋位”；； 3）放箭（设障）：从）放箭（设障）：从“到达棋位到达棋位”向向“皇后皇后”可行的路径上的任一棋可行的路径上的任一棋位放置一个永久性障碍物可以在该点放置一枚黑色的围棋子，任何棋位放置一个永久性障碍物可以在该点放置一枚黑色的围棋子，任何棋子都不可以越过子都不可以越过3. 胜负胜负结束标志为一方没有棋子可以移动最后可以走动棋子的一方获胜结束标志为一方没有棋子可以移动最后可以走动棋子的一方获胜 考虑到白方的先手优势，一般允许黑方有考虑到白方的先手优势，一般允许黑方有n次次pass（不走棋）（不走棋）东北大学机器博弈研究室走棋与放箭走棋与放箭东北大学机器博弈研究室幻影围棋幻影围棋•幻影围棋是一项欧洲的棋类游戏，因为下棋规则是基于幻影围棋是一项欧洲的棋类游戏，因为下棋规则是基于围棋，但又是围棋，但又是在围棋的基础上加入了信息不完全的限制在围棋的基础上加入了信息不完全的限制——看不到对方的落子，看不到对方的落子，故名幻影围棋。

故名幻影围棋•棋盘：棋盘：9×9围棋的棋盘围棋的棋盘•棋子：黑白两种围棋棋子棋子：黑白两种围棋棋子•实际上有实际上有3个棋盘，黑方棋盘，白方棋盘，裁判棋盘个棋盘，黑方棋盘，白方棋盘，裁判棋盘•本方只清楚自己的落子情况，对于对方落子情况只能判本方只清楚自己的落子情况，对于对方落子情况只能判断和猜测裁判的棋盘才给出真正的棋局断和猜测裁判的棋盘才给出真正的棋局东北大学机器博弈研究室东北大学机器博弈研究室幻影围棋棋规幻影围棋棋规1.黑白双方轮流落子，黑白双方轮流落子，落子的基本规则与围棋一致，其中气、禁招等落子的基本规则与围棋一致，其中气、禁招等概念都相同；概念都相同；2.幻影围棋中加入了信息隐藏的概念幻影围棋中加入了信息隐藏的概念——在下棋时，双方都无法看到在下棋时，双方都无法看到对手棋盘上的落子，形成两个不完备信息的棋盘，完备信息的对弈对手棋盘上的落子，形成两个不完备信息的棋盘，完备信息的对弈棋盘是由双方的棋盘取并集而成；棋盘是由双方的棋盘取并集而成；3.由于信息隐藏，就需要一个中间裁判裁判可以看到双方棋盘，也由于信息隐藏，就需要一个中间裁判裁判可以看到双方棋盘，也就是说，就是说，从裁判角度所看到的是一个完备信息的从裁判角度所看到的是一个完备信息的9×9围棋棋盘，并且围棋棋盘，并且根据围棋规则判断双方落子是否合法，如果合法的话返回根据围棋规则判断双方落子是否合法，如果合法的话返回legal，若，若不合法则返回不合法则返回illegal；；4.当有一方落子后出现当有一方落子后出现提子提子情况时，裁判会向双方返回提子数目与位情况时，裁判会向双方返回提子数目与位置信息，双方同时更改棋面；置信息，双方同时更改棋面；5.当一方所有落子都返回当一方所有落子都返回illegal时即可判断该方时即可判断该方PASS；；6.直至双方都无法再落子，即双方都返回直至双方都无法再落子，即双方都返回PASS，此时由裁判根据所占，此时由裁判根据所占地域多少判定胜负。

地域多少判定胜负 东北大学机器博弈研究室一盘人机对弈的棋谱一盘人机对弈的棋谱摘自：摘自：Tristan Cazenave 《《A Phantom Go Program》》黑方（黑方（B）：计算机程序，白方（）：计算机程序，白方（W）：幻影围棋选手）：幻影围棋选手东北大学机器博弈研究室30手后的裁判棋盘手后的裁判棋盘30手后的黑棋棋盘手后的黑棋棋盘摘自：摘自：Tristan Cazenave 《《A Phantom Go Program》》东北大学机器博弈研究室最终棋局最终棋局•领地已经分明，没有继续落领地已经分明，没有继续落子的必要了，双方子的必要了，双方pass•黑先手，落黑先手，落32子；白后手，子；白后手，落落30子，其中子，其中2子被提出子被提出（（H8, J7））•白棋获胜，白棋获胜，49:32•白棋策略：先将棋盘分为左白棋策略：先将棋盘分为左右两部分，做活左半部分，右两部分，做活左半部分，确保优势到最后确保优势到最后东北大学机器博弈研究室在游戏软件的编写中在游戏软件的编写中提高素质！提高素质！让创新的火花让创新的火花在机器博弈中迸发！在机器博弈中迸发！联系：联系： http:/// 东北大学机器博弈研究室。