Thank you, I should have thought of it in that (Time complexity) context. Time complexity is not just about how long it takes but also about the nature of the problem. Chess is neither P nor NP, but the question of complexity is certainly related.
Maybe my question is: Why can there be a Heuristic that does fairly well and is nowhere near exponential? Even a count of the pieces left on the board usually says something that only a full search can prove.
Thank you, I should have thought of it in that (Time complexity) context. Time complexity is not just about how long it takes but also about the nature of the problem. Chess is neither P nor NP, but the question of complexity is certainly related.
Maybe my question is: Why can there be a Heuristic that does fairly well and is nowhere near exponential? Even a count of the pieces left on the board usually says something that only a full search can prove.