的着法最佳值.ppt

中国象棋计算机博弈关键技术分析 徐心和 东北大学人工智能与机器人研究所 xuxinhe@ 中象机器博弈的关键技术分析 棋局表示 着法生成 评估函数 博弈搜索 系统开发 象棋博弈软件的基本构成 人机界面 棋局表示与数组管理 着法生成与博弈树展开 棋局评估函数 博弈搜索引擎 开局库 残局库 系统总控 棋局表示Board Representation 通常我们使用状态集合来表示 n 时刻的棋局状态。即 棋盘表示与棋盘矩阵 初始棋子状态的表示 棋子位置矩阵表示法 比特棋盘表示法 比特棋盘与棋局的布尔条件 比特棋盘用以记录棋局的某些布尔条件。 如果比特棋盘中对应某一格的位是“1”，那么这一格上的条件就是“真”；如果是“0”则对应的条件就是假。 布尔条件就是在“哪些格子上符合你所定义的条件”。 比如，“棋盘哪些位置有棋子？” “棋盘哪些位置有红棋棋子？” “棋盘哪些位置有车？” …… 这给计算机上的表示带来很大方便：12个字节，96位便可以表示一种条件（高6位为0）。 比特棋盘预置表法在着法生成中具有重要的地位，而且在评估中可以方便地判断棋子相互的联系和威胁。 #B——比特向量索引值 一个10位（9位）比特向量B可以表示一路（行）棋子的分布，它又可以有一个正整数#B作为索引，这将为今后的棋盘分析带来巨大方便； 表示路向棋子全部可行分布情况的索引值范围为0—210-1=1023； 表示行向棋子全部可行分布情况的索引值范围为0—29-1=511； 这样通过索引值就可以找到相应棋子的分布情况。 棋局的哈希数(H)与哈希变换 棋局的哈希数(H)与哈希变换 着法生成原理Move Generation 着法生成是博弈树展开的关键环节 着法的表示 相对着法：马八进七，炮5平2——非完整信息，需要与当前局面结合 着法算子的运算功能：提-动-落-吃 提址——from 即此着的出发位置； 动子——moved（chessman moved）即走动的棋子； 落址——to 即着法的到达位置； 吃子——killed（chessman Captured）即吃掉的棋子。 对着法的要求：合法性、完整性、有序性 着法生成的棋盘扫描法 确定走动的棋子（moved） 找到该棋子的当前位置（from） 根据象棋规则，扫描棋盘，逐个找到全部合理落址（to）（考虑制约条件、有效区域、本方占位、对方占位等） 如果落址为本方棋子，则不可行；若为对方棋子，则可以吃子（Captured） 如果到达落址，构成 “将军”（叫杀），则应该给对方以提示——“将！” 着法生成的棋盘扫描规则 区域定义： 定义棋盘有效区域 定义红方半区 定义黑方半区 定义红方九宫 定义黑方九宫 提址(from)为(i,j)的动子着法生成规则 提址(from)为(i,j)的动子着法生成规则 提址(from)为(i,j)的动子着法生成规则 棋盘扫描法遇到的问题 虽然在着法的表达上，棋盘扫描法最为直观、简洁，但实战意义不强。 因为扫描过程大量耗时：扫描动子、提址、制约条件、合理区域、双方占位、吃子等都是动态生成的，尤其区域判断和棋子种类检测等，时间开销巨大。 对于吃子着法和未吃子着法无法分别生成，只能全部生成，再做筛选。 模板匹配法 可以为某些动子设计“模板”，只要匹配到提址，便可以迅速找到落址。 通过单项比特矩阵比对，实现“本方子则止，对方子则吃”，完成“提-动-落-吃”内容的确定。 比较适合使用模板的动子为马和相（象）。 预置表法 棋盘状态确定之后，各子的可行着法是确定的。 预置表的思想是把某种棋子在棋盘每个合理位置上，所有可能的棋盘状态下的合理着法预先存储起来，生成一个小型数据表集合。 在生成着法时，通过查询，取代各种计算。 预置表的实质是用空间换时间，即牺牲一定的内存空间加速程序的运行速度。 预置表初始化很费时，但只需在程序开始运行时初始化一次，而且占用内存空间不大。 预置表法 棋子布局的布尔行向量形式 [101000010] 非吃子着法的落址为 [000110100] 可能的吃子着法的落址为 [100000000] 炮着法的预置表总的空间占用计算 每一行棋子的可行排列数恰好对应于9位二进制数（有子为1，无子为0），即 29 = 512 种情况（项）。 考虑到炮在行向的 9 种可能位置，预置表的规模即为 9*512 项。 分别考虑吃子着法与非吃子着法（2倍） 考虑路向情况，则总表规模为 2*9*512+2*10*1024=29696项 每项占用 4 字节，则总空间占用量为 116 k 预置表的使用 已知动子（炮）的提址（ i , j ） 由第 i 行的比特向量和炮在第 j 位置查找对应的预置表项，分别得到吃子