Первая стратегия, предложенная Кули, несколько проще. Пробой Gi пусть будет любая случайно выбранная комбинация с одной повторяющейся цифрой, например 4311, 6552 или 1335. Выполните эту пробу и постройте пространство Pi на основе ответа Ri. Новая проба Gi+1 ищется по пространству Рi, i ≥ 1, путем поочередного сравнения всех комбинаций С из Pi с пробой Gi. В качестве следующей пробы выбирается наименее похожая на Gi комбинация С. Мерой сходства служит число точных совпадений, а в случае равенства — число цифр, совпадающих по значению, но расположенных по-другому. Так, среди трех комбинаций 2641, 2356 и 1345 наиболее похожей на 2345 будет 1345, а 2641 — наименее похожей. Если имеется несколько наименее похожих комбинаций, то можно выбрать любую кандидатуру случайным образом. Тур прекращается, когда будет получен ответ «четыре точных попадания», и, разумеется, в случае пространства из одного элемента в качестве следующей пробы всегда надо брать этот элемент. Как показывают эксперименты, размеры пространства решений сокращаются после каждой пробы примерно в 4 раза и никогда не требуется более шести проб.
Вторая стратегия предложена Дональдом Кнутом. Он утверждает, что она минимизирует наибольшее число проб, необходимых для нахождения кода; никакой код не требует более пяти проб. В основе алгоритма лежит наблюдение, что нам хотелось бы сделать пространство Pi как можно меньше. Следовательно, мы выбираем пробу Gi, минимизирующую |Pi| по всем возможным ответам Ri. Кандидатом в Gi будет любая комбинация С. Попробуйте применить все возможные комбинации С в качестве проб к пространству Pi−1; пусть Sc, <0,0> обозначает число членов Pi−1, дающих в ответе нулевое число точных совпадений и нулевое Число совпадений только по цвету[38] Sc, <0,1> — число членов, дающих соответственно нуль и одно совпадение и т. д. до Sc, <4,0> для наиболее удачной комбинации с четырьмя точными совпадениями. Введем обозначение
Теперь в качестве пробы Gi выберите комбинацию С, минимизирующую Sc (при наличии нескольких таких С выберите комбинацию из Pi−1, если это возможно; если же нет — делайте случайный выбор). Вы, вероятно, уже заметили, что этот алгоритм можно использовать для предварительного анализа великого комбинатора, так чтобы в процессе игры не был нужен никакой анализ комбинаций. Проделав такой анализ, Кнут показал, что оптимальной первой пробой при использовании его стратегии будет ххуу, где х ≠ у. Для проверки своей программы посмотрите, начинает ли она с пробы ххуу.
Тема. Напишите программу, которая будет разыгрывать партии великого комбинатора. Реализуйте стратегию отгадывания, так чтобы машина могла загадывать коды и отгадывать их. Кроме собственно игры ваша программа может накапливать сведения о мастерстве разных игроков. Ваш местный великий комбинатор, возможно, пожелает приехать в Англию на очередной чемпионат. С вашей программой, как и другими игровыми программами, вероятно, будет иметь дело не слишком искушенный пользователь. Поэтому следует позаботиться о том, чтобы ввод данных был простым и естественным, а вывод понятным и красиво оформленным.
Рекомендации исполнителю. Единственная серьезная проблема в этом этюде связана с эффективностью при программировании алгоритма анализа — эффективностью как по памяти, так и по времени. Особенно длинный внутренний цикл требуется для второй стратегии. Заметьте, что комбинации суть не что иное, как числа, записанные по основанию 6 (но вместо цифр от 0 до 5 используются цифры от 1 до 6). Избранный вами язык, вероятно, повлияет на выбор представления, но старайтесь все же построить эффективный внутренний цикл для алгоритма угадывания кода.
Инструментовка. Для этой задачи пригоден почти любой процедурный язык с достаточно развитыми структурами данных. Эта программа в значительной мере — упражнение по структурному программированию.
Длительность исполнения. Одному исполнителю на 2 недели.
38
Здесь автор имеет в виду вариант той же игры, в котором вместо цифр используются фишки, окрашенные в шесть цветов. —