provably optimal search algorithms? In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-chosen heuristics. These heuristics are not proven to be the optimal heuristics.  (they're not optimal obviously).

I am wondering however: 


  Is there some kind of search problem (ideally a non-trivial one), where (1) there is a specific known algorithm that solves it, and (2) a proof that the algorithm is optimal in the sense that there does not exist an algorithm that solves it faster in expectation, where (3) the probability distribution for that expectation is the relevant one for that practical search problem?


I'm interested in anything related to this. If you know something that seems partially relevant, please say so.

EDIT: Alternatively, please suggest a different notion of "optimality" if you think it is more relevant. I am not sure how relevant my notion of optimality is.

EDIT 2: I'm also interested in how this question relates to the 'No free lunch' theorems in search and optimization.
Finding an optimal solution for a problem is very difficult. for example in sorting you can prove that the optimal solution with comparison is $O(n \log n)$ but may be you can find an algorithm with $O(n)$ without comparison like hashing! another good example is NP Complete problems we even can't prove they haven't polynomial algorithm. so it is very hard to find an optimal solution for deep blue and similar algorithms and proving that the algorithm is optimal is very hard too.