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

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

Рисунок 19.2. Пример возможного хода с перемещением карт из одного столбика в другой. Карты, начиная с тройки треф и ниже в том же порядке, накладываются поверх четверки треф. Остальные столбики не показаны.

Игра кончается, когда не остается ни одного допустимого хода и ни одну карту нельзя положить в счетную стопку. Счет игры равен суммарному числу карт в счетных стопках. Как выяснилось, эта игра весьма популярна в Лас Вегасе (известном также под названием Город Просаженных Получек[29]). Колоду карт в казино можно получить по цене 1 долл. за карту (плюс 3 долл. за право начать игру), игрок же получает 5 долл. за каждую карту, вошедшую в счет. Таким образом, при счете 11 карт (за что причитается 55 долл.) игрок остается при своих, а каждая карта сверх того — его чистый выигрыш. Сомнительно, чтобы в казино действительно предлагались такие условия, но если это так, то мы вправе Подозревать, что владельцы должны иметь чудовищные прибыли. Каково в действительности ожидаемое число карт в счетных стопках? Насколько нечестными были бы при данных условиях доходы владельцев казино?

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

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

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

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

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

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

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

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

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

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

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

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