В 1978 году, когда я только поступил в институт, игра «Быки и коровы» была невероятно популярна. Мне удавалось удерживать лидерство в сериях матчей благодаря авторскому алгоритму, в основу которого легла теория информации. Проанализировав современные публикации на эту тему, я не встретил аналогичного подхода, поэтому решил систематизировать свои знания и представить стратегию техническому сообществу.
<figure class="wp-block-image size-large">
<img src="https://habrastorage.org/r/w1560/getpro/habr/upload_files/cf1/0e0/844/cf10e08448fd1aad76ac7a3a710590e2.png" alt="Иллюстрация к игре Быки и коровы" loading="lazy">
</figure>
<p>«Быки и коровы» — это классическая логическая дуэль. Один игрок загадывает число, а другой пытается его вычислить, получая подсказки: «быки» (цифры угаданы и стоят на своих местах) и «коровы» (цифры угаданы, но позиция неверна). На первый взгляд, успех зависит от интуиции и метода исключения, однако наиболее эффективные решения лежат в плоскости высшей математики.</p>
<p>Ключ к победе — управление <strong>энтропией</strong>. Каждый ход должен максимально снижать неопределенность. Не все вопросы одинаково эффективны: одни почти не продвигают игрока к цели, тогда как другие позволяют мгновенно отсечь сотни невозможных комбинаций.</p>
<h2>Теория информации как фундамент стратегии</h2>
<p>Научный подход к передаче данных стал возможен, когда ученые научились измерять информацию количественно. Если закодировать данные в двоичной системе, мерой станет бит. Ответ на вопрос, подразумевающий лишь «да» или «нет», при условии равновероятности исходов, составляет ровно один бит.</p>
<blockquote>
<p>Согласно формуле Хартли, если в множестве <strong>H</strong> содержится <strong>N</strong> равновероятных элементов, то для поиска конкретного значения <strong>x</strong> требуется получить объем информации, равный <strong>log<sub>2</sub>N</strong> бит.</p>
</blockquote>
<p>При хаотичном подборе вопросов значительная часть получаемых данных оказывается избыточной, так как она дублирует уже известные факты. Чтобы максимизировать эффективность, необходимо опираться на формулу Шеннона (Больцмана–Шеннона), которая учитывает вероятность различных исходов:</p>
<p style="text-align: center;"><strong>H(ξ) = Σ p<sub>k</sub> log<sub>2</sub>(1/p<sub>k</sub>)</strong></p>
<p>Здесь <strong>H(ξ)</strong> — энтропия, отражающая степень неопределенности. Максимальное количество информации мы извлекаем в тот момент, когда вероятности всех возможных ответов максимально близки друг к другу. Другими словами, идеальный вопрос — это тот, который делит оставшееся пространство вариантов на максимально равные группы.</p>
<figure class="wp-block-image size-large">
<img src="https://habrastorage.org/r/w1560/getpro/habr/upload_files/92f/df5/27f/92fdf527fdffac000b81c6e6342b2f4a.jpeg" alt="График зависимости энтропии от вероятности событий" loading="lazy">
<figcaption>Рис. 1. Зависимость количества информации от вероятности исхода</figcaption>
</figure>
<p><strong>Золотые правила эффективного вопроса:</strong></p>
<ul>
<li>Ответ должен приносить максимальный объем новой информации.</li>
<li>Вероятности различных исходов (количества быков и коров) должны быть распределены равномерно.</li>
<li>Вопрос не должен дублировать информацию, полученную ранее.</li>
</ul>
<h2>Анализ стартовой позиции</h2>
<p>В классическом варианте (4-значное число без повторов) существует 10 * 9 * 8 * 7 = <strong>5040</strong> возможных комбинаций. Изначальная неопределенность составляет <strong>log<sub>2</sub>5040 ≈ 12,30 бита</strong>.</p>
<p>Допустим, первый вопрос — «0123». На него существует 14 вариантов ответов (от «00» до «40»).</p>
<figure class="wp-block-image">
<img src="https://habrastorage.org/r/w1560/getpro/habr/upload_files/9e3/392/c0c/9e3392c0c00d7186c1c31ff35a13aac4.jpeg" alt="Структура ответов на первый вопрос" loading="lazy">
<figcaption>Рис. 2. Вероятностная структура ответов на стартовый вопрос</figcaption>
</figure>
<p>Самый вероятный сценарий — ответ «01» (одна цифра угадана не на своем месте). Он оставляет 1440 вариантов (10,49 бит неопределенности). В среднем же первый ход дает около 2,77 бита информации.</p>
<h2>Выбор оптимального продолжения</h2>
<p>При поиске второго вопроса важно соблюдать баланс: использовать часть проверенных цифр, меняя их позиции, и вводить новые. Например, если на «0123» получен ответ «01», оптимальным ходом будет «1456». Мы взяли одну цифру из первого набора, переместили её и добавили три свежих значения. Такой подход обеспечивает максимальное «расслоение» оставшихся вариантов.</p>
<figure class="wp-block-image">
<img src="https://habrastorage.org/r/w1560/getpro/habr/upload_files/f58/dd2/ba6/f58dd2ba65414b8bc6d1e5a3dd0464e8.jpeg" alt="Сравнение оптимальных и неоптимальных вопросов" loading="lazy">
<figcaption>Рис. 3. Эффективность различных стратегий второго хода</figcaption>
</figure>
<p>Использование неоптимального вопроса (например, простой перестановки «0132») дает крайне мало новой информации — всего 0,65 бита против 2,86 бита при грамотной стратегии. Потеря эффективности на этом этапе увеличивает количество необходимых ходов на 8–10%.</p>
<h2>Эвристики для средней и финальной стадий</h2>
<p>Начиная с третьего хода, я рекомендую использовать метод структурного анализа. Мы мысленно (или в таблице) формируем группы чисел, подходящие под предыдущие ответы, и выбираем вопрос, который охватывает наиболее многочисленную структуру.</p>
<p><strong>Пример анализа:</strong><br>
Если после двух ходов мы понимаем, что единица либо не входит в число (и тогда у нас около 27 вариантов), либо входит (и тогда вариант всего один), логичнее направить следующий вопрос на проверку первой, более обширной группы.</p>
<h3>Эндшпиль: когда вариантов осталось мало</h3>
<p>Когда круг подозреваемых сужается до 5–10 чисел, тактика меняется. Теперь цель — не просто угадать, а задать вопрос, который разделит все оставшиеся числа по разным ответам. В финале вопрос даже не обязательно должен быть одним из потенциально загаданных чисел; его задача — служить идеальным «разделителем».</p>
<figure class="wp-block-image">
<img src="https://habrastorage.org/r/w1560/getpro/habr/upload_files/bd0/e1c/758/bd0e1c7582e1a54a977e83c429bda8c0.jpeg" alt="Разделение вариантов в финале" loading="lazy">
<figcaption>Рис. 4. Пример вопроса-разделителя для финальной стадии</figcaption>
</figure>
<h2>Резюме стратегии</h2>
<p>Математически обоснованный алгоритм победы сводится к трем эвристическим правилам:</p>
<ol>
<li><strong>Стремление к максимуму:</strong> Формируйте вопрос так, чтобы теоретически существовала возможность получить ответ «4 быка» (40).</li>
<li><strong>Структурный приоритет:</strong> Выбирайте комбинации, которые затрагивают наибольшее количество оставшихся числовых структур.</li>
<li><strong>Финальная сепарация:</strong> В конце игры ищите «вопрос-дискриминатор», который распределяет оставшиеся варианты по уникальным ответам.</li>
</ol>
<hr>
<h3>Дополнительные материалы</h3>
<ul>
<li><a href="https://ru.wikipedia.org/wiki/Быки_и_коровы">История и правила игры в Википедии</a></li>
<li>Альфред Реньи. «Трилогия о математике» — об основах теории информации в доступной форме.</li>
<li>Claude E. Shannon. «A Mathematical Theory of Communication» — фундаментальный труд для глубокого изучения темы.</li>
</ul>
