Come creare una buona funzione di valutazione per un gioco?

https://stackoverflow.com/questions/1291377

18-09-2019
|

Domanda

Scrivo programmi per giocare varianti di gioco da tavolo a volte. La strategia di base è di serie la potatura alfa-beta o ricerche simili, a volte aumentata dai soliti approcci alla endgames o aperture. Ho per lo più giocato con varianti di scacchi, in modo che quando arriva il momento di scegliere il mio funzione di valutazione, io uso una funzione di base di valutazione degli scacchi.

Tuttavia, ora sto scrivendo un programma per giocare un nuovo gioco da tavolo. Come faccio a scegliere un buon o addirittura decente funzione di valutazione?

Le sfide principali sono che gli stessi pezzi sono sempre sul tavolo, quindi una funzione di materiale al solito non cambierà in base alla posizione, e il gioco è stato giocato meno di un migliaio di volte o giù di lì, così gli esseri umani non necessariamente giocare abbastanza bene ancora dare intuizione. (PS. Ho considerato un approccio MoGo, ma i giochi casuali non sono suscettibili di interrompere.)

Dettagli gioco : La partita si gioca su una tavola 10-by-10 con un fisso sei pezzi per lato. I pezzi hanno certe regole di movimento, e interagiscono in un certo modo, ma nessun pezzo viene mai catturato. L'obiettivo del gioco è quello di avere sufficiente di tutti i pezzi in alcune piazze speciali sul bordo. L'obiettivo del programma di computer è quello di fornire un giocatore che è competitivo con o meglio di giocatori umani attuali.

Soluzione

Trova un paio di candidati per la funzione di valutazione, come la mobilità (numero di mosse possibili) meno la mobilità dell'avversario, quindi provare a trovare il peso ottimale per ogni metrica. Gli algoritmi genetici sembrano funzionare abbastanza bene per ottimizzare i pesi in una funzione di valutazione.

Crea una popolazione con pesi casuali, la loro lotta contro l'altro con una profondità limitata e si gira, sostituire i perdenti con combinazioni casuali tra i vincitori, shuffle, e ripetere, stampando la media della popolazione dopo ogni generazione. Lasciarlo funzionare finché non si è soddisfatti del risultato, o fino a vedere la necessità di regolare la gamma per alcune delle metriche e riprovare, se risulta che il valore ottimale per una metrica potrebbe essere fuori della vostra gamma iniziale.

Fine edit: A più accettata, studiato, capito approccio che non sapevo al momento è qualcosa che si chiama "Evolution differenziale". Prole sono creati da 3 genitori invece di 2, in modo tale che evita il problema di convergenza prematura verso la media.

Altri suggerimenti

Vorrei iniziare con alcuni principi fondamentali e passare a cose più difficili in seguito.

agente di base e di un framework di test

Non importa quale approccio si prende è necessario iniziare con qualcosa di davvero semplice e stupido. L'approccio migliore per un agente muta è uno casuale (generare tutte le possibili mosse, seleziona uno a caso). Questo servirà come punto di partenza per confrontare tutti gli altri agenti. Avete bisogno di un forte quadro di riferimento per il confronto. Qualcosa che prende vari agenti, permette di giocare un determinato numero di partite tra loro e restituisce la matrice della performance. Sulla base dei risultati, si calcola l'idoneità per ogni agente. Per esempio la funzione tournament(agent1, agent2, agent3, 500) giocherà 500 partite tra ogni coppia di agente (la riproduzione del primo / secondo) e si restituisce qualcosa come:

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

Qui per esempio, io uso 2 punti per una vittoria, 1 punto per la funzione draw punteggio, e alla fine solo sommando tutto per trovare il fitness. Questa tabella mi dice subito che agent3 è il migliore, e agent1 non è davvero diverso da agent2.

Quindi, una volta che queste due cose importanti sono impostati si è pronti a sperimentare le funzioni di valutazione.

Cominciamo con la selezione delle funzioni

Prima di tutto il necessario per creare funzione di valutazione not a terrible. Con questo voglio dire che questa funzione dovrebbe identificare correttamente 3 aspetti importanti (win / draw / perdita). Questo sembra ovvio, ma ho visto una quantità significativa di bot, in cui i creatori non erano in grado di impostare correttamente questi 3 aspetti.
Quindi si usa il tuo ingegno umano di trovare alcune caratteristiche lo stato del gioco. La prima cosa da fare è parlare con un esperto di gioco e chiedergli come ha accesso alla posizione.
Se non avete l'esperto, o anche appena creato le regole del vostro gioco 5 minuti fa, non sottovalutare la capacità del umano per la ricerca di schemi. Anche dopo aver giocato un paio di partite, una persona intelligente può dare idee come egli avrebbe dovuto giocare (non significa che egli possa realizzare le idee). Utilizzare queste idee come le caratteristiche.
A questo punto non si ha realmente bisogno di sapere come queste caratteristiche influenzano il gioco. Esempio di caratteristiche:. Valore della mobilità pezzi, pezzi, il controllo delle posizioni importanti, la sicurezza, il numero totale di possibili mosse, la vicinanza ad un rivestimento
Dopo aver codificato queste caratteristiche e li hanno usati separatamente per vedere ciò che funziona meglio (non affrettatevi a scartare caratteristiche che non eseguono ragionevole di per sé, potrebbero essere utili in combinazione con gli altri), si è pronti di sperimentare combinazioni.

Costruzione valutazioni migliori combinando e ponderazione caratteristiche semplici. Ci sono un paio di approcci standard.

Crea una funzione uber sulla base di varie combinazioni di vostre caratteristiche. Può essere eval = f_1 * a_1 + ... f_n * a_n lineare (caratteristiche f_i, coefficienti a_i), ma può essere qualsiasi cosa. Poi istanziare molti agenti con pesi assolutamente casuali per questa funzione di valutazione e di utilizzare algoritmi genetici per riprodurli agains vicenda. Confrontare i risultati utilizzando il framework di test, scarta un paio di perdenti chiare e mutare un paio di vincitori. Continuare lo stesso processo. (Si tratta di un abbozzo, saperne di più su GA)
Con l'idea di back-propagazione da un reti neurali per eseguire il propagare l'errore dalla fine della partita per aggiornare i pesi della rete. Si può leggere di più come è stato fatto con backgammon (non ho scritto niente di simile, così dispiaciuto per la brevità).

È possibile lavorare senza funzione di valutazione! Questo potrebbe sembrare folle per una persona che ha sentito solo circa Minimax / alfa-beta, ma ci sono metodi che non richiedono una valutazione a tutti. Uno di loro si chiama Monte Carlo albero di ricerca e come a Monte Carlo in un nome suggerisce che utilizza un sacco di casuale (non dovrebbe essere casuale, è possibile utilizzare le precedenti buoni agenti) gioco gioca per generare un albero. Questo è un enorme argomento di per sé, così io vi darò la mia spiegazione davvero di alto livello. Si inizia con una radice, crea il tuo frontiera, che si tenta di espandere. Una volta che si espande qualcosa, solo casualmente andare alla foglia. Ottenere il risultato dalla foglia, si backpropagate il risultato. Fare questo molte volte, e raccogliere le statistiche di ogni bambino della frontiera corrente. Selezionare il migliore. C'è la teoria significativo lì che si riferisce a come si fa a bilanciare tra esplorazione e lo sfruttamento e una buona cosa da leggere c'è UCT (Alta fiducia algoritmo Bound)

Vorrei guardare un algoritmo di apprendimento automatico supervisionato come l'apprendimento di rinforzo. Scopri Rinforzo apprendimento in giochi da tavolo . Penso che vi darà alcune buone indicazioni per guardare in.

Inoltre, controllare strategia di acquisizione per il Gioco Othello Sulla base di Reinforcement Learning (link PDF) in cui, date le regole del gioco, una buona "funzione di payoff" si può imparare. Questo è strettamente legato al TD-Gammon ...

Durante l'addestramento, la rete neurale si è utilizzato per selezionare mosse per entrambe le parti ... La piuttosto sorprendente scoperta è stata che una notevole quantità di apprendimento in realtà ha avuto luogo, anche nella conoscenza zero iniziale esperimenti che utilizzano una scheda grezzo codifica.

Se nessuno capisce il gioco ancora, non c'è modo si può ottenere una funzione di valutazione decente. Non mi dire che standard di alfa-beta con conteggio materiale è buono o addirittura decente per gli scacchi o le sue varianti (forse gli scacchi perdenti è un'eccezione).

Si potrebbe provare a reti neurali con algoritmi di feedback o di apprendimento macchina simile ma di solito succhiare fino a quando non hanno tonnellate di formazione, che in questo caso probabilmente non è a disposizione. E anche allora, se non succhiare, non è possibile acquisire conoscenze da loro.

Credo che ci sia alcun modo a corto di comprensione del gioco il meglio che si può e, per cominciare, lasciare le incognite come casuale sulla funzione di valutazione (o semplicemente fuori dal quadro fino a quando le incognite farsi conoscere).

Naturalmente, se si desidera condividere ulteriori informazioni sul gioco si potrebbe ottenere migliori idee da parte della comunità.

Se ho capito bene, si vuole una buona funzione di valutazione statica per utilizzare le foglie del tuo albero min-max. Se è così, è meglio ricordare che lo scopo di questa funzione di valutazione statica è quello di fornire un rating da quanto è buono che a bordo è per il giocatore del computer. Così è

f (Board1)> f (board2)

allora deve essere vero che Board1 è meglio per il computer (è più probabile di vincere alla fine) che in board2. Naturalmente, nessuna funzione statica è mai completamente corretta per tutte le schede.

Quindi, lei dice che "L'obiettivo del gioco è quello di avere sufficiente di tutti i pezzi in alcune piazze speciali sul bordo", quindi un primo tentativo di f (bordo) sarebbe semplicemente per contare il numero di pezzi della informatici ha su quelle piazze speciali. È quindi possibile finezza di più.

Senza conoscere le specifiche del gioco è impossibile che invia ipotesi migliori. Se ci hai dato le regole del gioco sono sicuro che gli utenti StackOverflow sarebbe in grado di venire con tonnellate di idee originali per tali funzioni.

Mentre è possibile utilizzare vari metodi di apprendimento automatico a venire con una funzione di valutazione (TD-Learning, utilizzato in tali progetti come gnubackgammon, ne è un esempio), i risultati sono sicuramente dipende dal gioco stesso. Per backgammon, funziona davvero bene, perché la natura stocastica del gioco (dadi che rotolano) costringe lo studente ad esplorare il territorio che non può decidere di fare. Senza una componente cruciale, probabilmente finire con una funzione di valutazione che è buono contro se stessa, ma non contro gli altri.

Dato che differenza materiale non può essere applicabile, è il concetto di mobilità importanti - vale a dire il numero di mosse possibile che avete a disposizione? Sta controllando una certa area del consiglio di solito meglio di no? Parlare con le persone che giocano il gioco per scoprire alcuni indizi.

Mentre è preferibile avere come bene di una funzione di valutazione, come si può, è anche bisogno di affinare l'algoritmo di ricerca in modo da poter cercare come profondamente il più possibile. A volte, questo è in realtà più di una preoccupazione, dal momento che un profondo ricercatore con una funzione di valutazione mediocre può battere ricerche poco profondi con una buona funzione di valutazione. Tutto dipende dal dominio. (Gnubackgammon gioca un gioco esperto con una ricerca 1-ply, per esempio)

Ci sono altre tecniche è possibile utilizzare per migliorare la qualità della ricerca, soprattutto, di avere una tabella di trasposizione ai risultati di ricerca di cache di avere il suono di potatura in avanti.

Mi raccomando guardando oltre queste diapositive .

È inoltre necessario fare attenzione alla scelta. Se l'algoritmo non ha un rapporto noto al valore effettivo, le funzioni standard di AI non funzioneranno correttamente. Per essere valida, la funzione di valutazione, o euristica deve essere la stessa, o al di sotto del valore reale in modo coerente o sarà guidare le vostre decisioni in un modo strano (che si potrebbe sostenere per gli scacchi, anche se penso che i punti standard vanno bene ).

Quello che di solito fare è scoprire che cosa è capace e ciò che è necessario. Per alcuni giochi, come Sokoban, ho usato il numero minimo di contenitore di mosse necessarie per ottenere una scatola (in isolamento) dalla posizione corrente ad una delle sedi della porta. Questa non è una risposta precisa per il numero di mosse richieste, ma penso che sia una buona euristica in quanto non potrà mai sopravvalutare e può essere pre-calcolato per l'intero Consiglio. Quando sommando il punteggio per una scheda è solo la somma dei valori per ogni posizione di dialogo corrente.

In una simulazione di vita artificiale che ho scritto ad evolversi pacchetto caccia e la difesa pack, il sistema di punteggio che ho usato è stato solo per guidare l'evoluzione e di non eseguire alcuna potatura. Ho dato ogni creatura un punto per essere nato. Per ogni punto di energia che hanno consumato nella loro vita, ho dato loro un ulteriore punto. Ho quindi utilizzato la somma dei punti della loro generazione per determinare la probabilità di ogni stato di riprodursi. Nel mio caso, ho semplicemente usato la percentuale del totale dei punti della loro generazione che avevano acquisito. Se avessi voluto evolversi creature che erano fantastici ad eludere, avrei segnato giù per ottenere punti consumati fuori di loro.

Si dovrebbe anche fare attenzione a che la funzione non è troppo difficile di un obiettivo da colpire. Se si sta cercando di evolvere qualcosa, si vuole fare in modo lo spazio delle soluzioni ha una pendenza decente. Si vuole guidare l'evoluzione in una direzione, non solo dichiarare una vittoria, se capita di colpire in modo casuale.

Senza sapere di più sul tuo gioco che sarebbe difficile per dirvi come costruire una funzione. Ci sono valori chiari su qualcosa che indicano una vittoria o una perdita? Avete un modo di stimare un costo minimo per colmare il divario?

Se si forniscono ulteriori informazioni, sarei felice di provare e di fornire un quadro più chiaro. Ci sono un sacco di ottimi libri sul tema pure.

Jacob

Prendere in mente che non è nescessarily vero che una funzione di valutazione decente esiste ancora. Per questa dichiarazione ho supporre che, una funzione di valutazione deve essere di bassa complessità (P).

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow