Likewise, there's a lot of work that's gone into other known search-space problems. Adversarial strategy (like playing chess), for example has had a ton of work poured into it. There's the so-called "A*" algorithm, which employs some interesting pruning techniques against the search tree. That, of course, has to employ a huersitic function, again (generally some sort of "scoring", like in chess you could add up the point values of all your pieces and subtract the point-values of all of your opponent's pieces). It also makes use of some interesting properties of adverserial strategy, such as the fact that your opponent will not willingly choose a move that allows the possibillity of an exceptional counter-move on your part.

Anyway, the point I meant was: I don't have a good optimization to use against this (and I gave an example of how this is similar to some other AI problems that do have interesting optimizations). Part of what gets in the way is the lack of some sort of helpful heuristic. That is, I haven't yet thought of a good way of representing (as a mathematical function applied against a stage of the algorithm) that an algorithm is likely to "contain more information", in such a way that it doesn't "cheat" and impose my foreknowledge of the answer on the problem :-)

------------
:Wq
Not an editor command: Wq
[download]