Re: computer-go: Hashing during minimax

[Don Dailey <drd@xxxxxxx>]

Sorting the  moves by static evaluation  is a great thing.   It may be
too expensive if you are near  leaf nodes, but you can instrument your
program to find out where to stop.

The  hash table  should  be a  big  win, but  there  is little  detail
provided   about  your   implementation.    It's  easy   to  get   the
implementation details wrong,  so I would be suspicious  of this.  How
are you generating the hash  key?  Are you storing both the evaluation
and  providing a best  move to  speed up  the search  if the  entry is
unusuable for a cutoff?

Can you provide more details?   How deep is the search?   Is it global
or local?  

>   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?

You must re-evaluate in this case, unless of course you are only using
the hash table as a cache for keeping static evaluations.

I would  like to be  sure I'm understanding your  questions correctly.
Can you clarify and provide more detail?

Don



   Date: Wed, 23 Apr 2003 09:53:22 -0700
   Content-Type: text/plain; charset=US-ASCII; format=flowed
   From: Peter Drake <drake@xxxxxxxxxxxxxxxxx>
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   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/