«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.
> 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.)
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.
> 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.
The "next check should satisfy all previous feedback" part is not exactly true. That's hard-mode wordle, but hard mode is provably slower to solve than non-hard-mode (https://www.poirrier.ca/notes/wordle-optimal/) where the next guess can be inconsistent with previous feedback.
> 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.
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
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...
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.
From the post: «In the context of resource-constraint embedded devices, it may make sense to tailor an interpreter to a specific applications to gain best performance.»
The «key problems» are also discussed in the introduction of the paper at the top of page 2 - including why it’s practical in their context.
Also in the paper, they say speedups based on optimizing a subset of benchmarks generalize to other benchmarks as well, but not across environments.
Last I checked, starting with an «optimizing your environment» task, is far from being considered «not very practical»
Not really, once a program is compiled with -retpoline, new hardware won't bring back reliable branch prediction.
I'd hope maybe, just maybe, this would be enough to put a focus on compilers producing code that ends up using processor-optimized paths chosen at runtime, to avoid "overheads ranging from 10% to 50%".
Though, in this case, that would essentially mean making the entire executable region writable for some window of time, which is clearly too dangerous, so I guess the 0.1% speedups from compiling undefined behavior in new and interesting ways, will continue taking priority.
I mean, it's a compiler flag right, obviously whoever's going to run a program on an unaffected platform will take the effort to recompile everything with the flag removed.
Just the same way every serious application currently provides different executables for running on systems where SSE2, SSE4.1, or AVX2 is present.
Not quite - lots of "serious" applications these days are written to target JIT compilers, which would be capable of switching retpoline on and off depending on need.
I'd rather have linkers go down a similar road that the Linux kernel went on a over a decade ago: provide binary patches in a table (essentially alternative machine code) and have the linker patch the correct alternative depending on the CPU and it's bugs. The Linux kernel already contains an "alternatives" segment which is exactly this kind of list of patches. It would be trivial to add such a table to ELF and PE formats and have the runtime linker process that while it's plowing through the code anyway.
There's a lot of space left in code already to insert trampolines later. And in the end of the day most memory is data, not code.
And eventually, this code will get replaced anyway (just like today there are often multiple code paths in binaries, and a lot of code is compiled for host anyway).
In any case, the performance impact of a couple extra bytes per indirect call is small compared to disabling branch target prediction.
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.