Guessing Game

(ToC)


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

English IDE <<--- Click this link and write your game program here.

When your game runs,Raise your hand in Zoom to continue.

If you didn't watch the video, or if you didn't pay much attention, and if you cannot figure out why your game does not run properly, you might reconsider: Watch the Video.

Or, 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

Let's do a game. If you and your friend wanted to play the Guessing Game, you might start off by announcing:
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. Except it says nothing about how you will decide what questions to ask. Besides, it's not yet in good "Five Concepts" form:

5 Concepts
 Sequence
 Iteration
 Conditional
 Input/Output
 Variables


The first line in the program description is a greeting, basically Output in our Five Concepts. With only a slight modification and we can use it as is:

Say "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.


The second line invites them to do some internal thinking, but not to tell us anything. So it's not Input, it's not anything that involves the computer. We could leave it as part of the greeting:

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


The third line is where all the hard work happens. Asking a question is Output, but a question supposes that they will answer it. That would be Input

Say "Hi. We are going to play the Guessing Game."
Say "You think of a number, ..."
{finish out the greeting by saying...}
{...the rest of what you told your friend}
Say {whatever the question is}
Input answer
then I will tell you what number you thought of.


The word "some" suggests that there is more than one, but not very many. That sounds like a Repeat (Iteration) to me:

Say "Hi. We are going to play the Guessing Game."
Say "You think of a number, ..."
{finish out the greeting by saying...}
{...the rest of what you told your friend}
Repeat {"some"}
  Say {whatever the question is}
  Input answer
  {do something with the answer}
  If {we know the answer} then Exit
  Next iteration
then I will tell you what number you thought of.


And finally ending with:

Say "Hi. We are going to play the Guessing Game."
Say "You think of a number, ..."
{finish out the greeting by saying...}
{...the rest of what you told your friend}
Repeat {"some"}
  Say {whatever the question is}
  Input answer
  {do something with the answer}
  If {we know the answer} then Exit
  Next iteration
Say "You thought of " {the guessed number}


OK, now lets talk about how you can guess their number in the fewest possible number of questions. Let's keep it simple by setting a limit on what number they will think of, say 1 to 99. And because you are a polite, friendly programmer, you want to tell you friend what range to think of a number in:

Say "You think of a number between 1 and 99,..."


The technique you will use is called "Binary Search" but I call it "Lion hunting." Imagine you have a forest with a lion lurking somewhere in the forest. How do you find the lion?

First you draw line (sounds like "lion") across the forest to cut it in half. The lion is either in the north half or the south half. Then you take that half and cut it in half again. Each time you have half as many places to look through, and pretty soon you have only one place to look, and that's where the lion is! Or in our case, it's the number they were thinking of.

It works for any range of numbers, so let's use a shorter range to experiment with, say 1 to 9, shown here in a single column:

9top
8
7
6
5middle
4
3
2
1bottom


I put arrows at the top and bottom of the forest -- that would be this column of all possible numbers. We need a third arrow halfway between those two arrows. That middle arrow is the Question I want to ask: Is your number less than the middle (in this case 5)? If it is (like maybe if we're looking for 3), then we slide the top arrow down to the middle, otherwise we slide the bottom arrow up. Then we compute a new middle and ask again:

9top
8
7middle
6
5bottom
4
3
2
1
We repeat this process until the arrows meet:
9
8
7top
6middle
5bottom
4
3
2
We are always asking if it's less, so the top number needs to be greater than the largest number they might guess (100 if we told them 99), otherwise we'll never guess it.

Now when you look at our arrows, you see they point at different numbers as the game progresses, that is, they vary. Does that sound like "variable"? We have three arrows, therefore three variables. I called mine top, bottom, and middle, but you can give yours any names you like. I suggest you use names that reflect what the numbers in them represent.

Let's look at the program description again, and see how we can improve it. I'm going to add the Reference section from the English IDE here, so we can spell our commands correctly:

English Programming Language Quick Reference

Input variable [sizetype] {I}   Repeat [count] {R} If condition [then] {C}
Print/Say/Displayvalues {O}   Next {R} Else/Otherwise {C}
Let name [= value] {V}   Exit/Again {R}
Round/Truncate variable {V}
Now, we need three variables as part of the startup (before we get into the repetition):
Say "Hi. We are going to play the Guessing Game."
Say "You think of a number between 1 and 99, ..."
{finish out the greeting by saying...}
{...the rest of what you told your friend}
Variable top = 10
Variable bottom = 1
Variable middle
Repeat {"some"}
  Say {whatever the question is}
  Input answer
  {do something with the answer}
  If {we know the answer} then Exit
  Next iteration
Say "You thought of " {the guessed number}


Then we have some vague generalities to nail down. The first is where I put

Say {whatever the question is}


What is the question you should ask? How about

Say "Is your number less than the middle?"


What's wrong with that? The person who thought of a number and is trying to answer your yes/no questions, they have no idea what you mean by "the middle" so they certainly can't give you a yes/no answer. Anyway, we have a variable named "middle" inside the program, and whatever value that variable arrow points to, we want to display that number, not the name. We do that by putting the name outside the quotation marks, like this

Say "Is your number less than " middle "?"


The next question is, How to calculate the middle. It is the middle between the current values of top and bottom. There are several ways to do the calculation:

1. Subtract bottom from both ends, cut the new top in half, then add bottom back on, which is the middle

2. Repeat, simultaneously subtracting 1 from the top and adding 1 to the bottom until they meet or cross, and that is the middle.

3. I think the easiest way is to add the top and bottom and divide by two.


Later, when you redo this program in Java, you can specify that you want a whole number (integer) result, but in the English computer, that's an extra step, using Round or Truncate. Both commands convert a fractional value to integer, but Truncate always goes down, so your results are more consistent.

Let middle = (top+bottom)/2
Round middle
Notice the parentheses. Normally computers mix addition and division the same way they taught you in school: do all the multiplication and division first, then do the addition and subtraction. But computations inside parentheses take precedence over that. We want it to add first, then divide. When in doubt, use parentheses. That's true in Java too.

Looking up at the Reference, I see that the Input command has an optional size parameter, so I can accept a single character ('Y' or 'N') which is easier for the user to type:

Say "Is your number less than " middle "? (Y/N)"
Input answer 1
If answer = 'Y' then Let top = middle
If answer = 'N' then Let bottom = middle


Another vague computation to turn into one of the Five Concepts, how do we know that we know the number? We know that top and bottom are always getting closer to each other, either top coming down, or else bottom moving up. Pretty soon top will be one more than bottom, so the midpoint (after rounding) is now equal, either to top or bottom (so nothing moves). When that happens, bottom is the number to be guessed (because it is always less than top). So

If bottom+1=top then Exit


Finally,the guessed number to be printed in the last line, it's the same number:

Say "Hi. We are going to play the Guessing Game."
Say "You think of a number between 1 and 99, ..."
{finish out the greeting by saying...}
{...the rest of what you told your friend}
Variable top = 10
Variable bottom = 1
Variable middle
Repeat {"some"}
  Let middle = (top+bottom)/2
  Round middle
  Say "Is your number less than " middle "?"
  Input answer 1
  If answer = 'Y' then Let top = middle
  If answer = 'N' then Let bottom = middle
  If bottom+1=top then Exit
  Next iteration
Say "You thought of the number " bottom


Hmmm, I wonder if this works. Select all 17 lines & Copy, then go to the English IDE and paste it into the program panel, then click on the Run button and see what happens.

OK, your turn. Erase my code and write you own version of the Guessing Game. Let us see your work!
 

[2021 August 27]