Home
🧠

20Q

I pulled the brain out of the PSP Mini’s version of 20Q and put it in a browser. You can play with it at 20q.jordanscales.com.
It's a small brain: 3,083 things and 365 questions. Here's how it works.

πŸ”— Tables all the way down

The game ships its brain inside the executable. Once decrypted (with some help from PPSSPP), it's sitting there as one big table: a row for every item and a column for every question.
Each cell is 4 bits so two answers fit in a byte. The whole brain is about 570KB.
function lookup(thing, question) {
  const i = thing * 369 + question
  const byte = brain[i >> 1]

  // Even cells are the low 4 bits, odd cells are the high 4 bits
  return i % 2 === 0 ? byte & 0xf : byte >> 4
}
Those 4 bits boil down to two flags: yes or no, and strong or weak.
function flags(value) {
  return {
    yes: (value & 8) !== 0,
    strong: (value & 7) >= 3,
  }
}
Here's what the brain thinks about a couple of things.
              Is it hard   Four legs    Is it a tool
a globe       strong yes   strong no    weak no
an elephant   weak no      strong yes   strong no

πŸ”— Scoring answers

You don't just answer yes or no. You can say "Probably", "Rarely", "Depends,” among others. The game has a table for these too. Each one has a side (yes-ish or no-ish), a bonus, and a penalty. I personally shy away from these answers but staying true to the original brain I included them.
const RESPONSES = {
  Yes:      { side: "yes", bonus: 4, penalty: 4 },
  No:       { side: "no",  bonus: 4, penalty: 4 },
  Usually:  { side: "yes", bonus: 4, penalty: 2 },
  Rarely:   { side: "no",  bonus: 4, penalty: 2 },
  Probably: { side: "yes", bonus: 3, penalty: 1 },
  Doubtful: { side: "no",  bonus: 3, penalty: 1 },
  Unknown:  { side: "yes", bonus: 0, penalty: 0 },
  // ...and a few more
}
For every item, the brain checks your answer against its entry in the table. If they agree, the thing gets the bonus. If they don't, it gets the penalty.
function score(thing, answers) {
  let bonus = 0
  let penalty = 0

  for (const { question, response } of answers) {
    const { yes, strong } = flags(lookup(thing, question))
    const times = strong ? 2 : 1

    if (yes === (response.side === "yes")) {
      bonus += response.bonus * times
    } else {
      penalty += response.penalty * times
    }
  }

  return bonus - penalty
}
Notice that a wrong "Probably" only costs 1 because hedging is cheap.

πŸ”— The shortlist

After every answer, the brain scores all 3,083 things and keeps the top 20. Then it trims anything too far behind the leader.
const top = shortlist[0].score
const drop = Math.floor(top / 3)
const keep = Math.max(0, top - drop - 32)

shortlist = shortlist
  .map((t) => ({ ...t, weight: t.score - drop }))
  .filter((t) => t.weight > keep)
Each survivor gets a weight. We'll need it next.

πŸ”— Picking a question

This is the clever part. For every question it hasn't asked yet, the brain splits the shortlist into a yes pile and a no pile.
function rate(question, shortlist) {
  let yes = 0
  let no = 0

  for (const { thing, weight } of shortlist) {
    const f = flags(lookup(thing, question))
    const w = weight * (f.strong ? 3 : 1)

    if (f.yes) yes += w
    else no += w
  }

  return 2 * Math.min(yes, no) - Math.max(yes, no)
}
The best question has the most even split. A 50/50 question cuts the shortlist in half, no matter what you answer.
At the start everything is tied, so the first question is always "Is it hard?" (a weighted 4,430 yes to 4,515 no). Side note: the PSP version adds a bit of random noise to each rating to mix things up, but I left it out so every game can be replayed.

πŸ”— Guessing

After 20 questions, the brain guesses its leader. If it's wrong, that thing is out for good. It asks one more question and guesses again.

πŸ”— An elephant

Here's a game where I thought of an elephant and gave the brain's own answers back to it.
 1  Is it hard?                     Doubtful  leader: a giraffe
 2  Does it have four legs?         Yes       leader: a giraffe
 5  Is it a carnivore?              No        leader: a giraffe
 6  Does it like to run?            No        leader: a platypus (duck-billed)
 7  Is it very large?               Yes       leader: a sofa
 8  Can you buy it?                 Doubtful  leader: an elephant's trunk
11  Can you sit on it?              Yes       leader: an elephant's trunk
12  Is it dangerous?                Yes       leader: an elephant
17  Is it used for transportation?  Yes       leader: an elephant
By question 17 the shortlist is down to one thing. After 20, it guesses an elephant.

πŸ”— Watching it think

The visualizer puts every thing on a map. Things with similar answers sit close together (using t-SNE), so animals end up in one corner and food in another. As you play, dots turn grey when they're ruled out, and orange when they make the shortlist.
The brain is deterministic, so a game is just a list of answers. The whole game fits in the URL.
https://20q.jordanscales.com/#g=YNNYNPNNNNNNNNNNNNNNr
Replaying that list rebuilds every step, which makes time travel easy. Click any row in the log to go back.
Thanks for reading! Let me know if you manage to stump it.