Adversarial Constraint Satisfaction by Game-tree Search

Many decision problems can be modelled as adversarial constraint satisfaction, which allows us to integrate methods from AI 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 one decision maker 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 variable and value ordering heuristics based on game playing strategies.We examine the performance of various algorithms on general-sum graph colouring games, for both multi-participant and multi-criteria optimisation.