What is the best strategy for guessing the number game?

[fisico30]

Hello Forum,
I just learned about the "guess the number" game. There are 100 numbers, from 1 to 100 and the computer must ask questions to find the correct number.

The computer could start from 1 and go up until it finds the right number. That would involve a certain number of questions.
Or the computer could ask more intelligent questions, like "is the number smaller or larger than 50", etc...


Most of the codes I have seen don't ask that "is the number smaller or larger than 50?" but simply ask some binary questions that are all similar (is this number smaller or larger than the previously guessed number? etc...)

Why?

thanks
fisico30

 

[uart]

Hi fisico30. This game usually uses a simple binary search, in which it always halves the interval in which it currently knows where the solution lies. So the "computer" would typically start with a guess of 50 and then simply require to be told if it was either correct or high or low.

If correct the game stops with a score of "one guess". If it was told 50 was high then it would next guess 25, if told 50 was low then it would next guess 75 and so on. Searching by continually halving the interval is easy to implement and fairly efficient.

BTW. This game is sometimes given as a exercise for students learning an introductory programming course. It's about the simplest example the you can think of that in some sense constitutes an "AI" game.

 

[fisico30]

Thanks uart,

great help. Ideally, the least number of guesses, questions, to get to the right answer, the better...

What would be a slightly more sophisticated version of this game? Instead of asking questions based on halving the interval in which it currently knows where the solution lies, would could be asked?

thanks
fisico30

 

[TylerH]

Increase the range, say to 0-1,000, and ask if *any* (not which) digit is correct.

 

[fisico30]

Thanks, I see.

So, if we get the number 3456, we would ask if any of the digits forming this number are correct...
that still seems far from being able to correctly guess the right number though...

thanks
fisico30

 

[TylerH]

You know it has to be 3xxx or x4xx or xx5x or xxx6.