article1197.asp.htm

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

<!--<TABLE>
	<TR>
		<TD>
			
		</TD>
		<TD>
			See Also:
		</TD>
	</TR>
	<TR>
		<TD COLSPAN=2>-->

<P ALIGN="center"><SPAN CLASS="title">Chess Programming Part V: Advanced Search</SPAN>
<BR><SPAN CLASS="author">by <A HREF="javascript:if(confirm('http://pages.infinit.net/idjy/  \n\n这个文件不能通过 Teleport Pro 取回, 因为 它被访问于一个域或在它的起始地址边界外部的路径上.  \n\n你想从服务器打开它吗?'))window.location='http://pages.infinit.net/idjy/'" tppabs="http://pages.infinit.net/idjy/">Fran&ccedil;ois Dominic Laram&eacute;e</A></SPAN></P>

<P>Hey, it looks like there are dozens (and dozens) of you reading this series!&nbsp; I'm tickled pink!
<P>In this next-to-last article, we will examine advanced search-related techniques which can speed up and/or strengthen your chess-playing program.&nbsp; In most cases, the concepts (if not the actual code) also apply to a variety of other 2-player games; adapting them to your particular problem, however, shall remain an exercise for the proverbial reader.

<H1>Why Bother?</H1>
<P>So far, all of the search algorithms we have looked at examine a position's consequences to a fixed "depth".&nbsp; However, this is rarely a good thing.&nbsp; For example, suppose that your program uses an iterative-deepening alpha-beta algorithm with maximum depth 5-ply.&nbsp; Now look at these cases:
<UL>
  <LI>Along a certain line of play, you discover a position where one of the players is checkmated or stalemated at depth 3.&nbsp; Obviously, you don't want to keep searching, because the final state of the game has been resolved.&nbsp; Not only would searching to depth 5 be a colossal waste of effort, it may also allow the machine to finagle its way into an illegal solution!</LI>
  <LI>Now, suppose that, at depth 5, you capture a pawn.&nbsp; The program would be likely to score this position in a favorable light, and your program might decide that the continuation leading to it is a useful one.&nbsp; However, if you had looked one ply further, you might have discovered that capturing the pawn left your queen undefended.&nbsp; Oops.</LI>
  <LI>Finally, suppose that your queen is trapped.&nbsp; No matter what you do, she will be captured by the opponent at ply 4, except for one specific case where her death will happen at ply 6.&nbsp; If you search to depth 5, the continuations where the queen is captured at ply 4 will be examined accurately, and scored as likely disasters.&nbsp; However, the unique line of play where the queen is only captured at ply 6 (outside of the search tree) doesn't reveal the capture to the machine, which thinks that the queen is safe and gives it a much better score!&nbsp; Now, if all you have to do to push the queen capture outside of the search tree is delay the opponent with a diversion, doing so may be worth the risk: although it could damage your position, it might also cause the opponent to make a mistake and allow the queen to escape.&nbsp; But what if you can only delay the queen capture by sacrificing a rook?&nbsp; To the machine, losing a rook at ply 4 is less damaging than losing a queen, so it will merrily throw its good piece away and "hide" the too-horrible-to-mention queen capture beyond its search horizon.&nbsp; (During its next turn, of course, the machine will discover that the queen must now be captured at ply 4 in all cases, and that it has wasted a rook for no gain.)&nbsp; Hans Berliner described this "horizon effect" a long time ago, and it is the most effective justification for the "quiescence search" described in the next section.</LI>
</UL>
<P>The bottom line is this: a great many positions in chess (and in other games as well) are just too chaotic to be evaluated properly.&nbsp; An evaluation function can only be applied effectively to "quiet" positions where not much of importance is likely to happen in the immediate future.&nbsp; How to identify these is our next topic.

<H1>Quiet, Please!</H1>
<P>There are two ways to assess a position's value: dynamic evaluation (i.e., look at what it may lead to) and static evaluation (i.e., see what it looks like on its own, irrespective of consequences).&nbsp; Dynamic evaluation is performed through search; as we have just mentioned, static evaluation is only feasible when the position is not likely to undergo an overwhelming change of balance in the near future.&nbsp; Such relatively stable positions are called "quiet" or "quiescent", and they are identified via "quiescence search".
<P>The basic concept of Quiescence Search is the following: once the program has searched everything to a fixed depth (say, 6-ply), we continue each line of play selectively, by searching "non-quiescent" moves only, until we find a quiescent position, and only then apply the evaluator.
<P>Finding a quiet position requires some knowledge about the game.&nbsp; For example, which moves are likely to cause a drastic change in the balance of power on the board?&nbsp; For chess, material balance tends to be the overwhelming consideration in the evaluator, so anything that changes material is fair game: captures (especially those of major pieces) and pawn promotions certainly qualify, while checks may also be worth a look (just in case they might lead to checkmate).&nbsp; In checkers, captures and promotions also seem like reasonable choices.&nbsp; In Othello, every single move is a capture, and "material balance" can change so much in so little time that it might be argued that there are no quiet positions at all!
<P>My own program uses a simple quiescence search which extends all lines of play (after a full-width search to depth X) by looking exclusively at captures.&nbsp; Since there are usually not that many legal captures in a given position, the branching factor in the quiescence search tends to be small (4-6 on average, and quickly converging to 0 as pieces are eaten on both sides).&nbsp; Nevertheless, the quiescence search algorithm is called on a LOT of positions, and so it tends to swallow 50% or more of the entire processing time.&nbsp; Make sure that you need such a scheme in your own game before committing to it.
<P>Only when no capture is possible does my program apply its evaluator.&nbsp; The result is a selectively-extended search tree which is anything but fixed-depth, and which defeats most of the nasty consequences of the "horizon effect".