Re: computer-go: Hashing during minimax

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I use a small hash table for each tactical search, but I do not use a hash 
table for the full board search.

David

At 09:53 AM 4/23/2003 -0700, Peter Drake wrote:
> I'm working on the minimax part of my program.
>
> I found that sorting the moves by static evaluation at each ply is a big 
> win, because it allows alpha-beta pruning to cut a lot of nodes out of the 
> tree.
>
> On the other hand, storing the boards I've already evaluated (in a hash 
> table) seems to be a loss.  I get a lot of hits, roughly halving the 
> number of evaluations I have to do, but this seems to be overwhelmed by 
> the cost of maintaining a hash table containing tens of thousands of 
> boards.  Of course, the trade-off may go the other way when I'm using a 
> less trivial evaluation function (currently just counting stones) and 
> considering fewer moves (currently considering everything).
>
> What are people doing about this problem?  Limiting the size of the table, 
> and either ignoring additional boards or overwriting earlier 
> ones?  Skipping stored boards altogether?
>
> I have one other concern:  suppose I evaluate a board at a leaf node, and 
> later encounter it again higher in the tree.  Should I re-evaluate it?
>
> Peter Drake
> Assistant Professor of Computer Science
> Lewis & Clark College
> http://www.lclark.edu/~drake/