Lifted backward search for general game playing

A General Game player is a computer program that can play games of which the rules are only known at run-time. These rules are usually given as a logic program. General Game players commonly apply a tree search over the state space, which is time consuming. In this paper we therefore present a new method that allows a player to detect that a future state satisfies some beneficial properties, without having to explicitly generate that state in the search tree. This may lead to faster algorithms and hence to better performance. Our method employs a search algorithm that searches backwards through formula space rather than state space.