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

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

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

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

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

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

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

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

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