计算机象棋循序渐进
 
象棋百科全书网 (webmaster@xqbase.com) 20084
 
() 细微智慧些了
 
  与本文配套的树模顺序是“象棋小巫师0.4版,顺序清单是:
  (1) XQWL04.CPP——C++源顺序;
  (2) XQWLIGHT.RC——资源形貌文件;
  (3) RESOURCE.H——资源符号界说文件;
  (4) RES目录——图标、图画、声响等资源。
 
  在阅读本章前,推荐读者先阅读象棋百科全书网盘算机博弈专栏的以下几篇译文:
  (1) 国际象棋顺序设想(五):低级搜索要领(François Dominic Laramée)
  (2) 数据组织——Zobrist键值(Bruce Moreland)
  (3) 基本搜索要领——简介()(David Eppstein)
  (4) 低级搜索要领——简介()(David Eppstein)
  (5) 低级搜索要领——静态搜索(Bruce Moreland)
  (6) 低级搜索要领——空着裁剪(Bruce Moreland)
  (7) 其他战略——一次又一次检测(Bruce Moreland)
 
  咱们的顺序最终会走棋了,不外许多时刻它很低能。由于水平线效应,任何转变都只搜索流动的深度。另有,有时它会长将。咱们能做哪些革新呢?
 
4.1 战胜水平线效应
 
  战胜水平线效应的要领有以下几种:
  (1) 静态(Quiescence)搜索。进入静态搜索时,要斟酌两种状况,一是不被将军的状况,首先实验不走是否是能够截断,然后搜索一切吃子的走法(能够依照MVV/LVA排序);二是被将军的状况,这时刻就必老天生一切的走法了(能够依照历史表排序)
  (2) 空步(Null-Move)裁剪。空步裁剪的代码异常简朴,但某些条件下其实不适用,一是被将军的状况下,二是进入残局时(自身一方的子力总价值小于某个阈值),三是不要一连做两次空步裁剪,否则会致使搜索的退步。
  (3) 将军延长。
 
4.2 搜检一次又一次局势
 
  在象棋小巫师的前几个版本中,一次又一次局势剖断不是必需的,由于任何转变都只搜索流动的深度。然则静态搜索和将军延长会带来一个问题——遇到“解将还将”的局势,搜索就会无终点地停止下去,直到顺序瓦解。
  有两个设施能够处置责罚这个问题:
  (1) 限制现实搜索深度(经由历程 nDistance 来限制)
  (2) 自动识别一次又一次局势,遇到这样的局势就依据划定礼貌前往和棋或杀棋的分数。
  前者完成起来异常简朴,咱们的顺序也这样做了,但依旧使顺序做了许多无用的搜索。在这个版本中,咱们重点把气力花在搜检一次又一次局势上了。
  搜检一次又一次局势的设施很简朴,每走一个走法就把以后局势的校验码纪录上去,再看看前几个局势的校验码是否是与以后值相等。当一次又一次局势发作时,就要依据双方的将军状况来剖断输赢——片面长将者判负(前往杀棋分数而没需要要连续搜索了),双长将或双方都存在非将走轨则判和(前往和棋分数)
  象棋小巫师用了一个 RepStatus 函数来搜检一次又一次,若是局势存在一次又一次,那末它的前往值将很有意义:
 
return 1 + (bPerpCheck ? 2 : 0) + (bOppPerpCheck ? 4 : 0);
 
  早先bPerpCheck(本方长将)bOppPerpCheck(对方长将)都设为TRUE,当一方存在非将走法时就改成FALSE,这样 RepStatus 的前往值有有这几种能够:
  A. 前往0,透露表现没有一次又一次局势;
  B. 前往1,透露表现存在一次又一次局势,但双方都无长将(判和)
  C. 前往3(=1+2),透露表现存在一次又一次局势,本方片面长将(判本方负)
  D. 前往5(=1+4),透露表现存在一次又一次局势,对方片面长将(判对方负)
  E. 前往7(=1+2+4),透露表现存在一次又一次局势,双方长将(判和)
 
4.3 Zobrist校验码
 
  咱们把Zobrist值作为局势的校验码,有益之处在于盘算迅速。除了搜检一次又一次局势外,校验码另有以下功用:
  (1) 作为置换表(Hash)的键值;
  (2) 作为残局库的查找依据。
  象棋小巫师天生的Zobrist校验码跟开源象棋顺序 ElephantEye 是一致的(以空密钥的RC4密码流作为随机序列),这样就能够够运用 ElephantEye 的残局库了。Zobrist值总共96位,放在 dwKeydwLock0 dwLock1 中,其中 dwKey 在搜检一次又一次局势时用,也作为置换表的键值,dwLock0 dwLock1 用作置换表的校验值,其余,dwLock1 照样查找残局库的依据(前面会说到)
  • 上一篇 计算机象棋循序渐进():最后级的野生智能
  • 下一篇 计算机象棋循序渐进():质的飞跃
  • 返 回 象棋百科全书——盘算机博弈
  • www.xqbase.com