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