Пасьянс "Лицом вверх" - PullRequest
Новая
       17

Пасьянс "Лицом вверх"

0 голосов
/ 31 января 2011

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

10 points for moving Aces to top
9 points for moving 2s to top
8 points for moving 3s to top
7 points for moving 4s to top
6 points for moving 5s to top
5 points for moving 6s to top
4 points for moving 7s to top
3 points for moving 8s to top
2 points for moving 9s to top
1 points for moving 10s or face-cards to top
2 points for freeing a "downcard" (face-down card on the table)
2 points for moving a card from the deck to the table
-2 points deducted for moving a card from the top to the table
-20 points deducted for flipping over the deck
Putting a card back to the top after moving it from the top to the table does not give double points.

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

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

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

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

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

Ответы [ 2 ]

3 голосов
/ 31 января 2011

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

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

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

1 голос
/ 31 января 2011

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

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

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

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

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

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

...