The last player theorem

摘要

Game trees are an important model of decision-making situations, both in artificial intelligence and decision analysis, but many of the properties of game trees are not well understood. One of these properties is known as biasing: when a minimax search is done to an odd search depth, all moves tend to look good, and when it is done to an even search depth, all modes tend to look bad.One explanation sometimes proposed for biasing is that whenever a player makes a move his position is ‘strengthened’, and that the evaluation function used in the minimax search reflects this. However, the mathematical results in this paper suggest that biasing may instead be due to the errors made by the evaluation function.