🚀 go-pugleaf

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
gudeman@cs.arizona.edu