The optimal value function is an evaluation function which encapsulates complete knowledge of the best expected search outcome attainable from each state:
Such an evaluation function is ideal in that a greedy local search
with respect to will always make the globally optimal move.
This section reviews the literature on computing
, and
motivates and describes our new approximation algorithms for this
problem.