The X-0-0 Heuristic in Game Tree Analysis

Abstract

Programs for two-person games, such as chess or Go, are heavily dependent on Minimax evaluation of large game trees, which is combined with heuristics in an attempt to prune these trees as severely as possible. In particular, alpha-beta pruning, usually combined with killer heuristic, is used in all major minimax-based programs, In this paper we shall propose a new heuristic which could be incorporated into minimax-based programs, and which should significantly increase pruning possible during analysis of game trees. This new heuristic, which can be combined with alpha-beta and killer heuristic, is called X-0-0 heuristic. The development of heuristic was prompted by difficulty of analyzing large game trees in Go, and is based on a formalism and extension of Go proverb the enemy's play is my own key play.