Гадалка Шеннона

В студенческое время я наткнулся на интересную статью об игре "Чет-нечет" на домашней страничке пользователя ltwood.

Правила очень простые. Игрок загадывает один вариант из двух: "чет" или "нечет", а оппонент пытается угадать выбор игрока. Если угадать не удалось, то очко получает загадавший, а если угадать получилось - то угадывающий. Кто первым наберет 20 очков, тот и молодец!

Кажется, что в этой игре все случайно. Случайно загадывается число, потом случайно второй игрок пытается угадать что же было загадано. Я очень сильно удивился, когда попробовал поиграть в эту игру с программой и за десять попыток так ни разу и не выиграл.

Парадокс в том, что мы думаем что загадываем числа случайно. На самом деле все не так, и последовательность загаданных чисел не случайна.

Исходного кода оригинальной гадалки в открытом доступе нет, есть только описание алгоритма, по которому я сделал свою реализацию на TypeScrypt.

Демоверсия

Попробуйте набрать 50 очков и выиграть. Чтобы выбирать вариант с клавиатуры, кликните внутри серой рамки, а потом пользуйтесь клавишами "1" - нечет или "2" - чет.

Как Это работает

Математически алгоритм на странице сайта ltwood. Я рассмотрю простой пример, чтобы показать принцип.

В основе алгоритма находится популяция "демонов" - автоматов, которые на основании ходов игрока и предсказанных значениях выдают новое предсказание. Демонами управляет супервайзер. Задача супервайзера в том, чтобы опросить всех демонов, выбрать ответ от одного их них, а после получения ответа игрока пометить тех, кто выдал правильный ответ.

Алгоритм состоит из двух шагов:

Рассмотрим работу на примере одного демона.

Пусть у нас есть демон, который смотрит на последний хода игрока и на свое последнее предсказание.

Строим два вектора:

В самом начале, когда у демона нет никакой информации о ходах игрока, эти векторы будут выглядеть как [0] и [1]. Но с накоплением данных, они всегда будут каждый по 5 элементов.

После чего смотрим, который из таких наборов в прошлом приносил победу чаще, и соответственно выбираем или вариант с 0, или с 1.

После получения действительного хода игрока, мы увеличиваем вес того набора, который оказался верным. И далее снова предсказываем ход.

Теперь с числами.

Ход 1

У демона нет информации, наборы [0] и [1] равнозначны, выбираем [0], а значит предсказываем ход игрока 0.

Игрок загадывал 1. Обновляем веса: 

[0] = 0
[1] = 1

Ход 2

Строим векторы на основе последних ходов: 

0: [0, 1, 0]
1: [0, 1, 1]

Для этих векторов тоже еще нет весов, так что снова выбираем первый, предсказываем 0.

Игрок снова выбрал 1. Обновляем веса (помним, что еще были прошлые вектора из одного элемента): 

[0] = 0
[1] = 1
[0, 1, 0] = 0
[0, 1, 1] = 1

Ход 3

Картина такая же, как на втором ходу, но отличие в том, что у нас есть веса с прошлого хода: 

0: [0, 1, 0] - 0
1: [0, 1, 1] - 1

Выбираем вариант 1, игрок снова выбирает 1. Предсказание удалось!

Расширение алгоритма

Это был самый элементарный вариант. Понятно, что на таком далеко не уедешь, и никого не обыграешь. Чтобы хорошо предугадывать ходы игроков, используется несколько демонов с разной величиной просматриваемой истории. Следит за ними "супервайзер", который ведет для каждого демона рейтинг. На основе этого рейтинга выбираются ответы тех демонов, которые были наиболее успешны в своих предсказаниях.

Ссылки

01.05.2019, anton@vakhrushev.me