(ppt)-中国象棋计算机博弈关键技术分析

东北大学人工智能与机器人研究所,中国象棋计算机博弈 关键技术分析,徐心和 东北大学人工智能与机器人研究所 xuxinhegmail.com,2006.4.5,东北大学人工智能与机器人研究所,中象机器博弈的关键技术分析,棋局表示 着法生成 评估函数 博弈搜索 系统开发,东北大学人工智能与机器人研究所,系统建模基本约定,立足红方 向上进攻,东北大学人工智能与机器人研究所,状态演化方程：, 棋谱,(红方),(黑方),中国象棋棋局演化过程,东北大学人工智能与机器人研究所,棋局状态展开示意图,东北大学人工智能与机器人研究所,红方走棋时展开深度为4的博弈树,东北大学人工智能与机器人研究所,象棋博弈软件的基本构成,人机界面 棋局表示与数组管理 着法生成与博弈树展开 棋局评估函数 博弈搜索引擎 开局库 残局库 系统总控,东北大学人工智能与机器人研究所,棋局表示 Board Representation,通常我们使用状态集合来表示 n 时刻的棋局状态。即,棋局状态矩阵 棋子状态矩阵 棋子位置矩阵 比特棋盘矩阵,东北大学人工智能与机器人研究所,棋盘表示与棋盘矩阵,矩阵元素为数偶， 表示棋盘坐标值。,行向,路向,东北大学人工智能与机器人研究所,棋子表示法,黑子中的砗、码、砲将在不便区分车、马、炮的红黑方时使用,东北大学人工智能与机器人研究所,初始棋局状态的表示,行向,路向,东北大学人工智能与机器人研究所,初始棋子状态的表示,东北大学人工智能与机器人研究所,棋子位置矩阵表示法,第1行表示编号为k的棋子在棋盘矩阵中的行号， 第2行表示编号为k的棋子在棋盘矩阵中的列（路）号。,对于初始棋局,东北大学人工智能与机器人研究所,比特棋盘表示法,# 表示计算比特向量（二进制数）对应的十进制整数,东北大学人工智能与机器人研究所,比特棋盘与棋局的布尔条件,比特棋盘用以记录棋局的某些布尔条件。 如果比特棋盘中对应某一格的位是“1”，那么这一格上的条件就是“真”；如果是“0”则对应的条件就是假。 布尔条件就是在“哪些格子上符合你所定义的条件”。 比如，“棋盘哪些位置有棋子？” “棋盘哪些位置有红棋棋子？” “棋盘哪些位置有车？” 这给计算机上的表示带来很大方便：12个字节，96位便可以表示一种条件（高6位为0）。 比特棋盘预置表法在着法生成中具有重要的地位，而且在评估中可以方便地判断棋子相互的联系和威胁。,东北大学人工智能与机器人研究所,初始行、路比特向量对应数值,东北大学人工智能与机器人研究所,#B比特向量索引值,一个10位（9位）比特向量B可以表示一路（行）棋子的分布，它又可以有一个正整数#B作为索引，这将为今后的棋盘分析带来巨大方便； 表示路向棋子全部可行分布情况的索引值范围为0210-1=1023； 表示行向棋子全部可行分布情况的索引值范围为029-1=511； 这样通过索引值就可以找到相应棋子的分布情况。,东北大学人工智能与机器人研究所,棋局的哈希数(H)与哈希变换,生成64位随机数,哈希变换,东北大学人工智能与机器人研究所,棋局的哈希数(H)与哈希变换,由当前棋局P M生成64位随机数,H 便构成当前棋局的索引值，与棋局形成单向对应， 即由P 可以生成H，但由H 无法产生P。 哈希变换没有反变换！,东北大学人工智能与机器人研究所,着法生成原理 Move Generation,着法生成是博弈树展开的关键环节,东北大学人工智能与机器人研究所,着法的表示,相对着法：马八进七，炮5平2非完整信息，需要与当前局面结合 着法算子的运算功能：提-动-落-吃 提址from 即此着的出发位置； 动子moved（chessman moved）即走动的棋子； 落址to 即着法的到达位置； 吃子killed（chessman Captured）即吃掉的棋子。 对着法的要求：合法性、完整性、有序性,东北大学人工智能与机器人研究所,着法生成的棋盘扫描法,确定走动的棋子（moved） 找到该棋子的当前位置（from） 根据象棋规则，扫描棋盘，逐个找到全部合理落址（to）（考虑制约条件、有效区域、本方占位、对方占位等） 如果落址为本方棋子，则不可行；若为对方棋子，则可以吃子（Captured） 如果到达落址，构成 “将军”（叫杀），则应该给对方以提示“将！”,东北大学人工智能与机器人研究所,着法生成的棋盘扫描规则,区域定义： 定义棋盘有效区域 定义红方半区 定义黑方半区 定义红方九宫 定义黑方九宫,字符说明：A-area, R-red, B-black, P-palace,东北大学人工智能与机器人研究所,提址(from)为(i,j)的动子着法生成规则,东北大学人工智能与机器人研究所,提址(from)为(i,j)的动子着法生成规则,东北大学人工智能与机器人研究所,提址(from)为(i,j)的动子着法生成规则,东北大学人工智能与机器人研究所,棋盘扫描法遇到的问题,虽然在着法的表达上，棋盘扫描法最为直观、简洁，但实战意义不强。 因为扫描过程大量耗时：扫描动子、提址、制约条件、合理区域、双方占位、吃子等都是动态生成的，尤其区域判断和棋子种类检测等，时间开销巨大。 对于吃子着法和未吃子着法无法分别生成，只能全部生成，再做筛选。,东北大学人工智能与机器人研究所,模板匹配法,可以为某些动子设计“模板”，只要匹配到提址，便可以迅速找到落址。 通过单项比特矩阵比对，实现“本方子则止，对方子则吃”，完成“提-动-落-吃”内容的确定。 比较适合使用模板的动子为马和相（象）。,走马匹配模板,东北大学人工智能与机器人研究所,预置表法,棋盘状态确定之后，各子的可行着法是确定的。 预置表的思想是把某种棋子在棋盘每个合理位置上，所有可能的棋盘状态下的合理着法预先存储起来，生成一个小型数据表集合。 在生成着法时，通过查询，取代各种计算。 预置表的实质是用空间换时间，即牺牲一定的内存空间加速程序的运行速度。 预置表初始化很费时，但只需在程序开始运行时初始化一次，而且占用内存空间不大。,东北大学人工智能与机器人研究所,预置表法,棋子布局的布尔行向量形式 101000010 非吃子着法的落址为 000110100 可能的吃子着法的落址为 100000000,炮行着法预置表项举例 动子为炮 提址为（i, 6）,东北大学人工智能与机器人研究所,炮着法的预置表总的空间占用计算,每一行棋子的可行排列数恰好对应于9位二进制数（有子为1，无子为0），即 29 = 512 种情况（项）。 考虑到炮在行向的 9 种可能位置，预置表的规模即为 9*512 项。 分别考虑吃子着法与非吃子着法（2倍） 考虑路向情况，则总表规模为 2*9*512+2*10*1024=29696项 每项占用 4 字节，则总空间占用量为 116 k,东北大学人工智能与机器人研究所,预置表的使用,已知动子（炮）的提址（ i , j ） 由第 i 行的比特向量和炮在第 j 位置查找对应的预置表项，分别得到吃子着法的比特向量和非吃子着法的比特向量；吃子着法仅为“可能”，还要判断“本方子则止，对方子则吃”； 查找该行本方棋子比特向量，与吃子着法比特向量“与”，输出为 1 则为非法着法； 查找该行对方棋子比特向量，与吃子着法比特向量“与”，输出为 1 则为合法吃子着法，得到落址； 由该落址便可以得到“吃子”。,东北大学人工智能与机器人研究所,评估函数,在难以判断输赢的情况下识别棋局的好坏，可行的办法就是对局面进行量化 通过为棋局“打分”，评判棋局的好坏。 由于评估需要大量的象棋知识，仁者见仁，智者见智； 评估函数的设计便成为机器博弈中最为人性化和模糊化的部分。 目前对于评估函数取得共识的观点，应该包括如下部分 ：,东北大学人工智能与机器人研究所,固定子力评估值e1(m),车- 600， 炮- 285，马- 270 相- 120，士- 125 兵、卒- 20 帅、将无穷大值，具体数值可以给6000 红方为正值，黑方为负值,东北大学人工智能与机器人研究所,棋子位置评估值e2(m,i,j),各兵种在棋盘的不同位置上权值不同 可由三维数组给出： 三维数组可以按兵种分解为若干个二维数组，而且要区分红方和黑方,x 分别为各兵种代码,东北大学人工智能与机器人研究所,红车位置评估值(m=r),车坐大堂分值最高！,东北大学人工智能与机器人研究所,马窝心和马卧槽大不相同！,红马位置评估值(m=h),东北大学人工智能与机器人研究所,当头炮分值较高！,红炮位置评估值(m=c),东北大学人工智能与机器人研究所,红兵位置评估值(m=p),可见进入九宫的兵顶大车！,东北大学人工智能与机器人研究所,棋子灵活度评估值e3,对各兵种而言，每多一个可走位置就加上一定分值。 如设定：兵-15 士-1 象-1 车-6 马-12 炮-6 将-0,东北大学人工智能与机器人研究所,棋子配合评估值e4,重点是车马炮的配合与牵制。 过河兵牵手可加120分。 连环马、担子炮、霸王车等都可以考虑加分。 将帅安全评估值e5 此项多从盘势上加以考虑。 多子归边、空头炮、当头炮、沉底炮、将帅位置等，都要给予一定的惩罚或奖励分。,东北大学人工智能与机器人研究所,评估函数的计算,本方为正值，对方为负值，其代数和即为当前局面评估值。 显然，总值为正对我方有利，负值对对方有利。绝对值的大小说明双方棋势的差距。 不难看出，评估函数中涉及到的权值系数可能多达上千个，都需要认真选择与权衡。系统开发难点。,东北大学人工智能与机器人研究所,博弈搜索引擎 （Game search engine),东北大学人工智能与机器人研究所,基本定义、概念与称谓,博弈树/对局树（Game tree） 状态空间（State space）状态、初始 状态、目标状态 搜索空间（Search space） 方走棋方/对方， 红方/黑方，Max/Min 节点（局面）根节点，祖父节点/父节点/子节点/孙节点，叶节点 回合连续两个着法，2步为一个回合 着法得分（评估值）,东北大学人工智能与机器人研究所,博弈搜索引擎,搜索策略广度优先（Breadth-first search） 深度优先（Depth-first search） 迭代深化（Iterative search） 搜索技巧 截断/剪枝（cut-off） 剪枝（pruning） 扩展/延伸（extended） 搜索结果返回值/倒推值/局面评估值 最佳路径/当前着法（The best move）,东北大学人工智能与机器人研究所,广度优先搜索近根为先,东北大学人工智能与机器人研究所,深度优先搜索远根为先,东北大学人工智能与机器人研究所,红方走棋时展开深度为4的博弈树,东北大学人工智能与机器人研究所,博弈树分析,博弈树上的每一个节点都代表一个棋局，棋手就是要在众多的叶子节点上挑选一个“最佳的路径与局面”作为自己的选择，从而反推到当前的着法。 中国象棋博弈树的庞大是可以想象的。 如果按照每一步平均有45种可行着法，每局棋平均走90步，那从开始局面展开到分出胜负，则要考虑 种局面。 据说，这一天文数字要比地球上的原子数目还要多，即使用世界上最快的计算机进行计算，直到地球毁灭也无法算出第一步的着法。,东北大学人工智能与机器人研究所,搜索法是求解此类图模型的基本方法,无法搜索到最终的胜负状态，只能靠评估。 搜索的目标如何在有限深度的博弈树中找到评估值最高而又不剧烈波动的最佳棋局目标状态。 最佳路径（Principal continuation）从当前状态出发到达最佳状态的路径，它代表着理智双方精彩对弈的系列着法。 最佳着法（The best move）最佳路径上的第1步棋。 所谓“不剧烈波动”就是说最佳棋局不是在进行子力交换与激烈拼杀的过程当中。,东北大学人工智能与机器人研究所,搜索策略的划分,A类穷尽搜索（Exhau