- 296

- 0

After playing it for a while, the idea occured 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.