Начало
Учебные материалы
Mastermind
или...
ОПТИМАЛЬНЫЕ СТРАТЕГИИ
ДЛЯ ИГРЫ С УГАДЫВАНИЕМ
В игре, как и в музыкальном произведении, можно выделить тему
и мотивы. Причина успеха самых удачных игр часто состоит в
том, что они мастерски соединяют по-новому некоторые из давно
известных принципов построения игр. Как и в музыке, старая
идея, возрожденная в новом обличье, может выглядеть
привлекательней, чем мешанина свежеиспеченных новых веяний. В
середине 70-х годов широкую популярность в Англии получила игра
великий комбинатор (MastermindI), и она, похоже, станет
классикой. Вы и ваш компьютер получите большое удовольствие,
сыграв в нее.
Правила великого комбинатора крайне просты. Один из игроков,
Загадывающий, записывает секретную комбинацию из любых
четырех цифр от 1 до 6 (повторения допускаются), называемую
кодом. Второй игрок, отгадывающий, пытается раскрыть код,
высказывая разумные предположения, называемые пробами. Каждая
проба, как и код, представляет собой произвольную комбинацию
из четырех цифр в диапазоне от 1 до 6. Отгадывающий игрок
сообщает пробу загадывающему, и тот должен ответить, сколько
цифр в пробе совпадает с цифрами кода как по положению, так
и по величине и сколько из остальных цифр пробы входят в код,
но стоят на другом месте. Так, на пробу 1123 при коде 4221
будет получен ответ: «Одна цифра совпадает и стоит на том же
месте, и еще одна совпадает, но стоит на другом месте». Тур
игры продолжается до тех пор, пока отгадывающий не назовет
пробу, в точности совпадающую с кодом, т. е. пока не отгадает
код. После этого игроки меняются ролями и проводят еще один
тур. Победителем считается тот из игроков, кто определит код
противника за меньшее число проб. Хотя здесь не последнюю
роль играет везенье, тем не менее игрок, систематически
делающий правильные умозаключения из получаемой информации,
должен иметь лучшие результаты по итогам нескольких партий.
Практически вы должны пытаться выводить из ответов на ваши
пробы отрицательные следствия относительно того, какие коды
невозможны; психологические тесты показывают, что для многих
людей это оказывается совсем не просто.
Написать программу, имитирующую роль загадывающего, не
составляет труда. Отгадывание головоломок, заданных машиной, —
тоже развлечение, позволяющее отточить ум. Однако гораздо
интереснее, если компьютер сможет выступать также и в роли
отгадывающего, чтобы можно было сыграть несколько партий и
определить победителя. Боб Кули из Lawrence Livermore Laboratory и
Д. Кнут разработали довольно близкие стратегии, позволяющие
ЭВМ достигнуть высокого класса игры. Центральное место в обеих
стратегиях занимает идея пространства решений. Начальное
пространство решений `Р_0` состоит из всех возможных кодов (и
имеет, следовательно, `6^4` элементов); после i-й пробы `G_i`
пространство `P_i` состоит из всех тех членов пространства `P_{i-1}`,
которые не опровергаются ответом Ri. Иными словами, пространство
`P_i` — это множество всех комбинаций, которые все еще могут быть
кодом; задача отгадывающего — свести пространство к одному
элементу.
Первая стратегия, предложенная Кули, несколько проще. Пробой
`G_i` пусть будет любая случайно выбранная комбинация с одной
повторяющейся цифрой, например 4311, 6552 или 1335.
Выполните эту пробу и постройте пространство `P_i` на основе ответа
`R_i`. Новая проба `G_{i+1}` ищется по пространству `Р_i, i>=1`, путем
поочередного сравнения всех комбинаций `C` из `P_i` с пробой `G_i`.
В качестве следующей пробы выбирается наименее похожая на
`G_i` комбинация `C`. Мерой сходства служит число точных
совпадений, а в случае равенства — число цифр, совпадающих по
значению, но расположенных по-другому. Так, среди трех комбинаций
2641, 2356 и 1345 наиболее похожей на 2345 будет 1345, а 2641 —
наименее похожей. Если имеется несколько наименее похожих
комбинаций, то можно выбрать любую кандидатуру случайным
образом. Тур прекращается, когда будет получен ответ «четыре
точных попадания», и, разумеется, в случае пространства из
одного элемента в качестве следующей пробы всегда надо брать этот
элемент. Как показывают эксперименты, размеры пространства
решений сокращаются после каждой пробы примерно в 4 раза и
никогда не требуется более шести проб.
Вторая стратегия предложена Дональдом Кнутом. Он
утверждает, что она минимизирует наибольшее число проб,
необходимых для нахождения кода; никакой код не требует более пяти
проб. В основе алгоритма лежит наблюдение, что нам хотелось
бы сделать пространство `P_i` как можно меньше. Следовательно,
мы выбираем пробу `G_i`, минимизирующую `|P_i|` по всем
возможным ответам `R_i`. Кандидатом в `G_i` будет любая комбинация `C`.
Попробуйте применить все возможные комбинации `C` в качестве
проб к пространству `P_{i-1}`; пусть `S_{c, (:0,0:)}` обозначает число членов
`P_{i—1}`, дающих в ответе нулевое число точных совпадений и нулевое
Число совпадений только по цвету. `S_{c,(:0,1:)}` — число членов,
дающих соответственно нуль и одно совпадение и т. д. до `S_{c,(:4,0:)}` для
наиболее удачной комбинации с четырьмя точными совпадениями.
Введем обозначение\
`S_c = max_{(:i,j:)} S_{c,(:i,j:)}`.
Теперь в качестве пробы `G_i` выберите комбинацию `C`,
минимизирующую `S_c` (при наличии нескольких таких `C` выберите
комбинацию из `P_{i—1}`, если это возможно; если же нет —
делайте случайный выбор). Вы, вероятно, уже заметили, что этот алгоритм можно
использовать для предварительного анализа великого
комбинатора, так чтобы в процессе игры не был нужен никакой анализ
комбинаций. Проделав такой анализ, Кнут показал, что
оптимальной первой пробой при использовании его стратегии будет
`"xxyy"`, где `x!=y`. Для проверки своей программы посмотрите,
начинает ли она с пробы `"xxyy"`.
*Тема*. Напишите программу, которая будет разыгрывать партии
великого комбинатора. Реализуйте стратегию отгадывания, так
чтобы машина могла загадывать коды и отгадывать их. Кроме
собственно игры ваша программа может накапливать сведения
о мастерстве разных игроков. Ваш местный великий комбинатор,
возможно, пожелает приехать в Англию на очередной чемпионат.
С вашей программой, как и другими игровыми программами,
вероятно, будет иметь дело не слишком искушенный
пользователь. Поэтому следует позаботиться о том, чтобы ввод данных
был простым и естественным, а вывод понятным и красиво
оформленным.
*Рекомендации исполнителю.* Единственная серьезная проблема в
этом этюде связана с эффективностью при программировании
алгоритма анализа — эффективностью как по памяти, так и по
времени. Особенно длинный внутренний цикл требуется для
второй стратегии. Заметьте, что комбинации суть не что иное, как
числа, записанные по основанию 6 (но вместо цифр от 0 до 5
используются цифры от 1 до 6). Избранный вами язык, вероятно,
повлияет на выбор представления, но старайтесь все же построить
эффективный внутренний цикл для алгоритма угадывания кода.
