4 ms·

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 contest

by stevage 10mo ago

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.

owenlacey 10mo ago
Thank you! This is consistent with feedback I got from the pudding, and is ultimately the reason they didn't go ahead with the post. I tried reverse-engineering the information-theory approach to try see what sort of decisions it made. I noticed that for any match up score of X, the following match up would keep exactly X pairs in common. So if they scored 4/10 one week, they would change 6 couples before the next one. Employing that approach alone performed worse than the contestants did in real life, so didn't think it was worth mentioning!
- vitus 10mo ago
  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 sufficient. At the extreme of getting a score of 0, you also need the constraint that you're not repeating known-bad pairs. The same applies for pairs ruled out (or in!) from truth booths. Further, if your score goes down, you need to use that as a signal that one (or more) of the pairs you swapped out was actually correct, and you need to cycle those back in. I don't know what a human approximation of the entropy-minimization approach looks like in full. Good luck!
  - CmdDot 10mo ago
    «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 than a 50/50 chance of getting a no match and only excluding that single pairing.
    - vitus 10mo ago
      > 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.)
CmdDot 10mo ago
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 if it is correct. For wordle, «most probable» is mostly determined by letter frequency - while in Mastermind, it’s pure probability based on previous guesses. For instance, if you play a Mastermind variant with 8 pegs, and get a 2/8 in the first test - each of your 8 pegs had a 1/4 chance of being correct. So you select 2 at random to include in the next guess. If you then get a 2/8 from the second - you would include 4 previous entries in the next guess, 2 entries from the first that was not used in the second, as well as 2 entries from the 2nd - because the chance you chose the correct entries twice, is less than the chance the two hits are from the 6 you changed.
- codeflo 10mo ago
  > 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.
  - CmdDot 10mo ago
    When it comes to quickly reducing the search space of possible words, it is - that’s how you solve it optimally, even if (or in fact, especially) if the word they chose intentionally does not use the most frequent letters. The faster you can discard all words containing «e» because of a negative match, the better. If you want to be really optimal, you’ll use their list of possible words to calculate the actual positional frequencies and pick the highest closest match based on this - that’s what «mostly» was meant to imply, but the general principle of how to reduce the search space quickly is the same
  - IAmBroom 10mo ago
    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).

by stevage 10mo ago

owenlacey 10mo ago

Thank you! This is consistent with feedback I got from the pudding, and is ultimately the reason they didn't go ahead with the post. I tried reverse-engineering the information-theory approach to try see what sort of decisions it made. I noticed that for any match up score of X, the following match up would keep exactly X pairs in common. So if they scored 4/10 one week, they would change 6 couples before the next one. Employing that approach alone performed worse than the contestants did in real life, so didn't think it was worth mentioning!

vitus 10mo ago
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 sufficient. At the extreme of getting a score of 0, you also need the constraint that you're not repeating known-bad pairs. The same applies for pairs ruled out (or in!) from truth booths. Further, if your score goes down, you need to use that as a signal that one (or more) of the pairs you swapped out was actually correct, and you need to cycle those back in. I don't know what a human approximation of the entropy-minimization approach looks like in full. Good luck!
- CmdDot 10mo ago
  «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 than a 50/50 chance of getting a no match and only excluding that single pairing.
  - vitus 10mo ago
    > 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.)

CmdDot 10mo ago

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 if it is correct. For wordle, «most probable» is mostly determined by letter frequency - while in Mastermind, it’s pure probability based on previous guesses. For instance, if you play a Mastermind variant with 8 pegs, and get a 2/8 in the first test - each of your 8 pegs had a 1/4 chance of being correct. So you select 2 at random to include in the next guess. If you then get a 2/8 from the second - you would include 4 previous entries in the next guess, 2 entries from the first that was not used in the second, as well as 2 entries from the 2nd - because the chance you chose the correct entries twice, is less than the chance the two hits are from the 6 you changed.

codeflo 10mo ago
> 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.
- CmdDot 10mo ago
  When it comes to quickly reducing the search space of possible words, it is - that’s how you solve it optimally, even if (or in fact, especially) if the word they chose intentionally does not use the most frequent letters. The faster you can discard all words containing «e» because of a negative match, the better. If you want to be really optimal, you’ll use their list of possible words to calculate the actual positional frequencies and pick the highest closest match based on this - that’s what «mostly» was meant to imply, but the general principle of how to reduce the search space quickly is the same
- IAmBroom 10mo ago
  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).