Mixed logical and probabilistic reasoning in the game of Clue

Article type: Research Article

Authors: Neller, Todd W.^{; *} | Luo, Ziqian

Affiliations: Department of Computer Science, Gettysburg College, PA, USA

Correspondence: [*] Corresponding author. E-mail: tneller@gettysburg.edu.

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

DOI: 10.3233/ICG-180063

Journal: ICGA Journal, vol. 40, no. 4, pp. 406-416, 2018