0
$\begingroup$

There is a number guessing game played by two players. The rules and procedures are the following:

Let's say that we are playing the game with 4 digits. This is not fixed and not a strict rule of the game, of course. In the beginning, both sides choose a number which has 4 digits and digits are different from each other(i.e. from 1000 to 9999 with different digits)

For the sake of understanding, let's say player 1 has chosen 3572 and player 2 has chosen 8741. First player tries to guess second player's number. Let's say he said 6578. Second player must say "-2" in response. This is how he said that:

8741

6578

The number guessed by player 1 has guessed correctly two digits of the original number. But could not correctly guessed the positions of them. So it must be "-2".

Player 2 responds and asks in return: "3456". This is what player 1 must say:

3572

3456

He guessed two digits correct and guessed one digit in correct position but other one not in the correct position. So he must say "+1-1" in response. This will go on like this until one side eventually find the other player's number. Let's give another step just to clarify:

Having said "+1-1", player then asks the number: 7325

Why did he said that? Maybe he thought he guessed correctly the digits 7 and 5 in the previous turn and changed their positions.

8741

7325

Player has to reply with "-1" as only once digit is present in both numbers and its position is not correct.

In conclusion, numbers guessed whose digits are present in the original number and positions are the same must be replied as prefix "+", and whose digits are present but not in correct positions must be replied with prefix "-". If none of them is the case one must reply "0". When the reply is "+4" (i.e. number guessed correct) the game ends.

Question is, what is the logic behind this game? What is the mathematics? What should be the algorithm for guessing the correct number with minimum number of turns? What is the quickest possible approach? How should one choose the numbers that he is going to ask?

Note: Players cannot lie.

EDIT: I had to make this editing as I found another source. Contrary to the answers given, this game is not exactly called "Mastermind". However, it is a similar board game. According to the result of my searchings, this game is exactly called "Bulls and Cows". Here is the related Wikipedia article.

$\endgroup$
2
  • $\begingroup$ This is a rather old (board, too) game, known in some places as "Master Mind". Google it. $\endgroup$
    – DonAntonio
    May 5 '16 at 22:14
  • $\begingroup$ I had not known the name of this game. I will do a search. This helped me a lot. Thanks. $\endgroup$
    – D. Jones
    May 5 '16 at 22:18
2
$\begingroup$

This game, commonly known as Mastermind, has been studied using computer programs, at least for small sizes. There are 2 distinct possible optimization problems interesting here, one being to minimize the number of moves needed in the worst case, and the other being to minimize the average number of moves. Interestingly, these two problems have different optimal solutions! Details can be found on the linked Wikipedia article.

$\endgroup$
2
  • $\begingroup$ There is also a game-theoretic optimization problem here: since players take turns, it is possible to judge how close your opponent is to guessing your number. If you have reason to believe your opponent can guess the number in $k$ more moves, you would want to optimize for highest probability that you can guess his/her number in $<k$ moves. This may not be equal to the best average-case or best worst-case strategy, as you need not lend any weight to cases that will require more than $k$ guesses. $\endgroup$
    – Erick Wong
    Jun 1 '16 at 8:48
  • $\begingroup$ @ErickWong: Ah yes that would apply when you are playing two mastermind games simultaneously. I was only referring to the asymmetric one where one player is the setter and the other is the guesser. But even in that case, if the setter is not required to write down the set combination, he can purposely change it during the game to force the guesser into the worst case, and if so then the guesser should optimize for the worst case and not the average case. $\endgroup$
    – user21820
    Jun 1 '16 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.