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

Проба 3: 5461. 1 точное попадание. 3 совладения по значению.

Проба 4: 4165. 1 точное попадание. 3 совпадения по значению.

Проба 5: 4615. 2 точных попадания. 2 совпадения по значению.

Проба 6: 4651. 4 точных попадания. Игра окончена

Написать программу, имитирующую роль загадывающего, не составляет труда. Отгадывание головоломок, заданных машиной, — тоже развлечение, позволяющее отточить ум. Однако гораздо интереснее, если компьютер сможет выступать также и в роли отгадывающего, чтобы можно было сыграть несколько партий и определить победителя. Боб Кули из 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>} для наиболее удачной комбинации с четырьмя точными совпадениями. Введем обозначение

Теперь в качестве пробы G_i выберите комбинацию С, минимизирующую S_c (при наличии нескольких таких С выберите комбинацию из P_i?1, если это возможно; если же нет — делайте случайный выбор). Вы, вероятно, уже заметили, что этот алгоритм можно использовать для предварительного анализа великого комбинатора, так чтобы в процессе игры не был нужен никакой анализ комбинаций. Проделав такой анализ, Кнут показал, что оптимальной первой пробой при использовании его стратегии будет ххуу, где х ? у. Для проверки своей программы посмотрите, начинает ли она с пробы ххуу.

Тема. Напишите программу, которая будет разыгрывать партии великого комбинатора. Реализуйте стратегию отгадывания, так чтобы машина могла загадывать коды и отгадывать их. Кроме собственно игры ваша программа может накапливать сведения о мастерстве разных игроков. Ваш местный великий комбинатор, возможно, пожелает приехать в Англию на очередной чемпионат. С вашей программой, как и другими игровыми программами, вероятно, будет иметь дело не слишком искушенный пользователь. Поэтому следует позаботиться о том, чтобы ввод данных был простым и естественным, а вывод понятным и красиво оформленным.

Рекомендации исполнителю. Единственная серьезная проблема в этом этюде связана с эффективностью при программировании алгоритма анализа — эффективностью как по памяти, так и по времени. Особенно длинный внутренний цикл требуется для второй стратегии. Заметьте, что комбинации суть не что иное, как числа, записанные по основанию 6 (но вместо цифр от 0 до 5 используются цифры от 1 до 6). Избранный вами язык, вероятно, повлияет на выбор представления, но старайтесь все же построить эффективный внутренний цикл для алгоритма угадывания кода.

Инструментовка. Для этой задачи пригоден почти любой процедурный язык с достаточно развитыми структурами данных. Эта программа в значительной мере — упражнение по структурному программированию.

Длительность исполнения. Одному исполнителю на 2 недели.

Развитие темы. Наиболее очевидное расширение — это изменение множества цифр, из которых составляется код, или количество цифр в коде. Более развитая версия великого комбинатора допускает коды из пяти цифр от 1 до 8. Слишком большое значение любого из двух параметров может привести к непомерному росту времени работы, однако ни один из алгоритмов не зависит сколько-нибудь существенно от чисел 6 и 4. Программа без всякого труда могла бы читать объем словаря (число различных цифр) и длину кода в качестве исходных данных и соответствующим образом изменять свои алгоритмы анализа.

Литература

Алеф₀ (Aleph₀). Computer Recreations, Software — Practice and Experience, 1, pp. 201–204, 1971.

Mastermind. Invicta Plastics, Ltd. Oadby, Leicester, England.

Описывается исходная игра. Она сильно похожа на некоторые традиционные игры; вся Англия увлечена этой игрой из-за ее простоты.

Кнут (Knuth D. E.). The Computer as Master Mind. He опубликовано, 1976.

Кнут утверждает, что путем исчерпывающего анализа различных случаев можно показать оптимальность его стратегии в указанном выше смысле. Однако останется ли она оптимальной при изменении объема словаря и длины кода? И какая стратегия будет оптимальной, если мы стремимся свести к минимуму ожидаемое число проб, а не максимальное?

Таненбаум (Tanenbaum A. S). Computer Recreations: A Heuristic for Playing Jotto, Software — Practice and Experience, 3, pp. 397–399, 1973.

В обеих статьях из журнала Software — Practice and Experience рассматриваются игры, аналогичные великому комбинатору; описываются реальные программы и предлагаются некоторые стратегии машинной игры. Было бы, наверное, очень интересно организовать турнир между различными эвристиками.

Уэллс (Wells D.). Mastermind. Games and Puzzles, 23, pp. 10–11, March/April 1974.

Games and Puzzles — широко известный английский журнал, посвященный играм, головоломкам и всевозможным интеллектуальным развлечениям. По стилю он далек от математического издания: в нем вы скорее найдете исторический, тематический, эстетический и стратегический разбор абсолютно любого приятного времяпрепровождения (ну, почти любого), не требующего ничего, кроме обыкновенного стола. Постоянно публикуются новые и старые игры. А из головоломок вы почерпнете немало глубоких алгоритмических проблем. Короче говоря, это весьма ценное приобретение для любителей убить время.