Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> searching in hash table
        
(Message started by: ecks on Apr 16^th, 2009, 6:50pm)

Title: searching in hash table
Post by ecks on Apr 16^th, 2009, 6:50pm

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.

Title: Re: searching in hash table
Post by aaaa on Apr 16^th, 2009, 7:59pm

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.

Title: Re: searching in hash table
Post by Fritzlein on Apr 16^th, 2009, 8:45pm

on 04/16/09 at 18:50:53, 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.

Title: Re: searching in hash table
Post by lightvector on Apr 16^th, 2009, 9:04pm

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.

Title: Re: searching in hash table
Post by ecks on Apr 17^th, 2009, 2:44am

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.