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

[Karol Golab <karol@xxxxxx>]

On Wed, Mar 09, 2005 at 05:27:35AM +0000, Peter McKenzie wrote:
> 
> >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):

  I usually store both the evaluation and alpha-beta bounds. This allows
for reusing evaluation if it's inside current window and limiting the
current window if it overlaps with the stored one.
  Sure, the ifs managing all cases are ugly and I have had more than one
bug there. But after a few runs with full debug and code audit it appears
to work correctly.

  Regards,
  Karol

-- 
   e-mail: karol@xxxxxxxxxxxxxxxxx
      www: http://www.tls.pl/
signature: not found

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