provably optimal search algorithms?
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.