computer-go: Hashing during minimax

[Peter Drake <drake@xxxxxxxxxx>]

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/