Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

stackoverflow.com

Post reply on HN
Print view View original

21–30 of 33 posts

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

#21

Post by wegfawefgawefg »

ndsipa_pomu wrote: post #10
wegfawefgawefg wrote: post #7

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

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.

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.

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

#22

Post by CyberDildonics »

wegfawefgawefg wrote: post #21
ndsipa_pomu wrote: post #10

Earlier quoted context omitted.

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.

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.

Why are you assuming anything, just learn how the game works. This game can be solved on the command line with grep. There is no opponent. What are you talking about here?

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

#23

Post by CyberDildonics »

bschne wrote: post #2

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

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.

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

#24

Post by wegfawefgawefg »

CyberDildonics wrote: post #22
wegfawefgawefg wrote: post #21

Earlier quoted context omitted.

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.

Why are you assuming anything, just learn how the game works. This game can be solved on the command line with grep. There is no opponent. What are you talking about here?

About two months ago i learned how mastermind worked, put a good hour into reading about it and the solutions. played a few games too. Having spent a very long time implementing algorithms for chess and tictactoe a number of years ago I immediatly understood it. My friend also gave presentations on some solutions in rust, that I attended twice. I admit i am responding with old knowledge but I believe it is still correct. I dont find the game or its solution that interesting. However, the concept of hidden state games that have no possibility for state changing between turns did seem interesting to me. As somebody well versed in reinforcement learning, it surprised me that its a distinction I never came across previously. Usually algorithms for games like this are divided into non hidden state (minimax solveable if branching factor is small) and hidden state games (a whole other thing). In masterminds case the "opponents move"( a relevant framing if you know how minimax works) is just presented to you after your turn. The "opponent" always plays optimally in that the response is fixed. So its not really hidden state, despite the player not knowing the initial conditions. I knew that there were optimal tabular and minimax solutions to mastermind, but those techniques only work if the game is truly a no hidden state game. However, the person above posted that mastermind actually is a hidden state game because the player does not a-priori know the state of the hidden rule. It occured to me that must be irrelevant for some reason, and so I tried to deduce why.

I hope I have explained my motivation, and why I responded about the particular aspect of the game in the way that I did. My apologies for coming off retarded and shit.

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

#25

Post by [deleted] »

CyberDildonics wrote: post #22
wegfawefgawefg wrote: post #21

Earlier quoted context omitted.

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.

Why are you assuming anything, just learn how the game works. This game can be solved on the command line with grep. There is no opponent. What are you talking about here?

[deleted]

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

#26

Post by CyberDildonics »

wegfawefgawefg wrote: post #24
CyberDildonics wrote: post #22

Earlier quoted context omitted.

Why are you assuming anything, just learn how the game works. This game can be solved on the command line with grep. There is no opponent. What are you talking about here?

About two months ago i learned how mastermind worked, put a good hour into reading about it and the solutions. played a few games too. Having spent a very long time implementing algorithms for chess and tictactoe a number of years ago I immediatly understood it. My friend also gave presentations on some solutions in rust, that I attended twice. I admit i am responding with old knowledge but I believe it is still corr…

You don't need to be well versed in reinforcement learning "a-priori" knowledge or worry about opponents moves or "optimal tabular and minimax solutions" or branching factors or anything else.

Start with a text file of every combination separated by lines.

RRRRR RRRRG RRRGG

Then use cat to output it to grep and use grep for all the constraints.

One for colors that aren't there. One for colors you know are in the right place. Then after that one grep for every color you know is there somewhere and one for each color you know isn't in a certain spot.

cat combinations.txt | grep -v [colors that aren't there] | grep ..R.G | grep B | grep -v .Y...

That's it. All you need is a command line. Generate guesses from the filtered list then add to the filters.

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

#27

Post by wegfawefgawefg »

CyberDildonics wrote: post #26
wegfawefgawefg wrote: post #24

Earlier quoted context omitted.

About two months ago i learned how mastermind worked, put a good hour into reading about it and the solutions. played a few games too. Having spent a very long time implementing algorithms for chess and tictactoe a number of years ago I immediatly understood it. My friend also gave presentations on some solutions in rust, that I attended twice. I admit i am responding with old knowledge but I believe it is still corr…

You don't need to be well versed in reinforcement learning "a-priori" knowledge or worry about opponents moves or "optimal tabular and minimax solutions" or branching factors or anything else. Start with a text file of every combination separated by lines. RRRRR RRRRG RRRGG Then use cat to output it to grep and use grep for all the constraints. One for colors that aren't there. One for colors you know are in the righ…

What you are saying may be true, and helpful, but just isn't related. My initial comment was about an optimal play algorithm. So that's what I was discussing.

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

#28

Post by CyberDildonics »

wegfawefgawefg wrote: post #27
CyberDildonics wrote: post #26

Earlier quoted context omitted.

You don't need to be well versed in reinforcement learning "a-priori" knowledge or worry about opponents moves or "optimal tabular and minimax solutions" or branching factors or anything else. Start with a text file of every combination separated by lines. RRRRR RRRRG RRRGG Then use cat to output it to grep and use grep for all the constraints. One for colors that aren't there. One for colors you know are in the righ…

What you are saying may be true, and helpful, but just isn't related. My initial comment was about an optimal play algorithm. So that's what I was discussing.

That doesn't even make sense.

Are any solutions more likely than any others?

How are you getting an "optimal play algorithm" when the entire game is about using what you know to filter the solutions that are still possible?

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

#29

Post by wegfawefgawefg »

CyberDildonics wrote: post #28
wegfawefgawefg wrote: post #27

Earlier quoted context omitted.

What you are saying may be true, and helpful, but just isn't related. My initial comment was about an optimal play algorithm. So that's what I was discussing.

That doesn't even make sense. Are any solutions more likely than any others? How are you getting an "optimal play algorithm" when the entire game is about using what you know to filter the solutions that are still possible?

You're framing it like an information extraction game, but it is also frameable as a zero-sum minimax game. And its an easy, and common solution to games like this. Read up.

https://en.wikipedia.org/wiki/Mastermind_(board_game)#Algori... https://en.wikipedia.org/wiki/Minimax#In_zero-sum_games

One of the early solutions to mastermind was by Donald Knuth. paper: https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/k... an implementation: https://github.com/johnathanlouie/mastermind

further development: https://arxiv.org/abs/1908.06183

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

#30

Post by bschne »

CyberDildonics wrote: post #23
bschne wrote: post #2

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

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.

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.
Post reply on HN