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.