RE: computer-go: Alpha-Beta Search

["Xu, Mousheng" <moushengxu@xxxxxxxxxxxxxxxx>]

Thanks, David.

The book is not available at the university library that I can access,
but I searched out another book based on the title by G. M. Baudet. I
won't be able to get the book before the coming weekend, any way.

Let's take Go playing as an application of the algorithm.

Here is how I understand:

Suppose I am trying to evaluate a Black move at certain depth of the
tree. In order to do that, I need to find out the best White move as the
next move. Finally, the value of the Black move is exactly the negative
of the best White move, but then why during the evaluation of White
moves, if the value of a White move is good (or bad) enough, then no
need to continue evaluation of other possible White moves? 

I might have misunderstood in a couple of places, already. :)

Thanks for any correction or suggestion.

-- Mousheng Xu

-----Original Message-----
From: Patricia Hughes and David Elsdon [mailto:babel17@xxxxxxxxxxxxxxxxx]
Sent: Monday, November 15, 1999 2:01 PM
To: computer-go@xxxxxxxxxxxxxxxxx
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