Are Hash Tables/Position Caches Inherently Slow?
John DeMastri
so please forgive any obvious gaffes or lack of complete understanding...
Now - I've implemented an engine in C++ (actually VC++ under NT, if it's
relevant) that does an exhaustive n-ply DFS of the game tree. The only eval
it does at the leaves (for now) is material count, since I've been working
on the tree traversal and min/max logic. I've gotten it to the point where
I think it's relatively quick for this simple test, but, I know I need to
maximize the time available for eval, and to do this, I wanted to prune out
duplicate positions from the searched tree.
To keep from searching farther when a duplicate position is reached, first I
have to recognize duplicate positions. I have implemented a cache using
straight STL multimaps, with an 8 byte key (64 bits - occupied squares), and
my position structure as the value. I do have to compare the position
structures (and they are, admittedly, a little chunky), but I thought the
choice of key would make the comparisons relatively infrequent. I find,
however, that the code slows down by an order of magnitude (!) when this
code is enabled. I am using straight STL accessor and insertion functions,
so there's no glue code to be concerned with. OK - I have 3 questions:
1 - Are STL multimaps inherently slow? This could be due to the fact that
they are intended to be general. Slow enough that writing a custom map data
class would help significantly?
2 - Is this the general method used by the big boys to thin the search
space? My original thought in using a DFS was that I would only have to
keep the path currently under consideration and the currently best path in
memory at any one time. Using this caching method requires all information
about all positions to remain somewhere in memory. Since this removes the
advantages of DFS, am I off track already?
3 - Are there other methods to thin the search space to which I am not
familiar? Part of the appeal of "reinventing the wheel" without doing deep
research beforehand is that it's possible to bring fresh ideas to bear on a
problem space. Obviously, a down side of this approach is that I have a few
half finished wheels lying around here... It's time to see what's out
there. Any help is appreciated.
Thanks in advance for your help. I know that this is the simple part, and
that the real work is on the eval side. I'm looking forward to attacking
that bear soon...
John DeMastri
(replies preferred by ng, but email accepted)
Robert Hyatt
: First - This is my first "serious" attempt at implementing a chess engine,
Pretty badly so. Because you want to be able to search quickly, and the
memory requirement for a quick search is impossible when you talk about
storing *every* position. In fact, assuming you are using alpha/beta, you
don't even search *every* position, which would make this messy.
Most of "us" use a 64bit hash signature based on the "Zobrist" hashing
algorithm (ask if you haven't seen this before) so that we can store a
position and do random-probing to find if we have seen it before...
This is also not going to "thin" the search space appreciably, until you
reach simple endgames... You mentioned "min-max logic". If you aren't
using alpha/beta, you have to start there, because the savings is going
to be dramatic. Once you get that done, then move ordering is the next
critical issue since ordering is going to determine alpha/beta efficiency.
Only then will the hash table (transposition/refutation table as it is
commonly named) begin to pay off, because it will kick up move ordering
quite well.
But the main issue is that for any given node, you want your "maintenance
overhead" to be *very low*... IE doing positional evaluation is ok... but
don't try to use complex data structures that are time-consuming to handle,
because you have to do this stuff at every position you search...
: 3 - Are there other methods to thin the search space to which I am not
: familiar? Part of the appeal of "reinventing the wheel" without doing deep
: research beforehand is that it's possible to bring fresh ideas to bear on a
: problem space. Obviously, a down side of this approach is that I have a few
: half finished wheels lying around here... It's time to see what's out
: there. Any help is appreciated.
: Thanks in advance for your help. I know that this is the simple part, and
: that the real work is on the eval side. I'm looking forward to attacking
: that bear soon...
: John DeMastri
: (replies preferred by ng, but email accepted)
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
William Bryant
>Most of "us" use a 64bit hash signature based on the "Zobrist" hashing
>algorithm (ask if you haven't seen this before) so that we can store a
>position and do random-probing to find if we have seen it before...
>
Although most may be familiar with this algorithm, I am not. I would
appreciate a discription, referance, or both.
Thanks.
William Bryant
wbr...@ix.netcom.com
Robert Hyatt
:>Most of "us" use a 64bit hash signature based on the "Zobrist" hashing
: Thanks.
: William Bryant
: wbr...@ix.netcom.com
The idea is simple. Each square on the chess board is in one of 13
states. Number them (for example purposes) 0-5 for black pawn thru
black king, 6-11 for white pawn thru white king. the empty square we
can handle differently.
Assuming you have a 64 square board (rather than the 0x88 or other
layout which only makes the first dimension below larger) you create
an array of 64 bit integers (long long in most compilers, __int64 in
MSVC) random[64][12]. You populate this array with random numbers.
To compute the Zobrist hash key, you do this:
long long signature=0;
for (square=0;square<64;square++)
if (board[square]) signature^=random[square][board[square]];
and you are done... note that if the square is empty, nothing is
xor'ed in.
This is quick, but can be made quicker... because when you make a move
you can update the hash signature, rather than having to recalculate it
from scratch:
assume a white knight is moving from square b1 (1) to c3 (18). You save
the original hash signature, and to update it, you only do this:
signature^=random[1][7]; (this "undoes" the effect of the knight originally
occupying square b1 (1).)
signature^=random[18][7]; (this adds in the knight's random value on the
new square c3 (18).)
and you are done. *if* you were playing Nxc3 instead, removing a piece of
the opponent's, you would need to also xor in that piece on that square to
take it back out of the hash signature.
That's all there is to it... quick, easy and a snap to code...
Dann Corbit
[Zobrist 70] A New Hashing Method with Application for Game Playing.
Zobrist, A.L. Tech. rep. 88, Univ. of Wisconsin, April 1970.
There appears to be an update [I have never seen this one:]
Zobrist, A.L. (1990).
A New Hashing Method with Applications for Game Playing.
ICCA Journal, Vol. 13, No. 2, pp. 69-73. (A)
Some hashing methods with code:
http://www.ddj.com/ddj/1997/1997_09/algo/algo.htm
http://ourworld.compuserve.com/homepages/bob_jenkins/doobs.htm
--
Hypertext C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-FAQ ftp: ftp://rtfm.mit.edu, C-FAQ Book: ISBN 0-201-84519-9
Try "C Programming: A Modern Approach" ISBN 0-393-96945-2
Want Software? Algorithms? Pubs? http://www.infoseek.com
William Bryant wrote in message <6rv7fm$a...@dfw-ixnews8.ix.netcom.com>...
Dann Corbit
http://www.ics.uci.edu/~eppstein/180a/970424.html
Another implementation:
http://www.alcrypto.co.uk/cryptocd/source/hashes/zobrist/gillogly/zobrist_ha
sh.c
John DeMastri
material. My project can only improve thanks to your help! Back to the
design stage...
John DeMastri
Robert Hyatt wrote some very useful notesin message
<6rv91h$99b$1...@juniper.cis.uab.edu>...
William Bryant
<hy...@crafty.cis.uab.edu> wrote:
Thanks for the explination of the Zobrist hashing technique.
A couple of other questions, and pardon me if they simply show a basic
ignorance of hashing in general.
1) The Zobrist technique generates a unique hash signature (64 bits) based upon
a lookup table of 64 x 12 random numbers and the pieces on the board.
How do you gererate the hash table index for each position. Since the
hash table size may not be fixed at program startup (ie you can set
the hash size in crafty at runtime), how do you gererate a series of
indexes specific to a position but with an unknown (until runtime) upper
bound.
2. At each position, in addition to the hash signature, the depth and the
evaluation score of that position, do you store any other information
for lookup.
3. Finally, in further comments or help in hash table theory or implementation
as it relates to chess programs would be appreciated.
Thanks
William Bryant
wbr...@ix.netcom.com
Robert Hyatt
: In article <6rv91h$99b$1...@juniper.cis.uab.edu>, Robert Hyatt
: <hy...@crafty.cis.uab.edu> wrote:
: Thanks for the explination of the Zobrist hashing technique.
: A couple of other questions, and pardon me if they simply show a basic
: ignorance of hashing in general.
: 1) The Zobrist technique generates a unique hash signature (64 bits) based upon
: a lookup table of 64 x 12 random numbers and the pieces on the board.
: How do you gererate the hash table index for each position. Since the
: hash table size may not be fixed at program startup (ie you can set
: the hash size in crafty at runtime), how do you gererate a series of
: indexes specific to a position but with an unknown (until runtime) upper
: bound.
I require my hash tables to be a power of two in size.. so I can take the
rightmost N bits (N=log2(table_size)) as the probe address. If you don't
want to use a power of two size, you can do N=hash_key%table_size; But
this can cause some distribution problems if you aren't careful...
: 2. At each position, in addition to the hash signature, the depth and the
: evaluation score of that position, do you store any other information
: for lookup.
Not really... I carry a couple of "threat" flags around that say "extend this
position if it is encountered, because the opponent has a serious threat that
needs to be searched deeper than normal. But other than that, that is about it,
except for the "best move" that is critical for move ordering.. of course..
: 3. Finally, in further comments or help in hash table theory or implementation
No... you have three possible things you can store in the table:
1. You store an EXACT score when the value at the node you are storing is
> alpha && < beta.
2. you store an UPPER bound when you look at *all* moves at any depth and
when you finish the best score is still "alpha". This means that the score
is less than alpha, but we don't know how much less. So we store alpha in the
table and say "we know the score is no better than this, and probably is much
worse".
3. You store LOWER bound when you get a fail high at a position. You know
that the score is at least == beta and probably better. So you store beta,
along with the LOWER flag to let you know that this value represents the
*least* score you would expect here..
: as it relates to chess programs would be appreciated.
: Thanks
: William Bryant
: wbr...@ix.netcom.com
--