Алгоритм пасьянса «лицом вверх»

Question

Я разрабатываю программу для решения пасьянсов с максимально возможной результативностью. Игра засчитывается по следующей системе очков:

родовое слово

Карты из колоды переворачиваются по одной, и игрокам разрешается переворачивать колоду неограниченное количество раз (однако по-прежнему применяется вычет -20 баллов).

Я нашел различные руководства по стратегии, например Руководство по стратегии Клондайк для пасьянса Windows , но эти руководства предназначены для настоящих пасьянсов, в которых карты стола не известны.

Я хочу создать алгоритм для решения того, что я называю играми-пасьянсами «лицом вверх», в которых я должен знать колоду до того, как она раздается. Изменить: судя по статьям, приведенным в ответах ниже, эта игра получила название «вдумчивый пасьянс».

До сих пор моими идеями были: своего рода грубая форсировка, когда все возможные ходы проверяются и оцениваются; простой алгоритм, который просматривает каждый столбец индивидуально и пробует «лучший» ход; и, наконец, некий алгоритм, подобный поиску пути, где оценивается каждое движение и определяется лучший "путь".

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

Answer 1

Вам могут быть полезны следующие документы (похоже, это уже было сделано исследовательской группой).

Поиск пасьянса в реальном времени:

• http://web.engr.oregonstate.edu/~afern/paper / solitaire.pdf

Пасьянс: Человек против машины

• https://web.stanford.edu/~bvr/pubs/solitaire.pdf

Answer 2

Первое, что я попробую, - это наивный алгоритм просмотра вперед с фиксированным шагом, в котором на каждом шаге я анализирую все возможные шаги сгенерированного кода кода вперед и выбираю тот, который дает наивысший общий балл./ p>

Поэкспериментируйте с разными значениями кода n в одной и той же серии псевдослучайных пакетов и посмотрите, как (если вообще) улучшатся оценки за счет их увеличения.

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

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

И так далее, вы можете многое попробовать, и это звучит как отличное развлечение, так что наслаждайтесь.

Но если ничего не помогает, организуйте соревнование программистов.:)