🚀 go-pugleaf

In article  <1992Sep30.013941.1664@cis.uab.edu> Robert Hyatt writes:
]In article <22964@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:

]>It's been some time since I looked at this stuff, but as I recall,

Then don't post without refereshing your memory.

]>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.

Breadth-first search doesn't even use cost functions, you dimwit.
Don't post before your morning caffeine fix either.

]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...

Still, that doesn't reduce the complexity of an _exponential_
function.  So if the size of the tree is intractable, it will remain
intractable after pruning those nodes.

I think what I was getting at (although I'm posting pre-caffeine
again) is that an NP-hard search space cannot be made subexponential
though clever search strategies (unless P = NP).  But since (to my
knowledge) chess has not been proven NP-hard, my whole point was
rather pointless.  So never mind.
-- 
					David Gudeman
gudeman@cs.arizona.edu