Author |
Topic: searching in hash table (Read 1675 times) |
|
ecks
Forum Newbie
Arimaa player #4015
Gender: 
Posts: 2
|
 |
searching in hash table
« on: Apr 16th, 2009, 6:50pm » |
 Quote  Modify
|
hello, i am trying to write a simple arimaa bot. I am using zobrist hashing and currently for every evaluated board position, I am storing its value along with its hash into a list, which I binary search through every time that I need to make a different move in order to find transpositions. I am not happy with this implementation, however, since it takes longer to search through the list rather than to just go ahead and evaluate the board. I am doing this also only for the leaf nodes of a minimax algorithm, so I am not comparing intermediate hashtables. In the future I will compare intermediate hashtable values as well, but I thought that would take even longer since the list would need to get recursed even for intermediate values. I was wondering if there is other well known more efficient way to look at whether the board was already evaluated.
|
|
 IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: searching in hash table
« Reply #1 on: Apr 16th, 2009, 7:59pm » |
Quote Modify
|
The standard implementation of a transposition table is an array of board evaluations, indexable by a hash of their Zobrist keys. The most obvious choice of a hash function is one that simply masks away everything but the N least significant bits. A further equality check of Zobrist keys is necessary after a hash hit in order to prevent any collisions (other than the extremely unlikely case of two board positions sharing the same complete Zobrist key).
See http://chessprogramming.wikispaces.com/Transposition+Table for more.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: searching in hash table
« Reply #2 on: Apr 16th, 2009, 8:45pm » |
Quote Modify
|
on Apr 16th, 2009, 6:50pm, ecks wrote:| I am storing its value along with its hash into a list, which I binary search through |
|
I am not a programmer, but I thought the point of a hash table was direct addressing of the contents (in constant time) by the key, making a binary lookup (in log(n) time) unnecessary.
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: searching in hash table
« Reply #3 on: Apr 16th, 2009, 9:04pm » |
Quote Modify
|
Yep. Mask the first N bits and index into an array.
Also, doing hash lookups at interior nodes is usually more important than doing lookups at leaf nodes (although both is good, unless your evaluation is very fast). For instance, a detecting a transposition in the interior allows you to skip the search of an entire subtree, instead of skipping only one evaluation.
Also, because the game tree branches out exponentially, there are usually much fewer interior nodes than leaf nodes - if every additional depth is four times the nodes of the previous, for instance, then the great majority of nodes will be leaves. Doing even expensive computations at interior nodes costs very little.
|
|
IP Logged |
|
|
|
ecks
Forum Newbie
Arimaa player #4015
Gender:
Posts: 2
|
|
Re: searching in hash table
« Reply #4 on: Apr 17th, 2009, 2:44am » |
Quote Modify
|
ah got it, thanks, too bad I didn't think of that before. also, if you are using part of the hashkey as index, there's a an even likelier chance of collision. could you do something, like for instance, if you are inserting into position and you see that there is an element already in that slot, you take one more significant digit up until you find a free slot? then when you search for actual position, if the hashtables don't match, you can take one more significant digit up and so on.
|
| « Last Edit: Apr 17th, 2009, 2:59am by ecks » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print