Playing Clue: An Entropy-based Computer AI for the Classic Board Game

Abstract

This paper presents a Markov decision process based game-playing AI using an entropy reduction strategy for the game of Clue. The paper formulates Clue as a treasure hunt problem, which is relevant to mobile-sensor applications such as mine hunting, monitoring, and surveillance. In addition, the paper introduces a novel yet simple way of calculating the posterior probability of cards in the secret case le that was previously thought to be impossible, develops an entropy-reduction based strategy, and incorporates this with a MDP- based decision making agent. This paper also highlights an interesting relationship in which choosing the suggestion with the highest posterior probability of being in the case le also maximizes the expected reduction of entropy. The game results show that a computer player implementing the strategies developed in this paper outperforms commercial AIs.