📄 基本搜索方法——置换表.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/search_hashing.htm -->
<HTML><HEAD><TITLE>基本搜索方法——置换表</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2817" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——置换表_files/background.gif>
<DL dir=ltr>
<DIV align=center>
<CENTER>
<DT>《对弈程序基本技术》专题 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=隶书 size=6>置换表</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">Bruce Moreland (</FONT><A
href="mailto:brucemo@seanet.com"><FONT
face="Times New Roman">brucemo@seanet.com</FONT></A><FONT
face="Times New Roman">) / </FONT>文 </CENTER></DT></DIV>
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>一个多功能的数据结构</STRONG></FONT>
<DT>
<DT> 国际象棋的搜索树可以用图来表示，而置换结点可以引向以前搜索过的子树上。置换表可以用来检测这种情况，从而避免重复劳动。如果“<FONT
face="Times New Roman">1. e4 d6 2. d4</FONT>”以后的局面已经搜索过了，那就没有必要再搜索“<FONT
face="Times New Roman">1. d4 d6 2. e4</FONT>”以后的局面了。
<DT> 这个原因可能鼓舞着早期的电脑国际象棋程序的设计师们，而现在事实上这还是置换表的次要用途。在某些局面，例如在没有通路兵的王兵残局中，检查到的置换的数量是惊人的，以至于搜索可以在短达时间内达到很深的深度。
<DT> 省去重复的工作，这是置换表的一大特色，但是在一般的中局局面里，置换表的另一个作用更为重要。每个散列项里都有局面中最好的着法，我在“<A
href="http://www.elephantbase.net/computer/search_iterative.htm"
target=_blank>迭代加深</A>”这一章里解释过，首先搜索好的着法可以大幅度提高搜索效率。因此如果你在散列项里找到最好的着法，那么你首先搜索这个着法，这样会改进你的着法顺序，减少分枝因子，从而在短的时间内搜索得更深。
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>实现</STRONG></FONT>
<DT>
<DT> 主置换表是一个散列数组，每个散列项看上去像这样：
<DD>
<DD>#define hashfEXACT 0
<DD>#define hashfALPHA 1
<DD>#define hashfBETA 2
<DD>typedef struct tagHASHE {
<DD> U64 key;
<DD> int depth;
<DD> int flags;
<DD> int value;
<DD> MOVE best;
<DD>} HASHE;
<DD>
<DT> 这个散列数组是以“<A
href="http://www.elephantbase.net/computer/struct_zobrist.htm"
target=_blank><FONT
face="Times New Roman">Zobrist</FONT>键值</A>”为指标的。你求得局面的键值，除以散列表的项数得到余数，这个散列项就代表该局面。由于很多局面都有可能跟散列表中同一项作用，因此散列项需要包含一个校验值，它可以用来确认该项就是你要找的。通常校验值是一个<FONT
face="Times New Roman">64</FONT>位的数，也就是上面那个例子的第一个域。
<DT> 你从搜索中得到结果后，要保存到散列表中。如果你打算用散列表来避免重复工作，那么重要的是记住搜索有多深。如果你在一个结点上搜索了<FONT
face="Times New Roman">3</FONT>层，后来又打算做<FONT
face="Times New Roman">10</FONT>层搜索，你就不能认为散列项里的信息是准确的。因此子树的搜索深度也要记录。
<DT> 在<FONT face="Times New Roman">Alpha-Beta</FONT>搜索中，你很少能得到搜索结点的准确值。<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>的存在有助你裁剪掉没有用的子树，但是用<FONT
face="Times New Roman">Alpha-Beta</FONT>有个小的缺点，你通常不会知道一个结点到底有多坏或者有多好，你只是知道它足够坏或足够好，从而不需要浪费更多的时间。
<DT> 当然，这就引发了一个问题，散列项里到底要保存什么值，并且当你要获取它时怎样来做。答案是储存一个值，另加一个标志来说明这个值是什么含义。在我上面的例子中，比方说你在评价域中保存了<FONT
face="Times New Roman">16</FONT>，并且在标志域保存了“<FONT
face="Times New Roman">hashfEXACT</FONT>”，这就意味着该结点的评价是准确值<FONT
face="Times New Roman">16</FONT>；如果你在标志域中保存了“<FONT
face="Times New Roman">hashfALPHA</FONT>”，那么结点的值最多是<FONT
face="Times New Roman">16</FONT>；如果保存了“<FONT
face="Times New Roman">hashfBETA</FONT>”，这个值就至少是<FONT
face="Times New Roman">16</FONT>。
<DT> 当你在搜索中遇到特定情况时，很容易决定评价和标志应该保存哪些内容。然而避免错误是非常重要的，散列表是非常容易犯错误的，而且一旦犯下错误就很难捕捉出来。
<DT> 我的散列项的最后一个域，保存着上次搜索到这个局面时的最佳着法。有时我没有得到最佳着法，比如任何低出边界的情况<FONT
face="Times New Roman">(</FONT>返回一个小于或等于<FONT
face="Times New Roman">Alpha</FONT>的值<FONT
face="Times New Roman">)</FONT>，而其他情况必定有最佳着法，比如高出边界的情况<FONT
face="Times New Roman">(</FONT>返回一个大于或等于<FONT
face="Times New Roman">Beta</FONT>的值<FONT
face="Times New Roman">)</FONT>。<FONT
color=#0000ff>【译注：只有叶子结点才没有最佳着法，即便是</FONT><FONT face="Times New Roman"
color=#0000ff>Alpha</FONT><FONT
color=#0000ff>结点，所有的着法都是差的，也应该从中找一个最好的着法，它对更深一层的搜索会带来很大的好处。】</FONT>
<DT> 如果找到最佳着法，那么它应该首先被搜索。
<DT> 下面是示范程序，是根据<FONT
face="Times New Roman">Alpha-Beta</FONT>函数修改的，改动的地方用醒目的字标出：
<DT>
<DD>int AlphaBeta(int depth, int alpha, int beta) {
<DD><FONT color=#ff0000> int hashf = hashfALPHA;</FONT>
<DD><FONT color=#ff0000> if ((val = ProbeHash(depth, alpha, beta)) !=
valUNKNOWN) {</FONT>
<DD><FONT color=#ff0000> // </FONT><FONT
color=#0000ff>【valUNKNOWN必须小于-INFINITY或大于INFINITY，否则会跟评价值混淆。】</FONT>
<DD> return val;
<DD> }
<DD> if (depth == 0) {
<DD> val = Evaluate();
<DD><FONT color=#ff0000> RecordHash(depth, val, hashfEXACT);</FONT>
<DD> return val;
<DD> }
<DD> GenerateLegalMoves();
<DD> while (MovesLeft()) {
<DD> MakeNextMove();
<DD> val = -AlphaBeta(depth - 1, -beta, -alpha);
<DD> UnmakeMove();
<DD> if (val >= beta) {
<DD><FONT color=#ff0000> RecordHash(depth, beta, hashfBETA);</FONT>
<DD> return beta;
<DD> }
<DD> if (val > alpha) {
<DD><FONT color=#ff0000> hashf = hashfEXACT;</FONT>
<DD> alpha = val;
<DD> }
<DD> }
<DD><FONT color=#ff0000> RecordHash(depth, alpha, hashf);</FONT>
<DD> return alpha;
<DD>}
<DT>
<DT> 以下就是两个新的函数的代码：
<DD>
<DD>int ProbeHash(int depth, int alpha, int beta) {
<DD> HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
<DD> if (phashe->key == ZobristKey()) {
<DD> if (phashe->depth >= depth) {
<DD> if (phashe->flags == hashfEXACT) {
<DD> return phashe->val;
<DD> }
<DD> if ((phashe->flags == hashfALPHA) && (phashe->val <=
alpha)) {
<DD> return alpha;
<DD> }
<DD> if ((phashe->flags == hashfBETA) && (phashe->val >=
beta)) {
<DD> return beta;
<DD> }
<DD> }
<DD> RememberBestMove();
<DD> }
<DD> return valUNKNOWN;
<DD>}
<DD>
<DD>void RecordHash(int depth, int val, int hashf) {
<DD> HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
<DD> phashe->key = ZobristKey();
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -