🚀 go-pugleaf

In article <22964@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>In article  <lcf2ctINN2te@coltexo.cs.utexas.edu> Donald A. Varvel writes:
>]First of all, it is not necessary to visit every node in the game tree.
>]Period.  Alpha-beta pruning yields the same result as min-max, provided
>]each works with the same assumptions.  That is, an alpha-beta search
>]of the entire game tree yields the same result as min-max, while cutting
>]of many branches without analysis.  That's a minor point, though, since
>]A-B doesn't promise an easy solution either.
>
>It's been some time since I looked at this stuff, but as I recall,
>search strategies that are still guaranteed to find the optimal
>solution cannot be asymptotically better than breadth-first search
>with the same cost function.  So alpha-beta pruning will do no better
>than remove a polynomial number states from an exponential search
>space.
>-- 
>					David Gudeman

Alpha-beta with good move ordering reduces the size of the minimax
tree to nearly the square root of the size of the minimax tree.  alpha
beta does not guarantee to find the shortest path to a win, but it will
find the best score.  If you make the path length part of the scoring
function, then even this complaint fades away.  breadth-first is not
appropriate to alpha-beta.....  it works with minimax DEPTH-FIRST game
trees only.  

Bob Hyatt

-- 
!Robert Hyatt                    Computer and Information Sciences   !
!hyatt@cis.uab.edu               University of Alabama at Birmingham !