- #1
Millennial
- 296
- 0
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.
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.