Re: [Bug-gnubg] [Fwd: gnubg search function]

[Thomas Hauk]

On Fri, 28 Mar 2003, Joseph Heled wrote:
> Would you care to enlighten us a little more, say by explaining how it 
> would speed up a 1ply search? Just a rough idea would do.

The algorithm wouldn't speed up a 1-ply search; at 1-ply, all children of 
the root node are guaranteed to be expanded (because it is a max node). 
The benefits of search algorithms like alphabeta and *-minimax is they 
reduce the complexity of deep searches.

Alphabeta uses upper and lower bounds on what can be acheived to create 
cutoffs. For example, if you are searching in a part of the tree where 
you have a move that guarantees you a score of at most 10, but you 
already know of a move that will guarantee you a score of 12, then you can 
cut off search there because there's no sense looking around for a move 
worse than you already have.

*-minimax works on the same principle, but uses a weighted sum of the 
moves beneath a chance node to determine upper and lower bounds.

--Tom