📄 高级搜索方法——简介(二).htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://www.elephantbase.net/computer/advanced_intro2.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.2817" name=GENERATOR></HEAD>
<BODY background=高级搜索方法——简介(二)_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT>《对弈程序基本技术》专题 </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=Arial size=6><STRONG>Alpha-Beta</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">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>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DT><FONT size=3> 尽管我们已经讨论过</FONT><FONT face="Times New Roman"
size=3>Alpha-Beta</FONT><FONT
size=3>搜索简单有效，还是有很多方法试图更有效地对博弈树进行搜索。它们中的大部分思想就是，如果认为介于</FONT><FONT
face="Times New Roman" size=3>Alpha</FONT><FONT size=3>和</FONT><FONT
face="Times New Roman" size=3>Beta</FONT><FONT
size=3>间的评价是感兴趣的，而其他评价都是不感兴趣的，那么对不感兴趣的评价作截断会让</FONT><FONT
face="Times New Roman" size=3>Alpha-Beta</FONT><FONT
size=3>更有效。如果我们把</FONT><FONT face="Times New Roman" size=3>Alpha</FONT><FONT
size=3>和</FONT><FONT face="Times New Roman" size=3>Beta</FONT><FONT
size=3>的间距缩小，那么感兴趣的评价会更少，截断会更多。</FONT>
<DT> 首先让我们回顾一下原始的<FONT face="Times New Roman">Alpha-Beta</FONT>搜索，忽略散列表和“<A
href="http://www.elephantbase.net/computer/other_winning.htm"
target=_blank>用当前层数调整胜利值</A>”的细节。
<DT>
<DD>// 基本的Alpha-Beta搜索
<DD>int alphabeta(int depth, int alpha, int beta) {
<DD> move bestmove;
<DD> if (棋局结束 || depth <= 0) {
<DD> return eval();
<DD> }
<DD> for (每个合理着法 m) {
<DD> 执行着法 m;
<DD> score = -alphabeta(depth - 1, -beta, -alpha);
<DD> if (score >= alpha) {
<DD> alpha = score;
<DD> bestmove = m;
<DD> }
<DD> 撤消着法 m;
<DD> if (alpha >= beta) {
<DD> break;
<DD> }
<DD> }
<DD> return alpha;
<DD>}
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>超出边界</STRONG></FONT><FONT face=Arial
size=5><STRONG>(Fail-Soft)</STRONG></FONT><FONT face=楷体_GB2312
size=5><STRONG>的</STRONG></FONT><FONT face=Arial
size=5><STRONG>Alpha-Beta</STRONG></FONT>
<DT>
<DT> 以上代码总是返回<FONT face="Times New Roman">Alpha</FONT>、<FONT
face="Times New Roman">Beta</FONT>或在<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>之间的数。换句话说，当某个值不感兴趣时，从返回值无法得到任何信息。原因就是当前值被变量<FONT
face="Times New Roman">Alpha</FONT>所保存，它从感兴趣的值的窗口下沿开始一直增长的，没有可能返回比<FONT
face="Times New Roman">Alpha</FONT>更小的值。一个对<FONT
face="Times New Roman">Alpha-Beta</FONT>的简单改进就是把当前评价和<FONT
face="Times New Roman">Alpha</FONT>分开保存。下面的伪代码用常数“<FONT
face="Times New Roman">WIN</FONT>”表示最大评价，它可以在<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索中返回任何评价。
<DT>
<DD>// 超出边界的Alpha-Beta搜索
<DD>int alphabeta(int depth, int alpha, int beta) {
<DD> move bestmove;
<DD> int current = -WIN;
<DD> if (棋局结束 || depth <= 0) {
<DD> return eval();
<DD> }
<DD> for (每个可能的着法 m) {
<DD> 执行着法 m;
<DD> score = -alphabeta(depth - 1, -beta, -alpha);
<DD> 撤消着法 m;
<DD> if (score >= current) {
<DD> current = score;
<DD> bestmove = m;
<DD> if (score >= alpha) {
<DD> alpha = score;
<DD> }
<DD> if (score >= beta) {
<DD> break; // <FONT
color=#0000ff>【译注：这里可以直接返回score、current或alpha，如果返回beta，则是不会高出边界的Alpha-Beta搜索。】</FONT>
<DD> }
<DD> }
<DD> }
<DD> return current;
<DD>}
<DT>
<DT> 这样改动以后，就可以知道比以前稍多一点的信息。如果返回值<FONT
face="Times New Roman"><EM>x</EM></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"><EM>x</EM></FONT>。类似地，如果<FONT
face="Times New Roman"><EM>x</EM></FONT>大于或等于<FONT
face="Times New Roman">Beta</FONT>，我们就知道搜索值至少是<FONT
face="Times New Roman"><EM>x</EM></FONT>。这些微小的上界和下界变化不会影响搜索本身，但是它们能导致散列表命中率的提高。超出边界的<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索对下面要介绍的<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>算法有重要作用。
<DT>
<DT><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>找最好路线时，可以调用：
<DD>
<DD>alphabeta(depth, -WIN, WIN)
<DT>
<DT> 这里 <FONT face=Symbol>-</FONT><FONT face="Times New Roman">WIN </FONT>和
<FONT face="Times New Roman">WIN
</FONT>之间的范围很大，表明我们不知道搜索值是多少，因此任何可能的值都必须考虑。随后，要走的那步保存在搜索函数外部的变量中。
<DT> 期望搜索的不同之处在于，我们可以人为地指定一个狭窄窗口<FONT
face="Times New Roman">(</FONT>用前一个搜索值为中心<FONT
face="Times New Roman">)</FONT>，对搜索通常是有帮助的。如果你搜索失败，必须加宽窗口重新搜索：
<DT>
<DD>// 期望搜索
<DD>int alpha = previous - WINDOW;
<DD>int beta = previous + WINDOW;
<DD>for ( ; ; ) {
<DD> score = alphabeta(depth, alpha, beta);
<DD> if (score <= alpha) {
<DD> alpha = -WIN;
<DD> } else if (score >= beta) {
<DD> beta = WIN;
<DD> } else {
<DD> break;
<DD> }
<DD>}
<DT>
<DT> 权衡狭窄搜索所节约的时间，和因为失败而重新搜索的时间，可以决定常数 <FONT face="Times New Roman">WINDOW
</FONT>的大小。在国际象棋中，典型的值也许是半个兵。期望搜索的变体有，搜索失败时适当增加窗口宽度，或者用初始窗口而没必要以前一次搜索结果为中心，等等。
<DT>
<DT><FONT face=Arial
size=5><STRONG>MTD(</STRONG><EM><STRONG>f</STRONG></EM><STRONG>)</STRONG></FONT>
<DT>
<DT> 这个技术跟期望搜索一样，只是在调用<FONT
face="Times New Roman">Alpha-Beta</FONT>时对初始值进行调整。搜索窗口越窄搜索就越快，这个技术的思想就是让搜索窗口尽可能的窄：始终用“<FONT
face="Times New Roman">beta = alpha + 1</FONT>”来调用<FONT
face="Times New Roman">Alpha-Beta</FONT>。用这样一个“零宽度”搜索的作用是用<FONT
face="Times New Roman">Alpha</FONT>和确切值作比较：如果搜索的返回值最多是<FONT
face="Times New Roman">Alpha</FONT>，那么确切值本身最多是<FONT
face="Times New Roman">Alpha</FONT>，相反确切值大于<FONT
face="Times New Roman">Alpha</FONT>。
<DT> 我们可以用这个思想对确切值作二分搜索：
<DT>
<DD>int alpha = -WIN;
<DD>int beta = +WIN;
<DD>while (beta > alpha + 1) {
<DD> int test = (alpha + beta) / 2;
<DD> if (alphabeta(depth, test, test + 1) <= test) {
<DD> beta = test;
<DD> } else {
<DD> alpha = test + 1;
<DD> }
<DD>}
<DT>
<DT> 但是，这样会导致大规模的搜索<FONT face="Times New Roman">(</FONT>即 <FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -