How to solve the "Mastermind" guessing game? (2009)

https://stackoverflow.com/questions/1185634/how-to-solve-the-mastermind-guessing-game

by jokoon • 3 years ago

55 30 3 years ago

bschne2• 3 years ago

ICYMI, 3blue1brown (Grant Sanderson) has a video applying information theory to solving Wordle, which is conceptually similar to mastermind -- https://www.youtube.com/watch?v=v68zYyaEmEA

jeffbee• 3 years ago

There was also "Word Mastermind" which is almost exactly Wordle.

CyberDildonics6• 3 years ago

You don't need "information theory", you can just make a text file with each option on its own line, then use grep on the command line for each constraint with pipes in between.

bschne2• 3 years ago

the point of 3b1b's video wasn't "how can I figure out what words are still an option", but "what is the optimal word to guess at each step to minimize overall attempts needed to solve". Picking a "good" word will give you more information about the actual solution than picking a bad word, so you will get there faster.

justinsaccount• 3 years ago

This game is part of the Simon Tatham's Puzzle collection as "Guess" (https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/gues...)

I've seen a lot of algorithms for how to play this, Donal Knuth has one that can win in 5 moves, but none that are really usable by humans. The method I use, which seems to always win is:

Guess 1111

Depending how many 1's were right, Guess 1222, 1122, 1112, 2222

Continue in this manor until the solution is found.

I just played this game ID: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/gues...

where it worked perfectly:

RRRR -> (1, 0) One red, somewhere.

RYYY -> (0, 1) No yellows, red is not first

GRGG -> (0, 2) One green in the 2nd position, red is 3 or 4.

BGRB -> (1, 1) No blues, red must be last.

OGOR -> (4, 0) Success.

Have been meaning to simulate this and see if there are any games where this method would not work. Sometimes it takes all the moves but I've never lost.

bentcorner• 3 years ago

On Android the free app "Simon Tatham's Puzzles" has an implementation of Mastermind and this is the same algorithm I use to solve it.

It's not foolproof (it can get tricky if you're unlucky finding the location of pegs) but it's a very easy algorithm to remember and implement.

ustad• 3 years ago

Also for apple devices.

smtross• 3 years ago

I created a solver using a SAT/SMT solver that guesses a solution that is consistent with all the previous guesses and their corresponding feedback. It always returns a solution in a small number of guesses. I don’t think it is the optimal solving algorithm but it was a fun exercise!

abecedarius• 3 years ago

Knuth's algorithm was in a short paper reprinted in one of his collections -- I forget which, but I think there was a "Fun and Games" one?

bananskalhalk• 3 years ago

It is in the book "Selected papers on fun and games". But it is also available as a separate article "The Computer as Master Mind”.

I was certain he wrote the article about MOO and/or bulls and cows, but it seems like I remember wrong.

wegfawefgawefg6• 3 years ago

its a no hidden state turn game. so minimax. but state space is small. so render a table of all correct moves.

ndsipa_pomu• 3 years ago

You must be thinking of a different game. With Mastermind, the chosen 4 colours are hidden and the other player tries to guess the colours and positions.

wegfawefgawefg6• 3 years ago

hmm. Minimax provides an optimal strategy for mastermind. But minimax doesnt work for hidden state games. Therefore, I can only assume mastermind doesnt really satisfy the hidden state property due to the fact that the opponent cannot changed the state between your turns.

AtlasBarfed2• 3 years ago

So they are doing a large problem space investigation with Python?

Are there libraries that will allow for full multicore utilization in Python from the numeric analysis stuff? Am I wrong that Python isn't a great language for a computational experiment like this?

lrasinen• 3 years ago

There's nothing large about that space. With 6 colors and 4 choices you get 1296 possibilities. Would have been peanuts even for the first 8-bit home computers.

bell-cot• 3 years ago

The "Super Master Mind" version goes up to 9 colors and 5 holes. It claims that expands things to 59,049 possibilities.

AtlasBarfed2• 3 years ago

That's kind of strange, I only was peripherally reading the discussion and saw they were doing random/entropic strategies, which IMO you do if the problem space is so large that you can't wrap around it using normal exploration techniques.

bryan0• 3 years ago

I think people are way overthinking this. Guessing at random from the solution space converges surprisingly quickly.

jnellis• 3 years ago

This was one of the computer games from 1976 BASIC computer games that some of us worked on ports of for the Coding Horror: Basic Computer Games repo. I recall there were a number of errors in the original and thus a few in the ports, python being one. I ended up writing about the deduction logic for solving mastermind because it seemed non-intuitive.

https://github.com/coding-horror/basic-computer-games/blob/m...

nestorD• 3 years ago

I remember writing a Mastermind solver in Ocaml, about a year after getting started with programming. The solution space is fairly small so I would start with a random guess then, of all solutions that are still legal, pick the one that would -- at worst -- reduce the solution space the most (essentially a one move ahead minimax).

How to solve the "Mastermind" guessing game? (2009)

Related Stories