hashing function
Vladimir R. Medvedev
I'm writing my own chess engine. The board representation is integer arrays
based (I know that bitboards are much faster but there are some other
reasons to make representation quite simple). Where can I find a good
discussion of how to build hashing function for this case?
:) Please dont advice me to look at TSCP code. Tom did not implement
hashing, as I know :)
Thanks in advance.
VRM
Karlo Bala
ICS 180A, Spring 1997:
Strategy and board game programming
Lecture notes for April 24, 1997
Hashing and Move Ordering
I didn't really finish describing alpha-beta -- my pseudocode included a mysterious "sort list of moves" step that I didn't explain. I'll continue to leave that dangling while I talk about hashing; we'll connect it up in a little while.
The idea of hashing is very simple. Many games allow transpositions of moves, meaning different sequences of moves that end up leading to the same position. For instance, in chess, the opening moves 1. d4 Nf6 2. c4 and 1. c4 Nf6 2. d4 both give the same position (known as an Indian defense). White's two pawn moves could be made in either order without changing the result. As an example of a more complicated transposition, the moves 1. e4 c6 2. d4 d5 3. ed Qxd5 4. Nc3 Qd6 (Caro-Kann defense), 1. e4 d5 2. ed Qxd5 3. Nc3 Qd6 4. d4 c6 (Scandinavian opening), and 1. e4 Nf6 2. e5 Ng8 3. d4 d6 4. ed Qxd6 5. Nc3 c6 (Alekhine defense) all lead to the same position, after different numbers of moves.
Because of transpositions, the same positions can show up many places in the alpha-beta search tree. If we store a data structure that remembers what the results of searching each position were, we can look it up rather than searching it again. But...we don't have enough memory to store all the positions we search. And, lookups must be very fast to make it save time over just searching. Fortunately, we have one advantage: it's ok if we sometimes don't find the results from a position we already searched, and search the same position again, as long as it doesn't happen too often.
The answer: hash tables. Make a big array: as large as possible without blowing out your physical memory (you don't want to eat into virtual memory, it will be slow.)
struct {
long checksum; // or long long might be even better
int depth;
enum { exact, lower_bound, upper_bound } entry_type;
double eval;
} hashtable[HASH_TABLE_SIZE];For each position you search, compute a
"hash value" x indexing into the hash table and another "hash
value" y for checking whether you've found the right position.
Before searching a position, lookup hashtable[x]. If hashtable[x].checksum == y, hashtable[x].entry_type == exact, and hashtable[x].depth is at least the depth you are currently searching, return the eval stored there.
After searching the position, store y, the current depth, and the eval you just computed, into hashtable[x].
How to compute hash values?
Zobrist hashing technique (already mentioned before re repetition detection): Before playing the game (maybe hardcode this in your source code) make an array Z[square,piecetype] of random numbers. Hash(board) is then just sum(Z[s,p]) summed over the pieces currently on the board combined with any extra information you might have such as castling ability. Often the sum is replaced by a bitwise exclusive or (uparrow in C) which is a little faster and easier to work with, but arithmetic addition would probably work just as well. When you move to a new position, you don't have to recompute the hash from scratch; instead you can update the hash really quickly by subtracting the old piece square value from where the moved piece was and and adding the new value for its new location. Use this technique (with different random numbers) both for the hash value x and for the checksum y.Some further tips for using hashing effectively:
- Don't clean out the array after making a move, it only wastes time and some hashed positions might actually still be useful after the move.
- If the same position occurs at different levels in the tree (as in the second transposition example we listed above) this can actually give you deeper searches than you originally asked for; that's ok.
- Don't hash the positions very near the leaves of the search tree, there are too many of them (they'll take away hash table space from more valuable positions) and you're not saving much time by avoiding searching them.
How does hashing interact with alpha-beta?
A large fraction of chess program bugs are related to hashing. Partly, because it interacts in confusing ways with alpha-beta search. But, you can't avoid dealing with the issue, because you need both hashing and alpha-beta to have an efficient searcher. Recall that, when we call alphabeta(depth,alpha,beta) on a position, one of three things can happen: a fail high, in which we know the eval is at least beta but not exactly what it is; a fail low, in which we know the eval is at most alpha but not exactly what it is; and an exact result, alpha < eva < beta. We can only store an exact result in the hash table if we know the exact result. But a fail high or fail low result could still help us prune later. So, along with exact evals, store two other kinds of eval in hash table: a lower bound stating that the eval is at least beta, and an upper bound stating that the eval is at most alpha. We use the entry_type field of the hash table entry to specify what kind of eval is being stored. If the hash lookup comes back with one of these, we need to see whether it's useful enough to prune immediately without searching the node. If so, we return it, and otherwise search the node again. Here's some pseudocode for alpha-beta search with hashing. We maintain the hashtable index x and checksum y in global variables, that are updated as part of the process of making and unmaking moves.
double alphabeta(int depth, double alpha, double beta)
{
if (depth <= 0 || game is over) return evaluation();
if (hashtable[x].checksum == y && hashtable[x].depth >= depth)
switch (hashtable[x].entry_type) {
case exact: return hashtable[x].eval;
case lower_bound:
if (hashtable[x].eval >= beta)
return (hashtable[x].eval);
else break;
case upper_bound:
if (hashtable[x].eval <= alpha)
return (hashtable[x].eval);
else break;
}
int eval_is_exact = 0;
generate and sort list of moves available in the position
for (each move m) {
make move m;
double val = -alphabeta(depth - 1, -beta, -alpha);
unmake move m;
if (val >= beta) {
hashtable[x].checksum = y;
hashtable[x].depth = depth;
hashtable[x].entry_type = lower_bound;
hashtable[x].eval = val;
return val;
}
if (val > alpha) {
alpha = val;
eval_is_exact = 1;
}
}
hashtable[x].checksum = y;
hashtable[x].depth = depth;
if (eval_is_exact) hashtable[x].entry_type = exact;
else hashtable[x].entry_type = upper_bound;
hashtable[x].eval = alpha;
return alpha;
}
Alpha-beta and move ordering
I said we'd return to alpha-beta; here it is. We did an optimistic analysis last time of alpha-beta, showing that it can double your search depth if it prunes whenever it can. The condition that "it prunes whenever it can" can be expressed more simply: good moves are searched before bad ones. The moves don't have to be completely sorted, but the best one should be first or at least one of the best should be one of the first. What happens if not? Then we don't do any pruning and we don't search very deeply.
If we classify nodes into type A (all children get searched) and type B (we prune after finding a good child) then move ordering is important in both cases: in type B, you want to start with a child that will let you prune the rest. In type A, you want to choose a first child that is good enough to let all the other children be type B.
Of course, finding good moves is hard: it's the whole reason we're doing the search in the first place. But we have some clues: (1) we may have hashtable entries from previous iterations of iterated deepening that give approximations to search values (same positions searched less deeply). (2) we may have some game-specific information, e.g. in chess captures are often good moves, try them first. (3) the killer heuristic: if move m was best in a sibling, and is valid here too, try it.
So, before searching children, add a step: sort them by expected quality. Then do the search in the sorted order. (Sometimes you can modify the move generator to output moves in roughly-sorted order e.g. captures first, and save doing an explicit sort.)
One additional trick: if you think you're going to prune, you don't need to sort everything, you just need to output the first few items in sorted order. So you may want to use a sort that you can take items one by one from and stop early, e.g. selection sort or heapsort.
David Eppstein, Dept. Information & Computer Science, UC Irvine, Thursday, 28-Oct-1999 11:42:22 PDT.
K. Bala
ssalmine
> reasons to make representation quite simple).
Actually you _don't_ know that because that is not quite true! With
todays 32-bit machines bitboards are not faster, maybe sometimes even
slower than arrays. It largely depends on implementation. The benefits
are some evaluation terms that can be measured very fast using
Bitboards, like pawn structure. You should check
www.icdchess.com/forums. There you'll get _all_ the info you need on CC.
Severi
Chris Mayer
If we have a 32 bit hash function, we have about 4 billion different
possible positions. A crash will occur (2 different positions hashing
to the same value) after only 20,991 positions are stored, using 95%
probability. Therefore, 32 bits is a bad thing. (remember 23 people
have a 50% chance of sharing a birthday?)
So we should use a 64 bit hash function. This will cause a crash
after roughly 1.3 Billion positions are stored, again with 95%
confidence.
Is this good enough? In a typical game, this is exceeded quite
easily, which means the chance of a crash is still expected.
Are there other methods to minimize this, or are a few crashes not
severe enough to give a bad move?
Thanks,
Chris Mayer
Robert Hyatt
> Thanks,
> Chris Mayer
If you use a good hashing function, this can be minimized. IE your
math is right for two totally random positions. But in reality, that
doesn't happen... two positions have to be pretty close together in the
game itself (say within 20 plies) in order to have a chance to be
stored in the table at the same time. This makes it a bit less likely
than you would think for a collision to occur...
--
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
Chris Mayer
and I also just thought of another factor. My math assumed ALL 1.3
billion positions are actually stored, allowing the next one to crash
with ANY of those, when in reality hash tables can't be that big, only
a few million or so are stored at any given time, so a collision is
even less likely than I had originally calculated.
If we assume a 64 bit hash, and 1 million entries all full, the odds
of a collision for the next position is 2^20 / 2^64. To get the 95%
confidence we have [1.0 - 1 / 2^44] * N = 0.95, and solve for N to get
the number of positions before we would expect a collision.
This comes out to about 1.67 x 10^13, quite a better number than 1.3 x
10^9.
Chris
On 18 Oct 2000 00:48:06 GMT, Robert Hyatt <hy...@crafty.cis.uab.edu>
wrote:
Tommy in Oz
> severe enough to give a bad move?
Try running it on Linux. They keep telling me you reduce your chances of a
crash if Linux is your operating system.
Yeah, yeah. I know, its a corny joke. :)
Tom.
Jeffrey A. Young
Chris Mayer <cmay...@home.com> wrote:
>Could someone please check my math here?
>
>If we have a 32 bit hash function, we have about 4 billion different
>possible positions. A crash will occur (2 different positions hashing
>to the same value) after only 20,991 positions are stored, using 95%
>probability. Therefore, 32 bits is a bad thing. (remember 23 people
>have a 50% chance of sharing a birthday?)
>
>So we should use a 64 bit hash function. This will cause a crash
>after roughly 1.3 Billion positions are stored, again with 95%
>confidence.
>
>Is this good enough? In a typical game, this is exceeded quite
>easily, which means the chance of a crash is still expected.
>
>severe enough to give a bad move?
"Crashes" as you call them (more conventionally called "collisions")
are not a severe problem for hashing. When you get one, you simply
have to do a little more checking and/or searching to find the place
for the colliding position to reside. It causes some slowdown, but
nowhere near enough to counter the huge speedup given by hashing.
Jeff
Jeffrey A. Young
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
>Chris Mayer <cmay...@home.com> wrote:
>> Could someone please check my math here?
>
>> If we have a 32 bit hash function, we have about 4 billion different
>> possible positions. A crash will occur (2 different positions hashing
>> to the same value) after only 20,991 positions are stored, using 95%
>> probability. Therefore, 32 bits is a bad thing. (remember 23 people
>> have a 50% chance of sharing a birthday?)
>
>> So we should use a 64 bit hash function. This will cause a crash
>> after roughly 1.3 Billion positions are stored, again with 95%
>> confidence.
>
>> Is this good enough? In a typical game, this is exceeded quite
>> easily, which means the chance of a crash is still expected.
>
>> Are there other methods to minimize this, or are a few crashes not
>> severe enough to give a bad move?
>
>> Thanks,
>
>> Chris Mayer
>
>
>If you use a good hashing function, this can be minimized. IE your
>math is right for two totally random positions. But in reality, that
>doesn't happen... two positions have to be pretty close together in the
>game itself (say within 20 plies) in order to have a chance to be
>stored in the table at the same time. This makes it a bit less likely
>than you would think for a collision to occur...
With a good hash function, it doesn't matter how "close" two positions
are -- the probability of collision is the same. Or are you talking
about a "tailored" hash function that is not intended to be uniformly
random? It would seem that any such "tailoring" would necessarily
entail more clumping and thus cause drastically more collisions at
some points. Can you really guarantee that such points _only_ happen
at great ply distances? How?
And are collisions really a bigger problem in chess programs than in
other hashing applications?
Jeff
Robert Hyatt
> In article <8sis06$sot$1...@juniper.cis.uab.edu>,
> Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
>>> Could someone please check my math here?
>>
>>> If we have a 32 bit hash function, we have about 4 billion different
>>> possible positions. A crash will occur (2 different positions hashing
>>> to the same value) after only 20,991 positions are stored, using 95%
>>> probability. Therefore, 32 bits is a bad thing. (remember 23 people
>>> have a 50% chance of sharing a birthday?)
>>
>>> So we should use a 64 bit hash function. This will cause a crash
>>> after roughly 1.3 Billion positions are stored, again with 95%
>>> confidence.
>>
>>> Is this good enough? In a typical game, this is exceeded quite
>>> easily, which means the chance of a crash is still expected.
>>
>>> Are there other methods to minimize this, or are a few crashes not
>>> severe enough to give a bad move?
>>
>>> Thanks,
>>
>>> Chris Mayer
>>
>>
>>If you use a good hashing function, this can be minimized. IE your
>>math is right for two totally random positions. But in reality, that
>>doesn't happen... two positions have to be pretty close together in the
>>game itself (say within 20 plies) in order to have a chance to be
>>stored in the table at the same time. This makes it a bit less likely
>>than you would think for a collision to occur...
> With a good hash function, it doesn't matter how "close" two positions
> are -- the probability of collision is the same. Or are you talking
> about a "tailored" hash function that is not intended to be uniformly
> random?
correct. The best measure is "hamming distance between two moves."
With a good hashing function (for a search) this number increases
rapidly as you make moves, and then starts to decrease again as you go
even deeper.
That is better than a hashing function that has a uniform (and necessarily
small) hamming distance between two randomly chosen positions.
>It would seem that any such "tailoring" would necessarily
> entail more clumping and thus cause drastically more collisions at
> some points. Can you really guarantee that such points _only_ happen
> at great ply distances? How?
By using the Zobrist hashing algorithm with reasonably chosen random numbers
for the hashing parts.
> And are collisions really a bigger problem in chess programs than in
> other hashing applications?
> Jeff
Hard to say. There are two known types of collisions:
1. a collision that has _no_ effect on the ultimate score backed up to
the root. These are harmless.
2. a collision that does affect the root score. These are killers. But
they are much less common due to the nature of the tree search itself.
A wrong score can cause great problems, as hash scores are trusted absolutely
and are used to avoid searching at the current position where the hit has
occurred. We know we get errors. But most of them fall into category 1
above, thank goodness... because the tree is so large and it takes lots
of positions to influence the root score.
Robert Hyatt
> Chris Mayer <cmay...@home.com> wrote:
>>Could someone please check my math here?
>>
>>If we have a 32 bit hash function, we have about 4 billion different
>>possible positions. A crash will occur (2 different positions hashing
>>to the same value) after only 20,991 positions are stored, using 95%
>>probability. Therefore, 32 bits is a bad thing. (remember 23 people
>>have a 50% chance of sharing a birthday?)
>>
>>So we should use a 64 bit hash function. This will cause a crash
>>after roughly 1.3 Billion positions are stored, again with 95%
>>confidence.
>>
>>Is this good enough? In a typical game, this is exceeded quite
>>easily, which means the chance of a crash is still expected.
>>
>>Are there other methods to minimize this, or are a few crashes not
>>severe enough to give a bad move?
> "Crashes" as you call them (more conventionally called "collisions")
> are not a severe problem for hashing. When you get one, you simply
> have to do a little more checking and/or searching to find the place
> for the colliding position to reside. It causes some slowdown, but
> nowhere near enough to counter the huge speedup given by hashing.
> Jeff
Not in chess. We don't store the _real_ position in the table. If we
get a bogus signature collision, we don't even _know_ that it happened.
We just get incorrect scores, moves, bounds, etc...
William Tunstall-Pedoe
<jyo...@steptools.com> writes
>In article <9qmpuscfp3ieq37in...@4ax.com>,
>Chris Mayer <cmay...@home.com> wrote:
>>Could someone please check my math here?
>>
>>
>>Are there other methods to minimize this, or are a few crashes not
>>severe enough to give a bad move?
>
>"Crashes" as you call them (more conventionally called "collisions")
>are not a severe problem for hashing. When you get one, you simply
>have to do a little more checking and/or searching to find the place
>for the colliding position to reside. It causes some slowdown, but
>nowhere near enough to counter the huge speedup given by hashing.
>
Crashes are not the same as collisions in this context. A collision is
when the hash function initially points to a place in the table that
already contains a (different) record. As a hash table, by definition,
is a means of storing records in a smaller number of slots than there
are possible key values, this event is fundamental to the algorithm and
happens extremely frequently.
How chess differs from most applications where hashing is used, is that
for speed and space reasons, the key used is not the position itself but
a longer version of the hash code. This is where the confusion comes in.
A crash is when two different positions get the same identifying
"signature", thus the chess algorithm has no means of telling them apart
and will retrieve wrong information from the hash table. If the entire
position was stored in the table (a list of pieces, squares, rights, ep
and who to move) this would never happen. The thread is about how many
bits (32 or 64) are needed to minimize this possibility.
The actual hash code is often trivially derived from the long version of
it. e.g. by making the table a power of two and masking off a certain
number of bits from the signature.
William Tunstall-Pedoe
---------------------------------------------------------------
| * Crossword Maestro * (solves cryptic and non-cryptic clues)|
| * Anagram Genius * (remarkable anagrams of any text) |
---------------------------------------------------------------
| More information from: http://www.genius2000.com/ |
---------------------------------------------------------------
Urban Koistinen
! How chess differs from most applications where hashing is used, is that
! for speed and space reasons, the key used is not the position itself but
! a longer version of the hash code. This is where the confusion comes in.
! A crash is when two different positions get the same identifying
! "signature", thus the chess algorithm has no means of telling them apart
! and will retrieve wrong information from the hash table. If the entire
! position was stored in the table (a list of pieces, squares, rights, ep
! and who to move) this would never happen. The thread is about how many
! bits (32 or 64) are needed to minimize this possibility.
! The actual hash code is often trivially derived from the long version of
! it. e.g. by making the table a power of two and masking off a certain
! number of bits from the signature.
Assuming a full hash table.
s*p/h = chance of a crash (good approximation when small)
s = number of slots for each key, often 1
p = number of different positions looked up
h = number of different hash values (65536 if 16 bit)
The hash value is the value stored in the table,
not the hash key used to decide where to store.
s=1,p=2**32,h=2**40 means one run in 256 would have a crash.
Having crashes need not affect the final result as the vast
majority of positions in the search tree will be non-critical.
Go for a 64 bit hash value if you want to be sure of no crashes,
use 32 bits if you want to maximize program strength.
Also, remember that the hash key is separate.
Urban Koistinen - m10...@abc.se
Dan Thies
As has been pointed out, even if a collision occurs, the odds of it changing the
final move selected are minimal. Especially with the right hashing algorithm,
since two positions that share a hash signature are very likely to have similar
or identical scores from the evaluation.
I worried about it years ago, tested by comparing searches with and without hash
tables, and decided it wasn't worth worrying about. After simulating a few
hundred games, I didn't see any difference between them.
Dan