Trying to find an algorithm for the Number Mastermind game

  • Thread starter Arman777
  • Start date
  • #1
1,986
166
I am trying to write a code to guess the secret number. For example, if I have a secret number called 412.
My code will take the inputs as

120 - 0
312 - 2
439 - 1

where the numbers on the right gives the position of the correct digit at the correct location. I have thought some codes but it seems they would contain many many lines of codes. Can someone recommend me some algorithms
 

Answers and Replies

  • #3
1,986
166
The problem is I am given the number of guesses by another user. I mean I am not getting any values from a server or something. I am given the data let me give you an example. FOr instance I have given only data such as

402 0
390 0
816 2
848 2
777 0
815 1

By using only this data how can I find the secret number ?
 
  • #4
Baluncore
Science Advisor
8,964
3,548
By using only this data how can I find the secret number ?
If those are successive guesses with a score, all from one previous game, then how do you know that there is sufficient information to identify only one code, secret number?
Maybe your last guess will be different to the codebreaker's last guess.
 
  • #5
Halc
Gold Member
270
211
The game is supposed to give two scores for each guess.
In master-mind, it was black pegs for correct color in correct position, and white for correct color in wrong position. There were two algorithms for white pegs which differed if a color could appear more than once in the answer.

I wrote a small program to play the other side so I could do it solitaire instead of requiring a second person. With 4 pegs each filled with one of 6 random colors, I could work out the answer in typically under 5 guesses.
 
  • Like
Likes JamieSalaor
  • #6
34,880
6,621
I am trying to write a code to guess the secret number. For example, if I have a secret number called 412.
My code will take the inputs as

120 - 0
312 - 2
439 - 1

where the numbers on the right gives the position of the correct digit at the correct location.
If the secret number is 412, shouldn't the algorithm tell you if you get two digits correct, or even all three? Why is only digit 2 in the middle guess above identified? The third digit is also correct.
The game is supposed to give two scores for each guess.
In master-mind, it was black pegs for correct color in correct position, and white for correct color in wrong position. There were two algorithms for white pegs which differed if a color could appear more than once in the answer.
This post seems to be related to the questions I've asked above. I've never played Mastermind, so I don't know how the game is played.
 
  • #7
Halc
Gold Member
270
211
If the secret number is 412, shouldn't the algorithm tell you if you get two digits correct, or even all three? Why is only digit 2 in the middle guess above identified? The third digit is also correct.
2 means two of the digits are correct. It doesn't identify which ones.
 
  • Like
Likes JamieSalaor and hmmm27
  • #8
34,880
6,621
2 means two of the digits are correct. It doesn't identify which ones.
Which is different from what was stated in the OP.
where the numbers on the right gives the position of the correct digit at the correct location.
 
  • #9
Baluncore
Science Advisor
8,964
3,548
By using only this data how can I find the secret number ?
This is a protean game, with very many different implementations and rules.
The last rule is always; “Other rules may be specified.”

There is no possibility of writing code until every rule has been specified.
You may as well be playing “Mornington Crescent” or any of it's derivatives.
https://en.wikipedia.org/wiki/Mornington_Crescent_(game)
 
  • #10
pbuk
Science Advisor
Gold Member
2,146
888
Is this another coding challenge related question? It certainly isn't any standard version of the Mastermind game which is as others have described (and solutions for which are published as others have also linked).

The idea of a coding challenge is for you to work it out yourself. It is OK to ask for help with technical issues but asking for someone else to solve a problem so that you can submit the solution to a coding challenge is a waste of everyone's time.
 
  • #11
1,986
166
Is this another coding challenge related question? It certainly isn't any standard version of the Mastermind game which is as others have described (and solutions for which are published as others have also linked).

The idea of a coding challenge is for you to work it out yourself. It is OK to ask for help with technical issues but asking for someone else to solve a problem so that you can submit the solution to a coding challenge is a waste of everyone's time.
I am really not looking for a code. I am just trying to implement an algorithm. I have found one but it requires a great amount of coding and I was looking for a clever one.

Consider this as a new a game it looks like a mastermind yes, but it is different. Let me be muc more clear about the question. Suppose my friend Julia and I playing this game. She guessed a number which I dont know.

And she guessed "846". And my guesses are

402 0
390 0
816 2
848 2
777 0
815 1

For each guess Julia should answer how many digits are correct i.e. are the same in the proposed value and in his secret number - and are placed in the same position.

My algorithm should take the guess values and obtain the secret number.
 
  • #12
1,986
166
I think its a challenging question and we can find some clever algorithm to solve the problem with minimum effort.
 
  • #13
pbuk
Science Advisor
Gold Member
2,146
888
This
I am really not looking for a code. I am just trying to implement an algorithm. I have found one but it requires a great amount of coding and I was looking for a clever one.
No, the idea is not to implement someone else's algorithm, the idea is to come up with the algorithm yourself. This belongs in homework really so if the following hint isn't enough to get to one solution I suggest you repost there.
Solving a problem by 'brute force' means trying every possible solution and seeing if it works. Often there are too many possible solutions to make this work in a reasonable amount of time so we have to try something else. How many possible solutions are there here?
 
Last edited:
  • #14
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,809
10,468
What is it you want?

You asked for an algorithm for Mastermind.
You got one.
Then you said, "No, no, this isn't Mastermind. It is some other game like Mastermind."

You have to give us the rules. It is not sufficient to give us one example of a played game and hope we can infer the rules. You are asking us to guess the correct question and then provide the answer.
 
  • #15
1,986
166
This

No, the idea is not to implement someone else's algorithm, the idea is to come up with the algorithm yourself. This belongs in homework really so if the following hint isn't enough to get to one solution I suggest you repost there.
Solving a problem by 'brute force' means trying every possible solution and seeing if it works. Often there are too many possible solutions to make this work in a reasonable amount of time so we have to try something else. How many possible solutions are there here?
I know that its just I am trying to create a discussion type subject. You dont have to give me the answer. I can start by telling my idea

So for the 3 digit number we can seperate the digits. Let me consider the previous example

1 - Create an array that contains all the 3 digit numbers (100, 999) (Let us call this array pos_num)
2- Take a guess number (let us take 402)
3 - If the returned value is "0",
3 - Seperate its digits _4_, _0_, _2_
4 - Remove all numbers that contains _4_ in the first digit, similarly remove all the numbers that contains _0_ in the second digit and remove all the numbers that contain _2_ at the third digit.

It goes like this. Its similar if the returned value is 1 and for the 2 but it seems a bit messy to create a code. This is not a homework ..
 
  • #16
Halc
Gold Member
270
211
I can start by telling my idea

So for the 3 digit number we can seperate the digits. Let me consider the previous example

1 - Create an array that contains all the 3 digit numbers (100, 999)
First of all, zero is not legal as a first digit? That's one 'color' that is not legal in certain positions, which kind of goes against the general master-mind vibe. The general form of the game is X many positions, and Y many colors/characters that each position can be. There's no rule about it having to look like a number at all, let alone a normalized one. The program I use uses letters, so up to 26 'colors'.
Your OP is very vague about this. Nowhere does it say that the number of digits of your normalized number is known, so the correct answer may well be 332780195.
Secondly, this brute method works for this trivial example of a thousand possibilities, but not so good if there's say 20 positions and 17 colors to choose from. Your computer doesn't have enough time or memory for an array that large.

How does a human do it? I don't find myself iterating though all 1000 numbers and rejecting them one by one. I can glance at just those middle two clues and narrow it down to just two possibilities. What is a non-brute method that might do that?

Finally, suppose there is more than one answer that satisfies all the clues. How does the algorithm pick one? Just say "unsolvable with current information"? Or is it playing the game and needs to choose something? If the latter, what makes for a good choice vs. a poor one? Does it only pick from the list of possible solutions or is it trying to minimize the number of guesses needed?
 
Last edited:
  • Like
Likes JamieSalaor
  • #17
Baluncore
Science Advisor
8,964
3,548
Let the first poor guess be 402 – 0. Then a second very lucky guess is 846, which happens to be the correct answer.

If I gave you 402 – 0, you could not possibly derive the correct answer from that one bad guess.

It demonstrates that there may be no rational solution to many examples.
 
  • #18
639
451
Is this the game?

You guess a number. If it's wrong you get back the number of correct digits. The goal is to find the answer using the fewest guesses?

If so, you probably want to track not just what you've ruled out, but also the probabilities.
 
  • #19
pbuk
Science Advisor
Gold Member
2,146
888
1 - Create an array that contains all the 3 digit numbers (100, 999) (Let us call this array pos_num)
Like @Halc I am surprised that you are excluding the possibility of 0 as a first digit.

2- Take a guess number (let us take 402)
3 - If the returned value is "0",
3 - Seperate its digits _4_, _0_, _2_
4 - Remove all numbers that contains _4_ in the first digit, similarly remove all the numbers that contains _0_ in the second digit and remove all the numbers that contain _2_ at the third digit.
So doing it that way you take the set of possible solutions and eliminate from it elements that cannot be solutions - that should work, at the end you should have left only candidates that fit each of the marking responses (of which there may be none, one or more than one).

I can think of an easier way to find candidates that fit each of the marking responses though, can you?

This is not a homework ..
No but it fits the criteria for the homework section, I'll get it moved.

Secondly, this brute method works for this trivial example of a thousand possibilities, but not so good if there's say 20 positions and 17 colors to choose from. Your computer doesn't have enough time or memory for an array that large.
Yes but we don't have 20 positions and 17 colours: premature generalisation is an even bigger sin than premature optimisation IMHO.

If I gave you 402 – 0, you could not possibly derive the correct answer from that one bad guess.
Why do you see this as a problem? A suitable algorithm should be able to identify and report all possible solutions, even if there are more than one (or none).

It demonstrates that there may be no rational solution to many examples.
What does an irrational solution look like :wink:
 
  • #20
pbuk
Science Advisor
Gold Member
2,146
888
Oh, you might find the following piece of code useful:
Python:
def getDigit(n, index):
  return (n // (10 ** index)) % 10
 
  • Like
Likes Arman777 and sysprog
  • #21
1,961
1,195
I was ready to give the post #19 reply of @pbuk a 'like', but the
What does an irrational solution look like :wink:
at the end made me change the 'like' to a 'haha', and now he gets a 'like' for post #20 ##\dots##
 
  • #22
Halc
Gold Member
270
211
If so, you probably want to track not just what you've ruled out, but also the probabilities.
There are probabilities? I mean, each clue eliminates a bunch of otherwise viable answers. The remaining ones are equally probable assuming it was randomly chosen in the first place.
That said, some next-guesses are far superior to other ones, and a good algorithm would choose one of those despite the fact that all remaining possibilities are equally probable. Sometimes the best next guess is one that is known to have been eliminated, and thus has zero probability of being correct.

Yes but we don't have 20 positions and 17 colours: premature generalisation is an even bigger sin than premature optimisation IMHO.
I could just write a program that does effectively: print ("846") then. It seems to be a generalization to write one that prints the answer for a different data set. Just saying, where do you draw the line?
I always think in terms of scalability, but nevertheless agree that a good scalable solution may not be optimal if the working dataset is known to be confined to small cases.
 
  • Like
Likes JamieSalaor
  • #23
639
451
There are probabilities? I mean, each clue eliminates a bunch of otherwise viable answers. The remaining ones are equally probable assuming it was randomly chosen in the first place.
That said, some next-guesses are far superior to other ones, and a good algorithm would choose one of those despite the fact that all remaining possibilities are equally probable. Sometimes the best next guess is one that is known to have been eliminated, and thus has zero probability of being correct.


I could just write a program that does effectively: print ("846") then. It seems to be a generalization to write one that prints the answer for a different data set. Just saying, where do you draw the line?
I always think in terms of scalability, but nevertheless agree that a good scalable solution may not be optimal if the working dataset is known to be confined to small cases.
The probability would be based on your knowledge (in a Bayesian sense).

There would be probabilities for each digit separately. For example, if your first guess is 123 and it gives back 2. Then it means that 1 out of 3 digits were incorrect. So there is a 2/3 chance for each digit that it is the one you guessed and 1/3 probability it is something else.

At each guess there would be one or more maximum likely guesses. You keep updating your probabilities after each guess.

A greedy algorithm would always choose one of the most probable new guesses. I'm not saying that the greedy algorithm is necessarily optimal though. That was just my initial thought.
 
Last edited:
  • #24
1,986
166
I can think of an easier way to find candidates that fit each of the marking responses though, can you?
Maybe a hint ?
 
  • #25
pbuk
Science Advisor
Gold Member
2,146
888
I could just write a program that does effectively: print ("846") then. It seems to be a generalization to write one that prints the answer for a different data set.
No, it is a requirement that the program works out the solution for any set of marked guesses, not just the example.

Just saying, where do you draw the line?
At the requirements. It is a requirement to solve for any 3-digit problem.
 

Related Threads on Trying to find an algorithm for the Number Mastermind game

Replies
13
Views
2K
Replies
0
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
2
Views
581
Replies
12
Views
1K
Replies
1
Views
3K
  • Last Post
Replies
12
Views
1K
Top