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

Анализ пасьянса

Каждой первоначальной раскладке соответствует в точности один оптимальный результат, хотя достичь его можно при различных последовательностях ходов. По-видимому, существует некоторая очень сложная вероятностная функция для вычисления ожидаемого значения оптимального результата. Но даже если бы удалось явно выписать эту функцию, она, несомненно, содержала бы столь большое количество членов, что вычислить ее было бы делом крайне затруднительным. Нельзя ли вместо этого попытаться сыграть достаточно много партий и извлечь интересующую статистику из полученных таким образом результатов? Эта идея применения моделирования для получения результата, который теоретически может быть непосредственно вычислен, уже встречалась в других главах книги именно потому, что, как и в данном случае, превращение компьютера в модель интересующего нас реального процесса оказывается весьма плодотворным. Какова необходимая последовательность действий при моделировании пасьянса? Во-первых, нужны подпрограммы для получения первоначальной раскладки, для проверки существования возможных ходов в данной позиции, для перемещения карт, для переворачивания верхней карты стопки, для перекладывания карты в счетную стопку — словом, процедуры, реализующие явный процесс раскладывания пасьянса. При помощи этих процедур можно вычислить результат любой заданной последовательности ходов. Для того чтобы найти оптимальный результат, реализуем на базе этих процедур стратегию поиска. После сдачи карт получаем некоторую начальную позицию. Стратегия поиска состоит в выполнении для каждой позиции, получающейся в ходе игры, следующих действий:

Подсчитать, сколько возможных ходов имеется для данной позиции. Их всегда не более семи.

Если возможных ходов нет, то данная последовательность ходов закончена, и можно записать ее счет. Установить новую текущую позицию, взяв верхний элемент со стека позиций, и возвратиться к началу цикла. Если стек позиций пуст, то закончить поиск.

Если есть только один ход, то выполнить его и вернуться к началу цикла.

Если ходов несколько, то упорядочить их (способ упорядочения не играет роли), записать в стек позиций текущую позицию, упорядоченный список возможных ходов, а также тот факт, что первый ход уже сделан. Выполнить первый ход и возвратиться к началу цикла. Заметим, что в шаге один, если позиция была взята со стека, неявно предполагается, что при подсчете числа возможных ходов вначале всегда ищется частично завершенный список возможных ходов.

Эта стратегия осуществляет поиск «сначала в глубину» по всем возможным последовательностям ходов с запоминанием еще не исследованных позиций в стеке. Поскольку проверяются все возможные последовательности ходов, то данная стратегия гарантирует нахождение некоторой, быть может не единственной, оптимальной последовательности.

Одна из неприятных для игрока особенностей этого пасьянса состоит в том, что довольно часто сразу после первоначальной раскладки не оказывается вообще ни одного возможного хода. Раскладка карт — это лишь некоторый сложный способ тасования. Несмотря на значительную вероятность быстрого окончания игры, следует ожидать все же, что дерево позиций может вырасти до очень больших размеров. Но дерево это на деле является графом, поскольку к одной и той же позиции вполне можно прийти после различных последовательностей ходов. Если некоторая позиция уже была однажды исследована, нет нужды рассматривать ее снова. Оптимальный результат игры не зависит от порядка ходов или от конкретной последовательности ходов, ведущей к нему. Если все уже исследованные позиции запоминать, то каждую вновь возникшую позицию можно во избежание повторной обработки сравнивать с этими старыми позициями. Сохранять нужно только сами позиции, без списка возможных ходов. Естественно, при этом возникает проблема поиска в множестве старых позиций.

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

Указания исполнителю. Организация карт в представлении позиции, а также способ хранения старых позиций решающим образом определяют уровень эффективности программы. Если позиция является текущей или находится в стеке, то для нее должно быть известно состояние всех стопок и соответствующих им столбиков, а также счетных стопок. Позиция в стеке должна содержать, кроме того, список еще не проверенных ходов. Для ускорения поиска возможных ходов нужно иметь вектор состояния для всех карт, в котором должны быть такие признаки карты: лежит ли она рубашкой вверх, находится ли уже в счете, лежит ли рубашкой вниз внутри столбика (какого именно?), лежит ли рубашкой вниз в низу столбика (какого именно?). Быть может, вы сумеете придумать другую структуру данных, обеспечивающую быстрое нахождение возможных ходов. В любом случае при запоминании старой позиции часть информации, как уже использованную, можно отбросить, экономя таким образом память.

Здесь потребуется два специальных алгоритма. Во-первых, как реализовать тасование карт в ЭВМ? Вот процедура, предложенная Кнутом. Пусть rand52 — функция, генерирующая случайные целые числа, равномерно распределенные в отрезке от 1 до 52. Поместите все карты в массив карта длины 52; как в нем расположены карты вначале — не имеет значения. После этого для i от 1 до 52 поменяйте местами элементы карта[i] и карта[rand52], каждый раз заново обращаясь к функции rand52. Одного такого тасования будет достаточно.

Во-вторых, как находить старые позиции? Это классическая задача поиска в растущей базе данных. Очевидным решением тут представляется хеш-таблица, где ключом поиска служит вся позиция. Поскольку полное сравнение двух позиций на равенство, скорее всего, обойдется слишком дорого, то разумно, по-видимому, будет применить виртуальный хеш-код. Пространство, отведенное для хранения старых позиций, может переполняться, поэтому вы должны уметь время от времени освобождать его. Наилучший способ освобождения памяти состоит, пожалуй, в том, чтобы иметь при каждой позиции счетчик, показывающий, сколько раз к ней обращались, и отбрасывать каждый раз те позиции, которые участвовали реже всего. Другой способ, который можно использовать и в сочетании с первым, — хранить список всех старых позиций и всякий раз, когда ищется какая-либо позиция, перемещать ее в голову списка. Когда придет время отбросить часть позиций, то кандидатами на уничтожение будут позиции в хвосте списка, поскольку к ним дольше всего не было обращений. Принятый вами способ отбрасывания старых позиций окажет влияние на выбор стратегии поиска, и наоборот. Заметим, что, хотя алгоритм отбрасывания старых позиций и не влияет на правильность программы анализа пасьянсов, тем не менее он может существенно ее замедлить.

Инструментовка. Эта задача требует средств для удобной работы со структурами данных умеренной сложности. В интересах эффективности выделение и освобождение памяти не следует доверять системе, так что Снобол, видимо, не подойдет. Претендентами могут быть языки Алгол W, Паскаль, PL/I, Лисп и даже Кобол. Вы сможете оценить достоинства структур данных, определяемых программистом, если попытаетесь решить эту задачу сначала на одном из упомянутых выше языков, а потом еще раз на языке типа Фортран или XPL, в которых сложные структуры данных приходится представлять при помощи параллельных массивов.

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

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

Оглавление книги