- 电脑象棋循序渐进
-
-
- (四) 稍微聪明些了
-
- 与本文配套的示范程序是“象棋小巫师”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位，放在 dwKey、dwLock0 和 dwLock1 中，其中 dwKey 在检查重复局面时用，也作为置换表的键值，dwLock0 和 dwLock1 用作置换表的校验值，另外，dwLock1 还是查找开局库的依据(后面会提到)。
上一篇 电脑象棋循序渐进(三)：最初级的人工智能
下一篇 电脑象棋循序渐进(五)：质的飞跃
返 回 象棋百科全书——计算机博弈
