[HN Gopher] How to solve the "Mastermind" guessing game? (2009)
___________________________________________________________________
How to solve the "Mastermind" guessing game? (2009)
Author : jokoon
Score : 47 points
Date : 2024-01-12 15:09 UTC (1 days ago)
(HTM) web link (stackoverflow.com)
(TXT) w3m dump (stackoverflow.com)
| bschne wrote:
| 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 wrote:
| There was also "Word Mastermind" which is almost exactly
| Wordle.
| justinsaccount wrote:
| 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 wrote:
| 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 wrote:
| Also for apple devices.
| smtross wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| "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.
| wegfawefgawefg wrote:
| its a no hidden state turn game. so minimax. but state space is
| small. so render a table of all correct moves.
| ndsipa_pomu wrote:
| 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.
| AtlasBarfed wrote:
| 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 wrote:
| 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 wrote:
| The "Super Master Mind" version goes up to 9 colors and 5
| holes. It claims that expands things to 59,049 possibilities.
| AtlasBarfed wrote:
| 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 wrote:
| I think people are way overthinking this. Guessing at random from
| the solution space converges surprisingly quickly.
| jnellis wrote:
| 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 wrote:
| 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).
___________________________________________________________________
(page generated 2024-01-13 23:01 UTC)