计算机象棋循序渐进
 
象棋百科全书网 (webmaster@xqbase.com) 20084
 
() 字斟句酌
 
  与本文配套的树模顺序是“象棋小巫师0.6版,顺序清单是:
  (1) XQWL06.CPP——C++源顺序;
  (2) XQWLIGHT.RC——资源形貌文件;
  (3) RESOURCE.H——资源符号界说文件;
  (4) RES目录——图标、图画、声响等资源;
  (5) BOOK.DAT——残局库文件。
 
  在阅读本章前,推荐读者先阅读象棋百科全书网盘算机博弈专栏的以下几篇译文:
  (1) 低级搜索要领——主要变例搜索(Bruce Moreland)
  (2) 低级搜索要领——搜索的不稳固性(Bruce Moreland)
 
  只管咱们的顺序在架构上以前靠近完整,但细节上存在很多问题:
  (1) 关于统一个局势,总是走流动的走法;
  (2) 搜索算法是否是能更优化一些(某些读者听说过PVSNega-Scout之类的算法)
  (3) 很多若干杀棋局势会走出稀里懵懂的走法。
  本章咱们将把这些问题逐一处置责罚。
 
6.1 残局库
 
  残局库险些是每一个象棋顺序必备的部件,它的有益之处是:
  (1) 纵然再笨的顺序,残局库能使得它们在残局阶段看上去不那末专业;
  (2) 经由历程随机选择走法,闪残局天真多变,增长棋战的意见意义性。
  象棋小巫师运用开源象棋顺序 ElephantEye 的残局库,残局库文件 BOOK.DAT 的组织是:
 
struct BookItem {
 DWORD dwLock;
 WORD wmv, wvl;
} BookTable[BOOK_SIZE];
 
  其中,dwLock 纪录下排场 Zobrist 校验码中的 dwLock1wmv 是走法,wvl 是权重(随机选择走法的几率,仅当两个一样的 dwLock 有分歧的 wmv 时,wvl 的值才有意义)
  搜索一个局势时,首先不做Alpha-Beta搜索,而是查找 BookTable 中有无对应的项,有的话就直接前往一个走法。由于 ElephantEye 在制造残局库时是依照 dwLock 排序的,因而能够用二分查找。找到一项以后,把它前后 dwLock 一样的一切项都掏出,从中随机选择一个 wmv
  ElephantEye 为了收缩残局库的容量,一切对称的局势只用一项,以是当一个局势在 BookTable 中找不到时,还应当试一下它的对称局势是否是在 BookTable 中。
 
6.2 根节点的稀奇处置责罚
 
  现在咱们的顺序一残局不会总是跳正马了,依据 ElephantEye 供应的残局库,它大局部时刻走中炮,有时也走仙人指路(进兵)或飞相。然则当它脱分残局库时,依然挣脱不了头脑的单调性,譬喻咱们第一步走边兵(残局库中固然没有这个局势),它依旧只会跳统一边的正马。
  一个处置责罚设施是:在根节点处,让一个不是最好的走法也能在一定的几率庖代前一个走法。咱们的顺序是这样写的:
 
if (vl > vlBest) {
 vlBest = vl;
 对vlBest作小局限的随机浮动;
}
 
  咱们把根节点的搜索函数零丁星散,这样做有许多有益之处:
  (1) 处置责罚思索的随机性;
  (2) 没有需要实验 Beta 截断(根节点处 Beta 一直是 +INFINITY)
  (3) 省略了搜检一次又一次局势、取得置换表、空步裁剪等步骤。
 
6.3 PVS
 
  许多盘算机博弈的资料都引见了PVS算法,但它只需当走法递次充裕优化时才气带来显著的有益之处,因而象棋小巫师直到最终一个版本才用了这类算法。
 
6.4 长将判负战略
 
  由于片面长将稳定作负的划定礼貌,0.6之前的版本若是发作这类状况,想固然地提供-MATE_VALUE的值,再依据杀棋步数作调整。然则由于长将判负并非对某个单纯局势的评分,而是跟线路有关的,以是运用置换表时就会发生异常严重的结果——某个局势的信息能够来自其余一条分歧的线路。
  象棋小巫师的处置责罚设施就是:取得置换表时把“应用长将判负战略搜索到的局势”过滤掉。为此这个版本中咱们把长将判负的局势定为BAN_VALUE(MATE_VALUE - 100),若是某个局势分值在WIN_VALUE(MATE_VALUE - 200)BAN_VALUE之间,那末这个局势就是“应用长将判负战略搜索到的局势”。
  咱们依旧把局部“应用长将判负战略搜索到的局势”纪录到置换表,由于这些局势供应的最好走法是有启示价值的。反过去说,若是“应用长将判负战略搜索到的局势”没有最好走法,那末这类局势就没有需要纪录到置换表了。
  经由这类处置责罚,咱们的顺序在杀棋阶段不再见走出稀里懵懂的走法了,最终一个疑问杂症最终占领了。
  • 上一篇 计算机象棋循序渐进():质的飞跃
  • 下一篇
  • 返 回 象棋百科全书——盘算机博弈
  • www.xqbase.com