Re: computer-go: Alpha-Beta Search

["Chris Whittington" <Chris@xxxxxxxxxxxxxxxxxx>]

>----- Original Message -----
>From: Patricia Hughes and David Elsdon <babel17@xxxxxxxxxxxxxxxxx>
>To: <computer-go@xxxxxxxxxxxxxxxxx>
>Sent: 15 November 1999 22:01
>Subject: computer-go: Alpha-Beta Search


> The Knuth Paper to read is:
>
> Knuth and Moore "An analysis of alpha-beta pruning" Artificial
> Intelligence 6(4), 293-326, 1975.
>
> Note that you will only get the reduction of the branch factor to the
> square root of the branch factor if the search is perfectly ordered by
> the goodness (according to the evaluation function) of the moves. So
> provided your ordering is reasonably good most of the time you will get
> fairly close to optimal pruning.
>
> Cheers
>
> David Elsdon

Chess experience is that move ordering is almost optimal, mostly just by
non-demain specific tricks which could wrap to Go.

To try and illustrate why a/b works on sqrt basis ....

Think of after the first move has been searched and evaluated. If your first
move is actually best (and it is likely to be because you chose it from a
previous iteration at depth-1), Then on your *second* move your opponent
will try as his first refutation the same refutation move that he tried
before. Usually this refutation works, and tells you that your opponent can
at least make you do worse if you played this second move instead - so, this
is the clever bit of a/b, you cut all his remaining replies to your second
move, no point in proving a loser is a bigger loser. And so on through the
rest of the move list.

You can see that this 'refutation' move is chosen as simply the best move
found before. So it is non-domain specific.

There other many other move ordering tricks.

You play 361 moves, but he usually refutes you with 1 move. So the tree
expands as 361x1x361x1 etc. sqrt.

Interesting in this model is the idea that most of your moves are junk, and
his not.

Chris Whittington




Chris Whittington

>
>
>