Guessing Game

Video Introduction (00 minutes) <<--- Watch this video first, then

English IDE <<--- Click this link and write your game program in the program panel.

When your game runs, click the yellow Done button in the IDE to continue.

If you are like me and prefer to read at your own pace instead of whatever pace set in some video, You can read the transcript (and probably come out ahead of the non-readers).
 

Video Transcript: 5. Guessing Game

Hi. We are going to play the Guessing Game.
You think of a number,
then I will ask some yes/no questions,
then I will tell you what number you thought of.

That tells your friend how the game will be played, and as such it's a pretty good start at describing (with some pronoun switches) how the computer will play the game you just described. So let's do that Top-Down Design (TDD) thing (in the English IDE), because it's good practice:

"Guessing Game"
  Tell the person how it is played
  Ask some yes/no questions
  Tell what the number is

Converting the first line of the top level to code is easy (you just print out the four lines in our original description). The last line isn't much harder, presumably you have a variable that holds the guessed number, so you print that out with a descriptive label.

It's that middle line that is the bummer. Of course it says nothing about how you will decide what questions to ask, nor what you will do with the answers. Somehow asking the right questions is supposed to let the computer know (from a yes/no answer alone) something about the number the person is thinking of.

Steve thinks that TDD can take us to the solution, or at least kick the can down the road until we can solve it, but he already knows how to do it. It's called "begging the question" when you solve a problem by using the answer. The problem is that we don't even know what kind of question to ask. If we did, then the problem would be as easy as Steve makes it out to be.

Sometimes the real world programs we are trying to write are like this. If you don't even know whether the problem can be solved -- or worse, you don't know what you don't know -- then TDD is a waste of time. First, figure out in your mind how to solve the problem. Everybody does it that way. Even Steve knows you must do that. Otherwise your TDD structure might be all wrong.

But this is a very old problem, and nobody ever figured it out for themselves. I didn't think it up myself either. 20 million programmers didn't invent it, every one of us got it from somebody else, except some mathematician eighty or a hundred years ago figured it out. The rest of us all heard (or read) about it and copied the idea. Google Knows All -- IF you can think of what to ask for, the right search terms. I usually can't. So I will tell you: it's called "Binary Search" and Google will give you a zillion hits on how to do binary search. Now you know it can be done, we can get on with the program design...

Oh wait, if this is new to you, you still don't know what kind of question to ask. I call it "Lion* Hunting" because it's like hunting for a lion in the forest. You don't know where the lion is, so you divide the forest in half, and the lion is either in one half or the other. Now your problem is half as big. Now you know what kind of question to ask, "Is the lion north (or west) of the line I just drew?" There are some details to figure out, but we can aim our design to help us figure that part out. We are not writing any code yet, just thinking out loud (in English) about what needs to be done.

The forest is the range of all possible numbers the person might choose from. That could get astronomical, so to keep things reasonable, we can tell them what range to choose from, say "one to 99". They already know what their number is, so our question to divide the forest in half would be based on a range of numbers, initially all less than 100, and then half of that, and then half again, and so on. Now (and not sooner, as Steve supposes) we know that we can ask questions of the form "Is your number less than __?" We also now know how to decide what number to fill in the blank, it will be the middle of the previous range. We still need to figure out what code to do all that, but we can use TDD for that.

So let's work on the details for that middle line in our code design, now expanded to three dots (in green, because we do not need to look at the grayed-out rest of the program at this time):

"Guessing Game"
  Tell the person how it is played
  {Ask some yes/no questions}
    ...
  Tell what the number is

Remember, we are aiming to convert everything to good "Six Concepts" form:

Six Concepts
 Sequence -- Steps, one by one, in order
 Iteration -- A sequence that is repeated more than once
 Conditional -- A sequence that is skipped, depending on some test
 Variables -- Named values stored in memory, with commands to change the values
 Input/Output -- Bringing values in from outside the computer, or sending them out
 Subroutines -- A named sequence called up from somewhere else by a single command

Previously we did our TDD by breaking out each line to be explained into its own subroutine, but it is also possible (as we see today) to do the same analysis directly in-line (using a comment in place of the subroutine name). The important thing is to go through the process.

The first thing we might notice from this one-line description (the green line above) is the word "some" which suggests repetition, the second of our Six Concepts, let's put that in, along with a (blue) description of what needs to happen inside that repetition:

"Guessing Game"
  Tell the person how it is played
  {Ask some yes/no questions}
    Repeat
      {Decide what question to ask, or if done}
      Ask the question
      Input answer
      Next
  Tell what the number is

Already you see that two of those more detailed lines are already each one of the Six, so they have no braces. So let's work on what the question is. For starters, it needs to be a variable (another of the Six). So whatever gets decided, it needs to formulate a variable that is a question the computer can Ask (print out). We already know what the question is:

Let question = "Is your number less than __?"

Of course that blank to be filled in is really a variable -- we can give it a name now: I called it "lion" but you can name yours anything you like (like "middle" or "fribble" or whatever), if it helps you to understand what you are doing -- and it needs to be outside the quotation marks if we want the value of that variable to be printed instead of its name:

Let question = "Is your number less than " # lion # "?"

But we still need to figure out where to draw the lion (I mean line), that is, what value goes into the variable. The first time through the middle is obviously 50, but the next time, if they said yes (their number is less than 50) the middle of the range 1..49 is 25, but if they said no, then you want the middle of the range 50..99, which is 75. So we need to keep track of the range top and bottom, so to know what to take the middle of. Initially the top is 100 and the bottom is 1, but those values need to be set outside the loop. Oops, the first line "Tell the person how it is played" is incomplete, it should be part of a more general "Initialization" step (now blue here):

"Guessing Game"
  {Initialization}
    Let top = 100
    Let bottom = 1
    Tell the person how it is played
  {Ask some yes/no questions}
    Repeat
      {Decide what question to ask, or if done}
        {Decide if done}
        Let lion = {the middle between top and bottom}
        Let question = "Is your number less than " # lion # "?"
      Ask the question
      ...

So how do we know if we are done? Let's play the game in our mind, and to keep things simple, assume the range is one to nine. That's nine values, so we don't know which number was chosen.

We ask the question, "Is it less than 5?" and the answer is No, so now we know it must be one of the five numbers 5,6,7,8,9.

"Is it less than 7?" Yes, so it must be either five or six.

"Is it less than 6?" The next time we draw the line through the forest, there's only one number in the chosen side, so that must the number.

Notice we always ask if the number is "less than" the middle, so when the answer is Yes, the middle is excluded (recall at the beginning we chose 100 for the top, but we told the person 99, so top is always excluded. If you don't do that, then if the person chooses your specified top, your program can't guess it. After you get your program working, you can experiment to convince yourself that this is true. It's called a "boundary condition" and many computer bugs are due to invalid boundary conditions. You need to always test your programs with values on both sides of the edge of valid data.

Anyway, because top is always excluded, and bottom is always included in the range being considered, when these two numbers (variables) differ by exactly one, then (blue) bottom (the included value) is the correct guess:

"Guessing Game"
  ...
  Repeat
    {Decide what question to ask, or if done}
      {Decide if done}
        If bottom+1=top then Exit
      ...
    Next
  {Tell what the number is}
    Say "Your number is " # bottom
  Done

Did you figure out how to find the middle of your range? The most obvious way is to use a temporary variable to hold the number of elements in the range (the difference between top and bottom), then divide that in half, then add the bottom back on.

let tmp = top-bottom
let tmp = tmp/2
Let lion = tmp+bottom

Less obvious (but simpler and quicker) is to add the top and bottom and cut that in half. You should convince yourself (don't take my word for it, but you can use the test method in the Variables section) that this always works correctly:

Let lion = (top+bottom)/2

What happens if there are an odd number of numbers in the range? Then the middle will be a half of a number, which looks bad. You should round to the nearest integer (whole number). It turns out it doesn't really matter if you round up or down, any whole number near the middle works fine, so long as there is at least one number on each side (but you already checked that).

Round lion

You can figure out where to put this code.

I think there is a small part of the initialization that is incomplete, where you tell the person what is going on. You can do that without my help. You might also consider making the Yes/No input easier on the person, require only a single letter (Y or N, you did the same thing for the operator in the Calculator) and be sure to tell them as part of your question what you are expecting them to type.

If you put all that into the IDE and Run it, it will keep asking the same question over and over, and never get to the correct number. Do you know why that is? Where is it we are cutting the forest in half? I don't see any code to do that. I don't see anything that even looks at the person's answer. Can you figure out where that needs to go, and what to do about it? If you can't figure it out, get help. Ask another student, or else call for a Mentor.

Mentor Alert

Congratulations! Your program ran correctly. Click this link to advance to the next program: Rock-Paper-Scissors
 

[2021 December 15]

*Lion The name is a pun on the idea of hunting by drawing lines (sounds like "lions") across the data to divide it in half.