?? the hash table.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.netlib.org/utk/lsi/pcwLSI/text/node346.html -->
<!Converted with LaTeX2HTML 0.7a2 (Fri Dec 2 1994) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds ><HTML><HEAD><TITLE>The Hash Table</TITLE>
<META content="text/html; charset=big5" http-equiv=Content-Type>
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY>
<META name=description value=" The Hash Table">
<META name=keywords value="BOOK">
<META name=resource-type value="document">
<META name=distribution value="global">
<P><BR>
<HR>
<A href="http://www.netlib.org/utk/lsi/pcwLSI/text/node347.html"
name=tex2html7019><IMG align=bottom alt=next
src="The Hash Table.files/next_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node342.html"
name=tex2html7017><IMG align=bottom alt=up
src="The Hash Table.files/up_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node345.html"
name=tex2html7011><IMG align=bottom alt=previous
src="The Hash Table.files/previous_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node1.html"
name=tex2html7021><IMG align=bottom alt=contents
src="The Hash Table.files/contents_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node484.html"
name=tex2html7022><IMG align=bottom alt=index
src="The Hash Table.files/index_motif.gif"></A> <BR><B>Next:</B> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node347.html"
name=tex2html7020>The Opening</A> <B>Up:</B> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node342.html"
name=tex2html7018>14.3.1 Sequential Computer Chess</A> <B>Previous:</B> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node345.html"
name=tex2html7012>Iterative Deepening</A> <BR>
<HR>
<P>
<H3><A name=SECTION001631400000000000000>The Hash Table</A></H3>
<P>During the tree search, the same board position may occur several times.
There are two reasons for this. The first is transposition, or the fact that the
same board position can be reached by different sequences of moves. The second
reason is iterative deepening-the same position will be reached in the depth two
search, the depth three search, and so on. The hash table is a way of storing
information about positions which have already been searched; if the same
position is reached again, the search can be sped up or eliminated entirely by
using this information.
<P>The hash table plays a central role in a good chess program and so we will
describe it in some detail. First of all, the hash table is a form of
content-addressable memory-with each chess board (a node in the chess tree) we
wish to associate some slot in the table. Therefore, a hashing function <B>h</B>
is required, which maps chess boards to slots in the table. The function
<B>h</B> is designed so as to scatter similar boards across the table. This is
done because in any single search the boards appearing in the tree differ by
just a few moves and we wish to avoid collisions (different boards mapping to
the same slot) as much as possible. Our hash function is taken from [<A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node483.html#Zobrist70a">Zobrist:70a</A>].
Each slot in the table contains
<UL>
<LI>the known bounds on the score of this position;
<LI>the depth to which these bounds are valid;
<LI>a suggested move to try;
<LI>a staleness flag; and
<LI>a 64-bit collision check </LI></UL>Instead of just blindly generating all
legal moves at a position and then going down these lines of play, the hash
table is first queried about the position. Occasionally, the hash table bounds
are so well-determined as to cause an immediate alpha-beta cutoff. More often,
the hash table has a suggested move to try and this is searched first. The
64-bit collision check is employed to ensure that the slot has information about
the same position that the program is currently considering (remember, more than
one chess board can map to the same slot in the table).
<P>Whenever the program completes the search of a subtree of substantial size
(i.e., one of depth greater than some minimum), the knowledge gained is written
into the hash table. The writing is not completely naive, however. The table
contains only a finite number of slots, so collisions occur; writeback acts to
keep the most valuable information. The depth field of the slot helps in making
the decision as to what is most valuable. The information coming from the
subtree of greater depth (and hence, greater value) is kept.
<P>The staleness flag allows us to keep information from one search to the next.
When time runs out and a search is considered finished, the hash table is not
simply cleared. Instead, the staleness flag is set in all slots. If, during the
next search, a read is done on a stale slot the staleness flag is cleared, the
idea being that this position again seems to be useful. On writeback, if the
staleness flag is set, the slot is simply overwritten, without checking the
depths. This prevents the hash table from becoming clogged with old information.
<P>Proper use of an intelligent hash table such as the one described above gives
one, in effect, a ``principal variation'' throughout the chess tree. As
discussed in [<A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node483.html#Ebeling85a">Ebeling:85a</A>],
a hash table can effectively give near-perfect move ordering and hence, very
efficient pruning.
<P><BR>
<HR>
<A href="http://www.netlib.org/utk/lsi/pcwLSI/text/node347.html"
name=tex2html7019><IMG align=bottom alt=next
src="The Hash Table.files/next_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node342.html"
name=tex2html7017><IMG align=bottom alt=up
src="The Hash Table.files/up_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node345.html"
name=tex2html7011><IMG align=bottom alt=previous
src="The Hash Table.files/previous_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node1.html"
name=tex2html7021><IMG align=bottom alt=contents
src="The Hash Table.files/contents_motif.gif"></A> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node484.html"
name=tex2html7022><IMG align=bottom alt=index
src="The Hash Table.files/index_motif.gif"></A> <BR><B>Next:</B> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node347.html"
name=tex2html7020>The Opening</A> <B>Up:</B> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node342.html"
name=tex2html7018>14.3.1 Sequential Computer Chess</A> <B>Previous:</B> <A
href="http://www.netlib.org/utk/lsi/pcwLSI/text/node345.html"
name=tex2html7012>Iterative Deepening</A> <BR>
<HR>
<P><BR>
<HR>
<P>
<ADDRESS><I>Guy Robinson <BR>Wed Mar 1 10:19:35 EST 1995</I>
</ADDRESS></BODY></HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -