电脑象棋循序渐进
 
象棋百科全书网 (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