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.
Best Answer
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.