Java版中国象棋项目设计论文

散列项的最后一个域BtestMove，保存着上次搜索到这个局面时的最佳着法。有时没有得到最佳着法，比如任何低出边界的情况(返回一个小于或等于Alpha的值)，而其他情况必定有最佳着法，比如高出边界的情况(返回一个大于或等于Beta的值)。代码如下：

int AlphaBeta(int depth, int alpha, int beta) { int hashf = HashAlpha;

if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN) {

// valUNKNOWN必须小于-INFINITY或大于INFINITY，否则会跟评价值混淆。 return val;

}

if (depth == 0) { val = Evaluate();

RecordHash(depth, val, hashfEXACT);

return val; }

GenerateLegalMoves(); while (MovesLeft()) { MakeNextMove();

val = -AlphaBeta(depth - 1, -beta, -alpha); UnmakeMove();

if (val >= beta) {

RecordHash(depth, beta, HashBETA); return beta; }

if (val > alpha) { hashf = hashfEXACT; alpha = val; } }

RecordHash(depth, alpha, hashf); return alpha;

}

以下就是两个新的函数的代码：

- 37 -

int ProbeHash(MoveStruct HashMove, int Alpha, int Beta, int Depth) { boolean MateNode; HashRecord TempHash;

int tmpInt = (int) (Position.ZobristKey & HashMask); long tmpLong1 = Position.ZobristLock,tmpLong2;

TempHash = HashList[(int) (Position.ZobristKey & HashMask)];

if (TempHash.Flag!=0 && TempHash.ZobristLock == Position.ZobristLock) { MateNode = false; if (TempHash.Value > MaxValue - MaxMoveNum / 2) {

}

TempHash.Value -= Position.MoveNum - StartMove; MateNode = true; } else if (TempHash.Value < MaxMoveNum / 2 - MaxValue) { TempHash.Value += MoveNum - StartMove; MateNode = true; } if (MateNode || TempHash.Depth >= Depth) { if ((TempHash.Flag & HashBeta)!=0) { if (TempHash.Value >= Beta) { HitBeta ++; return TempHash.Value; } } else if ((TempHash.Flag & HashAlpha)!=0) { if (TempHash.Value <= Alpha) { HitAlpha ++; return TempHash.Value; } } else if ((TempHash.Flag & HashPv)!=0) { HitPv ++; return TempHash.Value; } else { return UnknownValue; } } if (TempHash.BestMove.src == -1) { return UnknownValue; } else { HashMove = TempHash.BestMove; return ObsoleteValue; } }

return UnknownValue;

void RecordHash(MoveStruct HashMove, int HashFlag, int Value, int Depth) { HashRecord TempHash;

TempHash = HashList[(int) (Position.ZobristKey & HashMask)]; if ((TempHash.Flag!=0) && TempHash.Depth > Depth) { return; }

- 38 -

}

TempHash.ZobristLock = Position.ZobristLock; TempHash.Flag = HashFlag; TempHash.Depth = Depth; TempHash.Value = Value;

if (TempHash.Value > MaxValue - MaxMoveNum / 2) { TempHash.Value += Position.MoveNum - StartMove; } else if (TempHash.Value < MaxMoveNum / 2 - MaxValue) { TempHash.Value -= Position.MoveNum - StartMove; }

TempHash.BestMove = HashMove;

HashList[(int) (Position.ZobristKey & HashMask)] = TempHash;

源码网整理：www.codepub.com 5.4.2 替换策略

当向散列表中记录新的散列项时，如果该位置已被占用，那么是否覆盖该散列项？如何选择覆盖策略？―始终替换‖的策略即简单地覆盖已经存在的值。这或许不是最好的策略，但很容易实现。另一个策略是―同样深度或更深时替换‖。除非新局面的深度大于或等于散列表中已经有的值，否则已经存在的结点将被保留。

如果使用―同样深度或更深时替换‖的策略，那么散列表可能最终会被过期的但很深的结点所占满。解决方案就是每次你走棋时都清除散列表，或者在散列项中加入―顺序‖这个域，从而使这个策略变成变成―同样深度，或更深，或原来是旧的搜索，才替换‖。

上面的代码使用了“同样深度或更深时替换‖的策略。 5.5 其他策略 5.5.1 静态搜索

中国象棋中会有很多强制的应对。如果有人用马吃掉你的炮，那么你最好吃还他的马。Alpha-Beta搜索不是特别针对这种情况的。你把深度参数传递给函数，当深度到达零就做完了，即使一方被“将死‖。

一个应对的方法称为―静态搜索‖(Quiescent Search)。当Alpha-Beta用尽深度后，通过调用静态搜索来代替调用―Evaluate()‖。这个函数也对局面作评价，只是避免了在明显有对策的情况下看错局势。

简而言之，静态搜索就是应对可能的动态局面的搜索。

典型的静态搜索只搜索吃子着法。这会引发一个问题，因为在中国象棋中吃子通常不是强制的。如果局势很平静，而且面对的吃子只有(车吃兵，导致丢车)，不会强迫车去吃兵的，所以静态搜索不应该强迫吃子。

- 39 -

伪代码如下：

int Quies(int alpha, int beta) { val = Evaluate(); if (val >= beta) { return beta; }

if (val > alpha) { alpha = val; }

GenerateGoodCaptures(); while (CapturesLeft()) { MakeNextCapture();

val = -Quies(-beta, -alpha); UnmakeMove(); if (val >= beta) { return beta; }

if (val > alpha) { alpha = val; } }

return alpha; }

这看上去和―Alpha-Beta‖非常相似，但是区别是很明显的。这个函数调用静态评价，如果评价好得足以截断而不需要试图吃子时，就马上截断(返回Beta)。如果评价不足以产生截断，但是比Alpha好，那么就更新Alpha来反映静态评价。

然后尝试吃子着法，如果其中任何一个产生截断，搜索就中止。可能它们没有一个是好的，这也没问题。

这个函数有几个可能的结果：可能评价函数会返回足够高的数值，使得函数通过Beta截断马上返回；也可能某个吃子产生Beta截断；可能静态评价比较坏，而任何吃子着法也不会更好；或者可能任何吃子都不好，但是静态评价只比Alpha高一点点。

注意这里静态搜索中没有传递―深度‖这个参数。正因为如此，如果找到好的吃子，或者有一系列连续的强制性吃子的着法，那么搜索可能会非常深。

―好的‖吃子的界定也是仁者见仁智者见智的。如果允许任何吃子，并且以任何原始的顺序来搜索，那么你会降低搜索效率，并且导致静态搜索的膨胀，从而大幅度降低搜索深度，并使程序崩溃。

有一些简单的做法可以避免静态搜索的膨胀，最简单的就是MVV/LVA。MVV/LVA 意思是―最有价值的受害者/最没价值的攻击者‖(Most Valuable Victim/Least Valuable

- 40 -