article1046.asp.htm

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

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

<CENTER><SPAN CLASS="title">Chess Programming Part II: Data Structures</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/"></A>Fran&ccedil;ois Dominic Laram&eacute;e</SPAN></CENTER>

<P>Last month, I presented the major building blocks required to write a program to play chess, or any other two-player game of perfect information.&nbsp; Today, I will discuss in a bit more detail the most fundamental of these building blocks: the internal representation of the game board.
<P>You may be surprised to notice that, for all intents and purposes, the state of the art in this area has not changed in thirty years.&nbsp; This is due to a combination of ingenuity (i.e., smart people made smart choices very early in the field's history) and necessity (i.e., good data structures were a pre-requisite to everything else, and without these effective techniques, not much would have been achieved.)
<P>While we're at it, I will also present three support data structures which, although not absolutely required to make the computer <I>play</I>, are invaluable if you want it to play <I>well</I>.&nbsp; Of these, two (one of which consumes ungodly amounts of memory) are designed to accelerate search through the game tree, while the third is used to speed up move generation.
<P>Before we go any further, a word to the wise: in chess as in any other game, the simplest data structure that will get the job done is usually the one you should use.&nbsp; While chess programmers have developed numerous clever data representation tricks to make their programs go faster, very simple stuff is quite sufficient in many other games.&nbsp; If you are a novice working on a game for which there is limited literature, start with something easy, encapsulate it well, and you can experiment with more advanced representations once your program works.

<H1>Basic Board Representations</H1>
<P>Back in the 1970's, personal computer memory was at a premium (that's an understatement if there ever was one!), so the most compact the board representations, the better.&nbsp; There is a lot to be said for the most self-evident scheme: a 64-byte array, where each byte represents a single square on the board and contains an integer constant representing the piece located in that square.&nbsp; (Any chess board data structure also needs a few bytes of storage to track down <I>en passant</I> pawn capture opportunities and castling privileges, but we'll ignore that for now, since this is usually implemented separately, and pretty much always the same way.)
<P>A few refinements on this technique soon became popular:
<UL>
  <LI>The original SARGON extended the 64-byte array by surounding it with two layers of "bogus squares" containing sentinel values marking the squares as illegal.&nbsp; This trick accelerated move generation: for example, a bishop would generate moves by sliding one square at a time until it reached an illegal square, then stop.&nbsp; No need for complicated <I>a priori </I>computations to make sure that a move would not take a piece out of the memory area associated with the board.&nbsp; The second layer of fake squares is required by knight moves: for example, a knight on a corner square might try to jump out of bounds by two columns, so a single protection layer would be no protection at all!</LI>
  <LI>MYCHESS reversed the process and represented the board in only 32 bytes, each of which was associated with a single piece (i.e., the white king, the black King's Knight's pawn, etc.) and contained the number of the square where that piece was located, or a sentinel value if the piece had been captured.&nbsp; This technique had a serious drawback: it was impossible to promote a pawn to a piece which had not already been captured.&nbsp; Later versions of the program fixed this problem.</LI>
</UL>

<P>Today, this type of super-miserly structure would only be useful (maybe) if you wrote a chess program for a Palm Pilot, a cell phone or a set-top box where 80-90% of resources are consumed by the operating system and non-game services.&nbsp; However, for some other types of games, there is really no alternative!
<P>For more information on vintage chess programs, read David Welsh's book, <I>Computer Chess</I>, published in 1984.

<H1>Bit Boards</H1>
<P>For many games, it is hard to imagine better representations than the simple one-square, one-slot array.&nbsp; However, for chess, checkers and other games played on a 64-square board, a clever trick was developed (apparently by the KAISSA team in the Soviet Union) in the late 60's: the bit board.
<P>KAISSA ran on a mainframe equipped with a 64-bit processor.&nbsp; Now, 64 happens to be the number of squares on a chess board, so it was possible to use a single memory word to represent a yes-or-no or true-or-false predicate for the whole board.&nbsp; For example, one bitboard might contain the answer to "Is there a white piece here?" for each square of the board.
<P>Therefore, the state of a chess game could be completely represented by 12 bitboards: one each for the presence of white pawns, white rooks, black pawns, etc.&nbsp; Adding two bitboards for "all white pieces" and "all black pieces" might accelerate further computations.&nbsp; You might also want to hold a database of bitboards representing the squares attacked by a certain piece on a certain square, etc.; these constants come in handy at move generation time.
<P>The main justification for bit boards is that a lot of useful operations can be performed using the processor's instruction set's 1-cycle logical operators.&nbsp; For example, suppose you need to verify whether the white queen is checking the black king.&nbsp; With a simple square-array representation, you would need to:
<UL>
  <LI>Find the queen's position, which requires a linear search of the array and may take 64 load-test cycles.</LI>
  <LI>Examine the squares to which it is able to move, in all eight directions, until you either find the king or run out of possible moves.</LI>
</UL>

<P>This process is always time-consuming, more so when the queen happens to be located near the end of the array, and even more so when there is no check to be found, which is almost always the case!
<P>With a bitboard representation, you would:
<UL>
  <LI>Load the "white queen position" bitboard.</LI>
  <LI>Use it to index the database of bitboards representing squares attacked by queens.</LI>
  <LI>Logical-AND that bitboard with the one for "black king position".</LI>
</UL>
<P>If the result is non-zero, then the white queen is checking the black king.&nbsp; Assuming that the attack bitboard database is in cache memory, the entire operation has consumed 3-4 clock cycles!
<P>Another example: if you need to generate the moves of the white knights currently on the board, just find the attack bitboards associated with the positions occupied by the knights and AND them with the logical complement of the bitboard representing "all squares occupied by white pieces" (i.e, apply the logical NOT operator to the bitboard), because the only restriction on knights is that they can not capture their own pieces!
<P>For a (slightly) more detailed discussion of bitboards, see the article describing the CHESS 4.5 program developed at Northwestern University, in Peter Frey's book <I>Chess Skill in Man and Machine</I>; there are at least two editions of this book, published in 1977 and 1981.
<P>Note: To this day, few personal computers use true 64-bit processors, so at least some of the speed advantages associated with bitboards are lost.&nbsp; Still, the technique is pervasive, and quite useful.