I’m reading Introduction to Artificial Intelligence by Ertel.
This line has me stumped from the textbook (page 102):
For decidable problems such as the 8-puzzle this means that the whole search tree must be traversed up to a maximal depth whether a heuristic is being used or not.
And decidable ca be defined thus:
an algorithm that can and will return a Boolean true or false value (instead of looping indefinitely)
Why can’t the program return if it encounters the goal state before it has traversed the entire tree? What am I missing?
In case context is important, this is the preceding sentence:
In closing, it remains to note that heuristics have no performance advantage for unsolvable problems because the unsolvability of a problem can only be established when the complete tree has been searched through.
See page 102.
It says elsewhere in the book that heuristics often reduce computation dramatically for “solvable problems”! Is there a difference between “decidable” and “solvable” problems that’s relevant here? It’s not explained why heuristics are good for “solvable” problems and bad for “decidable” ones.
2
A problem is solvable iff a solution exists.
A problem is decidable iff we can tell whether the problem is solvable or not, i.e. whether a solution exists.
The 8-puzzle is not always solvable, but it is decidable since if a solution exists, we know it will take at most 31 single-tile moves. So to decide whether a given 8-puzzle is solvable, we must find any solution. If no sequence of moves with max length of 31 solves the problem, we know that this puzzle is unsolvable.
Now we can restate this in terms of whether the problem is solvable:
-
For a solvable problem, we only need to find one solution to prove that it’s solvable. Here, heuristics can speed up finding a solution.
-
For an unsolvable problem, we have to prove that not a single solution exists. Since a heuristic will not lead to a solution for an unsolvable problem, we have to investigate the whole game tree to be sure that it contains no solutions. Since we have to investigate every possible game state, a heuristic will not matter (all a heuristic does is prioritize promising moves). Since a heuristic adds a computational cost, using a heuristic will be a net loss for unsolvable problems.
The funny thing is that we do not generally know a priori whether a given problem is solvable.
Edit: This comment from another user(@esoteric) adds some additional clarity:
Try thinking of it as a statement of what happens in the worst case, especially given that half of the initial positions are unsolvable, and viewing the opportunity for early termination as a happy accident. Consider also that if the traversal is unlucky, it still may be required to walk the entire tree before finding a solution even if the instance is solvable. So, for > 50% of all instances, a full traversal is required. Given that, it’s reasonable for the algorithm to expect to have to traverse the entire tree.
10