计算机象棋循序渐进
 
象棋百科全书网 (webmaster@xqbase.com) 20084
 
() 质的飞跃
 
  与本文配套的树模顺序是“象棋小巫师0.5版,顺序清单是:
  (1) XQWL05.CPP——C++源顺序;
  (2) XQWLIGHT.RC——资源形貌文件;
  (3) RESOURCE.H——资源符号界说文件;
  (4) RES目录——图标、图画、声响等资源。
 
  在阅读本章前,推荐读者先阅读象棋百科全书网盘算机博弈专栏的以下几篇译文:
  (1) 基本搜索要领——简介()(David Eppstein)
  (2) 基本搜索要领——置换表(Bruce Moreland)
  (3) 其他战略——胜利局势(Bruce Moreland)
 
5.1 置换表
 
  没有置换表,就称不上是完整的盘算机博弈顺序。
  象棋小巫师的置换表异常简朴,以局势的 Zobrist Key % HASH_SIZE 作为索引值。每一个置换表项存储的内容不外就是:A. 深度,B. 符号,C. 分值,D. 最好走法,E. Zobrist Lock 校验码。置换表的处置责罚函数也很主流——一个 ProbeHash 和一个 RecordHash 就足够了。
  先说 RecordHash,纵使使用深度优先的替换战略,RecordHash 也异常简朴,在剖断深度后,将 Hash 表项中的每一个值填上就是了。
  再看看 ProbeHash 是怎样应用置换表信息的:
  (1) 搜检局势所对应的置换表项,若是 Zobrist Lock 校验码婚配,那末咱们就以为掷中(Hit)了;
  (2) 是否是能间接应用置换表中的效果,取决于两个重点要点:A. 深度是否是到达要求,B. PV节点还要求斟酌界限。
  第二种状况是最好的(完整应用)ProbeHash 前往一个非 -MATE_VALUE 的值,这样就能够纰谬该节点停止睁开了。
  若是仅仅相符第一种状况,那末该置换表项的信息依旧是有意义的——它的最好走法给了咱们一定的启示(局部应用)
 
5.2 杀棋分数调整
 
  象棋小巫师从掌握走棋最先,就以前斟酌了杀棋分数。不外增长了置换表以后,这个分数要停止调整——置换表中的分值不能是距离根节点的杀棋分值,而是距离以后(置换表项)节点的分值。以是当分值靠近 INFINITY -INFINITY 时,ProbeHash RecordHash 都要做纤细的调整:
  (1) 关于RecordHash:置换表项纪录的杀棋步数 = 现实杀棋步数 - 置换表项距离根节点的步数;
  (2) 关于ProbeHash:现实杀棋步数 = 置换表项纪录的杀棋步数 + 置换表项距离根节点的步数。
 
5.3 杀手(Killer)走法
 
  把这个术语取名为Killer真是很多若干新鲜,但咱们照样因袭这个术语。
  杀手走法就是兄弟节点中发生Beta截断的走法。依据国际象棋的心得,杀手走法发生截断的能够性极大,以是咱们在中国象棋里吸收了这个心得。很显著,兄弟节点中的走法一定在以后节点下能走,以是在实验杀手走法之前先要对它停止走法合理性的剖断。咱们在0.2版中就写过 LegalMove 这个函数,这里它将大显武艺。若是杀手走法实在发生截断了,那末前面耗时更多的 GenerateMove 就能够够不用执行了。
  怎样生存和取得“兄弟节点中发生截断的走法”呢?咱们能够把这个问题简朴化——距离根节点步数(nDistance)异样多的节点,相互都称为“兄弟”节点,换句话说,亲兄弟、堂表兄弟以及相干更冷漠的兄弟都称为“兄弟”。
  咱们能够把距离根节点的步数(nDistance)作为索引值,组织一个杀手走法表。象棋小巫师的每一个杀手走法表项存有两个杀手走法,走法一比走法二优先:存一个走法时,走法二被走法一替换,走法一被新走法替换;取走法时,先取走法一,后取走法二。
 
5.4 优化走法递次
 
  应用种种信息通道(如置换表、杀手走法、历史表等)来优化走法递次的手腕称为“启示”。象棋小巫师0.5之前,咱们只用历史表作启示,但从这个版本最先,咱们使用了多种启示体式格局:
  (1) 若是置换表中有过该局势的数据,但没有设施完整应用,那末少数状况下它是浅一层搜索中发生截断的走法,咱们能够首先实验它;
  (2) 然后是两个杀手走法(若是其中某个杀手走法与置换表走法一样,那末能够跳过)
  (3) 然后天生悉数走法,按历史表排序,再依次搜索(能够扫除置换表走法和两个杀手走法)
  这样,咱们就能够够组织一个状态机,来形貌走法递次的若干阶段:
  咱们把状态机写在一个叫 Next 的函数中,那末 Alpha-Beta 的循环体就是:
 
…… // 初始化状态机
while ((mv = Next()) != 0) {
 MakeMove(mv);
 …… // Alpha-Beta递归调用
 UndoMakeMove(mv);
 …… // Alpha-Beta界限剖断
}
 
  在 Next 函数中,咱们用了不带breakswitch ... case组织:
 
switch (nPhase) {
case PHASE_HASH:
 nPhase = PHASE_KILLER_1;
 …… // 若是有置换表走法,就能够够前往,再次调用就直接跳到 PHASE_KILLER_1
 // 注重:这里没有break!
case PHASE_KILLER_1:
 nPhase = PHASE_KILLER_2;
 ……
}
 
  这就是“基于置换表的启示式Alpha-Beta搜索”,现在顶尖的计算机(国际)象棋顺序都逃走不了这类架构,只不外它们在置换表和启示算法上越发优化而已。
  • 上一篇 计算机象棋循序渐进():细微智慧些了
  • 下一篇 计算机象棋循序渐进():字斟句酌
  • 返 回 象棋百科全书——盘算机博弈
  • www.xqbase.com