Struttura / algoritmo per la soluzione di gioco con le carte sovrapposte

Question

Si consideri un gioco di carte lungo le linee di Tower Solitaire, Tripeaks, o Fairway Solitaire: il tavolo è costituito da un numero di carte che sono immediatamente disponibili, ognuno dei quali potrebbe essere coprono altre carte sotto di essa (che li hanno bloccati vengano riprodotti) . Hai una carta "fondazione", ed è possibile rimuovere una carta dal tavolo se è esattamente un rango sopra o sotto la carta di fondazione, a quel punto diventa la tua nuova carta di fondazione. Si dispone di un numero limitato di carte di sostituzione a cui attingere quando non si può giocare una carta dal tavolo, quindi in genere si desidera riprodurre la sequenza più lunga di carte possibile.

In primo luogo, come è possibile rappresentare la scheda per facilitare la ricerca di una soluzione? In secondo luogo, l'algoritmo usereste per trovare la sequenza più lunga giocabile?

Esempio:

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

Schede sulle carte del blocco di fondo sulla parte superiore di essere rimosso: Non è possibile rimuovere 4a fino a quando entrambi 3 e 2 sono andati. Assumendo che il carta di partenza è un asso, il gioco ottimale qui sarebbe 2, 3, 4b, 5, 4a. (Si può anche giocare 2, 3, 4 bis, invece, ma non è così buono.)

Credo che questo dovrebbe essere rappresentato come una sorta di grafo orientato. Si potrebbe avere bordi da 3 e da 2 a 4 bis e 4 ter da 2 e al 5, ma avresti anche bordi tra il 3 e 2 e tra il 4a e 5, dal momento che uno è giocabile dopo l'altro? In caso affermativo, il fatto che essi possono essere riprodotti in qualsiasi ordine (3 allora 2 o 2 quindi 3) formano un ciclo nel grafo che impedisce di utilizzare algoritmi efficienti "più lungo percorso"? (Credo che trovare il percorso più lungo in un grafico è NP-completo se il grafico contiene cicli.)

Answer 1

Che cosa se rappresenti questo come un grafico del gioco-stato (con i potenziali prossimi stati calcolati al volo) - che non avrà cicli, che significa che è un DFS dritto sui potenziali stati del gioco (che potrebbe essere molto numerosi ancora) dal punto di partenza.

Answer 2

Il punto è costruire un grafo orientato aciclico con il minor numero di nodi possibili, i cui nodi bloccherebbe completamente lo spazio del fenomeno. Quindi è possibile eseguire il solito algoritmo.

Suggerisco una codifica in base alla forma della struttura delle carte rimanenti al tavolo.

I primi dati dello stato potrebbe essere l'ID univoco del più a sinistra - carta superiore. (Come ad esempio 4a, è unico nel senso che v'è una sola carta 4a). Il resto della forma può essere rappresentato da uno dei -1,0,1 per ogni carta disponibili (carta che è pronto per essere portato) descrive se la prossima carta a sinistra è sullo stesso 'livello' o è Sali profondo o superiore. (Questo sta sfruttando l'ipotesi che una scheda si sovrappone solo 2 altre carte e che la struttura assomiglia a quella che hai dato nell'esempio).