📄 基本搜索方法——简介(三).htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/search_intro3.htm -->
<HTML><HEAD><TITLE>基本搜索方法——简介(三)</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="" name=Owner>
<META content="" name=Reply-To>
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——简介(三)_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT size=3>《对弈程序基本技术》专题</FONT> </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">David Eppstein */</FONT>文
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">* </FONT>加州爱尔文大学<FONT
face="Times New Roman">(UC Irvine)</FONT>信息与计算机科学系 </CENTER></DT></DIV>
<DT>
<DT> 我还没有讲完<FONT
face="Times New Roman">Alpha-Beta</FONT>呢，因为我的伪代码里包含神秘的“排序着法”还没有解释，暂时先扔在一边，在讲完散列技术后，我将继续这部分内容。
<DT> 散列技术的思想非常简单，很多棋类会出现“置换”的着法，即着法顺序的不同会导致相同的局面。例如在国际象棋中，开局走“<FONT
face="Times New Roman">1. d4 Nf6 2. c4</FONT>”和“<FONT
face="Times New Roman">1. c4 Nf6 2. d4</FONT>”都会导致一样的局面<FONT
face="Times New Roman">(</FONT>称为印度防御<FONT
face="Times New Roman">)</FONT>，白方两次进兵可以按不同的顺序走。再看一个更加复杂置换：“<FONT
face="Times New Roman">1. e4 c6 2. d4 d5 3. ed Qxd5 4. Nc3 Qd6</FONT>”<FONT
face="Times New Roman">(</FONT>卡罗<FONT
face="Times New Roman">-</FONT>卡恩防御<FONT
face="Times New Roman">)</FONT>，“<FONT face="Times New Roman">1. e4 d5 2. ed
Qxd5 3. Nc3 Qd6 4. d4 c6</FONT>”<FONT
face="Times New Roman">(</FONT>斯堪的那维亚防御<FONT
face="Times New Roman">)</FONT>，以及“<FONT face="Times New Roman">1. e4 Nf6 2.
e5 Ng8 3. d4 d6 4. ed Qxd6 5.Nc3 c6</FONT>”<FONT
face="Times New Roman">(</FONT>阿廖欣防御<FONT
face="Times New Roman">)</FONT>都会在走不同的步数后到达相同的局面。
<DT> 因为换位，相同的局面能在<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索树的很多位置上找到。如果有一种数据结构能够保存以前找过的每一个位置，那么我们不必重新搜索，取而代之的是查找局面。但是有两个困难摆在面前，一是我们没有足够的存储器来存放所有搜索过的局面，二是查找速度要足够快以至于超过搜索的时间。幸运的是，找不到已经搜索过的局面也没关系，再搜索一遍就是了，因为毕竟这种情况不会经常发生。
<DT> 这种数据结构就是“散列表”<FONT face="Times New Roman">(Hash
Tables)</FONT>，一个很大的数组，大到不超出物理存储器为止<FONT
face="Times New Roman">(</FONT>不要扩展到虚拟存储器，否则会非常慢的<FONT
face="Times New Roman">)</FONT>。
<DT>
<DD>struct {
<DD> long checksum; // long long 可能会更好
<DD> int depth;
<DD> enum { exact, lower_bound, upper_bound } entry_type;
<DD> double eval;
<DD>} hashtable[HASH_TABLE_SIZE]; //<FONT
color=#0000ff>【译注：完整的散列表还应记录最佳着法。】</FONT>
<DT>
<DT> 对于每一个需要搜索的局面，先计算散列值<FONT
face="Times New Roman"><EM>x</EM></FONT>作为散列表的指标，另计算散列值<FONT
face="Times New Roman"><EM>y</EM></FONT>来检查这个局面是否是所要找的局面。
<DT> 在搜索一个局面前，先去找 <FONT
face="Times New Roman">hashtable[<EM>x</EM>]</FONT>，如果 <FONT
face="Times New Roman">hashtable[<EM>x</EM>].checksum ==
<EM>y</EM></FONT>，<FONT
face="Times New Roman">hashtable[<EM>x</EM>].entry_type == exact</FONT>，并且
<FONT face="Times New Roman">hashtable[<EM>x</EM>].depth
</FONT>不比现在需要搜索的深度浅，那么就可以返回 <FONT
face="Times New Roman">hashtable[<EM>x</EM>].eval</FONT>。
<DT> 每搜索完一个局面，就把散列值<FONT
face="Times New Roman"><EM>y</EM></FONT>、当前搜索的深度和搜索的评分保存到 <FONT
face="Times New Roman">hashtable[<EM>x</EM>] </FONT>里。
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>如何计算散列值？</STRONG></FONT>
<DT>
<DT> <FONT face="Times New Roman">Zobrist </FONT>散列技术<FONT
face="Times New Roman">(</FONT>已经在“重复检测”这个话题中探讨过了<FONT
face="Times New Roman">)</FONT>是指：在下棋以前<FONT
face="Times New Roman">(</FONT>但在程序里<FONT
face="Times New Roman">)</FONT>产生随机数组<FONT face="Times New Roman">Z[square,
piecetype]</FONT>。棋盘的散列值就是棋盘上各个棋子的<FONT face="Times New Roman">Z[s,
p]</FONT>相加，再加上一些额外的信息如是否能王车易位等。通常求和被“异或”运算所代替，因为它操作方便且快速，但算术加法会更好些。走完一步棋后，不要把散列值整个都算一遍，只要减去原来位置的棋子和格子值，并加上新位置的棋子和格子值，就实现了散列值的更新。这个技术同时适用于散列值<FONT
face="Times New Roman"><EM>x</EM></FONT>和校验值<FONT
face="Times New Roman"><EM>y</EM>(</FONT>但要使用不同的随机数表<FONT
face="Times New Roman">)</FONT>。
<DT> 在散列技术中，另有一些十分有用的诀窍：
<DT> <FONT face="Times New Roman">(1)
</FONT>在走完一步后，不要把散列表清空，这样不但浪费时间，而且原来的内容或许对后面的走法有用。<FONT
color=#0000ff>【这里指的是电脑完成整个局面的搜索，走完一步后不需要清空散列表，电脑进行下一回合时，上一回合留下的信息或许有用。当然，是否清空散列表不能一概而论，还要取决于散列表的覆盖策略，以后的文章将谈到这个问题。】</FONT>
<DT> <FONT face="Times New Roman">(2) </FONT>如果相同的局面出现在搜索树的不同深度中<FONT
face="Times New Roman">(</FONT>例如上面讲到置换时的第二个例子<FONT
face="Times New Roman">)</FONT>，那么你可能得到比预期更深的搜索结果，这样会非常好。<FONT
color=#0000ff>【译者把这个现象称为“搜索树的迁移式延伸”，当这种情况出现在残局时反而不是好事，因为你有可能找到一步杀棋，而它却不是最短路线，你就停止了搜索。后面的文章会说明一个问题，当你搜索到杀棋时，如果你的着法不是最短路线，那么在实战中可能明知杀棋但怎么也杀不了。】</FONT>
<DT> <FONT face="Times New Roman">(3)
</FONT>不要在搜索树靠近叶子的局面上用散列技术，因为这些局面太多了<FONT
face="Times New Roman">(</FONT>它们可能取代别的更重要的局面<FONT
face="Times New Roman">)</FONT>，并且不去搜索这些局面也不会省掉很多时间。<FONT
color=#0000ff>【如果把搜索分为完全搜索和静态搜索两个阶段，那么静态搜索的结果是肯定不写入散列表的，因为静态搜索的分枝因子非常小(只考虑吃子着法)，所以查找散列表的时间或许比搜索的时间还长。在完全搜索中，这条法则是就“始终覆盖”这一策略而言的，若使用“深度优先”策略则无所谓。】</FONT>
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>散列技术如何跟</STRONG></FONT><FONT
face=Arial size=5><STRONG>Alpha-Beta</STRONG></FONT><FONT face=楷体_GB2312
size=5><STRONG>联系起来？</STRONG></FONT>
<DT>
<DT> 国际象棋程序中很多的错误都跟散列技术有关，原因是它们要跟<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索联系起来，但你无法绕开这个话题，因为散列技术和<FONT
face="Times New Roman">Alpha-Beta</FONT>都是非常有效的搜索方法。现在重新来看<FONT
face="Times New Roman">Alpha-Beta</FONT>，当你在一个局面中调用 <FONT
face="Times New Roman">alphabeta(depth, alpha, beta) </FONT>时，可能有三种情况发生：<FONT
face="Times New Roman">(1) </FONT>高出边界<FONT face="Times New Roman">(Fail
High)</FONT>，即返回评分至少是<FONT face="Times New Roman">Beta</FONT>，但到底多少却不知道；<FONT
face="Times New Roman">(2) </FONT>低出边界<FONT face="Times New Roman">(Fail
Low)</FONT>，即返回评分最多是<FONT face="Times New Roman">Alpha</FONT>，但到底多少也不知道；<FONT
face="Times New Roman">(3) </FONT>准确值，即返回评分在<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>之间。如果我们知道准确结果，那么散列表中只记录准确评分，但是高出边界和低出边界的情况，仍然在以后的裁剪中有用。可以跟记录准确评分一样，散列表中也可以记录这两种情况的评分，“下界标志”<FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -