article1171.asp.htm

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

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

<P ALIGN="center"><SPAN CLASS="title">Chess Programming Part IV: Basic 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>Fourth article in this complicated, code-deprived, dry-as-Metamucil series, and you're still reading? Drop me an email if you are, so that I know I'm writing these for a reason!
<P>Anyway, this month's installment focuses on the basics of two-agent search in strategy games: why it is useful, how to do it, and what it implies for the computer's style of play. The techniques I will discuss apply equally well to most two-player games, but by themselves, they are not quite sufficient to play good chess; next month, I will describe advanced techniques which significantly increase playing strength and search efficiency, usually at the same time.

<H1>Why Search?</H1>
<P>Well, basically, because we are not smart enough to do without it.
<P>A really bright program might be able to look at a board position and determine who is ahead, by how much, and what sort of plan should be implemented to drive the advantage to fruition. Unfortunately, there are so many patterns to discern, so many rules and so many exceptions, that even the cleverest programs just aren't very good at this sort of thing. What they <I>are</I> good at, however, is computing fast. Therefore, instead of trying to figure out good moves just by looking at a board, chess programs use their brute force to do it: look at every move, then at every possible countermove by the opponent, etc., until the processor melts down.
<P>Deep searches are an easy way to "teach" the machine about relatively complicated tactics. For example, consider the knight fork, a move which places a knight on a square from which it can attack two different pieces (say, a rook and the queen). Finding a way to represent this type of position logically would require some effort, more so if we also had to determine whether the knight was itself protected from capture. However, a plain dumb 3-ply search will "learn" the value of a fork on its own: it will eventually try to move the knight to the forking square, will test all replies to this attack, and then capture one of the undefended pieces, changing the board's material balance. And since a full-width search looks at everything, it will never miss an opportunity: if there is a 5-move combination, however obscure, that leads to checkmate or to a queen capture, the machine <I>will</I> see it if its search is deep enough. Therefore, the deeper the search, the more complicated the "plans" which the machine can stumble upon.

<H1>Grandpa MiniMax</H1>
<P>The basic idea underlying all two-agent search algorithms is Minimax. It dates back from the Dark Ages; I believe Von Neumann himself first described it over 60 years ago.
<P>Minimax can be defined as follows:
<UL>
  <LI>Assume that there is a way to evaluate a board position so that we know whether Player 1 (whom we will call Max) is going to win, whether his opponent (Min) will, or whether the position will lead to a draw. This evaluation takes the form of a number: a positive number indicates that Max is leading, a negative number, that Min is ahead, and a zero, that nobody has acquired an advantage.</LI>
  <LI>Max's job is to make moves which will increase the board's evaluation (i.e., he will try to maximize the evaluation).</LI>
  <LI>Min's job is to make moves which decrease the board's evaluation (i.e., he will try to minimize it).</LI>
  <LI>Assume that both players play flawlessly, i.e., that they never make any mistakes and always make the moves that improve their respective positions the most.</LI>
</UL>
<P>How does this work? Well, suppose that there is a simple game which consists of exactly one move for each player, and that each has only two possible choices to make in a given situation. The evaluation function is only run on the final board positions, which result from a combination of moves by Min and Max.

<P ALIGN="center"><TABLE CELLSPACING="0" BORDER="1" CELLPADDING="4">
<TR >
  <TD ALIGN="center"><FONT COLOR="white"><B>Max Move</B></FONT></TD>
  <TD ALIGN="center"><FONT COLOR="white"><B>Min Move</B></FONT></TD>
  <TD ALIGN="center"><FONT COLOR="white"><B>Evaluation</B></FONT></TD>
</TR>
<TR>
  <TD ALIGN="center">A</TD>
  <TD ALIGN="center">C</TD>
  <TD ALIGN="center">12</TD>
</TR>
<TR>
  <TD ALIGN="center">A</TD>
  <TD ALIGN="center">D</TD>
  <TD ALIGN="center">-2</TD>
</TR>
<TR>
  <TD ALIGN="center">B</TD>
  <TD ALIGN="center">C</TD>
  <TD ALIGN="center">5</TD>
</TR>