Re: [computer-go] alpha-beta + graph history question

[Evan Daniel <evanbd@xxxxxxxxx>]

On Thu, 17 Mar 2005 08:12:06 +0000, Peter McKenzie
<peter_mckenzie@xxxxxxxxxxxxxxxxx> wrote:

> It's not overly important, but this is kind of an unusual way of expressing
> the alpha beta algorithm.
> More normal is something like this:
> 
> moveScore = -alphabeta(-beta, -alpha, depth -1)
> 
> so depth starts at D (depth of current iteration) counts down to zero, and
> the score is always relative to the side to move (positive means better for
> side to move).  Obviously your depth is counting up to D, but how about your
> scores?

I'm counting up instead of down because it made more sense to me, and
I didn't see how it made any actual difference.

I'm keeping score as positive = better for black, and then doing all tests as

if (score * toPlay >= beta * toPlay)

where toPlay is 1 for black, -1 for white.  This is logically
equivalent to negamax, but results in the numbers in the various data
structures being more intuitive to me when I look at them manually,
which I considered a big win.

> 
> >     if (child.score > score) {
> >       score = child.score;
> >       score_type = EXACT_SCORE;
> 
> in here don't you want to set alpha = child.score?  Otherwise you aren't
> narrowing the AB window.
> 
> >     }
> >
> >     if (score > beta) {
> 
> this should be >=

Oops, yes, I'm doing both of those correctly in my code.  That'll
teach me to write alpha-beta routines out in email without detailed
examination of my code first :)

> 
> >       store_transposition_table();
> >       score_type = BETA_CUTOFF;
> >       return score;
> >     }
> >
> >     if (score > alpha) {
> >       assert child.score_type == EXACT_SCORE;
> >     }
> 
> this assert seems OK to me, but then it is easy to make a mistake with this
> stuff :-)

Hmm....  then I must be doing something wrong elsewhere; time to keep
searching.  Mistakes seem very easy in this territory :)

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