The best "Guess Who?" strategy (and how I proved it)

The story of how I proved the optimal "Guess Who?" strategy in my 2016 paper and how it differs from pure binary search. *Links* https://marimo.app/l/noa32s App where you can play "Guess Who?" against the best strategy like in the video The graphs dropdown also includes the best bid and best win probability graph from the thumbnail too! My paper on the arXiv https://arxiv.org/abs/1509.03327 Mark Rober's videos from 2015    • BEST Guess Who Strategy- 96% WIN record us...   Mark Rober's shorts video from 2024    • How to ALWAYS WIN "Guess Who"   LearnYouSomeMath video on the subject (they also reference my paper!)    • S1 E6 - Dominating Mark Rober in Guess Who!   *Updates* Scott Lowe asked in a comment if I could calculate by how much is the optimal strategy better than pure binary search, which I did! Here are the results (see also comments for more discussions) Here is the table for the P1 win probability in the P1 vs P2 matchup when starting player is chosen randomly by fair coinflip from a starting pool of 31 characters. (see also full explanation below) | P2=Binary | P2=BinaryPlus | P2=Optimal -------------------------------------------------------------------------------------------------- P1=Binary | 50.00% | 39.07% | 28.15% P1=BinaryPlus | 60.93% | 50.00% | 44.17% P1=Optimal | 71.85% | 55.83% | 50.00% Explanation: Its easy to figure out the win probability for any two given strategies by working backwards since the total remaining players decreases by at least one on each turn (i.e. "use dynamic programming"), see the Algorithm 1 in the paper. I ran this for the matchups you suggested but it turned out that Pure Binary search is truly awful when it is losing because it essentially has 0% chance of winning once it gets behind. So I also added in the "BinaryPlus" strategy which is binary search unless the opponent has 2 people left and will win next turn, in which case BinaryPlus takes a random guess. (Like the person who guessed 9 in the video). You can also see the breakdown by whose starting turn it is where you can really see that the advantages come from when you go 2nd. Essentially the Optimal strategy does better when it losing and this is where the advantages come from +----------------+------------------------+---------------+-------------+------------------+ | P1 Strategy | P2 Strategy | P1 1st % | P1 2nd % | P1 Coin % | +----------------+------------------------+---------------+-------------+------------------+ | Binary | Binary | 96.88% | 3.12% | 50.00% | | Binary | BinaryPlus | 75.03% | 3.12% | 39.07% | | Binary | Optimal | 53.17% | 3.12% | 28.15% | | BinaryPlus | Binary | 96.88% | 24.97% | 60.93% | | BinaryPlus | BinaryPlus | 75.03% | 24.97% | 50.00% | | BinaryPlus | Optimal | 63.37% | 24.97% | 44.17% | | Optimal | Binary | 96.88% | 46.83% | 71.85% | | Optimal | BinaryPlus | 75.03% | 36.63% | 55.83% | | Optimal | Optimal | 66.29% | 33.71% | 50.00% | +---------------------+-------------------+---------------+---------------+---------------+ I ran it all in this colab file here https://colab.research.google.com/dri... .