~ Knuth's MASTERMIND algorithm in Python (board game)! ~
ThomasS1 (69)

Hey everyone,

Thought I'd share this implementation of Knuth's mastermind algorithm that I made in Python recently. This is about the classic mastermind board game, not the TV show!

What does it do?

You write down the secret code, and the computer will give you a series of guesses of the code. You have to respond with white and black pegs, which tells the computer how good its guess was (explained more in game). Depending on how many spaces and colours you chose to play with, it should guess the code correctly pretty quickly!

How does it work?

Wanna know how it works? Make sure you've played a game or two so you get the idea of it. The code can be found here, but bear in mind that most of that is for the user interface! Here's how the algorithm itself works:

  1. Generates a set of all of the possible answer codes. This of course depends how many colours and spaces you choose; for this explanation we'll go with 3 colours and 3 spaces. The entire set would be this:
    000 001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222
    We'll call it S

  2. Starts with an initial guess of 123. Ask Knuth why that's the best one to start with, not me!!

  3. Gets the response in white and black pegs from the user. The algorithm of course stops if the response comes back as 4 black pegs, success.

  4. Removes from S any code that would not, if it were the answer code, get the given response from the user. Woah. What did that mean?!
    The algorithm goes through every item in S. For each one it says, 'if that code were the answer, what response would I have got for the guess I made?' It calculates the response it would have got, and if it's not the same as the response it did get, then it removes that item from S, because we know it can't be the answer code.
    Still confused? Maybe this explanation on Stack Exchange will help (check out the top answer)

  5. Works out which of the remaining possible answer codes is the best option to use as the next guess. This is the most complicated stage. It doesn't actually eliminate any possibilities, it just works out which is the best one to guess next. It works out which one will, in a worst-case scenario, remove the most possibilities from S on the next turn. It's really hard to explain, so I'm not going to try to here, but if you're curious, there's a great explanation again on Stack Exchange (again, it's the top answer. I didn't write it)

  6. Repeat from stage 3!

To finish

Just to make it super clear, the idea of this program is not to play Mastermind against the computer (that would involve you playing a game as the codebreaker too). It's just to show Knuth's mastermind algorithm in action.

Hope you like the program! Find any errors or got any questions? Please comment below! Oh, and, feel free to leave an upvote...

Thanks!

You are viewing a single comment. View All
ThomasS1 (69)

Upvote this comment if you'd like to see a more detailed explanation / tutorial of the code for this!