RE: computer-go: Hashing during minimax

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> 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. [...]
>
> 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?

As your evaluations are cheap, you need to minimize the cost of
maintaining the hash table. I'd allocate it once at a fixed size, and
overwrite existing entries. Don't store the whole board, just the hash
code and the evaluation. If it's not faster than evaluating the
position, your evaluation function is too simple. :-)

During alpha-beta search, you'll also want a hash table to store the
result and best move at each node, and then use that to generate the
best move in positions you've already seen. This is especially valuable
if you use iterative deepening or a minimal-window search technique such
as Scout, as you'll often get back to positions you've already seen.

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

Yes, the ko state might be different, so you should re-evaluate it.
However, the problem is worse than that, as you might reach the same
position at the same depth by two different move sequences, and as that
might cause different future moves to be legal, you'd need to
re-evaluate too, losing most of the benefits of hashing. A perfect
solution is hard; SmartGo avoids most such issues by modifying the hash
code when stones are captured in a way that depends on the move number
at which the stones were captured.

Anders Kierulf
www.smartgo.com