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

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

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

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

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

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

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

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

Литература

Гибсон (Gibson W. В.). How to Play Winning Solitaire. Frederick Fell, New York, NY, 1964.

Это единственная из известных автору книг о данном пасьянсе.