Re: [computer-go] Alpha-beta pruning vs transposition tables

["Peter McKenzie" <peter_mckenzie@xxxxxxxxxxx>]

From: Chris Fant <chrisfant@xxxxxxxxxxxxxxxxx>
> Reply-To: Chris Fant <chrisfant@xxxxxxxxxxxxxxxxx>,computer-go 
> <computer-go@xxxxxxxxxxxxxxxxx>
> To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
> Subject: Re: [computer-go] Alpha-beta pruning vs transposition tables
> Date: Tue, 8 Mar 2005 23:50:46 -0500
>
> > I discovered something of which I hadn't been aware:  alpha-beta
> > pruning and transposition tables can interact in nasty ways.  Perhaps
> > everyone else already knew this.
> >
> > The problem is that, when a branch is pruned, the root of that branch
> > is given an evaluation which may not be entirely accurate.  It's enough
> > to prove that the branch is irrelevant for this move, but storing this
> > value in a transposition table can lead to an incorrect result when the
> > position is encountered again.
> >
> > Clearly, not storing pruned values in the table would avoid this
> > problem.  Is it safe to store them as long as they aren't kept around
> > for the next search?

Best to store the bound type (EXACT, LOWER, UPPER) and use that when you 
retrieve the hash record.  As well as the link already given, you might find 
something of interest here (it's chess related but should translate easily 
enough):

http://www.seanet.com/~brucemo/topics/hashing.htm

> It is not immediately obvious and turns out nasty indeed.
It isn't that nasty once you get used to it.

Really nasty stuff can happen if you use path dependent information in your 
evaluation function.

cheers,
Peter

> This is why
> I currently have my TT turned off -- because when I wrote it, I did
> not understand this interaction.  Look here, in the section called
> "Result Caching":
>
> http://www.andromeda.com/people/ddyer/go/search.html
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
_________________________________________________________________
Need more speed? Get Xtra JetStream  @ http://xtra.co.nz/jetstream

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/