article1197.asp.htm

《电脑游戏中的人工智能制作》

<H1>The All-Important Null-Move</H1>
<P>One of the most effective ways to speed up a chess program is to introduce the concept of a null move into the equation.
<P>The null move consists, quite simply, of skipping a turn and letting the opponent play two moves in a row.&nbsp; In the overwhelming majority of positions, doing nothing is a bone-head idea: you should (almost) always be able to do *something* to improve your lot.&nbsp; (To be honest, there are a few "damned if I do, damned if I don't" positions where the null move would actually be your best bet, and the computer will not play them correctly, but such "zugzwang" positions are hopeless anyway, so the loss of performance is not very traumatic.)
<P>Allowing the computer to try a null move during search has several advantages related to speed and accuracy.&nbsp; For example:
<UL>
  <LI>Suppose that a position is so overwhelmingly in your favor that, even if you skipped your turn, the opponent couldn't respond with anything that would help.&nbsp; (In program terms, you would get a beta cutoff even without making a move.)&nbsp; Suppose further that this position is scheduled to be searched to depth N.&nbsp; The null move, in effect, takes out an entire ply of the search tree (you are searching only the null move instead of all your legal ones) and if your branching factor is B, searching the null move is equivalent to looking at a single depth N-1 subtree instead of B of them.&nbsp; With B=35 as in the typical chess middlegame, null-move search may only consume 3% of the resources required by a full depth-N examination.&nbsp; If the null move search reveals that you are still too strong even without playing (i.e., it creates a cutoff), you have saved 97% of your effort; if not, you must examine your own legal moves as usual, and have only wasted an extra 3%.&nbsp; On average, the gain is enormous.</LI>
  <LI>Now, suppose that, during quiescence search, you reach a position where your only legal capture is rook-takes-pawn, which is immediately followed by the opponent's knight-takes-rook.&nbsp; You'd be a lot better off not making the capture, and playing any other non-capture move, right?&nbsp; You can simulate this situation by inserting the null move into the quiescence search: if, in a given position during quiescence search, it is revealed that the null move is better than any capture, you can assume that continuing with captures from this position is a bad idea, and that since the best move is a quiet one, this is a position where the evaluation function itself should be applied!</LI>
</UL>
<P>Overall, the null-move heuristic can save between 20% and 75% of the effort required by a given search.&nbsp; Well worth the effort, especially when you consider that adding it to a program is a simple matter of changing the "side to play" flag and adding less than a dozen lines of code in the quiescence search algorithm!

<H1>Aspirated Search and MTD(f)</H1>
<P>Plain old alphabeta assumes nothing about a position's ultimate minimax value.&nbsp; It looks at *everything*, no matter how preposterous.&nbsp; However, if you have a pretty good idea of what the value will turn out to be (for example, because you are running an iterative-deepening scheme and have received the previous iteration's results), you might be able to identify lines of play that are so out of whack with your expectations that they can't possibly be right, and cut them off pre-emptively.
<P>For example, suppose that you have reason to believe that a position's value will be close to 0, because it is very well balanced.&nbsp; Now, suppose that an internal node's preliminary evaluation is at +20,000.&nbsp; You can cutoff with reasonable confidence.
<P>This is the idea behind "aspiration search", a variant of alphabeta in which, instead of using +INFINITY and -INFINITY as the initial bounds of the search, you set a small window around the expected value instead.&nbsp; If the actual value happens to fall within the window, you win: you'll get it without error, and faster than you would otherwise (because of the many extra cutoffs).&nbsp; If not, the algorithm will fail, but the error will be easy to detect (because the minimax value you'll receive will be equal to one of the bounds); you'll have to waste a bit of time re-searching with a wider window.&nbsp; If the former case happens more often than the latter, you win on average.&nbsp; Obviously, the better your initial guess of the expected value, the more useful this technique is.
<P>In the mid 1990's, researcher Aske Plaat extended aspiration search to its logical conclusion: what if you called an aspirated alphabeta with a search window of width equal to zero?&nbsp; It would fail all the time, of course...&nbsp; But it would do so *very quickly*, because it would cutoff every path almost immediately.&nbsp; Now, if the failure indicates that the actual value is lower than your estimate, you can try again, with another zero-width window around a smaller estimate, etc.&nbsp; In a sense, you could then use alphabeta to perform a binary search into the space of all possible minimax values, until you reach the only call which will *not* fail because the zero-width window will be centered on the position's actual value!
<P>This brilliant idea, presented in a paper available on the web at http://theory.lcs.mit.edu/~plaat/mtdf.html, has been embodied in the MTD(f) search algorithm, which is all of 10 lines long.&nbsp; Tacked on top of an alphabeta implementation equipped with a transposition table, MTD(f) is incredibly efficient and highly parallel-friendly.&nbsp; It also works better with "coarse-grain" (and therefore probably simpler and faster) evaluators: it is easy to see that it takes fewer probes to zero in on the actual value in a binary search if the smallest "atom" of value is equal to, say, 0.1 pawns rather than 0.001 pawns.
<P>There are other alphabeta variants in wider use (namely, the infamous NegaScout; I would rather teach General Relativity to orang-utangs than get into that mess) but Plaat insists that MTD(f) is the most efficient algorithm in existence today and I'll take his word for it.&nbsp; My own program uses MTD(f); you'll be able to marvel at the algorithm's simplicity very shortly!

<H1>Singular Extensions</H1>
<P>One last thing before we leave the topic of search: in chess, some moves are obviously better than others, and it may not be necessary to waste too much time searching for alternatives.
<P>For example, suppose that after running your iterative algorithm to depth N-1, you discover that one of your moves is worth +9000 (i.e., a capture of the opponent's queen) and all others are below 0.&nbsp; If saving time is a consideration, like in tournaments, you may want to bypass the whole depth N search and only look at the best move to depth N instead: if this extra ply does not lower its evaluation much, then you assume that the other moves won't be able to catch up, and you stop searching early.&nbsp; (Remember: if there are 35 valid moves at each ply on average, you may have just saved 97% of your total effort!)
<P>Deep Blue's team has pushed this idea one step further and implemented the concept of "singular extensions".&nbsp; If, at some point in the search, a move seems to be a lot better than all of the alternatives, it will be searched an extra ply just to make sure that there are no hidden traps there.&nbsp; (This is a vast oversimplification of the whole process, of course, but that's the basic idea.)&nbsp; Singular extensions are costly: adding an extra ply to a node roughly doubles the number of leaves in the tree, causing a commensurate increase in the number of calls to the evaluator; in other words, Deep Blue's specialized hardware can afford it, my cranky Java code can't.&nbsp; But it's hard to argue with the results, isn't it?

<H1>Next Month</H1>
<P>In Part VI, we wrap up the series with a discussion of evaluation functions, the code which actually tells your program whether a given board position is good or bad.&nbsp; This is an immense topic, and people can (and do) spend years refining their own evaluators, so we will have to content ourselves with a rather high-level discussion of the types of features which should be examined and their relative importance.&nbsp; If everything goes according to plan, I should also have some Java code for you to sink your teeth into at about that time, so stick around, won't you?

<P><I>Fran&ccedil;ois Dominic Laram&eacute;e, September 2000</I>

<P ALIGN="center"><B><A HREF="javascript:if(confirm('http://www.gamedev.net/community/forums/topic.asp?key=featart&uid=1197&forum_id=35&Topic_Title=Chess+Programming+Part+V%3A+Advanced+Search  \n\n这个文件不能通过 Teleport Pro 取回, 因为 它被链接到离它的起始地址太远的地方. 如果你增大起始地址在其范围内的深度设置, 这个文件将进行列队等待取回.  \n\n你想从服务器打开它吗?'))window.location='http://www.gamedev.net/community/forums/topic.asp?key=featart&uid=1197&forum_id=35&Topic_Title=Chess+Programming+Part+V%3A+Advanced+Search'" tppabs="http://www.gamedev.net/community/forums/topic.asp?key=featart&uid=1197&forum_id=35&Topic_Title=Chess+Programming+Part+V%3A+Advanced+Search">Discuss this article in the forums</A></B></P>
<P>
<CENTER>
<!-- -->