Структура/алгоритм решения игры с перекрывающимися карточками

Question

Рассмотрим карточную игру типа Tower Solitaire, Tripeaks или Fairway Solitaire:стол состоит из некоторого количества карт, которые доступны сразу же, каждая из которых может закрывать другие карты под собой (блокируя их игру).У вас есть одна «основная» карта, и вы можете удалить карту со стола, если она ровно на один ранг выше или ниже вашей базовой карты, и в этот момент она становится вашей новой базовой картой.У вас есть ограниченное количество замещающих карт, из которых вы можете взять, когда вы не можете разыграть карту со стола, поэтому обычно вам нужно разыграть как можно более длинную последовательность карт.

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

Пример:

  -4a- -5-
-3-  -2- -4b-

Карты внизу блокируют карты сверху от удаления:вы не можете удалить 4a, пока не исчезнут и 3, и 2.Если ваша стартовая карта — туз, оптимальной игрой здесь будет 2, 3, 4b, 5, 4a.(Вместо этого вы можете сыграть 2, 3, 4а, но это не так хорошо.)

Полагаю, это следует представить в виде некоего ориентированного графа.У вас будут ребра от 3 и 2 до 4a и от 2 и 4b до 5, но будут ли у вас также ребра между 3 и 2 и между 4a и 5, поскольку одно можно играть за другим?Если да, то будет ли тот факт, что их можно воспроизводить в любом порядке (3, затем 2 или 2, затем 3), образовать цикл в графе, который помешает вам использовать эффективные алгоритмы «самого длинного пути»?(Я считаю, что поиск самого длинного пути в графе является NP-полным, если граф содержит циклы.)

Answer 1

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

Answer 2

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

Я предлагаю кодировку, основанную на форме структуры остальных карт за столом.

Первыми данными в состоянии может быть уникальный идентификатор самой левой-самой верхней карты.(например, 4а, он уникален в том смысле, что существует только одна карта 4а).Остальная часть фигуры может быть представлена ​​одним из значений -1,0,1 для каждой доступной карты (карты, которую можно взять), описывающей, находится ли следующая карта слева на том же «уровне» или на одном уровне. глубже или выше.(При этом используется предположение, что одна карта перекрывает только две другие карты и что структура выглядит так, как вы указали в примере).