Re:How to solve the "Mastermind" guessing game? (2009)
by bentcorner on Saturday January 13, 2024 @10:20AM
(#38980707)
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.
Re:How to solve the "Mastermind" guessing game? (2009)
by ustad on Saturday January 13, 2024 @10:45AM
(#38980967)
Also for apple devices.
Re:How to solve the "Mastermind" guessing game? (2009)
by smtross on Saturday January 13, 2024 @11:08AM
(#38981206)
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!
Re:How to solve the "Mastermind" guessing game? (2009)
by abecedarius on Saturday January 13, 2024 @12:51PM
(#38982532)
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?
Re:How to solve the "Mastermind" guessing game? (2009)
by bananskalhalk on Saturday January 13, 2024 @01:07PM
(#38982708)
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.
Re:How to solve the "Mastermind" guessing game? (2009)
by Someone on Saturday January 13, 2024 @02:17PM
(#38983484)
“The Computer as Master Mind” PDF: https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/k...
It minimizes the worst-case, not the expected number of moves. I think Knuth’s algorithm can be beaten in that respect.
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.