undefined | Better HN

0 pointsdmurray6mo ago0 comments

You're correct but the complexity is in the things you're ignoring for simplicity.

This game is constructed such that the questions you can ask are not arbitrary, so you cannot choose them to always produce one bit of entropy (you need to frame your questions as ten matchups in parallel, using all the contestants exactly once) and the number of bits you need may indeed not be an integer.

Because you can't choose your questions to partition the state space arbitrarily, that affects not just the question you ask today, but also previous days: you want to leave yourself with a partitionable space tomorrow no matter what answers you get today.

In the Guess Who analogy, it's against the rules or at least the spirit to ask "does your character have a name which is alphabetically before Grace?". That would allow a strategy which always divides the state space exactly in two.

0 comments

1 comments · 1 top-level

thaumasiotes6mo ago

> and the number of bits you need may indeed not be an integer.

That's true but not relevant; needing a non-integer number of bits makes it possible for some games to end one turn faster than other games, but it doesn't make it possible for a maximum-entropy strategy to have more variation than that one maybe-necessary-maybe-not turn. The scenario described by my parent comment still isn't possible.

> This game is constructed such that the questions you can ask are not arbitrary, so you cannot choose them to always produce one bit of entropy (you need to frame your questions as ten matchups in parallel, using all the contestants exactly once)

You're confusing two types of questions. The question where you're targeting one bit of information is "are Matt and Felicia a match?", just one pair.

A full proposed matchup of n pairs has n+1 possible answers and so your goal is to produce log₂ (n+1) bits. (Better conceptualized as one base-n+1 "bit".) I agree that it's not obvious how to do this or to what extent it's possible.