📄 解剖大象的眼睛——中国象棋程序设计探索(三)：搜索和置换表.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/eleeye_search.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中国象棋程序设计探索(三)：搜索和置换表</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=解剖大象的眼睛——中国象棋程序设计探索(三)：搜索和置换表_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT face=隶书 size=6>解剖大象的眼睛</FONT><FONT
size=6><STRONG>——</STRONG></FONT><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">*</FONT> <FONT
face="Times New Roman">2005</FONT>年<FONT
face="Times New Roman">6</FONT>月初稿，<FONT
face="Times New Roman">2005</FONT>年<FONT face="Times New Roman">11</FONT>月修订
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">( * </FONT>联系地址：复旦大学化学系表面化学实验室，<FONT
face="Times New Roman">eMail</FONT>：<A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT> </CENTER></DT></DIV>
<DT>
<DT><FONT face=Arial size=5><STRONG>(</STRONG></FONT><FONT face=楷体_GB2312
size=5><STRONG>三</STRONG></FONT><FONT face=Arial size=5><STRONG>)
</STRONG></FONT><FONT face=楷体_GB2312 size=5><STRONG>搜索与置换表</STRONG></FONT>
<DT>
<DT> 在阅读本章前，建议读者先阅读《<A href="http://www.elephantbase.net/"
target=_blank>象棋百科全书</A>》网站中《<A
href="http://www.elephantbase.net/computer/outline.htm"
target=_blank>对弈程序基本技术</A>》专题的以下几篇译文：
<DT> <FONT face="Times New Roman">(1) </FONT><A
href="http://www.elephantbase.net/computer/search_intro1.htm"
target=_blank>基本搜索方法——简介<FONT face="Times New Roman">(</FONT>一<FONT
face="Times New Roman">)</FONT></A><FONT face="Times New Roman">(David
Eppstein)</FONT>；
<DT> <FONT face="Times New Roman">(2) </FONT><A
href="http://www.elephantbase.net/computer/search_intro2.htm"
target=_blank>基本搜索方法——简介<FONT face="Times New Roman">(</FONT>二<FONT
face="Times New Roman">)</FONT></A><FONT face="Times New Roman">(David
Eppstein)</FONT>；
<DT> <FONT face="Times New Roman">(3) </FONT><A
href="http://www.elephantbase.net/computer/search_intro3.htm"
target=_blank>基本搜索方法——简介<FONT face="Times New Roman">(</FONT>三<FONT
face="Times New Roman">)</FONT></A><FONT face="Times New Roman">(David
Eppstein)</FONT>；
<DT> <FONT face="Times New Roman">(4) </FONT><A
href="http://www.elephantbase.net/computer/search_minimax.htm"
target=_blank>基本搜索方法——最小<FONT face="Times New Roman">-</FONT>最大搜索</A><FONT
face="Times New Roman">(Bruce Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(5) </FONT><A
href="http://www.elephantbase.net/computer/search_alphabeta.htm"
target=_blank>基本搜索方法——<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索</A><FONT
face="Times New Roman">(Bruce Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(6) </FONT><A
href="http://www.elephantbase.net/computer/search_iterative.htm"
target=_blank>基本搜索方法——迭代加深</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(7) </FONT><A
href="http://www.elephantbase.net/computer/search_hashing.htm"
target=_blank>基本搜索方法——置换表</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(8) </FONT><A
href="http://www.elephantbase.net/computer/advanced_intro2.htm"
target=_blank>高级搜索方法——简介<FONT face="Times New Roman">(</FONT>二<FONT
face="Times New Roman">)</FONT></A><FONT face="Times New Roman">(David
Eppstein)</FONT>；
<DT> <FONT face="Times New Roman">(9) </FONT><A
href="http://www.elephantbase.net/computer/advanced_instability.htm"
target=_blank>高级搜索方法——搜索的不稳定性</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(10) </FONT><A
href="http://www.elephantbase.net/computer/other_winning.htm"
target=_blank>其他策略——胜利局面</A><FONT face="Times New Roman">(David
Eppstein)</FONT>。
<DT>
<DT><FONT face=Arial size=4><STRONG>3.1 </STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>搜索技术概述</STRONG></FONT>
<DT>
<DT> 搜索算法是象棋程序的核心算法，在众多搜索算法中，如何选择适合自己的算法，并有效地把它们组合起来，是决定搜索效率的关键所在。要做好这点，首先必须明确搜索的概念，把各种搜索算法作一下分类。
<DT> 象棋程序的搜索算法都是基于“最小<FONT face="Times New Roman">-</FONT>最大”策略的，因此衍生出以<FONT
face="Times New Roman">Alpha-Beta</FONT>为基础的完全搜索算法以及带裁剪的搜索算法。尽管<FONT
face="Times New Roman">Alpha-Beta</FONT>算法也有裁剪的过程，但是这种裁剪被证明是绝对可靠的，没有无负面作用，即通常所说的“截断”<FONT
face="Times New Roman">(Cut-off)</FONT>，它属于申朗所说的<FONT
face="Times New Roman">A</FONT>策略。
<DT> 我们现在所说的“裁剪”<FONT face="Times New Roman">(Pruning)</FONT>，特指“向前裁剪”<FONT
face="Times New Roman">(Forward
Pruning)</FONT>，即需要承担风险地对某些线路作的裁剪，也就是申朗所说的<FONT
face="Times New Roman">B</FONT>策略。尽管它是完全搜索算法的对立面，但为了克服完全搜索中的“水平线效应”<FONT
face="Times New Roman">(Horizon
Effect)</FONT>，它是程序中必不可少的部分。把裁剪反过来，对某些重要线路进行“延伸”<FONT
face="Times New Roman">(Extension)</FONT>，这种思想和裁剪有异曲同工之妙。
<DT> 如今，“带置换表的启发式<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索”成了象棋程序的主流，这种思想强调对着法排序的重要性，排序着法是由“启发”<FONT
face="Times New Roman">(Heuristic)</FONT>算法来完成的，它同“置换表”<FONT
face="Times New Roman">(Transposition Table)</FONT>一起，使搜索效率有大幅度的提高。
<DT> 因此，搜索算法大致可以分为以下四类：
<DT> <FONT face="Times New Roman">(1) </FONT>完全搜索算法，即<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索及其变种，诸如期望窗口、<FONT
face="Times New Roman">PVS</FONT>、<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>等；
<DT> <FONT face="Times New Roman">(2) </FONT>启发算法，对着法顺序进行优化，尽可能地提高<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索的效率，中国象棋中的启发算法有置换表启发、吃子启发、杀手着法启发和历史表启发等；
<DT> <FONT face="Times New Roman">(3)
</FONT>裁剪算法，运用棋类知识略去对某些着法的搜索，以提高搜索深度，中国象棋中最常用的裁剪算法是空着裁剪，当然还有其他方法。
<DT> <FONT face="Times New Roman">(4) </FONT>置换表。
<DT> 以上算法中，置换表被独立归为一类，因为它不但功能特殊，而且值得研究问题最多。置换表的初衷是利用置换现象来减少搜索<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">(</FONT>毕竟是裁剪的一种形式<FONT
face="Times New Roman">)</FONT>，而要彻底研究清楚并非那么容易。
<DT>
<DT><FONT face=Arial size=4><STRONG>3.2</STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG> 超出边界的</STRONG></FONT><FONT face=Arial
size=4><STRONG>Alpha-Beta</STRONG></FONT><FONT face=楷体_GB2312
size=4><STRONG>搜索</STRONG></FONT>
<DT>
<DT> 置换表的大部分问题出在边界上，直到目前笔者还无法彻底明白该如何设置边界，因此想把这个问题留给读者。首先我们从不带置换表的超出边界<FONT
face="Times New Roman">(Fail-Soft)</FONT>的<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索说起：
<DD>
<DD>int AlphaBeta(int Alpha, int Beta, int Depth) {
<DD> if (GameOver() || Depth <= 0) {
<DD> Value = Evaluate();
<DD><FONT color=#0000ff> // if (Value >= Beta) return Beta;</FONT>
<DD><FONT color=#0000ff> // if (Value <= Alpha) return Alpha;</FONT>
<DD> return Value;
<DD> }
<DD> Best = -MaxValue;
<DD> GenMoves();
<DD> while (MovesLeft()) {
<DD> MakeNextMove();
<DD> Value = -AlphaBeta(-Beta, -Alpha, Depth - 1);
<DD> UndoMakeMove();
<DD> if (Value >= Beta) {
<DD><FONT color=#0000ff> // return Beta;</FONT>
<DD><FONT color=#ff0000> return Value;</FONT>
<DD> }
<DD> if (Value > Best) {
<DD> Best = Value;
<DD> if (Value > Alpha) {
<DD> Alpha = Value;
<DD> }
<DD> }
<DD> }
<DD><FONT color=#0000ff> // return Alpha;</FONT>
<DD><FONT color=#ff0000> return Best;</FONT>
<DD>}
<DT>
<DT> 以上代码中，蓝色的被注释掉的部分是不超出边界的<FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -