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

Question

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

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

Пример:

  -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 для каждой доступной карты (карты, которая готова к извлечению), описывающей, находится ли следующая карта слева на том же «уровне», или это один уровень глубже или выше. (Это использует предположение, что карта перекрывает только 2 другие карты, и что структура выглядит так, как вы дали в примере).