Structure/algorithme pour résoudre le jeu avec des cartes qui se chevauchent

Question

Considérons un jeu de cartes sur le modèle de Tower Solitaire, Tripeaks, ou Fairway Solitaire: la table se compose d'un certain nombre de cartes immédiatement disponibles, chacune pouvant couvrir d'autres cartes en dessous (les empêchant d'être joués). Vous avez une carte "fondation", et vous pouvez retirer une carte de la table si elle se trouve exactement au-dessus ou au-dessous de votre carte de fondation, à quel moment elle devient votre nouvelle carte de base. Vous avez un nombre limité de cartes de remplacement à tirer quand vous ne pouvez pas jouer une carte depuis la table, donc vous voulez généralement jouer la plus longue séquence de cartes possible. D'abord, comment représenteriez-vous le conseil pour faciliter la recherche d'une solution? Deuxièmement, quel algorithme utiliseriez-vous pour trouver la plus longue séquence jouable?

Exemple:

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

cartes sur les cartes de bloc en bas au-dessus d'être retiré: vous ne pouvez pas retirer 4a jusqu'à ce que les 3 et 2 sont partis. En supposant que votre carte de départ est un as, le jeu optimal ici serait 2, 3, 4b, 5, 4a. (Vous pouvez jouer 2, 3, 4a à la place, mais ce n'est pas aussi bon.)

Je suppose que cela devrait être représenté comme une sorte de graphe orienté. Vous auriez des bords de 3 et 2 à 4a et de 2 et 4b à 5, mais auriez-vous aussi des bords entre 3 et 2 et entre 4a et 5, puisque l'un est jouable après l'autre? Si oui, est-ce que le fait qu'ils puissent être joués dans n'importe quel ordre (3 puis 2, ou 2 puis 3) forme un cycle dans le graphique qui vous empêche d'utiliser les algorithmes efficaces du "plus long chemin"? (Je crois que trouver le plus long chemin dans un graphe est NP-complet si le graphe contient des cycles.)

Answer 1

Et si vous représentez cela comme un graphe d'états de jeu (avec les prochains états potentiels calculés à la volée) - ça va pas de boucles, ce qui signifie qu'il s'agit d'un DFS direct sur les états potentiels du jeu (qui pourrait être encore assez nombreux) depuis le point de départ.

Answer 2

Le but est de construire un graphe acyclique orienté avec le plus petit nombre possible de nœuds, dont les nœuds captureraient complètement l'espace d'état du problème. Ensuite, vous pouvez exécuter votre algorithme habituel.

Je suggère un encodage basé sur la forme de la structure des cartes restantes à la table.

Les premières données dans l'état peuvent être l'ID unique de la carte la plus à gauche. (comme 4a par exemple, il est unique dans un sens qu'il n'y a qu'une seule carte 4a). Le reste de la forme peut être représenté par un de -1,0,1 pour chaque carte disponible (carte qui est prête à être prise) décrivant si la prochaine carte à gauche est au même niveau ou s'il s'agit d'un niveau plus profond ou plus haut. (Ceci exploite l'hypothèse qu'une carte chevauche seulement 2 autres cartes et que la structure ressemble à celle que vous avez donnée dans l'exemple).