ECAI 2004 Conference Paper

[full paper]

Adversarial Constraint Satisfaction using Game-tree Search

Kenneth N Brown, James Little, Paidi J Creed, Eugene C Freuder

Many decision problems can be modelled as "adversarial" constraint satisfaction, and doing so allows us to bring to bear methods from artificial intelligence game playing. In particular, by using the idea of "opponents", we can model both collaborative problem solving, where intelligent participants with different agendas must work together to solve a problem, and multi-criteria optimisation, where a single solver must balance different objectives. In this paper, we focus on the case where two opponents take turns to instantiate constrained variables, each trying to direct the solution towards their own objective. We represent the process as game-tree search. We develop constraint propagation methods and variable and value ordering heuristics based on game playing strategies. We examine the performance of various algorithms on general-sum graph colouring problems, for both multi-participant and multi-criteria optimisation.

Keywords: constraint satisfaction, search, game tree

Citation: Kenneth N Brown, James Little, Paidi J Creed, Eugene C Freuder: Adversarial Constraint Satisfaction using Game-tree Search. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.151-155.