Games and Search | Department of Intelligent Systems

Games and Search

Heuristic search is a widely used problem-solving technique, for example in computer game playing, pathfinding and planning. A typical approach is to represent a problem with a graph in which the vertices correspond to states and edges to actions. A search algorithm then searches the graph from the current state to some depth, heuristically evaluates the states at that depth, and backs up the values from there to the current state, where they are used to select the best action.

Practice shows that searching deeper leads to better actions. However, analyses of mathematical models showed that under apparently sensible conditions the opposite happens: backing-up amplifies the error of the heuristic evaluations and consequently deeper search yields worse actions. This phenomenon was termed search pathology. We investigated the causes of the pathology and the factors that influence the benefit of deeper search. We found that the pathology is more likely if the number of possible position values is low, branching factor of the graph high, and similarity of nearby states low. We also showed that the pathology in some of the mathematical models can be eliminated by careful modeling of the error of the heuristic evaluations.

In addition to the pathology, we work on other aspects areas of games and search. We have developed methods for playing card games, particularly tarok, and bidding in tarok. We have also contributed to a pathfinding method that trades some computation at runtime for precomputation of optimal search depths in various areas of the map.

Contact: M. Luštrek (mitja.lustrek@ijs.si)