article1046.asp.htm

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

<H1>Transposition Tables</H1>
<P>In chess, there are often many ways to reach the same position.&nbsp; For example, it doesn't matter whether you play 1. P-K4 ... 2. P-Q4 or 1. P-Q4... 2. P-K4; the game ends up in the same state.&nbsp; Achieving identical positions in different ways is called <I>transposing</I>.
<P>Now, of course, if your program has just spent considerable effort searching and evaluating the position resulting from 1. P-K4 ... 2. P-Q4, it would be nice if it were able to remember the results and avoid repeating this tedious work for 1. P-Q4... 2. P-K4.&nbsp; This is why all chess programs, since at least Richard Greenblatt's Mac Hack VI in the late 1960's, have incorporated a <I>transposition table</I>.
<P>A transposition table is a repository of past search results, usually implemented as a hash dictionary or similar structure to achieve maximum speed.&nbsp; When a position has been searched, the results (i.e., evaluation, depth of the search performed from this position, best move, etc.) are stored in the table.&nbsp; Then, when new positions have to be searched, we query the table first: if suitable results already exist for a specific position, we use them and bypass the search entirely.
<P>There are numerous advantages to this process, including:
<UL>
  <LI>Speed.&nbsp; In situations where there are lots of possible transpositions (i.e., in the endgame, when there are few pieces on the board), the table quickly fills up with useful results and 90% or more of all positions generated will be found in it.</LI>
  <LI>Free depth.&nbsp; Suppose you need to search a given position to a certain depth; say, four-ply (i.e., two moves for each player) ahead.&nbsp; If the transposition table already contains a six-ply result for this position, not only do you avoid the search, but you get more accurate results than you would have if you had been forced to do the work!</LI>
  <LI>Versatility.&nbsp; Every chess program has an "opening book" of some sort, i.e., a list of well-known positions and best moves selected from the chess literature and fed to the program to prevent it from making a fool out of itself (and its programmer) at the very beginning of the game.&nbsp; Since the opening book's modus operandi is identical to the transposition table (i.e., look up the position, and spit out the results if there are any), why not initialize the table with the opening book's content at the beginning of the game?&nbsp; This way, if the flow of the game ever leaves the opening book and later translates back into a position that was in it, there is a chance that the transposition table will still contain the appropriate information and be able to use it.</LI>
</UL>
<P>The only real drawback of the transposition table mechanism is its voracity in terms of memory.&nbsp; To be of any use whatsoever, the table must contain several thousand entries; a million or more is even better.&nbsp; At 16 bytes or so per entry, this can become a problem in memory-starved environments.
<P><B>Other uses of transposition tables</B>
<BR>CHESS 4.5 also employed hash tables to store the results of then-expensive computations which rarely changed in value or alternated between a small number of possible choices:
<UL>
  <LI>Pawn structure.&nbsp; Indexed only on the positions of pawns, this table requires little storage, and since there are comparatively few possible pawn moves, it changes so rarely that 99% of positions result in hash table hits.</LI>
  <LI>Material balance, i.e., the relative strength of the forces on the board, which only changes after a capture or a pawn promotion.</LI>
</UL>
<P>This may not be as useful in these days of plentiful CPU cycles, but the lesson is a valuable one: some measure of pre-processing can save a lot of computation at the cost of a little memory.&nbsp; Study your game carefully; there may be room for improvement here.

<H1>Generating Hash Keys for Chess Boards</H1>
<P>The transposition tables described above are usually implemented as hash dictionaries of some sort, which brings up the following topic: how do you generate hashing keys from chess boards, quickly and efficiently?
<P>The following scheme was described by Zobrist in 1970:
<UL>
  <LI>Generate 12x64 N-bit random numbers (where the transposition table has 2^N entries) and store them in a table.&nbsp; Each random number is associated with a given piece on a given square (i.e., black rook on H4, etc.)&nbsp; An empty square is represented by a null word.</LI>
  <LI>Start with a null hash key.</LI>
  <LI>Scan the board; when you encounter a piece, XOR its random number to the current hash key.&nbsp; Repeat until the entire board has been examined.</LI>
</UL>
<P>An interesting side effect of the scheme is that it will be very easy to update the hash value after a move, without re-scanning the entire board.&nbsp; Remember the old XOR-graphics?&nbsp; The way you XOR'ed a bitmap on top of a background to make it appear (usually in distorted colors), and XOR'ed it again to make it go away and restore the background to its original state?&nbsp; This works similarly.&nbsp; Say, for example, that a white rook on H1 captures a black pawn on H4.&nbsp; To update the hash key, XOR the "white rook on H1" random number once again (to "erase" its effects), the "black pawn on H4" (to destroy it) and the "white rook on H4" (to add a contribution from the new rook position).
<P>Use the exact same method, with different random numbers, to generate a second key (or "hash lock") to store in the transposition table along with the truly useful information.&nbsp; This is used to detect and avoid collisions: if, by chance, two boards hash to the exact same key and collide in the transposition table, odds are extremely low that they will also hash to the same lock!

<H1>History Tables</H1>
<P>The "history heuristic" is a descendant of the "killer move" technique.&nbsp; A thorough explanation belongs in the article on search; for now, it will be sufficient to say that a history table should be maintained to note which moves have had interesting results in the past (i.e., which ones have cut-off search quickly along a continuation) and should therefore be tried again at a later time.&nbsp; The history table is a simple 64x64 array of integer counters; when the search algorithm decides that a certain move has proven useful, it will ask the history table to increase its value.&nbsp; The values stored in the table will then be used to sort moves and make sure that more "historically powerful" ones will be tried first.

<H1>Pre-processing move generation</H1>
<P>Move generation (i.e., deciding which moves are legal given a specific position) is, with position evaluation, the most computationally expensive part of chess programming.&nbsp; Therefore, a bit of pre-processing in this area can go a long way towards speeding up the entire game.
<P>The scheme presented by Jean Goulet in his 1984 thesis <I>Data Structures for Chess</I> (McGill University) is a personal favorite.&nbsp; In a nutshell:
<UL>
  <LI>For move generation purposes, piece color is irrelevant except for pawns which move in opposite directions.</LI>
  <LI>There are 64 x 5 = 320 combinations of major piece and square from which to move, 48 squares on which a black pawn can be located (they can never retreat to the back rank, and they get promoted as soon as they reach the eight rank), and 48 where a white pawn can be located.</LI>
  <LI>Let us define a "ray" of moves as a sequence of moves by a piece, from a certain square, in the same direction.&nbsp; For example, all queen moves towards the "north" of the board from square H3 make up a ray.</LI>
  <LI>For each piece on each square, there are a certain number of rays along which movement might be possible.&nbsp; For example, a king in the middle of the board may be able to move in 8 different directions, while a bishop trapped in a corner only has one ray of escape possible.</LI>
  <LI>Prior to the game, compute a database of all rays for all pieces on all squares, assuming an empty board (i.e., movement is limited only by the edges and not by other pieces).</LI>
  <LI>When you generate moves for a piece on a square, scan each of its rays until you either reach the end of the ray or hit a piece.&nbsp; If it is an enemy piece, this last move is a capture.&nbsp; If it is a friendly piece, this last move is impossible.</LI>
</UL>
<P>With a properly designed database, move generation is reduced to a simple, mostly linear lookup; it requires virtually no computation at all.&nbsp; And the entire thing holds within a few dozen kilobytes; mere chump change compared to the transposition table!
<P>All of the techniques described above (bit boards, history, transposition table, pre-processed move database) will be illustrated in my own chess program, to be posted when I finish writing this series.&nbsp; Next month, I will examine move generation in more detail.
<P><I>Fran&ccedil;ois Dominic Laram&eacute;e, June 2000</I>

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