Costruire un bot NetHack: l'analisi bayesiana è una buona strategia?

Question

Un mio amico sta iniziando a costruire un bot NetHack (un bot che riproduce il gioco Roguelike: NetHack). C'è un ottimo robot di lavoro per il gioco simile Angband, ma funziona in parte a causa della facilità nel tornare in città e di essere sempre in grado di farsela di bassi livelli per guadagnare oggetti.

In NetHack, il problema è molto più difficile, perché il gioco premia la sperimentazione spericolata e si basa fondamentalmente su 1.000 casi limite.

Recentemente ho suggerito di utilizzare una sorta di analisi bayesiana naif, nello stesso modo in cui viene creato lo spam.

Fondamentalmente il bot in un primo momento costruiva un corpus, provando ogni possibile azione con ogni oggetto o creatura che trova e memorizzando quell'informazione con, per esempio, quanto fosse vicino a una morte, ferita di effetto negativo. Nel tempo sembra che tu possa generare un modello ragionevolmente giocabile.

Qualcuno può indicarci la direzione giusta di quello che sarebbe un buon inizio? Sto abbaiando sull'albero sbagliato o frainteso l'idea dell'analisi bayesiana?

Modifica: Il mio amico ha inserito un github repo of his NetHack patch che consente collegamenti Python. È ancora in uno stato piuttosto primitivo, ma se qualcuno è interessato ...

Answer 1

Sebbene l'analisi bayesiana comprenda molto di più, l'algoritmo di Naive Bayes ben noto dai filtri antispam si basa su un presupposto fondamentale: tutte le variabili sono essenzialmente indipendenti l'una dall'altra. Quindi, ad esempio, nel filtrare lo spam ogni parola viene solitamente trattata come una variabile, quindi questo significa assumere che se l'e-mail contiene la parola 'viagra', tale conoscenza influisce sulla probabilità che contenga anche la parola 'medicina' (o 'foo' "o" spam "o qualsiasi altra cosa). La cosa interessante è che questa assunzione è ovviamente falsa quando si parla di linguaggio naturale, ma riesce comunque a produrre risultati ragionevoli.

Ora, un modo in cui le persone talvolta aggirano l'ipotesi dell'indipendenza è definire variabili che sono tecnicamente combinazioni di cose (come cercare il token "buy viagra"). Ciò può funzionare se si conoscono casi specifici da cercare, ma in generale, in un ambiente di gioco, significa che in genere non è possibile ricordare nulla. Quindi ogni volta che devi muoverti, eseguire un'azione, ecc., È completamente indipendente da qualsiasi altra cosa tu abbia fatto finora. Direi anche per i giochi più semplici, questo è un modo molto inefficiente per imparare a giocare.

Suggerirei invece di utilizzare q-learning. La maggior parte degli esempi che trovi in ​​genere sono solo semplici giochi (come imparare a navigare su una mappa evitando muri, trappole, mostri, ecc.). L'apprendimento di rinforzo è un tipo di apprendimento online non supervisionato che funziona molto bene in situazioni che possono essere modellate come un agente che interagisce con un ambiente, come un gioco (o robot). Lo fa cercando di capire quale sia l'azione ottimale in ogni stato nell'ambiente (dove ogni stato può includere tutte le variabili necessarie, molto più che "dove sono io"). Il trucco è quindi mantenere uno stato sufficiente che aiuta il robot a prendere buone decisioni senza avere un punto distinto nello "spazio" del proprio stato per ogni possibile combinazione di azioni precedenti.

Per dirlo in termini più concreti, se si costruisse un robot di scacchi probabilmente si avrebbe problemi se si tentasse di creare un criterio decisionale che prendesse decisioni in base a tutte le mosse precedenti dall'insieme di tutte le possibili combinazioni di scacchi le mosse crescono molto rapidamente. Anche un modello più semplice di dove ogni pezzo si trova sulla scacchiera è ancora uno spazio molto grande, quindi devi trovare un modo per semplificare ciò di cui tieni traccia. Ma notate che riuscite a tenere traccia di alcuni stati in modo che il vostro bot non continui a provare a fare un termine a sinistra in un muro più e più volte.

La wikipedia article è un bel gergo pesante ma questo tutorial è un lavoro molto migliore che traduce i concetti in esempi reali.

L'unico problema è che è necessario essere in grado di definire i premi come "rinforzo" positivo. È necessario essere in grado di definire gli stati che il bot sta tentando di raggiungere, altrimenti continuerà solo per sempre.

Answer 2

In nethack le azioni sconosciute di solito hanno un effetto booleano - o guadagni o perdi. Le reti bayesiane si basano su valori di "logica fuzzy": un'azione può dare un guadagno con una determinata probabilità. Quindi, non hai bisogno di una rete bayesiana, solo una lista di "effetti scoperti" e se sono buoni o cattivi.

Non c'è bisogno di mangiare di nuovo la Cockatrice, vero?

Tutto sommato, dipende da quanto "conoscenza" si desidera dare al bot come starters. Vuoi che impari tutto "nel modo più duro", o gli darai da mangiare spoiler finché non sarà imbottito?

Answer 3

C'è un precedente: il mostruoso programma rog-o-matic è riuscito a fare il ladro e persino a restituire con l'amuleto di Yendor alcune volte. Sfortunatamente, il ladro è stato rilasciato solo un binario, non una fonte, quindi è morto (a meno che non si possa configurare un sistema 4.3BSD su un MicroVAX), lasciando rog-o-matic in grado di riprodurre nessuno dei cloni. Pende solo perché non sono emulazioni abbastanza vicine.

Tuttavia, rog-o-matic è, penso, il mio programma preferito di tutti i tempi, non solo per quello che ha ottenuto, ma per la leggibilità del codice e l'intelligibilità comprensibile dei suoi algoritmi. Ha usato "l'ereditarietà genetica": un nuovo giocatore erediterebbe una combinazione di preferenze da una coppia precedente di giocatori di successo, con un certo disallineamento casuale, quindi essere contro la macchina. Le preferenze più efficaci migrerebbero nel pool genetico e quelle meno riuscite.

La fonte può essere difficile da trovare in questi giorni, ma la ricerca "rogomatic" ti metterà sul percorso.

Answer 4

Dubito che l'analisi bayesiana ti porterà lontano perché la maggior parte di NetHack è altamente contestuale. Ci sono pochissime azioni che sono sempre una cattiva idea; la maggior parte sono anche risparmiatori di vita nella situazione "giusta" (un esempio estremo è mangiare una cockatrice: è male, a meno che tu non stia morendo di fame e attualmente polimorfi in un mostro resistente alla pietra, nel qual caso mangiare la cockatrice è la cosa giusta da fare). Alcune di quelle azioni "quasi cattive" sono necessarie per vincere la partita (ad esempio salendo le scale al livello 1 o deliberatamente cadendo in trappole per raggiungere Gehennom).

Quello che potreste provare sarebbe provare a farlo a livello "meta". Progetta il bot scegliendo come a caso tra una varietà di "comportamenti elementari". Quindi prova a misurare come vanno questi robot. Quindi estrai le combinazioni di comportamenti che sembrano promuovere la sopravvivenza; analisi bayesiana potrebbe farlo tra un vasto corpus di giochi insieme al loro "livello di successo". Ad esempio, se ci sono comportamenti "prendi i pugnali" e "evita di ingaggiare mostri in mischia", suppongo che l'analisi mostrerebbe che quei due comportamenti si adattano bene insieme: i robot che scelgono i pugnali senza usarli e i robot che cercano di lanciare missili contro i mostri senza raccogliere tali missili, probabilmente andrà peggio.

Questo in qualche modo imita ciò che i giocatori di apprendimento spesso chiedono in rec.games.roguelike.nethack. La maggior parte delle domande sono simili a: "Devo bere pozioni sconosciute per identificarle?" o "quale livello dovrebbe essere il mio personaggio prima di andare così in profondità nel dungeon?". Le risposte a queste domande dipendono fortemente da cos'altro sta facendo il giocatore, e non c'è una buona risposta assoluta.

Un punto difficile qui è come misurare il successo alla sopravvivenza. Se cerchi semplicemente di massimizzare il tempo speso prima di morire, allora preferirai i bot che non abbandonano mai i primi livelli; quelli possono vivere a lungo ma non vinceranno mai la partita. Se si misura il successo da quanto è profondo il personaggio prima di morire, i migliori robot saranno gli archeologi (che iniziano con un piccone) in una frenesia di scavo.

Answer 5

Apparentemente ci sono un buon numero di robot Nethack là fuori. Check out this listing: