Twenty questions with uncertain answers

[jack]

If you're playing twenty questions (say on something simple like "numbers from 1 to a 1000") the best strategy is to divide the output into two with each guess[1]. Eg. Higher than 500? Yes. Higher than 750? No. Higher than 625? Yes. Etc. Etc. This will take log(N) questions to find the exact answer. (Guessing randomly may produce the answer quicker, but on average will take mcuh longer.)

However, suppose when you ask a question, you're given the answer, but it's right only 90% of the time. (For simplicity, assume you can find out if you've got the right single answer at the end.) What's the right strategy? Is it to ask "Higher than 500" twice or more until you're sure? Or to follow the normal strategy until it gives a unique answer, and if that's wrong, start again?

The second game feels like what I often end up feeling like in real life... :)

[1] I remember reading a book that said learning to "gain information" from a guess rather than "make a right guess" was quite difficult for children to learn -- a teacher reported many children guess "higher than X" when they already knew it true, because they'd been so conditioned by class to expect a "yes, that's right" to be a good thing and "no, that's wrong" to be a bad thing.

Comments

[simont]

The second game is also not a bad model for Twenty Questions on a more general domain, given that real-world examples often involve questions on which the questioner and answerer can reasonably disagree.

eta: oh, or was that what you meant by "in real life"? I assumed you meant "real life when not playing 20Q", rather than "when playing 20Q on the domain of real life", but I now realise the latter might be a quite plausible parse. :-)

Even supposing the optimum strategy is feasible to analyse (by pure maths or computationally), I suspect it will depend on exactly what target you're optimising it for. The obvious criterion is "minimise the expected number of questions before guessing the answer correctly", but you may well find that that doesn't lead to the same strategy as the criterion "maximise the probability of guessing the answer correctly within the first N questions" (with N = oh, just for example, 20).

Other guessing games based on narrowing down a search space have this property: e.g. Mastermind has a different optimum strategy depending on whether you want to minimise the expected or the maximum number of guesses required. (Though when I was reading up on that one I never found a treatment of Mastermind as an adversarial game: if you're picking the sequence the other player will guess, is there some non-uniform pdf with which you should select from the 6^4 possibilities to make life harder for the guesser?)

[jack]

LOL. No, I meant "in actual real life", but in fact, real life twenty questions is a good example of real life :)

I agree it's probably going to be different -- I was hoping for an answer to either, I guess :)

[rmc28]

Asking repeatedly seems to be the strategy for small children, at least until they are conditioned into yes=right, no=wrong. That gives me the shivers. It's bad enough that I fall into interrogative, tell-me-what-I-already-know mode with children all too often. Must stop doing that.

See also http://xkcd.com/242/ Never mind scientists, Charles does this ALL THE TIME. "Oooh, that made Mummy shout, I wonder what happens if I do it again."

[ptc24]

For each possible answer, assign a probability, based on an equiprobability assumption. You can then calculate the entropy of the probability distribution. Based on your guesses, you can update probabilities based on Bayes theorem. You can choose which threshold to pick by seeing what effects a negative or positive result would have on the entropy, and choosing the threshold which gives the greatest effect.

I *suspect* the right threshold is the one where the number is as likely to be below the threshold as above.

It would be interesting to see what this looks like in practise; it ought to be do-able.

[simont]

That's fine as long as you just want to keep asking probabilistic questions and reducing entropy forever, but surely at some point you want to switch over to making one-element guesses that have some chance of ending the game? So you'd also need to decide at each stage whether it was more profitable to do the one or the other.

[ptc24]

I *suspect* that the same underlying entropy-reduction algorithm can be applied; however, the strategy that comes out of it will differ. However, a game-tree style analysis might show this to be wrong.

Again, this is testable. I could have fun with this.

[ptc24]

The following is an example of a simple guess at a good procedure (basically, make the guess that gives as close to 50:50 of higher/lower, guess a specific number when p > 0.5, keep updating a probability vector).

Output columns: Is it less than this number? Is the information correct? p[the actual correct number]

#!/usr/bin/env python

import random

size = 1000
x = random.randint(0,size-1)

pv = [1.0/size] * size

print "*", x, "*"

l = -1

for z in range(50):
    if l == -1:
        i = 0
        pp = 0.0
        lpp = 0.0
        while(pp < 0.5):
            lpp = pp
            pp += pv[i]
            i += 1
        if pp > (1.0 - lpp):
            i -= 1
            pp = lpp
        print i, 
        s = random.random() > 0.9
        os = s ^ (x < i)
        if os:
            m = 0.9
        else:
            m = 0.1
        g = -1
        for j in range(0,i):
            pv[j] *= m / pp
            if pv[j] > 0.5:
                g = j
        for j in range(i,size):
            pv[j] *= (1.0 - m) / (1.0 - pp)
            if pv[j] > 0.5:
                g = j
        print not s, 
        print pv[x]
    else:
        g = l
        l = -1
    if g > -1:
        if g == x:
            print "Guess", g, "correct!"
            break
        else:
            print "Guess", g, "incorrect!"
        pv[g] = 0
        s = sum(pv)
        for j in range(size):
            pv[j] /= s
            if pv[j] > 0.5:
                l = j