Я поступил в институт в 1978 году, когда игра «Быки и коровы» была на пике популярности. В серии игр никто не мог меня победить, а все благодаря относительно несложному алгоритму, разработанному мною на основе теории информации. Изучив современные источники, я не нашел среди них чего-то похожего на мой подход. Поэтому я решил поделиться своей стратегией в блоге ЛАНИТ, чтобы обсудить его с техническим сообществом.

Эта игра — классическая логическая задача, где один игрок загадывает число, а другой пытается его угадать, задавая вопросы и получая ответы в виде количества «быков» (угаданных цифр на правильных позициях) и «коров» (угаданных, но стоящих не на своих местах) [1]. На первый взгляд, метод решения кажется очевидным: задаешь вопросы, исключаешь невозможные варианты и постепенно находишь загаданное число. Однако, как показывает практика, некоторые стратегии работают лучше других. Почему? Ответ лежит в области математики, а именно — в теории информации.

Каждый вопрос (и ответ на него) несет информацию, которая сокращает неопределенность. Но не все вопросы одинаково полезны. Некоторые дают мало информации, оставляя игрока почти в том же положении, что и раньше, а другие позволяют сразу избавиться от множества возможных вариантов.

Оптимальная стратегия опирается на энтропию — ключевую концепцию теории информации. Энтропия измеряет, насколько сильно наши знания о загаданном числе меняются после получения ответа. Чем больше сокращается неопределенность (в среднем), тем лучше вопрос.

Что полезно знать о теории информации в контексте игры

Математическая теория информации стала возможна после того, как осознали, что количество информации можно задать числом [2]. Для этого необходимо закодировать информацию в виде последовательности нулей и единиц. Количество знаков этой последовательности может служить мерой количества информации. Ответ на вопрос, допускающий лишь два ответа «да» и «нет», а в остальном произвольный, служит единицей для измерения количества информации.

Каждая цифра числа, записанного в двоичной системе счисления, содержит одну единицу информации. Отсюда и название единицы информации — бит (от английского binary digit —двоичная цифра).

Если в заданном множестве Н, содержащем N элементов, выделен какой-то элемент х, о котором заранее известно лишь, что он принадлежит множеству Н, то, чтобы найти х, необходимо получить количество информации, равное log₂N битам. Эту формулу обычно называют формулой Хартли.

При неудачном выборе вопросов новой является лишь какая-то доля информации, а другая ее часть содержится в информации, полученной при ответе на предыдущие вопросы.

Формула Хартли исходит из молчаливого предположения о том, что все N элементов равновероятны. Однако такое предположение выполняется редко. В общем случае количество информации Н(ξ) можно найти по формуле Шеннона [3]:

(1) Н(ξ) = p₁log₂(1/p₁) + p₂log₂(1/p₂) + … + p_Nlog₂(1/p_N),

где ξ – неизвестный элемент множества Н = {х₁, х₂, …, х_N}, то есть ξ – случайная величина, принимающая значения х₁, х₂, …, х_N, а р_k – вероятность того, что ξ принимает значения х_k (k = 1, 2, … N).

Следует стремиться к тому, чтобы утвердительные и отрицательные ответы были равновероятны. Если при фиксированном значении N распределение вероятностей (p₁, р₂, ..., р_N) отлично от равномерного, то сумма p₁log₂(1/p₁) + p₂log₂(1/p₂) + … + p_Nlog₂(1/p_N) меньше log₂N. Т. е., если о случайной величине ξ известно лишь, что она принимает N различных значений, то при наблюдении одного значения ξ наибольшую информацию мы получаем в том случае, если все возможные значения ξ равновероятны.

Формула (1) впервые использовалась еще в XIX веке в работах Больцмана, поэтому ее также называют формулой Больцмана–Шеннона. Больцман пришел к ней, занимаясь совсем другой задачей – изучением энтропии. Энтропия физической системы служит мерой неупорядоченности системы или мерой неопределенности состояния молекул, образующих систему.

Неопределенность есть не что иное, как недостаток информации, или отрицательная информация. И наоборот, информация есть не что иное, как убыль неопределенности. До наблюдения случайной величины ξ мы пребываем в полной неопределенности относительно того, какое из своих значений она может принять. После того, как наблюдение произведено, неопределенность устраняется. Наблюдение случайной величины ξ содержит Н(ξ) бит информации; поскольку эта информация позволила избавиться от неопределенности, существовавшей до наблюдения, естественно принять число Н(ξ) за меру этой неопределенности.

Таким образом, Н(ξ) можно рассматривать и как меру неопределенности, существовавшей до наблюдения случайной величины ξ. Эту меру неопределенности и принято называть энтропией. 

Итак, формула Шеннона (1) допускает следующую интерпретацию. Если случайная величина ξ принимает значения х₁, х₂, …, х_N с вероятностями р₁, р₂, …, р_N, то энтропию величины ξ (то есть меру неопределенности, существовавшей до наблюдения величины ξ), которую мы обозначили Н(ξ), можно вычислить по формуле (1).

Кодовый знак, который может принимать лишь два значения, содержит один бит информации только тогда, когда оба его значения равновероятны (то есть вероятность каждого из них равна ½), а во всех остальных случаях количество информации (h), содержащейся в таком знаке, меньше одного бита:

Итак, вопрос нужно задавать так, чтобы: 

• ответ на него давал максимальное количество информации;

• вероятности различных ответов были по возможности близкими;

• ответ не содержал информацию, полученную из предыдущих вопросов.

Исходная неопределенность и первый вопрос

Я не программист, поэтому использовал Excel. Впервые такое исследование я выполнил около 15 лет назад в версии 2007. Мне потребовались чудовищные формулы, чтобы справиться с задачей. Сейчас Excel шагнул далеко вперед, и чтобы сэкономить время на проведение исследования в версии 365, я решил привлечь ChatGPT. И не прогадал. Помимо удовольствия от самого исследовани, я получил эстетическое наслаждение от тех решений, на которые натолкнул меня ИИ. Любители Excel найдут диалоги с чатом и описание формул по ссылке.

Тайное число можно задумать 10*9*8*7 = 5040 способами (на первом месте может стоять любая из 10 цифр, на втором – любая из 9 оставшихся и т.д.). Поскольку вероятность быть задуманным любого из 5040 чисел одинакова, неопределенность (Н) можно вычислить по формуле Хартли: Н = log₂N. Перед началом игры неопределенность составляет log₂5040 = 12,30 бита информации.

Первый вопрос может быть любым, например, 0123, и на него возможны 14 ответов:

Здесь: р – вероятность ответа, Н – неопределенность, оставшаяся после выбранного ответа, h – количество информации, полученное, если реализовался тот или иной ответ. Наиболее вероятный ответ – 01, означающий, что из вопроса в тайное число входит лишь одна цифра, причем стоит она не на своем месте.

Ответ 01 подразумевает, что задуманным может быть одно из 1440 чисел, то есть неопределенность, оставшаяся после этого ответа, составляет log₂1440 = 10,49 бита, а информация, полученная при таком ответе, — 12,30 – 10,49 = 1,81 бита. Ответ 40 дает 12,30 бита информации, а неопределенности после него не остается. Поскольку вероятности ответов различны, количество информации, содержащееся в вопросе, определяется по формуле Шеннона (1). Первый вопрос дает 2,77 бита информации.

Оптимальный второй вопрос

При выборе второго вопроса следует руководствоваться тремя идеями сформулированными выше. На практике это означает, что в первом приближении вопрос должен допускать ответ 40. Про второе приближение я расскажу позже.

Правило формирования второго вопроса

Пусть на первый вопрос (0123) мы получили ответ 01. Для второго вопроса возьмем одну цифру из первого вопроса, поставим ее на новое место и добавим три новые цифры. Получим, например, 1456. Если на вопрос 1 был получен ответ 11, надо взять две цифры из первого вопроса, одну оставить на своем месте, вторую поставить на новое место и добавить две новые цифры, например, 0435.

Если на вопрос 1 был получен ответ 01, то оптимальный вопрос 2 1456 также вернет 14 ответов:

Неоптимальные вторые вопросы

Посмотрим, сколько информации дадут вторые вопросы, выбранные неоптимальным образом. Продолжим рассматривать вариант, где на первый вопрос 0123 получен ответ 01.

Например, вопрос 2 – 0123 (нижняя строка таблицы) дает ноль бит информации, так как на него возможен только один ответ, а для N = 1 log₂1 = 0. Вопрос 2 0132 дает 0,650 бит информации, вопрос 2 0145 – 2,530 бит информации. Разных оптимальных вопросов 1440, и каждый из них дает 2,859 бит информации (верхняя строка таблицы).

Видно, что еще 180 вопросов (например, 1045) дают почти столько же информации – 2,774 бит. Но этот вопрос не может дать ответа 40! Т. е. вопрос подготовлен с нарушением правила. Насколько велика разница между 2,859 и 2,774 бита? На первый взгляд, она не выглядит большой. С другой стороны, при самом неблагоприятном ответе на вопрос 2 1456 (01) останется 378 вариантов тайного числа (см. строку выделенную желтым на рис. 3), а при самом неблагоприятном ответе на вопрос 2 1045 (также 01) – 408 вариантов. На 8% больше! Это и есть цена второго по оптимальности вопроса.

Последующие вопросы

При подготовке третьего и последующих вопросов я использую мнемоническое правило. Составляю структуры возможных тайных чисел, удовлетворяющие ответам на предыдущие вопросы. После этого выбираю вопрос 3, используя ту структуру, которая содержит больше вариантов (оценку провожу на глазок). Поясню на примерах.

Пример 1. Первые два вопроса и ответа были следующими:

Первый вариант – единица не входит, тогда входит одна цифра из 023, одна – из 456, и две – из ранее не использовавшихся цифр 789. Записываю я это так:

Ориентировочное число вариантов = 3 (одна цифра из 023)*3 (одна из 456)*3 (две из 789) = 27.

Второй вариант - входит единица, тогда не входят ни 023, ни 456. Значит, входят 789. Получаем набор цифр тайного числа 1789. Структура, отвечающая этому набору, одна.

Очевидно, что вариант 1 более вероятен. Для вопроса 3 берем одну цифру из 023, одну из 456, две из 789. Располагаем цифры так, чтобы не было совпадений мест расположения с вопросом 1 и вопросом 2.

Ранее упоминавшееся второе приближение требует, чтобы цифры, которые ранее уже встречались (4 и 2), были размещены в вопросе на новых позициях, т. е. на 2-й и 4-й. Вопрос 3 7482 лучше, чем 2784. В первом случае 4 и 2 стоят на местах, которые в вопросе 1 и вопросе 2 они не занимали. В то же время в вопросе 3 2784 цифра 2 стоит на месте цифры 4 из вопроса 2. Ответ на вопрос 3 7482 содержит 2,958 бит информации, а ответ на вопрос 3 2784 – «только» 2,955.

Видно, что второе приближение дает совсем небольшой выигрыш.

Пример2. Первые два вопроса и ответа были следующими:

Первый вариант - входят 13, тогда не входят, ни 02, ни 45, а из оставшихся цифр входят две:

Количество структур равно числу сочетаний из 4 по 2 – шесть.

Второй вариант - входит одна цифра из 13, тогда входит одна – из 02, одна – из 45, и одна – из 6789:

Количество структур = 2*2*2*4 = 32.

Третий вариант - не входят 13, тогда входят и 02 и 45. Единственная структура – 0245.

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

Концовка

Когда тайных чисел остается мало (до 5-10), можно выписать их все и попытаться составить такой вопрос, который максимально разделит потенциальных кандидатов по разным ответам. В концовке вопрос не обязательно должен подразумевать ответ 40.

Допустим, после нескольких ходов у нас осталось шесть возможных чисел:

В качестве следующего вопроса можно выбрать одно из них. В этом случае вы не подберете вопрос так, чтобы все числа дали разные ответы. Но вы гарантированно закончите игру за два хода, если используете вопрос, который не дает ответа 40. ChatGPT подобрал мне и сами тайные числа, и вопрос, который разделяет их шестью разными ответами, – 0218:

После ответа мы точно знаем, какое число загадано.

Стратегия концовки может быть полезна и на ранних стадиях, если, например, на вопрос 1 вам стали известны три цифры загаданного числа. Добавление одной новой цифры (строка 2 на рис. 8) дает чуть меньше информации, чем добавление двух новых цифр (строка 1 таблицы):

Итак, мы рассмотрели, как математическое понятие количества информации определяет алгоритм игры. Мы сформулировали три простые эвристики:

• выбирай очередной вопрос так, чтобы среди ответов мог быть вариант 40;

• среди доступных выбирай вопрос, отвечающий за наибольшее число различных структур;

• в концовке ищи вопросы, которые разделяют тайные числа по различным ответам.

Если у вас есть идеи по улучшению стратегии, поделитесь ими в комментариях.

Другие алгоритмы

“Как выигрывать в игре “Быки и коровы” (Метод выбитых зубов)” на Хабре (этот алгоритм кажется мне наивным и неэффективным)

Александр Словеснов. Оптимальные алгоритмы в играх быки-коровы и мастермайнд 

(Меня заинтересовал представленный автором алгоритм Лармауса. Александр упомянул, что его описание можно найти в Интернете. Я попытался это сделать, но все ссылки вели только на работу самого Александра. Копнув глубже, я понял, что речь о стратегии доктора Лармута (Dr. Larmouth's Strategy), описанной в частности у Джона Фрэнсиса (см. следующую ссылку). Александр в рамках алгоритма говорит о минимизации некой функции, в то время как Дж. Фрэнсис явно указывает: the function to be minimised in this case, based on information theory…)

John Francis. Strategies for playing MOO, or “Bulls and Cows”

Стратегии №2 и №3 излишне сложны и  рассчитаны на вычислительные мощности компьютеров.

Литература и источники

1. Быки и коровы в Википедии

2. Альфред Реньи. Трилогия о математике. – М.: Мир, 1980. – 376 с. 

(В сборник включены научно-популярные произведения известного венгерского математика и популяризатора науки: «Диалоги о математике», «Письма о вероятности», «Дневник. — Записки студента по теории информации», а также четыре статьи: о теории вероятностей, о ее преподавании, о числах Фибоначчи и о математической теории «деревьев»).

3. Claude E. Shannon. A Mathematical Theory of Communication. – 1948.

(Вышла на русском языке в сборнике «Работы по теории информации и кибернетике». – 1963. Формула Шеннона рассматривается, начиная со стр. 259 издания на русском языке.)