Algoritmo genetico per un gioco di carte (Dominion)

Question

Ho un programma F # funzionante che esegue Dominion, un gioco di carte. Mi piacerebbe utilizzare un algoritmo genetico per determinare le strategie ottimali per giocare. Tuttavia, non so molto su AI o algoritmi genetici. Puoi indicarmi qualche buona letteratura per iniziare?

Una strategia per giocare consiste in una reazione a una mano data. In ogni turno, un robot riceve una mano di carte. Può scegliere di giocare a carte azione o acquistare nuove carte, in base a ciò che è stato distribuito. L'obiettivo è terminare il gioco con il maggior numero possibile di carte punti vittoria.

Un approccio hardcoded potrebbe somigliare:

def play(hand, totalDeck): 
    if hand contains Smithy then use Smithy 
    if hand contains enough coins for Province then buy Province 
    if more than 30% of the totalDeck is Smithy, then buy coins 

pensavo di descrivere una strategia in termini di un vettore di porzioni target del ponte totale per ogni carta:

[Smithy, Province, Copper, ...] 
[.3, .2, .1, ...] 

Poi per mutare un bot, potrei semplicemente cambiare quel vettore in giro, e vedere se la versione mutata funziona meglio. La funzione fitness sarebbe il punteggio medio giocando a Dominion contro una varietà di altri robot. (Il punteggio di un robot dipende da chi sta giocando contro, ma si spera che giocando molte partite contro molti robot questo possa essere eliminato.)

Ha senso? Sono diretto lungo la strada giusta?

Answer 1

Da dove si disegna gli altri robot? Li mantieni statici? Se è così, il robot addestrato non diventerà "buono" al gioco di per sé, solo bravo a sfruttare il bot fittizio. In caso contrario, anche gli altri robot si evolvono e la percentuale di vincita non sarà un buon indicatore di qualità a meno che non si applichino altri vincoli. Ti rendi conto che con una popolazione piena di robot con abilità perfetta, le loro prestazioni reciproche appariranno mediocri!

si poteva prendere un approccio co-evolutivo:

• mutare tutti i bot in sufficientemente grandi popolazioni.
• Lasciate che competono uno contro l'altro più volte in un girone all'italiana, ad esempio 100 volte
• eliminare alcune delle peggiori bot dello spettacolo,
• mantenere un paio dei migliori bot invariati (elitarismo)
• Refill il resto della popolazione con mutazioni e crossover di buoni robot.

Oppure si potrebbe formare nei confronti di un punto di riferimento fisso:

• Fai un bot con una politica artigianale che appare buono, con la vostra conoscenza del gioco
• In alternativa, hanno giocatori umani (solo?) fornire le mosse. Questa potrebbe essere una buona fonte di esperienza di allenamento per il tuo bot, ma a meno che tu non abbia accesso a un ampio database di mosse umane (esperte), è molto lento.
• Treno contro il vostro punto di riferimento
• Selezionare i migliori interpreti, mutare, ecc

Answer 2

penso che il vettore non sarà davvero portare a buoni risultati a meno che il gioco è molto lineare.Vorrei suggerire il seguente approccio basato sulle regole:

In ogni turno si tiene un mazzo di carte e si desidera determinare la carta che si gioca o nel caso in cui non si gioca una carta che si desidera disegnare una nuova uno. Quello di cui hai bisogno è una sorta di funzione di priorità che ti dice quale carta è la migliore da giocare. Tale funzione prioritaria può essere descritta dalla programmazione genetica. Dovresti sempre giocare la carta con la priorità più alta a meno che nessuna carta abbia una priorità sopra un livello impostato (ad esempio 0), nel qual caso ne disegni una nuova. La programmazione genetica può essere utilizzata per evolvere questa funzione prioritaria.

Poiché si utilizza F # potrebbe essere una buona idea provare questo approccio con HeuristicLab che è scritto in C#. Puoi implementare il tuo programma come un problema lì e lasciare che la funzione di valutazione esegua una simulazione di quel gioco. Scrivi una grammatica e un interprete per la tua regola. Definisci un numero di parametri che consentano alla tua regola di priorità di prendere decisioni significative, ad es. alcune informazioni generali sul gioco come il numero di carte giocate, le province rimaste ecc. e alcune informazioni relative alla carta come l'impatto di giocare quella carta (in termini di punti vittoria) ecc. Queste sono le variabili di input per il tuo interprete che calcola un valore prioritario. La carta con il miglior valore di priorità è quella che scegli. Quindi per valutare la tua strategia definisci per es. 10 soluzioni casuali quando si crea un tale problema e nella valutazione si consente a ciascuna soluzione di competere con i bot casuali. Misura la quantità a cui batti ciascuno dei robot casuali, più alto vinci e più robot batti meglio è, più vinci e peggiorando il punteggio. È inoltre possibile aggiungere un analizzatore al problema che aggiornerà le soluzioni casuali del problema con quelle più performanti, in modo da farle evolvere nel tempo.

È anche possibile utilizzare l'idea della porzione di destinazione, se lo si desidera. In quel caso la tua codifica sarebbe un RealVector. Puoi anche ottimizzarlo con HeuristicLab (usa Strategia Evolutiva, Ottimizzazione dello Swarm Particelle o Algoritmo Genetico).

Answer 3

Dominion è un grande gioco, ma sarà difficile ottimizzare utilizzando un algoritmo genetico, poiché gli input di un dato gioco differiscono tra i giochi (i set di carte utilizzati), la strategia ottimale cambia nel corso del gioco, e il gioco ottimale per ogni data situazione apparirà lentamente solo in una ricerca genetica (intuitivamente, basata sulla mia buona conoscenza sia delle GA che del gioco).

Un approccio migliore a Dominion, penso, potrebbe essere un approccio euristico diretto (basato su regole) o, molto interessante, Ricerca Monte Carlo (vedere, ad esempio, http://cacm.acm.org/magazines/2012/3/146245-the-grand-challenge-of-computer-go/fulltext). Monto Carlo Search è attraente proprio perché:

• È facile generare una sequenza casuale di mosse in Dominion.
• E 'di almeno straight-forward per giudicare il "valore" di una tale sequenza (aumento di VP) edificio
• A-priori delle regole "miglior play" è difficile (questo è ciò che rende il gioco così buono)

È una bella sfida: dovresti blogare le tue esperienze.