Re: computer-go: Hashing during minimax

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

You might want to read Dennis Breuker's thesis. (It contains a lot of
information about transpositions/hash tables)

http://www.breuker.demon.nl/thesis/index.html

Erik



Peter Drake wrote:
> 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.

That's obvious, but sorting on evaluation can be expensive. Did you try
the basic move ordering techniques such as: transposition move, killer
moves, history heuristic?


> 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).

Why is your hash table so expensive to maintain? Hash tables should be
fast, otherwise what's the point of using them anyway? Or do you mean
that RAM is expensive :-) 

(btw 50% reduction from a hash table is not much, with deep searches one
may expect reductions far over 95%)


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

Replacement schemes is the buzz-word. I mainly use "two-deep" (see
breuker).


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

Normally yes, unless you see that you will not search deeper (may happen
with a sure win or loss). (store the depth in the hash table!)