Influence of Search Depth on Position Evaluation

By using a well-known chess program and a large data set of chess positions from real games we demonstrate empirically that with increasing search depth backed-up evaluations of won positions tend to increase, while backed-up evaluations of lost positions tend to decrease. We show three implications of this phenomenon in practice and in the theory of computer game playing. First, we show that heuristic evaluations obtained by searching to different search depths are not directly comparable. Second, we show that fewer decision changes with deeper search are a direct consequence of this property of heuristic evaluation functions. Third, we demonstrate that knowing this property may be used to develop a method for detecting fortresses in chess, which is an unsolved task in computer chess.