TY - CHAP
T1 - Realtime Online Solving of Quantified CSPs
AU - Stynes, David
AU - Brown, Kenneth N.
PY - 2009
Y1 - 2009
N2 - We define Realtime Online solving of Quantified Constraint Satisfaction Problems (QCSPs) as a model for realtime online CSP solving. We use a combination of propagation, lookahead and heuristics and show how all three improve performance. For adversarial opponents we show that we can achieve promising results through good lookahead and heuristics and that a version of alpha beta pruning performs strongly. For random opponents, we show that we can frequently achieve solutions even on problems which lack a winning strategy and that we can improve our success rate by using Existential Quantified Generalised Arc Consistency, a lower level of consistency than SQGAC, to maximise pruning without removing solutions. We also consider the power of the universal opponent and show that through good heuristic selection we can generate a significantly stronger player than a static heuristic provides.
AB - We define Realtime Online solving of Quantified Constraint Satisfaction Problems (QCSPs) as a model for realtime online CSP solving. We use a combination of propagation, lookahead and heuristics and show how all three improve performance. For adversarial opponents we show that we can achieve promising results through good lookahead and heuristics and that a version of alpha beta pruning performs strongly. For random opponents, we show that we can frequently achieve solutions even on problems which lack a winning strategy and that we can improve our success rate by using Existential Quantified Generalised Arc Consistency, a lower level of consistency than SQGAC, to maximise pruning without removing solutions. We also consider the power of the universal opponent and show that through good heuristic selection we can generate a significantly stronger player than a static heuristic provides.
UR - https://www.scopus.com/pages/publications/70350761423
U2 - 10.1007/978-3-642-04244-7_60
DO - 10.1007/978-3-642-04244-7_60
M3 - Chapter
AN - SCOPUS:70350761423
SN - 3642042430
SN - 9783642042430
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 771
EP - 786
BT - Principles and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings
T2 - 15th International Conference on Principles and Practice of Constraint Programming, CP 2009
Y2 - 20 September 2009 through 24 September 2009
ER -