Title

Mixed Logical and Probabilistic Reasoning in the Game of Clue

Roles

Student Author

Ziqian Luo '18, Gettysburg College

Document Type

Article

Publication Date

3-25-2019

Department 1

Computer Science

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.

DOI

10.3233/ICG-180063

Required Publisher's Statement

This article is available on the publisher's website.

Link to Full Text

COinS