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

中国象棋计算机博弈 关键技术分析 中象机器博弈的关键技术分析Ø 棋局表示 Ø 着法生成 Ø 评估函数 Ø 博弈搜索 Ø 系统开发系统建模基本约定立足红方 向上进攻状态演化方程： —— 棋谱(红方)(黑方)中国象棋棋局演化过程棋局状态展开示意图红方红方红方黑方黑方Depth 1Depth 3Depth 4Depth 2Depth 0红方走棋时展开深度为4的博弈树 象棋博弈软件的基本构成• 人机界面 • 棋局表示与数组管理 • 着法生成与博弈树展开 • 棋局评估函数 • 博弈搜索引擎 • 开局库 • 残局库 • 系统总控棋局表示 Board Representation• 通常我们使用状态集合来表示 n 时刻的棋局状 态即 ——棋局状态矩阵—— 棋子状态矩阵 ——棋子位置矩阵 ——比特棋盘矩阵棋盘表示与棋盘矩阵矩阵元素为数偶， 表示棋盘坐标值行向路向棋子表示法国际象棋KingRookKnightCannonQueenBishopPawn中国象棋KingRookHorseCannonGuardElephantPawn红子帅车马炮仕相兵Null字母代号krhcbep兵种编码12345670象棋明星 兵种编码020408060c0a0e黑子将车(砗)马(码)炮(砲)士象卒字母代号KRHCBEP兵种编码－1－2－3－4－5－6－7象棋明星 兵种编码121418161c1a1e黑子中的砗、码、砲将在不便区分车、马、炮的红黑方时使用初始棋局状态的表示兵种红帅红车红马红炮红士红相红兵无子 编码 １ ２３４５６７０ 兵种黑将黑车黑马黑炮黑士黑象黑兵 编码－１－２－３－４－５－６－７初始棋子状态的表示编码12345678910111213141516棋子黑将黑车黑马黑炮黑士黑象黑兵编码17181920212223242526272829303132棋子红帅红车红马红炮红士红相红兵棋子位置矩阵表示法k12345678910111213141516 黑将黑车黑马黑炮黑士黑象黑兵 k17181920212223242526272829303132 红帅红车红马红炮红士红相红兵第1行表示编号为k的棋子在棋盘矩阵中的行号， 第2行表示编号为k的棋子在棋盘矩阵中的列（路）号。

对于初始棋局比特棋盘表示法 路向比特向量 ( Vertical ）行向比特向量 ( Horizon )注意：# 表示计算比特向量（二进制数）对应的十进制整数比特棋盘与棋局的布尔条件• 比特棋盘用以记录棋局的某些布尔条件• 如果比特棋盘中对应某一格的位是“1”，那么这一格上 的条件就是“真”；如果是“0”则对应的条件就是假• 布尔条件就是在“哪些格子上符合你所定义的条件”• 比如，“棋盘哪些位置有棋子？” “棋盘哪些位置有红棋 棋子？” “棋盘哪些位置有车？” ……• 这给计算机上的表示带来很大方便：12个字节，96位 便可以表示一种条件（高6位为0） • 比特棋盘预置表法在着法生成中具有重要的地位，而 且在评估中可以方便地判断棋子相互的联系和威胁初始行、路比特向量对应数值#B——比特向量索引值• 一个10位（9位）比特向量B可以表示一路（行 ）棋子的分布，它又可以有一个正整数#B作为 索引，这将为今后的棋盘分析带来巨大方便； • 表示路向棋子全部可行分布情况的索引值范围 为0—210-1=1023； • 表示行向棋子全部可行分布情况的索引值范围 为0—29-1=511； • 这样通过索引值就可以找到相应棋子的分布情 况。

棋局的哈希数(H)与哈希变换黑将黑车黑马黑炮黑士黑象黑兵k12345678910111213141516 kM-1-2-2-3-3-4-4-5-5-6-6-7-7-7-7-7 红帅红车红马红炮红士红相红兵k17181920212223242526272829303132 kM1223344556677777生成64位随机数哈希变换棋局的哈希数(H)与哈希变换为异或算符，H 为64位数形成哈希数（值）由当前棋局P M生成64位随机数H 便构成当前棋局的索引值，与棋局形成单向对应， 即由P 可以生成H，但由H 无法产生P哈希变换没有反变换！着法生成原理 Move Generation• 着法生成是博弈树展开的关键环节着法的表示• 相对着法：马八进七，炮5平2——非完整信息，需要 与当前局面结合 • 着法算子的运算功能：提-动-落-吃• 提址——from 即此着的出发位置； • 动子——moved（chessman moved）即走动的棋子； • 落址——to 即着法的到达位置； • 吃子——killed（chessman Captured）即吃掉的棋子 • 对着法的要求：合法性、完整性、有序性着法生成的棋盘扫描法1.确定走动的棋子（moved） 2.找到该棋子的当前位置（from） 3.根据象棋规则，扫描棋盘，逐个找到全部合 理落址（to）（考虑制约条件、有效区域、 本方占位、对方占位等） 4.如果落址为本方棋子，则不可行；若为对方 棋子，则可以吃子（Captured） 5.如果到达落址，构成 “将军”（叫杀），则应 该给对方以提示——“将！”着法生成的棋盘扫描规则 • 区域定义：• 定义棋盘有效区域• 定义红方半区 • 定义黑方半区 • 定义红方九宫 • 定义黑方九宫 字符说明：A-area, R-red, B-black, P-palace提址(from)为(i,j)的动子着法生成规则 Captured提址(from)为(i,j)的动子着法生成规则Captured提址(from)为(i,j)的动子着法生成规则Captured棋盘扫描法遇到的问题• 虽然在着法的表达上，棋盘扫描法最为直观、 简洁，但实战意义不强。

• 因为扫描过程大量耗时：扫描动子、提址、制 约条件、合理区域、双方占位、吃子等都是动 态生成的，尤其区域判断和棋子种类检测等， 时间开销巨大 • 对于吃子着法和未吃子着法无法分别生成，只 能全部生成，再做筛选 模板匹配法 • 可以为某些动子设计“ 模板”，只要匹配到提 址，便可以迅速找到落 址 • 通过单项比特矩阵比对 ，实现“本方子则止， 对方子则吃”，完成“提 -动-落-吃”内容的确定 • 比较适合使用模板的动 子为马和相（象） 走马匹配模板预置表法• 棋盘状态确定之后，各子的可行着法是确定的 • 预置表的思想是把某种棋子在棋盘每个合理位置 上，所有可能的棋盘状态下的合理着法预先存储 起来，生成一个小型数据表集合 • 在生成着法时，通过查询，取代各种计算 • 预置表的实质是用空间换时间，即牺牲一定的内 存空间加速程序的运行速度 • 预置表初始化很费时，但只需在程序开始运行时 初始化一次，而且占用内存空间不大预置表法• 棋子布局的布尔行向量形式 [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）广度优先搜索——近根为先深度优先搜索——远根为先红方红方红方黑方黑方Depth 1Depth 3Depth 4Depth 2Depth 0红方走棋时展开深度为4的博弈树博弈树分析• 博弈树上的每一个节点都代表一个棋局，棋手 就是要在众多的叶子节点上挑选一个“最佳的 路径与局面”作为自己的选择，从而反推到当 前的着法。

• 中国象棋博弈树的庞大是可以想象的 • 如果按照每一步平均有45种可行着法，每局棋 平均走90步，那从开始局面展开到分出胜负， 则要考虑 种局面 • 据说，这一天文数字要比地球上的原子数目还 要多，即使用世界上最快的计算机进行计算， 直到地球毁灭也无法算出第一步的着法搜索法是求解此类图模型的基本方法 • 无法搜索到最终的胜负状态，只能靠评估 • 搜索的目标——如何在有限深度的博弈树中找到评估 值最高而又不剧烈波动的最佳棋局——目标状态 • 最佳路径（Principal continuation）——从当前状态出 发到达最佳状态的路径，它代表着理智双方精彩对弈 的系列着法。