The ‘Guess My Number’ Game

I have recently begun studying programming with Michael Dawson’s Python Programming for the Absolute Beginner. One of the practices in the book is programming ‘Guess My Number’ game, in which the player chooses an integer between 1 and 100 and the computer tries to guess that number (the game in which the role of player and computer is reversed is an easier one).  After the computer makes a guess, the player indicates whether the chosen number is higher or lower than the guess, and the computer makes a next guess until the guess is correct.

In the hindsight this was a fairly simple exercise, but it took me quite a while to figure out that I need to keep track of the lower and upper bounds in order to make a reasonable guess. So for example, if the program guesses 47 and the number is higher, then the program sets 47 as the lower bound, so its next guess will be greater than 47.

First I programmed so that the computer takes the average of the lower and upper bounds to make a guess (it drops all the decimals, so its initial guess, after taking the average of 101 and 0, is 50). For a randomly chosen number, this program will take an average of 5.8 trials and I think this is the lowest possible, but the verification will require another post.

The problem, however, is that the player will easily find out the pattern, so after playing a few games, he or she will choose the number that requires the most number of trials. For example, if the player chooses 100, then the program will always take 7 trials to make the correct guess. So once the player figure out the program’s algorithm, the program will make an average of 7 guesses before it hits the right number.

This is pretty obvious, but a formality of game theory might be helpful. The games played is sequential. There are two players, the computer and the human. The computer prefers lower average number of trials, while the human prefers the reverse. The computer’s set of strategies is algorithms of guessing; the human’s is choosing a number from 1 to 100. The game is sequential, in which the computer plays first and the human plays next (this implies that the human knows what strategy the computer chooses before he chooses the number).

So the question is: What is the best strategy for the computer? I thought that any strategy that does not involve randomness could be easily exploited by the human, so I made a second program that guesses a random value between the lower and upper bounds.

What would be the average number of trials for this second program? First I will need to determine whether the player will prefer to choose certain number over others. I am already stuck here, but my guess is that either all values have the same average number of trials or 50 has the highest one (since it has the greatest potential for fluctuations). If either were true, then we only need to calculate the average number of trials for guessing 50.

It didn’t sound too hard at first, but I was wrong. All I bothered to figure out was that the probability of guessing 50 in exactly 2 trials is 1.376% (Well, I also calculated that the chance of guessing 100 in exactly 2 trials is 5.177%, which seems to support that 50 indeed has the highest average number of trials). I was still curious enough to try 20 games and find the average number of trials to be 8.45. It seems choosing the random number does not seem to be a good strategy for the computer even for repeated games.

Is taking the median of lower and upper bounds the best strategy for the program? I still do not have a confident answer, but it seems so. One could add the complexity by allowing the computer to use a mixed strategy. For example, if for any given game there is a 80% chance that the program will use the median strategy and 20% chance the random strategy, it may change the payer’s best response to the program’s advantage.

The game can become even more complex by allowing the program to change its strategy for each game based on the player’s previous choices of the number. For example, if the player keeps choosing 100, then the program might make 100 as its initial guess the next game.

Finally, player could be allowed to lie for certain penalty. The player will then need to choose whether to lie or to be honest each turn, and the program will need some mechanism to determine the likelihood of the lying. This could in fact be an engaging strategy game, despite its seeming simplicity.