Search Algorithms for Mastermind

Anthony D. Rhodes Portland State University Abstract -- This paper presents two novel approaches to solving the classic board game mastermind, including a variant of simulated annealing (SA) and a technique we term maximum expected reduction in consistency (MERC). In addition, we compare search results for these algorithms to two baseline search methods: a random, uninformed search and the method of minimizing maximum query partition sets as originally developed by both Donald Knuth [3] and Peter Norvig [4]. I. INTRODUCTION Mastermind is a popular code-breaking two player game originally invented in the 1970s. The gameplay closely resembles the antecedent pen and paper game called "Bulls and Cows", which dates back at least a century. Mastermind consists of three components: a decoding board which includes a dozen or so rows of holes for query pegs, in addition to smaller holes for key pegs; the board also contains a space for the placement of the master code provided by the code-maker.