4 ms·

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

This game is part of the Simon Tatham's Puzzle collection as "Guess" (https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/guess.html 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/guess.html#c6p4g10Bm:bb2547a6 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 3y 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.
- deleted 3y ago
  [deleted]
- ustad 3y ago
  Also for apple devices.
smtross 3y 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 3y 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 3y 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.
  - Someone 3y ago
    “The Computer as Master Mind” PDF: https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.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.

bentcorner 3y 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.

deleted 3y ago
[deleted]
ustad 3y ago
Also for apple devices.

smtross 3y 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 3y 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 3y 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.
- Someone 3y ago
  “The Computer as Master Mind” PDF: https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.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.