TY - GEN
T1 - Adversarial constraint satisfaction by game-tree search
AU - Brown, Kenneth N.
AU - Little, James
AU - Creed, Paidi J.
AU - Freuder, Eugene C.
PY - 2004
Y1 - 2004
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85017402982
M3 - Conference proceeding
AN - SCOPUS:85017402982
T3 - Frontiers in Artificial Intelligence and Applications
SP - 151
EP - 155
BT - ECAI 2004 - 16th European Conference on Artificial Intelligence, including Prestigious Applications of Intelligent Systems, PAIS 2004 - Proceedings
A2 - de Mantaras, Ramon Lopez
A2 - Saitta, Lorenza
PB - IOS Press BV
T2 - 16th European Conference on Artificial Intelligence, ECAI 2004
Y2 - 22 August 2004 through 27 August 2004
ER -