> Season 8: In this season, they introduced gender fluidity. Whilst an interesting problem on its own, this would have wreaked havoc on my model.
Well I guess free money except for that one. In that one, one of the contestants, Danny, did the math for optimizing their remaining Truth Booths and Match Ups to get it down to a 50/50 shot.
They have an example that calculates the expected information gained by truth booths and all of the top ones are giving more than one bit. How can this be? It is a yes/no question a max of 1 bit should be possible
Fun post. I'd be interested to know: How many consecutive Truth Booths (or: how many consecutive Match Ups) are needed to narrow down the 10! possibilities to a single one?
Discussing "events" (ie, Truth Booth or Match Up) together muddles the analysis a bit.
I agree with Medea above that a Truth Booth should give at most 1 bit of information.
> I also pitched this idea to The Pudding, and had a great experience with them nerding out about this subject. Though they didn't take my up on my idea, I left with really great and actionable feedback, and I'm looking forward to my next rejection.
Would've been a great Pudding post imo, but oh well, happy to find this nice devblog instead.
This brings up an area that’s been on the edge of my curiosity for years: how do you combine the knowledge of the experts (contestants) with logic to do better either than either strategy individually?
It’s mostly about how to elicit the information from the contestants. Once you have the probabilities from them, it seems relatively straightforward.
I saw an episode of this and felt the contestants didn’t seem that interested in winning the money. Just romance. I was curious how suboptimally they tended to play.
This was great, but it skipped over the most interesting bit - how you actually choose which matchups and truth booths. That is, an actual strategy that contestants could use that doesn't require a computer.
If the goal is to find the perfect matching in some maximum number of turns or less, it's possible to do even better by using a full game tree that minimises the maximum height of the tree ( = number of turns required), instead of using information/entropy as done here.
Basically, using the entropy produces a game tree that minimises the number of steps needed in expectation -- but that tree could be quite unbalanced, having one or more low-probability leaves (perfect matchings) many turns away from the root. Such a leaf will randomly occur some small fraction of the time, meaning those games will be lost.
For concreteness, a game requiring 6 bits of information to identify the perfect matching will take 6 steps on average, and may sometimes require many more; a minimax tree of height 7 will always be solved in at most 7 steps. So if you're only allowed 7 steps, it's the safer choice.
As a math guy who loves reality tv, I was also drawn to the show and wrote a blog post [0] about how to programmatically calculate the probabilities as the show progresses. It was a lot of fun optimizing it to be performant. You can `pip install ayto` to use it to follow along with the show or try out scenarios.
The linked post is a very thorough treatment of AYTO and a great read. I really like the "guess who" bit on how to maximize the value of guesses. It's a shame the participants aren't allowed to have pen and paper—it makes optimization a lot trickier! I'm impressed they do as well as they do.
After he described the rules, my immediate reaction was 'this is like mastermind'. Sure enough, further down the page:
Other than that, in my research I came across a boardgame called Mastermind, which has been around since the 70s. This is a very similar premise - think of it as "Guess Who?" on hard mode.
A thing to note - the contestants are not allowed to have even pen and paper, as mentioned in the other blogpost. So they need to do these computations in their heads.
When my wife and I watched the show I wrote a solver on the side so we always had the current probabilities and impossible combinations on the side.
I am thinking about making a website for it when the next season starts.
Also: in Germany at least they have 10 x 10 candidates from the start, but sometimes they add a 11th or even 12th of one gender so that there are double matches (e.g. 1 woman has two man as match and needs to find one of it to succeed). This raises the possible combination quite a bit.
> This time, one guy has two matches which means that there will be eleven girls, but only ten boys.
One thing the show runners do subtle alterations that makes the logic much harder.
The Traitors has to do lots of these tricks when not playing the Celebrity edition because there's a self-selection for the sort of person who has already played Werewolf/Avalon-type games.
Love the approach of using information theory to optimize decisions. The concept of "expected information gained" is fascinating - it's basically what good analytics should do: help you ask the right questions to eliminate uncertainty fastest.
The interactive visualizations on this post are fantastic. More technical content should be presented this way. Makes complex probability much more intuitive.
Most hilarious part of this is that if you've ever watched "The Challenge" then you know that these people, truly, often cannot add 3 digit numbers together let alone understand information theory
> This post is my first foray into content like this. I wanted to scratch the itch of an interesting maths problem, with a light-hearted spin that I hope you enjoyed as much as I did making it.
Really impressive imo. I don't remember the last time I was this engaged reading an article on HN.
27 comments
[ 3.2 ms ] story [ 54.7 ms ] thread> 0 0.3679
> 1 0.3679
> 2 0.1839
> 3 0.0613
> 4 0.0153
> 5 0.0031
For 0, it's a well known [1] result 1/e, I remember a puzzle where people left their hat and then pick one randomly.
Looking at the table it looks like the general formula is 1/(e*n!) that is a Possion distribution. Compare with https://en.wikipedia.org/wiki/Poisson_distribution#Examples_...
Anyway, I'm not sure if my observation helps too much to solve the original problem.
[1] at least I know it :)
Well I guess free money except for that one. In that one, one of the contestants, Danny, did the math for optimizing their remaining Truth Booths and Match Ups to get it down to a 50/50 shot.
Discussing "events" (ie, Truth Booth or Match Up) together muddles the analysis a bit.
I agree with Medea above that a Truth Booth should give at most 1 bit of information.
Would've been a great Pudding post imo, but oh well, happy to find this nice devblog instead.
It’s mostly about how to elicit the information from the contestants. Once you have the probabilities from them, it seems relatively straightforward.
Basically, using the entropy produces a game tree that minimises the number of steps needed in expectation -- but that tree could be quite unbalanced, having one or more low-probability leaves (perfect matchings) many turns away from the root. Such a leaf will randomly occur some small fraction of the time, meaning those games will be lost.
For concreteness, a game requiring 6 bits of information to identify the perfect matching will take 6 steps on average, and may sometimes require many more; a minimax tree of height 7 will always be solved in at most 7 steps. So if you're only allowed 7 steps, it's the safer choice.
The linked post is a very thorough treatment of AYTO and a great read. I really like the "guess who" bit on how to maximize the value of guesses. It's a shame the participants aren't allowed to have pen and paper—it makes optimization a lot trickier! I'm impressed they do as well as they do.
[0]: https://danturkel.com/2023/01/25/math-code-are-you-the-one.h...
My lived childhood is old enough to be someone's "research."
I am thinking about making a website for it when the next season starts.
Also: in Germany at least they have 10 x 10 candidates from the start, but sometimes they add a 11th or even 12th of one gender so that there are double matches (e.g. 1 woman has two man as match and needs to find one of it to succeed). This raises the possible combination quite a bit.
An obvious one is the traitors, but I dunno if there's much you can do with this one as the contestants rarely gain much concrete information.
"Deal or no deal" / "let's make a deal" would have interesting game theory approaches - probably has a lot of parallels with Monty Hall?
Countdown (UK) - solving the maths puzzles on here using integer programming would be cool
One thing the show runners do subtle alterations that makes the logic much harder.
The Traitors has to do lots of these tricks when not playing the Celebrity edition because there's a self-selection for the sort of person who has already played Werewolf/Avalon-type games.
The interactive visualizations on this post are fantastic. More technical content should be presented this way. Makes complex probability much more intuitive.
> A truth booth is where a male & female ...
The use of "male" and "female" as nouns sounds very unnatural. "A man and a woman" would be a little less jarring, imo.
Really impressive imo. I don't remember the last time I was this engaged reading an article on HN.