中象计算机博弈关键技术分析

《中象计算机博弈关键技术分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国象棋计算机博弈关键技术分析徐心和东北大学人工智能与机器人研究所xuxinhe@gmail.com2006.4.5东北大学人工智能与机器人研究所中象机器博弈的关键技术分析棋局表示着法生成评估函数博弈搜索系统开发东北大学人工智能与机器人研究所系统建模基本约定立足红方向上进攻东北大学人工智能与机器人研究所状态演化方程：——棋谱(红方)(黑方)中国象棋棋局演化过程东北大学人工智能与机器人研究所棋局状态展开示意图东北大学人工智能与机器人研究所红方红方红方黑方黑方Depth1Depth3Depth4Dep

2、th2Depth0红方走棋时展开深度为4的博弈树东北大学人工智能与机器人研究所象棋博弈软件的基本构成人机界面棋局表示与数组管理着法生成与博弈树展开棋局评估函数博弈搜索引擎开局库残局库系统总控东北大学人工智能与机器人研究所棋局表示BoardRepresentation通常我们使用状态集合来表示n时刻的棋局状态。即——棋局状态矩阵——棋子状态矩阵——棋子位置矩阵——比特棋盘矩阵东北大学人工智能与机器人研究所棋盘表示与棋盘矩阵矩阵元素为数偶，表示棋盘坐标值。行向路向东北大学人工智能与机器人研究所棋子表示法

3、国际象棋KingRookKnightCannonQueenMinisterPawn中国象棋KingRookHorseCannonBishopElephantPawn红子帅车马炮仕相兵Null字母代号krhcbep棋局编码12345670象棋明星兵种编码020408060c0a0e黑子将车(砗)马(码)炮(砲)士象卒字母代号KRHCBEP棋局编码－1－2－3－4－5－6－7象棋明星兵种编码121418161c1a1e黑子中的砗、码、砲将在不便区分车、马、炮的红黑方时使用东北大学人工智能与机器人研究所初

4、始棋局状态的表示兵种红帅红车红马红炮红士红相红兵无子编码１２３４５６７０兵种黑将黑车黑马黑炮黑士黑象黑兵编码－１－２－３－４－５－６－７行向路向东北大学人工智能与机器人研究所初始棋子状态的表示编码12345678910111213141516棋子黑将黑车黑马黑炮黑士黑象黑兵编码17181920212223242526272829303132棋子红帅红车红马红炮红士红相红兵东北大学人工智能与机器人研究所棋子位置矩阵表示法k12345678910111213141516黑将黑车黑马黑炮黑士黑象黑兵k17

5、181920212223242526272829303132红帅红车红马红炮红士红相红兵第1行表示编号为k的棋子在棋盘矩阵中的行号，第2行表示编号为k的棋子在棋盘矩阵中的列（路）号。对于初始棋局东北大学人工智能与机器人研究所比特棋盘表示法路向比特向量(Vertical）行向比特向量(Horizon)注意：#表示计算比特向量（二进制数）对应的十进制整数行向路向东北大学人工智能与机器人研究所比特棋盘与棋局的布尔条件比特棋盘用以记录棋局的某些布尔条件。如果比特棋盘中对应某一格的位是“1”，那么这一格上的条

6、件就是“真”；如果是“0”则对应的条件就是假。布尔条件就是在“哪些格子上符合你所定义的条件”。比如，“棋盘哪些位置有棋子？”“棋盘哪些位置有红棋棋子？”“棋盘哪些位置有车？”……这给计算机上的表示带来很大方便：12个字节，96位便可以表示一种条件（高6位为0）。比特棋盘预置表法在着法生成中具有重要的地位，而且在评估中可以方便地判断棋子相互的联系和威胁。东北大学人工智能与机器人研究所初始行、路比特向量对应数值东北大学人工智能与机器人研究所#B——比特向量索引值一个10位（9位）比特向量B可以表示一路（

7、行）棋子的分布，它又可以有一个正整数#B作为索引，这将为今后的棋盘分析带来巨大方便；表示路向棋子全部可行分布情况的索引值范围为0—210-1=1023；表示行向棋子全部可行分布情况的索引值范围为0—29-1=511；这样通过索引值就可以找到相应棋子的分布情况。东北大学人工智能与机器人研究所棋局的哈希数(H)与哈希变换黑将黑车黑马黑炮黑士黑象黑兵k12345678910111213141516kM-1-2-2-3-3-4-4-5-5-6-6-7-7-7-7-7红帅红车红马红炮红士红相红兵k171819

8、20212223242526272829303132kM1223344556677777生成64位随机数哈希变换东北大学人工智能与机器人研究所棋局的哈希数(H)与哈希变换为异或算符，H为64位数形成哈希数（值）由当前棋局PM生成64位随机数H便构成当前棋局的索引值，与棋局形成单向对应，即由P可以生成H，但由H无法产生P。哈希变换没有反变换！东北大学人工智能与机器人研究所着法生成原理MoveGeneration着法生成是博弈树展开的关键环节东北大学人工智能与机器人研究所