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