Surely probability or something very much like it is conceptually the right way to deal with uncertainty, whether it’s logical uncertainty or any other kind? Granted, most of the time you don’t want to deal with explicit probability distributions and Bayesian updates because the computation can be expensive, but when you work with approximations you’re better off if you know what it is you’re approximating.
In the area of search algorithms, I think these kinds of approaches are woefully underrepresented, and I don’t think it’s because they aren’t particularly applicable. Granted, I could be wrong on this, because the core ideas aren’t particularly new (see, for example, Dynamic Probability, Computer Chess, and the Measurement of Knowledge by I. J. Good).
It’s an area of research I’m working on right now, so I’ve spent a fair amount of time looking into it. I could give a few references on the topic, but on the whole I think they’re quite sparse.
On the whole, though, it’s relatively limited. At a bare minimum there is plenty of room for probabilistic representations in order to give a better theoretical foundation, but I think there is also plenty of practical benefit to be gained from those techniques as well.
As a particular example of the applicability of these methods, there is a phenomenon referred to as “search pathology” or “minimax pathology”, in which for certain tree structures searching deeper actually leads to worse results, when using standard rules for propagating value estimates up a tree (most notably minimax). From a Bayesian perspective this clearly shouldn’t occur, and hence this phenomenon of pathology must be the result of a failure to correctly update on the evidence.
Surely probability or something very much like it is conceptually the right way to deal with uncertainty, whether it’s logical uncertainty or any other kind? Granted, most of the time you don’t want to deal with explicit probability distributions and Bayesian updates because the computation can be expensive, but when you work with approximations you’re better off if you know what it is you’re approximating.
In the area of search algorithms, I think these kinds of approaches are woefully underrepresented, and I don’t think it’s because they aren’t particularly applicable. Granted, I could be wrong on this, because the core ideas aren’t particularly new (see, for example, Dynamic Probability, Computer Chess, and the Measurement of Knowledge by I. J. Good).
It’s an area of research I’m working on right now, so I’ve spent a fair amount of time looking into it. I could give a few references on the topic, but on the whole I think they’re quite sparse.
Here’s some of the literature:
Heuristic search as evidential reasoning by Hansson and Mayer
A Bayesian Approach to Relevance in Game Playing by Baum and Smith
and also work following Stuart Russell’s concept of “metareasoning”
On Optimal Game-Tree Search using Rational Meta-Reasoning by Russell and Wefald
Principles of metareasoning by Russell and Wefald
and the relatively recent
Selecting Computations: Theory and Applications by Hay, Russell, Tolpin and Shimony.
On the whole, though, it’s relatively limited. At a bare minimum there is plenty of room for probabilistic representations in order to give a better theoretical foundation, but I think there is also plenty of practical benefit to be gained from those techniques as well.
As a particular example of the applicability of these methods, there is a phenomenon referred to as “search pathology” or “minimax pathology”, in which for certain tree structures searching deeper actually leads to worse results, when using standard rules for propagating value estimates up a tree (most notably minimax). From a Bayesian perspective this clearly shouldn’t occur, and hence this phenomenon of pathology must be the result of a failure to correctly update on the evidence.