Пасьянс «Косынка»

Косынка (также — «Клондайк») — старинный пасьянс. Играется одной колодой в 52 карты. Вы можете использовать правый клик мышки, чтобы открытые на столе карты попали в дом. Количество прокручиваний колоды в нашей версии пасьянса Косынка - бесконечно. Вам нужно постараться разложить все карты за минимальное количество ходов.

Сходимость пасьянса "Косынка"

Существует мнение, что любой пасьянс при правильном складывании сходится. Нет, это в корне неверно и если вы возьмете колоду карт и разложите её на столе в 7 стопок от 1 до 7 карт, а остальные положите рядом, то уйдет немало раздач, прежде чем у Вас сойдется хотя бы одна из них. Можно сказать, что пасьянс Косынка при случайном раскладе карт является несходимым :)

Существует математическая модель, который мы пользуемся при раздаче карт, по которой наша Косынка сходится почти всегда (99%). Хотя мы и пишем 100%, это не совсем так и если Вы будете играть онлайн в Косынку, то в 1 случае из 100 Вам представится возможность в этом убедиться.

Если при раздаче открытыми на столе или в закрытой колоде находятся 4 туза, то пасьянс сходится на 100%.

Оценить сходимость случайного расклада онлайн пасьянса Косынка методом перебора - достаточно трудоемкая компьютерная задача.

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

Существует ошибочное мнение, что пасьянс «Косынка» сходится всегда. Я думаю, вызвано это версией в ОС Windows, в которой расклады уже заложены, а не генерируются каждый раз.

Вопрос сходимости возник при создании сайта с пасьянсами, для которого нужны были расклады, выдаваемые пользователям. Для начала мы решили написать один из самых простых и распространенных вариантов игры — «Косынку» и не найдя готовую базу, стали генерировать случайные расклады. Написав JS код для игры мы обнаружили, что сходятся случайные расклады очень редко. На ~50 игр у нас сошлась только одна. Подсовывать пользователям пасьянс, который не сходится — не самый удачный вариант для сайта, поэтому стали искать пути выхода.

Выход первый — это забрутфорсить случайный расклад и определить сходимость. Помимо сложности алгоритма этот вариант еще и требовал каких-то неимоверных вычислительных мощностей, примерно, как обсчет партии в шашки. (В среднем пасьянс сходится за чуть более 100 ходов, при этом в процессе игры не всегда нужно выкладывать на стол карту). Этот вариант отпал.

Тогда решили написать правила для генератора пасьянса, посчитав что это будет более простой путь. Напомню, что в «Косынке» участвует 52 карты от двойки до туза 4-х мастей. Закрыты на столе в 7 стопках 21 карта, открыты на столе 7 и 24 карты в колоде, которую можно крутить. Нас интересуют для обсчета карты, которые в колоде и уже открытые на столе (всего 31 карта), т.к. именно ими игрок оперирует.

Правило при генерации добавили такое — среди карт в колоде и открытых на столе (31 карта) должна быть одна полная комбинация красных карт от двойки до туза и одна комбинация черных карт от двойки до туза. После применения такого правила генератор стал выдавать 1 из 150 раскладов удовлетворяющих условию (149 соответственно откидывал).

Сходимость таких раскладов резко повысилась и стала ~90% (по данным на 10.000 раскладов — 979 не сошлось ни разу, 9021 сошлось). Проверить такое количество раскладов нам помог краудсорсинг и наши пользователи, которые играли в пасьянс «Косынку».

P.S.: Мы пробовали разные правила применять при генерации, но расклады получались либо совсем простые и играть в них было не интересно (когда генератор выдавал нам 1 расклад из 1.000), либо их сходимость не поднималась до приемлемых значений. Спасибо за потраченное время и если Вы знаете правило (универсальный алгоритм) определения сходимости — буду рад прочитать про него.

Если про Косынку Вам всё понятно, можете разложить Паук одной масти или прочитать про сходимость Паука