[home]     [professional]     [personal]     [resume] Project: "Mastermind by importance sampling and Metropolis-Hastings" Technical papers and online demonstration:     [Online Demonstration]     [ISI 2005 Conference Paper]     [Masters Thesis] Abstract: Two machine learning algorithms are introduced for playing a one player version of the logical game Mastermind. The first strategy presented makes guesses according to an exponential distribution on a simple set of features. The model parameters were trained by performing a gradient descent algorithm on an importance sampling estimate of the mean number of turns required to win the game. The second strategy is based on the Metropolis-Hastings algorithm, and uses a simple cost function to evaluate each code proposed. This strategy requires more turns on average to complete the game, but provides a significant reduction in the number of codes that must be evaluated at each turn. This reduction in computation makes it possible to complete the game quickly for large scale versions of the game with more pegs and more colors. Lastly, the performance of the Metropolis-Hastings based strategy is examined on a modified version of the game where false information is given with some positive probability, and the performance is compared to that of human subjects.