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

Теперь в качестве пробы 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 — широко известный английский журнал, посвященный играм, головоломкам и всевозможным интеллектуальным развлечениям. По стилю он далек от математического издания: в нем вы скорее найдете исторический, тематический, эстетический и стратегический разбор абсолютно любого приятного времяпрепровождения (ну, почти любого), не требующего ничего, кроме обыкновенного стола. Постоянно публикуются новые и старые игры. А из головоломок вы почерпнете немало глубоких алгоритмических проблем. Короче говоря, это весьма ценное приобретение для любителей убить время.

24. Секрет фирмы, или Математический подход к раскрытию шифров