Mastermind Solver

Over spring break this year, I took a trip to Newburyport and Boston, both located in the Mssachutues. Boston mainly looked at graduate schools and had fun in the city, but Newburyport was my time to have a scenic few days to rest and enjoy the quiet life.

One evening, someone pulled out a game of mastermind after dinner, and the academic in me was immediately attracted to it. After reading the rule book, it was clear that mastermind was some kind of SAT problem/logic puzzle combined with minimax game theory packaged in an approachable and fun game. Essentially, this game is wordle with colored pegs instead of letters, and the feedback you get for your guess doesn't have any position information, only how many of your pegs are in the right spot and wrong spot.

After some digging, I found that Donald Knuth has already proposed a worst-case five-guess algorithm (for the original version of the game with 6 colors and 4 holes).

Below is my implementation of this approach but parametrized to handle any number of colors and holes.

import random
import itertools


random.seed(0)

def score_guess(guess, secret_code, verbose=False):
    red = 0
    white = 0
    for i in range(len(guess)):
        if guess[i] == secret_code[i]:
            red += 1
        else:
            if guess[i] in secret_code:
                white += 1
    return (red, white)

def play_mastermind(n=5, c=7):

    print("#" * 40)
    print("Welcome to Mastermind!")
    print("#" * 40)
    print()

    print("You are playing a game with {} colors and {} digits.".format(c, n))
    print()

    secret_code = []
    for i in range(n):
        secret_code.append(random.randint(0, c - 1))
    print("The secret code is:", secret_code)
    print()

    possible_secret_codes = list(itertools.product(range(c), repeat=n))

    guesses = 0

    guess = tuple([0 if (i < (n / 2)) else 1 for i in range(n)])

    while True:
        guesses += 1
        print("Try this guess: ", guess)
        input("Press enter to continue...")
        correct, close = score_guess(guess, secret_code)
        print("# of Red pegs:", correct)
        print("# of White pegs:", close)

        print()

        if correct == n:
            print("You win!")
            break
        
        possible_secret_codes = [x for x in possible_secret_codes if score_guess(guess, x) == (correct, close)]

        guess = random.choice(possible_secret_codes)

    print("It took", guesses, "guesses to win.")
    print()

    return guesses

if __name__ == "__main__":
    play_mastermind(n=5, c=7)

In my implementation, the computer plays itself, but this code can be modified to take the score pegs for each guess from the user rather than the computer. In addition, the code has been parameterized to allow the user to play with any number of colors and holes.

The interesting thing about this approach is that it has a worst-case guarantee rather than trying to perform as optimized as possible. This is because it does not try and intelligently pick its next guess. It only randomly selects its next guess from a pool of possible remaining guessing. There are ways to improve the selection by using concepts from game theory and information theory, like tree searches, but I didn't bother with that.