Cosa algoritmo dovrei usare per “il miglioramento genetico AI”

Question

Prima di tutto: si tratta di non una domanda su come fare un programma di giocare cinque di fila. c'è stato, fatto.

spiegazione introduttiva

Ho fatto un a-row-partita a cinque-in-come quadro di sperimentare il miglioramento geneticamente AI (ahi, che suona terribilmente pretenzioso). Come con la maggior parte dei giochi a turni la mossa migliore è deciso assegnando un punteggio ad ogni possibile mossa, e poi giocare la mossa con il punteggio più alto. La funzione per l'assegnazione di un punteggio ad un movimento (una piazza) va qualcosa come questo:

1. Se la piazza ha già una pedina, il punteggio è 0 dal momento che sarebbe illegale per inserire un nuovo token nella piazza.

2. Ogni casella può essere una parte di fino a 20 diverse righe vincenti (5 orizzontale, verticale 5, 10 diagonale). Il punteggio della piazza è la somma del punteggio di ciascuna di queste righe.

3. Il punteggio di una riga dipende dal numero di gettoni amiche e nemiche già in prima fila. Esempi:

   • Una riga con quattro gettoni amichevoli dovrebbe avere il punteggio infinito, perché se si inserisce un gettone non si vince la partita.
   • Il punteggio per una riga con quattro nemico gettoni dovrebbe essere molto elevato, in quanto se si non mettere un segno lì, l'avversario vincerà il suo prossimo turno .
   • Una fila con entrambi i token amiche e nemiche si punteggio 0, dal momento che questa riga non può mai essere parte di una riga vincente.

Dato questo algoritmo, ho dichiarato un tipo chiamato TBrain:

type
  TBrain = array[cFriendly..cEnemy , 0..4] of integer; 

I valori nella matrice indica il punteggio di una riga sia con N gettoni amichevoli e 0 gettoni nemiche, o 0 gettoni amichevoli e gettoni nemiche N. Se ci sono 5 gettoni in fila non c'è alcun punteggio in quanto la riga è completa.

In realtà è abbastanza facile decidere quali valori dovrebbero essere nella matrice. Cervello [0,4] (quattro gettoni amichevoli) dovrebbe essere "infinita", chiamiamolo che 1.000.000. vBrain [1,4] dovrebbe essere molto alto, ma non così alto che il cervello preferirebbe bloccando diversi nemico vince, piuttosto che vincente per sé

considerate questo il seguente (improbabile) scheda:

  0123456789
 +----------
0|1...1...12
1|.1..1..1.2
2|..1.1.1..2
3|...111...2
4|1111.1111.
5|...111....
6|..1.1.1...
7|.1..1..1..
8|1...1...1.

Il giocatore 2 dovrebbe mettere il suo gettone a (9,4), vincendo la partita, non a (4,4) anche se lui avrebbe poi bloccare 8 potenziali righe vincenti per il giocatore 1. Ergo, vBrain [1,4] dovrebbe essere (vBrain [0,4] / 8) -1. Lavorare in questo modo siamo in grado di trovare i valori ottimali per il "cervello", ma ancora una volta, questo è non quello che mi interessa. Voglio una algoritmo per trovare i migliori valori .

Ho implementato questo quadro in modo che sia totalmente deterministica. Non c'è valori casuali aggiunti ai punteggi, e se diverse piazze hanno lo stesso punteggio sarà scelto in alto a sinistra.

problema reale

Questo è tutto per l'introduzione, ora alla parte interessante (per me, almeno)

Ho due "cervelli", vBrain1 e vBrain2. Come dovrei fare queste iterativo meglio? Immagino qualcosa di simile:

1. Inizializza vBrain1 e vBrain2 con valori casuali.
2. Simulare un gioco tra di loro.
3. assegnare i valori dal vincitore al perdente, quindi modificare casualmente uno di loro un po '.

Questo non sembra il lavoro. I cervelli non ottengono più intelligente. Perché?

Se il punteggio-metodo di aggiungere alcuni piccoli valori casuali al risultato, in modo che due partite tra le stesse due cervelli sarebbero diverse? Quanto dovrebbero cambiare i valori per ogni iterazione? Come dovrebbero essere inizializzate il "cervello"? Con valori costanti? Con valori casuali?

Inoltre, questo ha niente a che fare con AI o algoritmi genetici a tutti?

PS: La domanda non ha nulla a che fare con cinque di fila. Questo è solo qualcosa che ho scelto perché posso dichiarare una molto semplice "Brain" per sperimentare su.

Answer 1

In generale, sì, si può fare un cervello più intelligente utilizzando tecniche di algoritmi genetici.

La casualità, o la mutazione, gioca un ruolo significativo sulla programmazione genetica.

Mi piace questo tutorial, genetica algoritmi: fredda Nome & Accidenti semplice
. (Esso utilizza Python per gli esempi, ma non è difficile capire loro)

Answer 2

Se si vuole affrontare questo problema come un algoritmo genetico, avrete bisogno di un intera popolazione di "cervello". Poi li valutare uno contro l'altro, o ogni combinazione o utilizzare uno stile di torneo. Quindi selezionare la parte superiore X% della popolazione e usare quelli come i genitori della generazione successiva, dove si creano prole attraverso la mutazione (che si ha) o incrociato genetica (ad esempio, le righe di swap o colonne tra due "cervelli").

Inoltre, se non si vede alcun progresso evolutivo, potrebbe essere necessario più di un semplice vincita / perdita, ma trovare un qualche tipo di sistema di punti in modo da poter classificare l'intera popolazione in modo più efficace, il che rende la selezione più facile.

Answer 3

Date un'occhiata a neuroevoluzione di aumentare Tologies (NEAT) . Un acronymn fantasia che in pratica significa l'evoluzione delle reti neurali - sia la loro struttura (topologia) e pesi delle connessioni. Ho scritto un'implementazione .Net chiamato SharpNEAT che si potrebbe desiderare di guardare. SharpNEAT V1 ha anche un esperimento di Tic-Tac-Toe.

http://sharpneat.sourceforge.net/