Structure / algorithme pour la résolution de jeu avec des cartes qui se chevauchent

Question

Pensez à un jeu de cartes le long des lignes de Solitaire Tour, Tripeaks ou Fairway Solitaire: la table se compose d'un certain nombre de cartes qui sont immédiatement disponibles, dont chacun pourrait être couvrant d'autres cartes en dessous (les bloquer d'être joué) . Vous avez une carte de « fondation », et vous pouvez retirer une carte de la table si elle est exactement un rang au-dessus ou en dessous de votre carte de fondation, à quel point il devient votre nouvelle carte de fondation. Vous avez un nombre limité de cartes de remplacement pour tirer lorsque vous ne pouvez pas jouer une carte de la table, de sorte que vous voulez généralement jouer la plus longue séquence de cartes possible.

Tout d'abord, comment voulez-vous représenter le conseil d'administration pour faciliter la recherche d'une solution? En second lieu, 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. Si l'on suppose votre carte de départ est un as, le jeu optimal serait ici 2, 3, 4b, 5, 4 bis. (Vous pouvez jouer 2, 3, 4 bis à 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 4b de 2 et 5, mais auriez-vous également des bords entre 3 et 2 et entre 4a et 5, puisque l'un est jouable après l'autre? Dans l'affirmative, le fait qu'ils peuvent être lus dans un ordre (3 puis 2, ou 2 puis 3) forment un cycle dans le graphique qui vous empêche d'utiliser les algorithmes efficaces « chemin le plus long »? (Je crois trouver le chemin le plus long dans un graphique est NP-complet si le graphique contient des cycles.)

Answer 1

Que faire si vous représentez cela comme un graphique de jeu-états (avec les états suivants potentiels calculés à la volée) - qui ne sera pas avoir des boucles, ce qui signifie qu'il est un DFS directement sur les états potentiels du jeu (ce qui pourrait être assez nombreux encore) à partir du point de départ.

Answer 2

Le but est de construire un graphe orienté acyclique ayant le moins de noeuds possibles, dont les noeuds seraient entièrement capturer l'espace d'état du problème. Ensuite, vous pouvez exécuter votre algorithme d'habitude.

Je suggère un codage en fonction de la forme de la structure des cartes restantes à la table.

Les premières données de l'état pourrait être l'ID unique de l'extrême gauche - carte supérieure. (Comme par exemple 4a, il est unique dans le sens où il n'y a qu'une seule carte 4a). Le reste de la forme peut être représentée par l'une des -1,0,1 pour chaque carte disponible (carte qui est prêt à prendre) décrivant si la prochaine carte à gauche est sur le même « niveau » ou il est d'un niveau plus profond ou plus. (Ce exploite l'hypothèse qu'une carte chevauche seulement 2 autres cartes et que la structure ressemble à celle que vous avez donné dans l'exemple).