Лучшая стратегия «Угадай, кто?» (и как я её доказал)

История о том, как я доказал оптимальную стратегию «Угадай, кто?» в своей работе 2016 года и чем она отличается от чистого бинарного поиска.

*Ссылки*
https://marimo.app/l/noa32s
Приложение, в котором можно сыграть в «Угадай, кто?» против лучшей стратегии, как на видео.
В раскрывающемся списке графиков также отображается график лучшей ставки и вероятности лучшего выигрыша из миниатюры!

Моя статья на arXiv https://arxiv.org/abs/1509.03327

Видео Марка Робера от 2015 года    • BEST Guess Who Strategy- 96% WIN record us...  

Короткие видео Марка Робера от 2024 года    • How to ALWAYS WIN "Guess Who"  

Видео LearnYouSomeMath по этой теме (там также есть ссылка на мою статью!)    • S1 E6 - Dominating Mark Rober in Guess Who!  

*Обновления*
Скотт Лоу спросил в комментарии, могу ли я рассчитать, насколько оптимальная стратегия лучше чистого бинарного поиска, что я и сделал! Вот результаты (см. также комментарии для дальнейшего обсуждения):

Вот таблица вероятности победы игрока P1 в матче P1 против P2, когда стартовый игрок выбирается случайным образом путём подбрасывания монеты из стартового пула из 31 персонажа. (см. также полное объяснение ниже):

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

Пояснение: Вероятность выигрыша для любых двух заданных стратегий легко рассчитать, двигаясь в обратном порядке, поскольку общее число оставшихся игроков уменьшается как минимум на одного с каждым ходом (т.е. «используйте динамическое программирование»). См. Алгоритм 1 в статье. Я применил его к предложенным вами матчапам, но оказалось, что чистый двоичный поиск действительно ужасен, когда проигрывает, поскольку его шансы на победу, как правило, равны 0%. Поэтому я также добавил стратегию «BinaryPlus», которая представляет собой двоичный поиск, если у противника не осталось 2 игрока и он выиграет на следующем ходу. В этом случае BinaryPlus делает случайное предположение. (Как тот, кто угадал 9 в видео).

Вы также можете увидеть разбивку по тому, чей это начальный ход, где действительно видно, что преимущество возникает, когда вы ходите вторым. По сути, стратегия «Оптимал» работает лучше, когда проигрывает, и именно в этом её преимущество.

+----------------+------------------------+--------------+-------------+------------------+
| Стратегия P1 | Стратегия P2 | P1 1-й % | P1 2-й % | P1 Coin % |
+----------------+------------------------+--------------+-------------+------------------+
| Бинарный | Бинарный | 96,88% | 3,12% | 50,00% |
| Бинарный | BinaryPlus | 75,03% | 3,12% | 39,07% |
| Бинарный | Оптимальный | 53,17% | 3,12% | 28,15% |
| BinaryPlus | Бинарный | 96,88% | 24,97% | 60,93% |
| BinaryPlus | BinaryPlus | 75,03% | 24,97% | 50,00% |
| BinaryPlus | Оптимальный | 63,37% | 24,97% | 44,17% |
| Оптимальный | Бинарный | 96,88% | 46,83% | 71,85% |
| Оптимальный | BinaryPlus | 75,03% | 36,63% | 55,83% |
| Оптимальный | Оптимальный | 66,29% | 33,71% | 50,00% |
+---------------------+-------------------+--------------+--------------+---------------+

Я всё это запустил в этом colab-файле https://colab.research.google.com/dri... .