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.