Find Optimal Strategy to Win 1-100 Hot and Cold Guessing Game

[Nimz]

I wrote a program for my calculator where the goal is for the user to determine the "randomly" selected number within a certain number of guesses. For the time being, I don't care that the number generator is only pseudorandom. The selected number, x, is always $1 \leq x \leq 100$, and the clues given are whether the number the user selects is closer, farther away, or the same distance from the selected number, compared to the previous guess. Basically, it's a hot and cold game.

A sample of what the inputs and outputs might look like is as follows:
? 40
- Nope
? 60
- Hot
? 80
- Cold
? 51
- Hot
? 59
- Lukewarm
? 55
- Congratulations! You won!

I have found a strategy that guarantees a win in no more than 10 guesses when on the 1-100 interval. Based on a limited number of small trials, I'm guessing that up to 2ⁿ+1, the optimum strategy will guarantee a win in no more than n+1 guesses. For the 1-100 interval, that means my guess is that no more than 8 guesses are needed for the optimum strategy. Can anyone here help me to verify that, and if possible, provide such a strategy?

 

[Nimz]

I already have a few ideas how to approach the problem. It's pretty clear for 1, 2, 3, 4, 5 that three guesses are needed. E.g. 1, then 5, when the output will determine whether the answer is 2, 3, or 4. Taking that as the base case, I'm thinking an induction argument that takes you from k to 2k-1 by adding one guess could be a way to start. I haven't checked yet whether this is a reasonable start.

 

[Nimz]

It's fairly easy to see that 8 is the lower bound on the maximum number of guesses required for the optimum strategy when going between 1 and 100. After every number input, there three possible outputs. For one of the outputs (lukewarm), there will be no more branching, so the optimum strategy will take at least n steps to reach every choice in an interval containing 2^n-1+2^n-2 choices. n=7 gives 96.

I have found a strategy that takes nine steps to reach every integer between 1 and 100, with only eight integers requiring nine steps. Several of the branches terminate prematurely (e.g. the fifth step), which gives me hope that a strategy with eight steps exists.

I'm not sure what notation to use to compactly (and legibly) show the nine-level tree I have here, representing the strategy I came up with, so I will edit this post in a bit to add a picture of the tree.

- edit -

Here's the picture of my tree attached (finally)

 

[0rthodontist]

But this is simply a binary search. The first number you pick does not matter so long as it is off-center, i.e. 40. The second number you pick should be 60. This is chosen so that if the answer is "cold" then you know that the number lies in the range 1..49, and if the answer is "hot" then you know that the number lies in the range 51..100. In general, if the last guess was x, and the new guess is y, then a verdict of "hot" implies the number n satisfies
"n lies in the interval [1, (x + y)/2) or ((x + y)/2, 100], whichever contains y"
and a verdict of "cold" implies that n lies in the other interval from the verdict of "hot."
Now given an x, you can make these two intervals whatever you like through choice of y. You can, for example, make them so that they always split the current known possible range in half, which is just a binary search, with 1 step to initialize and then 1 step per division thereafter.

Guesser(a, b) //a, b denote the closed endpoints of the interval of integers to guess in
let y = floor(a + (b - a) / 3) // arbitrary, so long as it's offcenter
if AskTeller(y) = win then return y
while(true)
   x <-- y
   y <-- a + b - x
   if y - x is odd then y <-- y + 1 //to take advantage of "lukewarm"
   q <-- AskTeller(y)
   if q = win then return y
   else if q = lukewarm then return (x + y)/2
   else if q = hot then
      a <-- (x + y)/2 + 1
   else if q = cold then
      b <-- (x + y)/2 - 1


AskTeller(y)
If the guess y is equal to the correct number n, return win.  Else if y is closer to n than the last guess, return hot.  If y is farther away, return cold.  If y is the same distance from n as the previous guess, return lukewarm.

 

[0rthodontist]

Ahh, never mind, my algorithm as listed is incorrect and a fixed version has a max depth of 10. Maybe there is a way to fix it but not right now.

 

[Nimz]

I forgot to add one note - in the tree, hot is to the left, cold is to the right, and lukewarm is straight down. It'd be a bit harder to interpret without knowing the key :P

 

[Nimz]

A maximally expanded tree of 5 levels will have 11 nodes. As far as I can tell, there are exactly two strategies that will fill that tree with the integers 1-11. I've developed an iterative notation (possibly similar to notations developed by others previously - I'm not familiar with what's been done). The base tree is S(H,L,C), where S is the starting number, H is the number chosen if the response was Hot, L for Lukewarm, and C for Cold. To make a tree with three levels out of this, replace H and C with S(H,L,C), and so on for more levels.

e.g. 2(X, 4(5, 3, 1), X) is one of the four ways to fill a three level tree with 1-5.

The two strategies for 1-11 (4 levels) are:
3(X, 7(11(10, 9, 8), 5, 1(2, 4, 6)), X) and
9(X, 5(1(2, 3, 4), 7, 11(10, 8, 6)), X)

I can't seem to get any that start with an even number to work. It seems to be necessary for an n-1 level tree to have a way to start with an even number in order for an n level tree to be possible. So I don't think it's possible to fill a 5 level tree with 1-23 that could represent a valid strategy.

 

[0rthodontist]

I have absolutely no idea what you are talking about. "A maximally expanded tree of 5 levels will have 11 nodes."?? What does that mean?

Anyway I found the bug in my code from earlier. The "bug" was that the modulo operator in Java, %, thinks that -5 % 2 == -1.

import java.math.*;
import java.util.*;

class Guesser
{
	public static int WIN = 0;
	public static int HOT = 1;
	public static int COLD = 2;
	public static int LUKEWARM = 3;
	public int prev;
	public int n;
	public int depth;
	public static int maxn = 100;
	public int Guesses(int a, int b, int y)
	{
		depth = 0;
		// q = response from teller
		// x = the last guess
		// y = the current guess
		// a = the mimimum possible value of n
		// b = the maximum possible value of n
		int q;
		int x;
		//int y = 1;//(int)Math.floor((a + (b - a))/3);
		System.out.print(a + "-" + b + ":" + y + ";");
		if (AskTeller(y) == WIN)
			return y;
		depth++;
		while(true)
		{
			x = y;
			y = a + b - x;
			if ((y - x) % 2 != 0 && y < x) y = y - 1;
			else if ((y - x) % 2 != 0 && y > x) y = y + 1;
			System.out.print(a + "-" + b + ":" + y + "," + x + "; ");
			q = AskTeller(y);
			depth++;
			if (q == WIN)
				return y;
			else if (q == LUKEWARM)
				return (x + y) / 2;
			else if (q == HOT && y > x)
				a = (x + y)/2 +1;
			else if (q == HOT && y < x)
				b = (x + y)/2 -1;
			else if (q == COLD && y < x)
				a = (x + y)/2 +1;
			else if (q == COLD && y > x)
				b = (x + y)/2 -1;
		}
	}
	
	public int AskTeller(int y)
	{
		if (y == n){
			prev = y;
			return WIN;}
		else if (Math.abs(y - n) == Math.abs(prev - n))
			{prev = y;
			return LUKEWARM;}
		else if (Math.abs(y - n) > Math.abs(prev - n))
			{prev = y;
			return COLD;}
		else if (Math.abs(y - n) < Math.abs(prev - n))
			{prev = y;
			return HOT;}
		return 20;
	}
	
	public void doIt()
	{
		int maxdepth = 0;
		//for(int j = 1; j <= maxn; j++){
		for(int i = 1; i <= maxn; i++)
		{
		//int i = 3;
			n = i;
			Guesses(1, maxn, 1);
			System.out.println("\n" + i);
			if (depth > maxdepth)
				maxdepth = depth;
		}
		System.out.println("Final depth: " + maxdepth + "  " + 1);
		//}
	}
	
	public static void main(String[] args)
	{
		Guesser g = new Guesser();
		g.doIt();
	}
}

This now reports a final depth of 8. That is the number of guesses required to determine what the answer is. It would actually be 1 more if, once you know the answer, you have to ask Teller whether or not it's right. So this may be a final depth of 9 in your way of doing things.

To get it to run on ranges other than 1 to 100, change maxn (at the top of the program) to the constant you want, and it will run on the range 1 to maxn.

 

[Nimz]

Sorry if I wasn't very clear on what I meant by a "maximally expanded tree of n levels." I was pressed for time when I wrote that, and wanted to put something up here before I had a chance to forget what I was doing. This being the case, it's very possible I made a typo or a slip in mental calculation when I said that a maximally expanded tree of 5 levels has 11 nodes. It should either be 4 levels or 23 nodes :P

A maximally expanded tree of n levels is a tree where the maximum distance from the root to the leaves is n-1 nodes (or vertices, if you prefer). Furthermore, the only leaves that are closer than n-1 nodes from the root are the ones corresponding to "lukewarm." That is, every hot branch and every cold branch has three branches under it unless that takes you to the n+1^th level.

Thus a maximally expanded tree of 5 levels will have one vertex in the first level (first guess), one vertex in the second level (second guess), three vertices in the third level (one for hot, one for cold, and one for lukewarm), six vertices in the fourth level (corresponding to the sequences HH, HL, HC, CH, CL, and CC), and twelve vertices in the fifth level (HHH, HHL, HHC, HCH, HCL, HCC, CHH, CHL, CHC, CCH, CCL, CCC). 23 vertices altogether.

I appreciate all the time you've put into this. I'm not sure I follow how your code works, though. I have vague familiarity with C++, but I'm a helluva lot more comfortable with the TI-85 version of BASIC. For example, this is the code for the program I wrote, with some of the formatting issues for the TI-85 screen glossed over:

PROGRAM:HOTCOLD
:round(rand*100+.5,0)->ANSWER
:Disp "Pick a number between 1 and 100.  You have 10 guesses!"
:0->TRIES

:Lbl PICK // warning - spaghetti code
:If TRIES>0
:x->y
:If TRIES>9
:Goto LOSE
:Input x
:If (i^4*x =/= i^4*abs (x))
:Goto PICK // complex number guesses break the program otherwise
:If x==ANSWER
:Goto WIN

:If x>100
:Then
:If TRIES>0
:y->x
:Goto PICK
:End

:If x<1
:Then
:If TRIES>0
:y->x
:Goto PICK
:End

:If (round(x,0) =/= x)
:Then
:If TRIES>0
:y->x
:Goto PICK
:End

:If TRIES==0
:Goto FIRST // y hasn't been defined yet

:If x==y
:Then
:Disp "Try a different #"
:Goto PICK
:End

// preliminary stuff to prevent the user from being stupid, etc.

:TRIES+1->TRIES
:If abs (x-ANSWER)<abs (y-ANSWER)
:Disp "HOT"
:If abs (y-ANSWER)<abs (x-ANSWER)
:Disp "COLD"
:If x+y==2*ANSWER
:Disp "LUKEWARM"
:Goto PICK

:Lbl FIRST
:TRIES+1->TRIES
:Disp "Nope."
:Goto PICK

:Lbl LOSE
:Disp "You took too long.  The answer was:  " + ANSWER
:Goto E

:Lbl WIN
:Disp "Congratulations!  You won, and with " + 9-TRIES + "guesses to spare!"

:Lbl E

I glossed over a couple of things that made the user interface a bit nicer (e.g. :If TRIES==9 :Disp "Congratulations! You won with your last guess!"), but that's the essense of the program. I also didn't directly use $\neq$, though it would've been a bit simpler if I had.

I would not be surprised to see a depth 8 strategy (by my definition) is possible for maxn=100. As I already noted, I drew a tree that diagrams a depth 9 strategy. Ideally, I'd like to find out what the critical values maxn are where the optimum depth is one more than for maxn-1.

 

[0rthodontist]

Well, in the program I wrote it only performs a binary search as I explained in post 4 (though post 4's algorithm is wrong). My program does not take much advantage of the fact that if you guess, you can get a "win" as well as a lukewarm, hot, or cold. So to search 1 ... 2^n it should take n+1 guesses (since one additional guess is required to initialize), and to search 1 ... 2^(n) + 1 it should take n+2 guesses. (Edit: though in practice the cutoff for maxn is one less, actually 1 .. 2^n - 1, i.e. it takes 7 guesses for 1..63 but 8 for 1..64, and 8 guesses for 1..127 but 9 for 1..128. I am not sure why)

The program really has depth 9 on maxn = 100. It says 8--that's the number of times it has to actually ask the teller before it knows--but the way you counted the levels of your tree, that translates to 9. My program terminates with a "win" as soon as it gets a "lukewarm," without bothering to "guess" the final value (which it already knows).

Also, most of the guesses my program makes are not actually in the range 1...maxn. They will usually be greater or smaller. Maybe that's cheating.

 

[0rthodontist]

Here is a program (made by modifying my other program) that works according to the minimax criterion. At every step it chooses the guess that, at worst, eliminates the largest possible number of values for the selected number x.

import java.math.*;
import java.util.*;

class Guesser2
{
	public static int WIN = 0;
	public static int HOT = 1;
	public static int COLD = 2;
	public static int LUKEWARM = 3;
	public int prev;
	public int n;
	public int depth;
	public int[] possible;
	public static final int maxn = 100;
	
	/*
	 * Returns the minimax best guess
	 */
	private int getBestGuess(int p)
	{
		int b = 0;
		int improv = 0;
		for(int g = 1; g <= maxn; g++)
		{
			if(possible[g] == 1)
			{
				b = g;
				break;
			}
		}
		
		for(int g = b; g <= maxn; g++) // g == the possible guess
		{
			if(possible[g] == 0)
				continue;
			int i = improvement(g, p);
			if(i > improv)
			{
				improv = i;
				b = g;
			}
		}
		return b;
	}
	
	private int improvement(int g, int p)
	{
		int worstcase;
		int hotimp = 0;
		int coldimp = 0;
		for(int i = 1; i <= maxn; i++)
		{
			if(possible[i] == 1)
			{
				if(Math.abs(p - i) < Math.abs(g - i))
					hotimp++;
				else if(Math.abs(p - i) > Math.abs(g - i))
					coldimp++;
			}
				
		}
		worstcase = Math.min(hotimp, coldimp);;
		
		return worstcase;
	}

	public int Guesses(int a, int b, int y)
	{
		possible = new int[maxn + 1];
		for(int i = 1; i <= maxn; i++)
			possible[i] = 1;
		possible[y] = 0;
		depth = 0;
		// q = response from teller
		// x = the last guess
		// y = the current guess
		int q;
		int x;
		//int y = 1;//(int)Math.floor((a + (b - a))/3);
		System.out.print(":" + y + ";");
		depth++;
		if (AskTeller(y) == WIN)
			return y;
		while(true)
		{
			x = y;
			y = getBestGuess(x);
			possible[y] = 0;
			System.out.print(y + "," + x + "; ");
			q = AskTeller(y);
			depth++;
			if (q == WIN)
				return y;
			else if (q == LUKEWARM)
				return (x + y) / 2;
			else if (q == HOT)
			{
				for(int i = 1; i <= maxn; i++)
				{
					if(possible[i] == 1)
					{
						if(Math.abs(x - i) < Math.abs(y - i))
							possible[i] = 0;
					}
						
				}
			}
			else if (q == COLD)
			{
				for(int i = 1; i <= maxn; i++)
				{
					if(possible[i] == 1)
					{
						if(Math.abs(x - i) > Math.abs(y - i))
							possible[i] = 0;
					}
				}
			}
		}
	}
	
	// returns the integer that is 1 closer to x than y is
	int closerTo(int y, int x)
	{
		if(y > x)
			return y - 1;
		else return y + 1;
	}
	
	public int AskTeller(int y)
	{
		if (y == n){
			prev = y;
			return WIN;}
		else if (Math.abs(y - n) == Math.abs(prev - n))
			{prev = y;
			return LUKEWARM;}
		else if (Math.abs(y - n) > Math.abs(prev - n))
			{prev = y;
			return COLD;}
		else if (Math.abs(y - n) < Math.abs(prev - n))
			{prev = y;
			return HOT;}
		return 20;
	}
	
	public void doIt()
	{
		int maxdepth = 0;
		//for(int j = 1; j <= maxn; j++){
		for(int i = 1; i <= maxn; i++)
		{
		//int i = 3;
			n = i;
			Guesses(1, maxn, 1);
			System.out.println("\n" + i);
			if (depth > maxdepth)
				maxdepth = depth;
		}
		System.out.println("Final depth: " + maxdepth + "  " + 1);
		//}
	}
	
	public static void main(String[] args)
	{
		Guesser2 g = new Guesser2();
		g.doIt();
	}
}

This performs somewhat less well than the program based on binary search, yielding an output of 11 (really a depth of 12) for maxn = 100.

 

[Nimz]

Also, most of the guesses my program makes are not actually in the range 1...maxn. They will usually be greater or smaller. Maybe that's cheating.

I actually hadn't considered that possibility. Like the puzzle of connecting the dots of a 3x3 grid with 4 lines, it pays to think outside the box. When I thought about it this afternoon, I came up with a strategy that could guarantee a win by the 8th guess. The only caveat is that you have to guess 104 to figure out whether the number is 97, 98, or 99 (otherwise it takes nine guesses). Even if the restriction is kept that you must guess between 1 and 100, only one of those numbers requires a ninth guess. It looks very promising that an 8 guess strategy exists with the restriction in place.

I modified my program so that the "stupid" guesses above 100 (and below 1) are allowed. In the 8 guess strategy, I kept the first two guesses the same, so everything on the left side of the tree I posted the picture of is the same.

The tree after 60 Nope, 40 Cold, using the convention I gave earlier (Post #7):
90(78(72(68(66(X, 67, 69), 70, 78(74, 73, 71)), 75, 88(76(81, 82, 83), 80, 66(76, 77, 79))), 84, 100(92(94(95, 93, 91), 96, 104(99, 98, 97)), 89, 86(88(X, 87, 85), X, X))), 65, 26(82(30(55, 56, 57), 54, 22(51, 52, 53)), 58, 98(30(63, 64, 65), 62, 59(61, X, X))))

The deepest parentheses are 5 layers, and there are 3 guesses before the parentheses, which means 8 guesses altogether. Since the 40 Hot branch already was reduced to 8 guesses, the entire strategy requires only 8 guesses :) Since a maximal tree of 7 levels has only 95 nodes, upper bound = lower bound on number of required guesses