Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01hx11xf36z
Title: Playing Clue: An Entropy-based Computer AI for the Classic Board Game
Authors: Xu, Jinhua
Advisors: Schapire, Robert
Department: Computer Science
Class Year: 2013
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.
Extent: 46 pages
URI: http://arks.princeton.edu/ark:/88435/dsp01hx11xf36z
Access Restrictions: Walk-in Access. This thesis can only be viewed on computer terminals at the Mudd Manuscript Library.
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Computer Science, 1987-2023

Files in This Item:
File SizeFormat 
Jinhua Xu.pdf1.8 MBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.