PacMan: quali tipi di euristica vengono principalmente utilizzati?

Question

Accanto A *, BFS, DFS e simili, quali sono le altre vie del bene conoscitiva algoritmi/euristica comunemente utilizzati in Pacman? Non penso che quelli che ho menzionato funzioneranno se ci sono più di un frutto da trovare per pacman.

Ho bisogno di alcuni buoni algoritmi di percorso di accertamento che PacMan può utilizzare per finire il labirinto con il minimo passo-count possibile. Ho provato a cercare una guida, ma finora non ho avuto fortuna. A * con Manhattan la distanza è menzionata ovunque ma funzionerà solo con labirinti con solo una (o due? O forse fino a pochi?) Frutta da ottenere.

BTW, mantenere le cose semplici, partendo dal presupposto che non esistono nemmeno i fantasmi intorno.

Alcuni esempi dei problemi PacMan originali: First, Second e Third

Answer 1

È commento dice che sta cercando percorso più breve. Questo problema è una variazione di TSP su un grafico planare e pertanto è NP-Hard. funzione

Possibili euristiche per A* che può risolvere il problema, ma non è admissible [quindi il percorso trovato non è sempre garantito ottimale]:

somma delle distanze Manhattan da tutti i frutti all'agente.

È anche possibile utilizzare un metodo euristico accettabile, di #fruits - ma ci vorrà molto tempo.

Se stai cercando ottimale, beh, è ​​difficile. È possibile provare tutte le permutazioni di frutta, e controllare la distanza totale che serve per viaggiare. Questa soluzione è fattoriale nel numero di frutti, e se è maggiore di 20 - con naute bruteforce - ci vorrà troppo tempo. Puoi in qualche modo renderlo migliore di riducendo il problema a TSP e utilizzare la soluzione di programmazione dinamica, anch'essa esponenziale, o alcune soluzioni euristiche di TSP.

---

Uno può anche migliorare la soluzione euristica non ammissibile per fornire un any-time algorithm:

iterativamente eseguire A* con una diminuzione funzione euristica: h(v) = h'(v)/m, dove h' è la funzione euristica ultima iterazione di A * e m > 1. Ciò garantisce che, ad un certo punto, la funzione euristica h sarà ammissibile e la soluzione trovata sarà ottimale. Tuttavia, ogni iterazione dovrebbe richiedere molto più tempo del precedente [esponenzialmente più lungo ..]

Answer 2

Si potrebbe forza bruta per un piccolo numero di frutti in un labirinto di dimensioni ragionevoli.

• Creare un grafico con un nodo per ogni pezzo di frutta nel labirinto.
• Usa A * o similare per trovare la distanza tra ogni coppia di frutta. (È necessario O(n^2) esecuzioni di A * per ottenere tutte le distanze a coppie tra i frutti n.)
• Collegare i nodi (frutti) nel grafico con i bordi ponderati in base alla distanza.
• Trova il ciclo economico nel grafico (visitare tutti i nodi, almeno una volta) con la forza bruta. Vedere cheapest cost traveral on complete graph.

Answer 3

So che questo è vecchio, ma probabilmente ci sono molte altre persone che cercano di risolvere questo problema (fa parte di Classe IA gratuita di Berkeley). C'è un sacco di suggerimenti di forza bruta, quindi mi contribuiscono abbastanza semplice che ottiene abbastanza vicino e RICEVIBILE :

1. Trova il frutto più vicino
2. Togliere quel frutto dalla lista dei frutti rimanenti e aggiungi la distanza totale
3. Trova il frutto più vicino a questo frutto
4. tornare al punto 2 e ripetere finché non ci sono più frutta
5. ritorno totale

modifica: precedente affermazione che questa è un'euristica ammissibile è falsa. Scusate!

Answer 4

euristico, che ha lavorato per me se si conosce l'aspetto di labirinto:

1. Trova la distanza reale tra due frutti al momento più lontane nel labirinto - chiamiamolo che x.
2. Trova la distanza reale dalla posizione corrente di Pacman al più vicino dei due precedenti frutti: chiamiamola .

Quindi, la risposta è solo: x + y.

Nota che le distanze reali non sono le distanze di Manhattan, ma le distanze real in labirinto - puoi calcolarlo (anche precalcolare se vuoi) perché conosci l'aspetto del labirinto (conosci tutti i muri, ...). Questa informazione (la distanza reale tra due punti nel labirinto) è statica perché i muri non cambiano.

L'interpretazione di questo x + y formula potrebbe essere qualcosa di simile:

• x - in entrambi i casi, si dovrà percorrere questa distanza, almeno alla fine
• y - mentre si è al alcuni dei due frutti più lontani, è meglio raccogliere il cibo che è vicino ad esso in modo da non dover tornare indietro

Se stai risolvendo questo come parte del progetto di classe di Berkeley AI, per r calcolo della distanza reale tra due punti è possibile utilizzare la funzione mazeDistance(pos1, pos2, gameState) che è già implementata e sta utilizzando la propria implementazione di bfs.Inoltre, questa euristica è ammissibile e coerente, almeno per i loro casi di test. A proposito, con questa euristica sono riuscito ad espandere solo 376 nodi nel labirinto di trickySearch.

Answer 5

Ho trovato il cibo più vicino (utilizzando le distanze manhattan) ma per la mia euristica ho usato la distanza effettiva dalla mia posizione al cibo più vicino. A questo ho aggiunto 1 per tutti quei punti cibo che non condividono riga o colonna con la mia posizione o punto cibo più vicino.

Poiché i punti di cibo che condividono la riga o il col con la mia posizione o la posizione di cibo più vicina verrebbero mangiati mentre andavo dalla mia posizione al cibo più vicino e Ive già ha contato il costo di questo nella distanza effettiva che ho menzionato nel secondo linea.

Così, in breve: euristica = mazeDistance (la mia posizione, più vicina stimato cibo) + punti lasciati fuori

Questo era ammissibile e coerente. Con ciò stavo espandendo 5500 nodi e ho ottenuto un 5/4 su FoodHeuristic. https://github.com/sukritiverma1996/Intro-to-AI-course

Answer 6

se si vuole ridurre il numero di nodi espansi e non si preoccupano di tempo di esecuzione, mi consiglia di utilizzare minimo Spanning Tree, il costo di bordo dovrebbe essere mazeDistance e utilizzando un CodaConPriorita, ogni volta che l'aggiunta di un nodo nel nodo visitato, cercare il nodo più vicino al nodo appena aggiunto e quindi aggiungerlo al nodo visitato, fino a quando tutto il nodo del cibo è stato aggiunto al nodo visitato. Se si sta affrontando un problema con il corso di intelligenza artificiale, il nodo espanso dovrebbe essere molto basso.

Answer 7

in un determinato stato di gioco, dire md(x) è la distanza di Manhattan da pacman al nodo x, considerare minmd(X) come una funzione che restituiscono xmin s.t md(xmin)<=md(x) per tutti x in X. Let X essere il set di cibi che Pacman ha lasciato a mangiare.

che pensare a questo proposito - se si considera un rilassamento del vostro mondo pacman in cui non ci sono muri, pacman potete camminare meno di md(xmin) dove xmin=minmd(X) a mangiare un po 'di frutta, e poi se vuole mangiare un altro frutto, lo deve andare non meno di md(xmin1) dove xmin1=minmd(X-{xmin}) e così via. restituire la somma di mds pacman camminato da xmin a xmin1 a xmin2 e così via e poiché questa è una soluzione ottimale per il relax ti sei guadagnato un ottimo ammissibile e costante funzione euristica euristica!

Un altro punto da considerare, è che si può anche ottenere un euristica migliore se si considerano le pareti, questo è un problema molto più dura così i didnt get in esso molto, ma ho notato che se tenuti pacman in un rettangolo con il prossimo frutto ottimale, dovrà pagare almeno altre 2 azioni se tra di esse ci sarà una linea di muro verticale o orizzontale FULL perché dovrà uscire dal rettangolo di delimitazione e rientrare di nuovo pagando almeno 2 azioni mentre lo fa per ogni tale muro. Questo può essere ulteriormente esaminato e puoi trovare anche altre funzioni speciali in questo rettangolo.

Answer 8

supponendo che questo è per il progetto Berkeley AI:

Nel caso generale, trovare il percorso più breve che visita ogni punto è NP-hard. Tuttavia, ciò non significa che sia difficile nella pratica. Il motivo è perché ci sono fixed parameter tractable algorithms e i labirinti di Pacman forniti rientrano nel caso di grafici che sono facili da risolvere.

In particolare, per ogni data larghezza di ramo, il percorso più breve può essere trovato nel polinomio temporale nella dimensione del grafico (ma esponenziale nella larghezza del ramo del grafico) mediante una semplice applicazione di programmazione dinamica. Ciò non viola la durezza NP poiché i grafici arbitrari possono avere una larghezza di ramo grande, ma significa che il problema può essere risolto in modo efficiente se ci si preoccupa solo dei grafici che hanno una larghezza di ramo bassa. I labirinti di Pacman hanno una scarsa connettività e quindi una bassa larghezza del ramo.

Per ulteriori dettagli, see this post.