Writing a program to play this game?

[Millennial]

Recently, I have came across an interesting game that can be played fairly easily between two people. Here is how it is played: Both you and your opponent pick a four digit integer with no digit repetition. Then, you perform specific "guesses" so as to determine what their number is. A guess is a four digit integer with no digit repetition as well. Your opponent compares your guess with his own number, and the result he gives you contains one -1 for each digit that both his number and your guess contains, but not in the same place; while it contains one +1 for each digit that both his number and your guess contains in the same place. As an example, assume your opponent's number is 1234 and your guess is 2135. 1,2 and 3 are in both the number and the guess, and among them, only 3 is contained in the same place in both numbers. Hence, the information your opponent gives you about this guess will be -2 +1 (3 digits common, the place of one digit is common as well). Note that you don't take the sum of these and you type it out as -2 +1, - and + is nothing more than notation. It could be A2B1, but I prefer using - and +.

After playing it for a while, the idea occurred to me to write a program that plays this game. I don't mean a program that picks a number and has you guess it, I mean a program that tries to guess what you picked. I have already written such a program, but there are problems with its speed such that I had to make some compromises to run it at acceptable speeds (maximum of 3-4 seconds per guess by the computer.) Given the game's apparent simplicity, I have been searching for ways to make the algorithm more efficient; but these ways have eluded me so far.

The algorithm I currently use performs an exhaustive search over the vector of currently possible numbers, using an evaluation function on each and choosing one out of random from the ones with the maximum score. The first guess is taken to be random automatically; because even though guessing a number with a 0 in it gives a higher score, a player that knows the first guess will have a 0 in it can exploit this by picking a number that lowers efficiency of the guess. After the program is given the results for the guess, it eliminates the numbers not satisfying that guess from the vector of currently possible numbers.

The main problem has been the evaluation function itself. It is the most natural evaluation function I could think of, and it is basically the average count of numbers this particular guess would eliminate. This is calculated by considering each individual possible results of the guess (there are 15) and calculating the value of (numbers eliminated by this result) * (numbers remaining after the result) / (current count of possible numbers), and summing them all. The count of numbers remaining after this particular result is equal to the numbers giving this result out of the currently possible numbers, and is necessary to weight the average accordingly. This particular evaluation function relies on the ability to find the number of numbers that will be remaining after a particular result, which is also a check over the current vector of possible numbers. If no sort of optimization or compromise is used here, the second move can take up to 3-4 minutes to make; as the computer has to perform over one billion runs of the function that checks if a particular number satisfies a particular result.

Can anyone think of a better algorithm or a better evaluation function than the ones I am using? A better algorithm is important for the more general case I am considering, where you pick x-digit numbers in base y and x < y with no digit repetition, and try to find the number using the same method as this game. While the program's playing strength currently is certainly a lot higher than mine, a generalization demands a better algorithm to avoid outrageous runtime.

Edit: I have described the algorithm verbally instead of posting the code, so anybody regardless of the programming languages they have knowledge of may state their opinions/suggestions.

 

[Mark44]

Let me see if I understand this. You pick a number, say 1234. Does the computer pick a number at random, say 2135, and ask you to enter a string that shows correct digits and correct places, which would be -2 + 1 in this case?

What does the computer do next? How does it have a list of currently possible numbers? Is it all of the four digit numbers with a 1 in any position, a 2 in any position, a 3 in any position, or a 5 in any position?

 

[mfb]

A minor detail first: there are just 14 possible results. -1+3 does not work: the 4th correct digit has to be at the right place as well.
Is 0 as first digit allowed? For simplicity I assume it is.

I don't understand why/where you want to perform billions of runs. Searching the whole game tree is certainly expensive, but you just have to do it (at most) once - you can store the result to automate at least the first 2, probably the first 3 or even all guesses. This reduces the complexity a lot.

It is certainly useful to randomize the first guess, but you can adjust the following guesses accordingly. This is probably clearer with an example:
Imagine your opponent would choose random numbers, so you don't have to randomize. Your first guess can be 0[/color]12[/color]3. Then you can have a lookup table "if the result is -2 +1, then continue with guess 0[/color]2[/color]56" (random example).
If you have to randomize, and your first guess becomes 7[/color]49[/color]8, then you can replace every "0" in your original table by "7", every "1" by "4" and so on. If the result is -2+1, your next guess would be something like 7[/color]9[/color]31 (where 3 and 1 are random again). You keep the structure, but not the numbers.

 

[Filip Larsen]

It seems to me the game you describe is the same as the board game "Master Mind", which just uses colored pegs instead of numbers, so if you are looking for how other people have "solved" the game you describe you may want to include "master mind" in your search as well.