Transcript Adversarial constraint solving

Adversarial Constraint Solving
Supervisors:
Ken
Brown,
4C
Cork Constraint Computation Centre (4C),
Eugene Freuder, 4C
University College Cork,
Youssef Hamadi, Microsoft
David Stynes,
Microsoft is a registered trademark
of Microsoft Corporation
Cork, Ireland
This work is funded by the Irish Research Council for Science, Engineering and Technology (IRCSET) Embark
Initiative in collaboration with Microsoft Research.
What is Adversarial Constraint Solving?
It is the combination of constraint satisfaction techniques with artificial intelligence
game playing to tackle decision problems in which two or more self-motivated agents
with different goals must produce a joint solution.
Constraint Satisfaction Problems (CSP)
AI Game Playing
We can use constraint propagation and other
techniques from constraint satisfaction to
reduce the size of variables’ domains.
Reason three moves ahead and estimate quality
of the resulting states.
Simple constraint problem
j
i<j
j=k
1
i
1
2
k
3
1
2
We can let agents reason about their
decisions and take into account their
adversaries’ possible future decisions.
my possible moves:
adversary's possible moves
2
3
3
k<m
2*i < m
2
3
4
5
-
-
-
+
evaluate
+
+
-
+
m
Propagate the estimates up the search tree to
get estimates for moves from the current state.
After Constraint Propagation
i<j
j
i
2
1
3
j=k
k
2
2
3
-
k<m
2*i < m
3
4
5
+
-
-
-
+
+
-
+
propagate
+
+
+
+
-
m
We hope to guide a CSP to a good solution, which suits the agents’ respective objectives, using
the AI game playing algorithms and they in turn benefit from the pruned search tree which CSP
provides.
We have applied Adversarial Constraint Solving to a simple abstract
security model based upon the board game Hex. And are exploring
the possibilities of expanding to include Soft/Fuzzy Constraints to
remove the need for backtracking or Quantified Constraints which
are particularly suited to modelling games.
A hex game.