From Game Trees to Game Graphs

摘要

The definition of the score of a game tree is extended using the minimax rule togame graphs containing cycles. This is accomplished by taking the limit of a sequence of scores of game trees that in some sense approximate the game graph. It is shown that this score is well defined for all game graphs, and algorithms for its evaluation are given, including one that uses memorization.