Mixed logical and probabilistic reasoning in the game of Clue

Abstract

We describe a means of mixed logical and probabilistic reasoning with knowledge in the popular game Clue. Using pseudo-Boolean constraints we call at-least constraints, we more efficiently represent cardinality constraints on Clue card deal knowledge, perform more general constraint satisfaction in order to determine places where cards provably are or are not, and then employ a WalkSAT-based solution sampling algorithm with a tabu search metaheuristic in order to estimate the probabilities of unknown card places. Finding a tradeoff between WalkSAT-heuristic efficiency in finding solution samples and the sampling bias such a heuristic introduces, we empirically study algorithmic variations in order to learn how such sampling error may be reduced.

Keywords

Clue Cluedo at-least constraints cardinality constraints extended clauses sampling logical reasoning probabilistic reasoning WalkSAT tabu search

Get full access to this article

View all access options for this article.

References

Dixon, H.E., Ginsberg, M.L. & Parke, A.J. (2004). Generalizing Boolean satisfiability I: Background and survey of existing work. Journal of Artificial Intelligence Research, 21, 193–243. https://www.aaai.org/Papers/JAIR/Vol21/JAIR-2107.pdf. doi:10.1613/jair.1353.

Glover, F. (1989). Tabu search – Part I. ORSA Journal on Computing, 1(3), 190–206. https://doi.org/10.1287/ijoc.1.3.190. doi:10.1287/ijoc.1.3.190.

Glover, F. (1990). Tabu search – Part II. ORSA Journal on Computing, 2(1), 4–32. https://doi.org/10.1287/ijoc.2.1.4. doi:10.1287/ijoc.2.1.4.

Gomes, C.P., Sabharwal, A. & Selman, B. (2009). Model counting. In

Biere ,

Heule ,

van Maaren and

Walsh (Eds.), Handbook of Satisfiability (pp. 633–654). IOS Press. Chap. 20, http://www.cs.cornell.edu/~sabhar/chapters/ModelCounting-SAT-Handbook-prelim.pdf. doi:10.3233/978-1-58603-929-5-633.

Knuth, D.E. (2000). Dancing links. In

Davies ,

Roscoe and

Woodcock (Eds.), Millenial Perspectives in Computer Science. Cornerstones of Computing (pp. 187–214). Macmillan Education UK. https://arxiv.org/abs/cs/0011047. ISBN 9780333922309.

Selman, B., Kautz, H.A. & Cohen, B. (1994). Noise strategies for improving local search. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94) (Vol. 1, pp. 337–343). Menlo Park, CA, USA: AAAI Press.

van Ditmarsch, H. & Kooi, B. (2015). One Hundred Prisoners and a Light Bulb (pp. 109–121). Springer. Chap. 11.

van Ditmarsch, H.P. (2000). Knowledge Games. PhD thesis, Groningen University, Groningen, Netherlands. ILLC Dissertation Series 2000-06.

van Ditmarsch, H.P. (2002). The description of game actions in Cluedo. In

L.A.

Petrosian and

V.V.

Mazalov (Eds.), Game Theory and Applications (Vol. 8, pp. 1–28). Nova Science Publishers.