Этюды для программистов

Правила великого комбинатора крайне просты. Один из игроков, загадывающий, записывает секретную комбинацию из любых четырех цифр от 1 до 6 (повторения допускаются), называемую кодом. Второй игрок, отгадывающий, пытается раскрыть код, высказывая разумные предположения, называемые пробами. Каждая проба, как и код, представляет собой произвольную комбинацию из четырех цифр в диапазоне от 1 до 6. Отгадывающий игрок сообщает пробу загадывающему, и тот должен ответить, сколько цифр в пробе совпадает с цифрами кода как по положению, так и по величине и сколько из остальных цифр пробы входят в код, но стоят на другом месте. Так, на пробу 1123 при коде 4221 будет получен ответ: «Одна цифра совпадает и стоит на том же месте, и еще одна совпадает, но стоит на другом месте». Тур игры продолжается до тех пор, пока отгадывающий не назовет пробу, в точности совпадающую с кодом, т. е. пока не отгадает код. После этого игроки меняются ролями и проводят еще один тур. Победителем считается тот из игроков, кто определит код противника за меньшее число проб. Хотя здесь не последнюю роль играет везенье, тем не менее игрок, систематически делающий правильные умозаключения из получаемой информации, должен иметь лучшие результаты по итогам нескольких партий. Практически вы должны пытаться выводить из ответов на ваши пробы отрицательные следствия относительно того, какие коды невозможны; психологические тесты показывают, что для многих людей это оказывается совсем не просто. В табл. 23.1 приведен один полный тур.

Написать программу, имитирующую роль загадывающего, не составляет труда. Отгадывание головоломок, заданных машиной, — тоже развлечение, позволяющее отточить ум. Однако гораздо интереснее, если компьютер сможет выступать также и в роли отгадывающего, чтобы можно было сыграть несколько партий и определить победителя. Боб Кули из Lawrence Livermore Laboratory и Д. Кнут разработали довольно близкие стратегии, позволяющие ЭВМ достигнуть высокого класса игры. Центральное место в обеих стратегиях занимает идея пространства решений. Начальное пространство решений Р₀ состоит из всех возможных кодов (и имеет, следовательно, б4 элементов); после i-й пробы G_i пространство P_i состоит из всех тех членов пространства P_i−1, которые не опровергаются ответом R_i. Иными словами, пространство P_i — это множество всех комбинаций, которые все еще могут быть кодом; задача отгадывающего — свести пространство к одному элементу.

Первая стратегия, предложенная Кули, несколько проще. Пробой Gi пусть будет любая случайно выбранная комбинация с одной повторяющейся цифрой, например 4311, 6552 или 1335. Выполните эту пробу и постройте пространство P_i на основе ответа R_i. Новая проба G_i+1 ищется по пространству Р_i, i ≥ 1, путем поочередного сравнения всех комбинаций С из P_i с пробой G_i. В качестве следующей пробы выбирается наименее похожая на G_i комбинация С. Мерой сходства служит число точных совпадений, а в случае равенства — число цифр, совпадающих по значению, но расположенных по-другому. Так, среди трех комбинаций 2641, 2356 и 1345 наиболее похожей на 2345 будет 1345, а 2641 — наименее похожей. Если имеется несколько наименее похожих комбинаций, то можно выбрать любую кандидатуру случайным образом. Тур прекращается, когда будет получен ответ «четыре точных попадания», и, разумеется, в случае пространства из одного элемента в качестве следующей пробы всегда надо брать этот элемент. Как показывают эксперименты, размеры пространства решений сокращаются после каждой пробы примерно в 4 раза и никогда не требуется более шести проб.

Вторая стратегия предложена Дональдом Кнутом. Он утверждает, что она минимизирует наибольшее число проб, необходимых для нахождения кода; никакой код не требует более пяти проб. В основе алгоритма лежит наблюдение, что нам хотелось бы сделать пространство P_i как можно меньше. Следовательно, мы выбираем пробу G_i, минимизирующую |P_i| по всем возможным ответам R_i. Кандидатом в G_i будет любая комбинация С. Попробуйте применить все возможные комбинации С в качестве проб к пространству P_i−1; пусть S_{c, <0,0>} обозначает число членов P_i−1, дающих в ответе нулевое число точных совпадений и нулевое Число совпадений только по цвету[38] S_{c, <0,1>} — число членов, дающих соответственно нуль и одно совпадение и т. д. до S_{c, <4,0>} для наиболее удачной комбинации с четырьмя точными совпадениями. Введем обозначение