中国象棋程序设计（四）水平效应、检查重复局面

声明：本程序设计参考象棋巫师源码（开发工具dephi 11，建议用delphi 10.3以上版本）。

上一章我们的程序终于会走棋了，不过很多时候它很低能。由于水平线效应，任何变化都只搜索固定的深度。还有，有时它会长将。我们能做哪些改进呢？

本章的目标：

• 用Zobrist校验码技术实现重复局面判定；
• 实现静态(Quiescence)搜索和MVV/LVA启发；
• 实现将军延伸和空步(Null-Move)裁剪。

4.1 克服水平线效应　　　

　　什么是水平线效应？（以下引用自其他博客）

　　之前搜索到叶子节点，都是调用评估函数，并返回估值。但有时叶子节点是一个吃子走法，这可能得到一个很好的评分，但如果是一个换子，即下一步对手又吃回来，可能局面是一个平手。在叶子节点，局面可能产生剧烈动荡，除非评估函数能非常精确的反映这一点，那么返回值不能很好的反映局面真实情况。这种现象称为水平效应。

　　克服水平线效应，一般可采取对叶子节点再向下搜索。但是，向下搜索多少步呢？无论多深总有返回的时候，返回的又是叶子节点。为了避免不必要的更深搜索，在叶子节点以下，只搜索吃子走法，因为吃子走法是导致局面剧烈动荡的主要原因。通常把这种思想称为静态（Quiescence）搜索。棋子是有限的，吃子走法不会无限膨胀。静态搜索与Alpha-Beta搜索很相似，主要有以下区别：

（1）静态搜索没有深度参数，结束递归调用有两种情况，一是分值大于beta产生剪枝，二是局面不再有吃子走法。

（2）如果是被将军的局面，生成所有走法。不是被将军的局面，只生成吃子走法。

（3）在上一节，生成全部走法后，会使用历史表的数据对着法排序，以便提高搜索效率，这叫历史表启发。如果只生成吃子走法，使用的是MVV/LVA启发。MVV/LVA的意思是“最有价值的受害者/最没价值的攻击者”。这个技术假设最好的吃子是吃到最大的子。如果不止一个棋子能吃到最大的子，那么假设用最小的子去吃是最好的。排序之后，会最先搜索最好的吃子走法。中国象棋棋子价值这样排列“帅>车>马（炮）>兵>士（相）”。象棋巫师的价值表是一个23个元素的一维数组，因为象棋巫师的棋子是这样定义的：8–14为红棋，16-22为黑棋，所以这个一维数长度为23，有棋子的区域定义棋子价值，没有棋子的区域定义为零。为了兼容，我们程序这样定义：

  // MVV/LVA每种子力的价值
cucMvvLva:array[0..32]of Byte =(
  4,3,1,1,5,1,1,3,4,3,3,2,2,2,2,2,
  4,3,1,1,5,1,1,3,4,3,3,2,2,2,2,2,0);
//排序算法　　
function MvvLva(mv:Word):Integer;
var
  s,d:TPoint;
begin
  s:=GetSrc(mv);
  d:=GetDest(mv);
  Result:= cucMvvLva[pcMove.chessbd[d.Y,d.X]] shl 3 - cucMvvLva[pcMove.chessbd[s.Y,s.X]]; //计算棋子的权重
end;
{按MVV/LVA值排序的比较函数}
function CompareMvvLva(const lpmv1,lpmv2:Integer):Integer;
begin
  Result:=MvvLva(lpmv2) - MvvLva(lpmv1);
end;