Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“Are you the one?” is free money

blog.owenlacey.dev

Post reply on HN
Print view View original

111–119 of 119 posts

Re: “Are you the one?” is free money

#111

Post by calfuris »

kruffalon wrote: post #107
CmdDot wrote: post #83

Earlier quoted context omitted.

In addition to Mastermind, Wordle also falls into the same category. Optimal play to reduce the search space in both follow the same general pattern - the next check should satisfy all previous feedback, and included entries should be the most probable ones, both of those previously tested, and those not. If entries are equally probable, include the one which eliminates the largest number of remaining possibilities i…

> Optimal play to reduce the search space in both follow the same general pattern - the next check should satisfy all previous feedback Thank you! I might look into this once I break my current streak of the localised wordle clone I'm playing now. I always try to use as many different bits for the first few rounds... But then again, maybe I'm not so good at these kinds of games as I think.

It's not actually optimal. Each check should account for all previous feedback, but it may be optimal to make a known-incorrect guess and trade the chance of winning with that guess for additional information.

For example, if your first guess on wordle is BOUND and you learn that the word is _OUND, you know the answer is one of FOUND, HOUND, MOUND, POUND, ROUND, SOUND, WOUND. Satisfying all previous feedback leaves you checking those one at a time and losing with probability 2/7. Or you could give up the 1-in-7 chance of winning in 2 and trade it for certainly winning in either 3 or 4: HARMS checks four of those options, and WHOOP identifies the remaining three.

Re: “Are you the one?” is free money

#112

Post by ChristopherDrum »

owenlacey wrote: post #75

What are some other gameshows one could nerd out about? I'll start: 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 program…

"Let's Make a Deal" was hosted by Monty Hall and is literally the Monty Hall problem.

Re: “Are you the one?” is free money

#113

Post by thaumasiotes »

dmurray wrote: post #60
thaumasiotes wrote: post #52

Earlier quoted context omitted.

> 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 I'm not following your logic. Consider the setup we actually have: 1. You get to ask a series of yes/no questions. (Ignoring the matchups.) 2. Each question can produce, in expectation, up to one bit of information. 3. In order to achieve this maximum expectatio…

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…

> 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.

Re: “Are you the one?” is free money

#114

Post by ChristopherDrum »

owenlacey wrote: post #73
ChristopherDrum wrote: post #49

I think the part that stings most about this article is when he says, "In my research I came across a boardgame called Mastermind." My lived childhood is old enough to be someone's "research."

Sorry :') My wife and I bought the game - it's a great turn based came you can play whilst having trashy reality shows on in the background!

No no, I was just blindsided by my own feelings when I read that and thought it was kind of funny. Judging from the inexplicable downvoting that comment received (?!) apparently that wasn't clear. I always enjoyed Mastermind, though there is a line of attack on the solution that can render it a little boring. It still maintains a bit of a Wordle-like pleasure.

Re: “Are you the one?” is free money

#115

Post by andrewaylett »

IAmBroom wrote: post #104
codeflo wrote: post #93

Earlier quoted context omitted.

> For wordle, «most probable» is mostly determined by letter frequency I don't think that's a justified assumption. I wouldn't be surprised if wordle puzzles intentionally don't follow common letter frequency to be more interesting to guess. That's certainly true for people casually playing hangman.

I would guess Wordle picks from a big bag'o'words. The words are all fairly common - "regel" is not going to show up - but I see no evidence the list favors "zebra" over "taint" (which has occurred, BTW).

The original Wordle had a hard-coded ordering that was visible in the source. I had a toy around with the list (as did many other people) a few years back, you can see my copy of the word list here: https://github.com/andrewaylett/wordle/blob/main/src/words.r...

Re: “Are you the one?” is free money

#116

Post by vitus »

CmdDot wrote: post #86
vitus wrote: post #79

Earlier quoted context omitted.

It should be easier to understand the optimal truth booth strategy. Since this is a yes/no type of question, the maximum entropy is 1 bit, as noted by yourself and others. As such, you want to pick a pair where the odds are as close to 50/50 as possible. > Employing that approach alone performed worse than the contestants did in real life, so didn't think it was worth mentioning! Yeah, this alone should not be suffic…

«As such, you want to pick a pair where the odds are as close to 50/50 as possible.» This is incorrect, the correct strategy is mostly to check the most probable match (the exception being if the people in that match has less possible pairings remaining than the next most probable match). The value of confirming a match, and thus eliminate all other pairings involving those two from the search space, is much higher t…

> This is incorrect, the correct strategy is mostly to check the most probable match (the exception being if the people in that match has less possible pairings remaining than the next most probable match).

Do you have any hard evidence, or just basing this on vibes? Because your proposed strategy is emphatically not how you maximize information gain.

Scaling up the problem to larger sizes, is it worth explicitly spending an action to confirm a match that has 99% probability? Is it worth it to (most likely) eliminate 1% of the space of outcomes (by probability)? Or would you rather halve your space?

This isn't purely hypothetical, either. The match-ups skew your probabilities such that your individual outcomes cease to be equally probable, so just looking at raw cardinalities is insufficient.

If you have a single match out of 10 pairings, and you've ruled out 8 of them directly, then if you target one of the two remaining pairs, you nominally have a 50/50 chance of getting a match (or no match!).

Meanwhile, you could have another match-up where you got 6 out of 10 pairings, and you've ruled out 2 of them (thus you have 8 remaining pairs to check, 6 of which are definitely matches). Do you spend your truth booth on the 50/50 shot (which actually will always reveal a match), or the 75/25 shot?

(I can construct examples where you have a 50/50 shot but without the guarantee on whether you reveal a match. Your information gain will still be the same.)

Re: “Are you the one?” is free money

#117

Post by hatthew »

jncfhnb wrote: post #87
hatthew wrote: post #24

Earlier quoted context omitted.

Yes, you learn more than 1 bit in that case. However, if you are told A is false, you still don't know whether B or C is true, so you gain less than 1 bit. Assuming A, B and C all have equal probability, your average/expected information gain is If you ask the question "which of A, B, or C is true?" then you're not asking a yes/no question, and it's not surprising that you expect to gain more than 1 bit of informatio…

but that’s all consistent. “Expected” gain is less than 1 for the truth booths and sometimes > 1 for actuals; and is > 1 on expected value of the match ups, which aren’t binary questions.

Sure, and the issue is that the article says "Suppose we have calculated the expected information gained by potential truth booths like below:" and then lists some values >1

edit: just saw that the article fixed this recently, and the values are now <1

Re: “Are you the one?” is free money

#118

Post by zvr »

0xkalle wrote: post #56

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 an…

Surely you mean 10 + 10 candidates (not 10x10).

Re: “Are you the one?” is free money

#119

Post by codebje »

vintermann wrote: post #58
codebje wrote: post #20

Earlier quoted context omitted.

Everything is lined up for sub-optimal play. For a start, the setting is an emotive one. It's not just a numeric game with arbitrary tokens, it's about "the perfect romantic partner." It would take an unusually self-isolating human to not identify who they feel their perfect match should be and bias towards that, subconsciously or consciously. We (nearly) all seek connection. Then, it's reality TV. Contestants will b…

> No-one is going to watch a full season of a handful of math nerds take a few minutes to progress a worksheet towards a solution each week coupled with whatever they do to pass the time otherwise. Um, what about those of us who watch Blood on the Clocktower streams?

Both of you are the exceptions that prove the rule?
Post reply on HN