计算机博弈引擎协议和博弈程序比赛ppt课件.ppt

03 03 2020 1 计算机博弈引擎协议和博弈程序比赛mailto 计算机博弈引擎协议和博弈程序比赛 03 03 2020 2 报告内容 1 国际象棋引擎协议历史2 博弈引擎协议3 博弈程序自动比赛4 UCCI引擎协议和UCCI引擎联赛 1 国际象棋引擎协议历史 03 03 2020 3 国际象棋引擎协议历史1 1从MANIAC到 深蓝 1 国际象棋引擎协议历史 c KenTompson和他设计的Belle a 最早机器下棋的构想 1769年 b 第一台会下棋MANIAC 1950年 03 03 2020 4 1 国际象棋引擎协议历史 d 深蓝 的两位设计师HansBerliner和许峰雄 e KenThompson和GaryKasparov 1 1从MANIAC到 深蓝 03 03 2020 5 1 2GNUChess和XBoard 1 国际象棋引擎协议历史 f WinBoard g WinBoard的作者TimMann h Crafty的作者RobertHyattCrafty是国际象棋程序的教科书 03 03 2020 6 1 国际象棋引擎协议历史 1 3WinBoard ChessBase和UCI并存的格局 XBoard WinBoard协议 最早 用得最多的开放引擎协议1986年 GNUChess诞生 有了文本界面的概念 1991年 XBoard诞生 支持Xboard的文本界面 1993年 Xboard在Windows下的版本WinBoard诞生 WinBoard协议形成体系 截止至2006年7月 支持WinBoard的程序共有312个 WBECRidderkerk ChessBase协议 ChessBase系列国际象棋程序的专用引擎协议1998年 由Fritz首创 支持Junior Hiarcs Shredder NIMZO等程序 2002年 由于Shredder创立UCI的原因 ChessBase开始全面支持UCI 目前支持5个商业引擎 Fritz Junior Hiarcs NIMZO和Zap Chess 和9个免费引擎 大都改自开放源程序的WinBoard引擎 UCI Chess960协议 新兴的开放引擎协议 与WinBoard相抗衡2000年 Shredder创立UCI协议 2002年 ChessBase开始全面支持UCI 截止至2006年7月 支持UCI的程序共有89个 其中65个也支持WinBoard WBECRidderkerk的统计数据 不包括克隆程序 如TogaII 03 03 2020 7 1 4WBECRidderkerk和PolyGlot WBECRidderkerk 规模最大的国际象棋引擎联赛组织2001年 WBECRidderkerk开始对WinBoard引擎进行测试 冠军引擎 Gandalf 第1期 Ruffian 第2 3期 DeepSjeng 第4 6期 第5期没有举行顶级组联赛 TheKing 第7期 PolyGlot 使UCI引擎和WinBoard引擎同台竞技2004年 UCI到WinBoard的适配器PolyGlot诞生 同年UCI引擎都加入了WBECRidderkerk联赛的行列 冠军引擎 Shredder 第8 9 10期 Fruit 第11期 Rybka 第12期 最近几期的冠军全部被UCI引擎包揽 1 国际象棋引擎协议历史 03 03 2020 8 报告内容1 国际象棋引擎协议历史 2 博弈引擎协议3 博弈程序自动比赛4 UCCI引擎协议和UCCI引擎联赛 2 博弈引擎协议 03 03 2020 9 博弈引擎协议2 1界面 引擎和 界面 引擎协议 界面 GUI 可视化操作模块 引擎 智能核心模块 界面 引擎协议 简称引擎协议 界面和引擎耦合方式 通讯方式 针对一个界面 符合某一协议的 可以设计出水平更高的引擎 针对一个引擎 符合某一协议的 可以设计出功能更强大的界面 引擎协议的意义在于 使博弈软件的设计者更专著于某一模块 要么是界面 要么是引擎 的设计 2 博弈引擎协议 03 03 2020 10 2 博弈引擎协议 2 2博弈引擎协议的技术特点A 通讯方式B 工作方式 同步和异步C 语法 指令和反馈D 后台思考E 认输和提和F 禁止着法G 历史着法 03 03 2020 11 标准输入 输出通道的通讯方式 A 通讯方式 ChessBase等非开放的引擎协议 类似DLL的API函数程序库 WinBoard UCI等开放的引擎协议 通过标准输入 输出通道实现通讯 标准输入 输出通道的优点 a 有利于引擎和界面的跨平台发展 b 单一的引擎或单一的界面有实现商业化的可能 界面程序向引擎程序传送的信息称为 指令 引擎程序向界面程序传诵的信息称为 反馈 2 博弈引擎协议 03 03 2020 12 同步方式 异步方式 B 工作方式 同步和异步 同步方式 界面和引擎采用同样的棋局进程 优点 通讯简单 缺点 a 引擎重复了界面的棋局进程处理 b 要应对 不同步 的情况 异步方式 引擎没有棋局进程 而只是针对一系列局面进行思考 给出着法 优点 a 无需处理棋局进程 b 不存在 不同步 的情况 缺点 a 通讯量大 协议内容繁多 b 要解决历史着法引起的重复局面问题 2 博弈引擎协议 03 03 2020 13 C 语法 指令和反馈 指令和反馈的要求 i 文本方式和行方式 ii 界面和引擎都随时待命 iii 语法规范 类似于DOS UNIX的控制台命令 引擎的状态 i 等待状态 ii 思考状态 语法说明书和示例 指令用红色表示 反馈用蓝色表示 ucciidnameElephantEyeDemooptionusemillisectypecheckdefaultfalseoptionusebooktypecheckdefaulttrueuccioksetoptionusemillisectruesetoptionusebookfalsepositionfenrnbakabnr 9 1c5c1 p1p1p1p1p 9 9 P1P1P1P1P 1C5C1 9 RNBAKABNRw 01gotime300000increment0infodepth6score4pvb0c2b9c7c3c4h9i7c2d4h7e7infonodes5000000time5000stopbestmoveb0c2ponderb9c7quitbye 引导状态 空闲状态 思考状态 空闲状态 2 博弈引擎协议 03 03 2020 14 D 后台思考 同步方式 引擎自动控制 有 是否启用后台思考 的开关 easy hard 异步方式 由界面控制 有专门的处理后台思考的指令和反馈 后台思考的工作原理 猜测着法 i 引擎提供猜测着法 bestmoveponder和是主要变例的前两个着法 ii 界面要求进行后台 goponderiii 对方着法与猜测着法一致 后台思考命中 ponderhitiv 后台思考没有命中 stop go 2 博弈引擎协议 03 03 2020 15 E 认输和提和 人类棋手采用的提和规则 走棋的一方提和 不走棋的一方决定是否接受提和 电脑的问题 是否 接受提和 是需要计算的 这样会打断 后台思考 适应电脑的提和规则 i 走棋的一方可在走棋的同时提和 ii 轮到对方走棋时 对方可以选择提和 也可以继续走棋 异步方式引擎协议对认输和提和的规定 i 引擎认输 bestmoveponderresignii 界面不需要向引擎发出认输指令 iii 引擎提和 bestmoveponderdrawiv 界面向引擎提和 godrawv 界面向引擎提和 后台思考命中 ponderhitdrawvi 引擎拒绝提和 bestmovepondervii 引擎接受提和 bestmoveponderdrawviii 界面不需要向引擎发出接受提和的指令 2 博弈引擎协议 03 03 2020 16 F 禁止着法 长打 中国象棋规则问题的疑难杂症 人类棋手采用的做法 遇到争议 由裁判作出仲裁 电脑可以采用的做法 如果不能正确判断 可由人类作出仲裁 界面向引擎发出禁止着法的指令 banmoves 2 博弈引擎协议 6回合后 红方没有禁着 车二进一是禁着界面要向引擎发送 banmovesh8h9 03 03 2020 17 G 历史着法 问题 引擎如何自动避免走出禁止着法 2回合后 红方没有禁着 2回合后 车二进一不是禁着6回合后 车二进一是禁着 6回合后 解决 界面向引擎传达历史着法 position moves 例 positionfen4k4 9 5a3 4r4 9 9 9 9 9 5K1R1w 01movesh0h9e9e8 2 博弈引擎协议 03 03 2020 18 2 3引擎协议适配器 实现两种不同的引擎协议之间的转换和通用 适配器的方向性 从 引擎端协议 到 界面端协议 例如 WinBoard 引擎 到ChessBase 界面 的适配器WinBoard 引擎 到UCI 界面 的适配器 WB2UCIUCI 引擎 到WinBoard 界面 的适配器 PolyGlot浅红象棋 引擎 到UCCI 界面 的适配器 QH2UCCIUCCI 引擎 到浅红象棋 界面 的适配器 UCCI2QH 2 博弈引擎协议 03 03 2020 19 报告内容1 国际象棋引擎协议历史2 博弈引擎协议 3 博弈程序自动比赛4 UCCI引擎协议和UCCI引擎联赛 3 博弈程序自动比赛 03 03 2020 20 3 博弈程序自动比赛 博弈程序自动比赛3 1国际大赛普遍采用的方式 手动比赛 ICGA11thComputerOlympiad 14thWorldComputer ChessChampionship WCCC 2004年世界电脑象棋争霸赛 2005年世界电脑围棋争霸赛 全国首届计算机博弈锦标赛3 2手动比赛带来的问题 比机器还是比程序 电脑之间的比赛为什么要人来操作 能否延长赛程 03 03 2020 21 3 博弈程序自动比赛 3 3民间赛事 自动比赛 WinBoardEngineCompetition WBEC Ridderkerk Netherlands Gomocup 电脑象棋 UCCI引擎 联赛3 4自动比赛的优势和技术问题 硬件环境公平 实现全天候工作 不需要人工操作 不需要参赛者到场 建立程序间的通讯方式 引擎协议是现成的通讯方式 赛程控制程序WinBoardTournamentManager WBTM UCCI引擎联赛模拟器 对比赛环境 程序 赛制等都要有详细严格的要求 WBEC有详细的规定 03 03 2020 22 3 5WBEC的环境和程序要求 硬件环境 每个级别联赛在一台机器上进行 双处理器 1024MB存储器 从超级到末级 处理器依次为 Opteron244 超级和甲级 AthlonMP2600 AthlonMP2400 AthlonMP2200 P3 1266Mhz 操作系统 WindowsXPPro64 超级和甲级 Windows2000Pro 其他级别 比赛软件 WBTM 联赛控制程序 WinBoard X 自动对弈程序 PolyGlot UCI到WinBoard适配器 3 4 5子Nalimov残局库 报名要求 在报名截止日期前将程序发给赛事组织者提供 程序要求 单线程的WinBoard或UCI引擎 程序设置 参赛者可提供最适合本程序的配置文件和开局库 稳定性要求 正式比赛前 进行1次3分钟走40步的测试赛 测试赛中程序崩溃超过2局 或者超时局数超过10 则取消正式比赛资格 但发现问题的程序有机会修正错误 或者用旧版稳定的程序代替 存储器限制 最多使用128MB置换表和32MB残局库缓冲区 程序版权 注名所有程序参与者 包括 作者限制 一位作者 程序的主要参与者 只能有一个程序参赛 参赛者权利 赛前可让赛事组织者测试其程序是否符合联赛规则 3 博弈程序自动比赛 03 03 2020 23 3 6WBEC的赛制和规则 时限 时段制 40分钟走40步 启用后台思考 因此需要使用双处理器 判和规则 1 逼和 2 50回合没有吃子或进兵 3 3次重复局面 4 双方明显没有足够子力获胜 例如王马对王 或王象对王 判负规则 1 被将死 例外情况 对方明显没有足够子力获胜 则判和 2 超时 例外同上 3 错判 将死 或 和棋 例外同上 4 不合法着法 例外同上 5 程序崩溃 例外同上 平分的名次判定依据 1 相互胜负 2 总胜局多者在前 3 执黑得分高者在前 3 博弈程序自动比赛 03 03 2020 24 3 7WBEC的升降级制度 超级 甲级 乙级 丙级 各24个程序 进行4次循环赛 先后手各两局 丁级32个程序 进行2次循环赛 先后手各一局 其余程序都编入末级 进行若干次循环赛 取决于参赛程序的数量 各级 除超级外 的第1名直接升入上一级别 甲级到丁级第2至5名和末级第2至7名要参加上一级别的资格赛 超级到乙级的最后5名 丙级和丁级的最后7名要参加同一级别的资格赛 超级到丙级资格赛的前4名和丁级资格赛的前6名留将参加本级别联赛 其余程序降入下一级别 超级 甲级 乙级 丙级资格赛进行4次循环赛 丁级进行2次循环赛 某个程序的等级分比任何一级的第10名还高 就有资格跟该级别的第10 11和12名各进行4局比赛 达到6 5分即可参该级别的联赛 这会给程序跳级的机会 如果某一级别的跳级没有成功 那么该程序可以尝试低一级别的跳级测试 新的程序加入时 首先跟丁级的第10 11和12名各进行4局比赛 达到6分即可参加该级别 并且用同样的过程测试是否参加更高级别的比赛 3 博弈程序自动比赛 03 03 2020 25 4 UCCI引擎协议和UCCI引擎联赛 报告内容1 国际象棋引擎协议历史2 博弈引擎协议3 博弈程序自动比赛 4 UCCI引擎协议和UCCI引擎联赛 03 03 2020 26 UCCI引擎协议和UCCI引擎联赛4 1UCCI引擎协议的初衷 2004年开设 象棋百科全书 网站 借鉴国际象棋的方法和理念 在中国象棋中引进ECCO PGN FEN等概念 中国象棋程序设计 这一课题成为试金石 UCI协议成为借鉴的首选4 2UCCI引擎协议的发展 UCCI引擎协议并非最早的中国象棋引擎协议 2000年 梦入神蛋 KillEgg 是首个公开源代码的中国象棋程序 2003年 浅红象棋 V2 8 支持引擎 并把梦入神蛋制成浅红象棋引擎 2005年 第一个UCCI界面 象堡 和第一个UCCI引擎 象眼 诞生 2006年 第一期UCCI引擎联赛举行 参赛程序有8个 截止到2006年7月 在 象棋百科全书 网站上登记的UCCI引擎共有16个 4 UCCI引擎协议和UCCI引擎联赛 03 03 2020 27 4 UCCI引擎协议和UCCI引擎联赛 2006年3月 UCCI界面 象堡 更名为 象棋巫师 03 03 2020 28 4 UCCI引擎协议和UCCI引擎联赛 4 3UCCI引擎联赛 2006年1月 UCCI引擎联赛模拟器研制成功 支持加时制时限和循环赛制 2006年2月 第一期UCCI引擎联赛举行 参赛程序有8个 2006年7月 梦入神蛋制成UCCI引擎参加第6期联赛 在联赛中排名垫底 2006年2月至7月 UCCI引擎联赛共举行了6期第1期 上海站 2 20 2 26 8队28轮快棋 象眼 夺冠第2期 北京站 3 24 3 27 8队28轮快棋 象棋旋风 夺冠第3期 南宁站 4 21 4 24 9队36轮慢棋 象棋旋风 夺冠第4期 南宁站 4 21 4 24 9队36轮快棋 EndEgg 夺冠第5期 南京站 6 2 6 9 12队44轮快棋 象棋旋风 夺冠第6期 杭州站 7 13 7 19 9队36轮慢棋 象棋旋风 夺冠 联赛的环境和程序要求 i 32位Windows平台 单线程的UCCI引擎 不启用后台思考 ii 用时和存储器限制视东道主提供的比赛用机器而定 联赛采用的规则 i 将死 不合法着法 单方面长将 超时判负 ii 50回合不吃子 除单方面长将外的循环着法判和 03 03 2020 29 4 UCCI引擎协议和UCCI引擎联赛 4 4中国象棋自动对弈的难题 用程序描述规则 亚洲规则的实现比中国规则简单 所以电脑象棋程序大都只支持亚洲规则 亚洲规则的 打 只包括 将 和 捉 不包括 杀 和 要抽吃 目前还没有一个程序声称完全支持亚洲规则 捉 的定义 自己的一个子可以攻击到对方的一个子 捉 的补充规定 i 走子之前已经构成攻击的不算捉 ii 兵 卒 和帅 将 的捉不算捉 iii 不能吃掉被捉子 吃掉后即被将死 的情况