Un'esplorazione dell'intelligenza artificiale evolutiva
Algoritmi Evolutivi (EA) sono un sottoinsieme dell'intelligenza artificiale che risolve problemi utilizzando metodi ispirati all'evoluzione biologica. Dall'ottimizzazione delle reti neurali alla pianificazione delle risorse, hanno una straordinaria gamma di applicazioni nel mondo reale. La loro bellezza emerge attraverso uno spostamento dell'attenzione su ciò che è necessario per risolvere un problema. Invece di descrivere i passaggi necessari per raggiungere un obiettivo, gli EA descrivono come si presenta l’obiettivo.
In questo articolo esplorerò come utilizzare questa fantastica intelligenza artificiale per generare puzzle di scacchi, i vantaggi che offre e gli svantaggi che dobbiamo considerare.
Un puzzle di scacchi è una posizione di scacchi legale, in cui una combinazione unica di mosse si traduce in una vittoria, che spesso finisce con uno scacco matto. Solitamente vengono trovati analizzando i database di giochi competitivi tra giocatori umani.
Generando i miei enigmi utilizzando nient'altro che codice, casualità e un pizzico di biologia, è possibile creare un database di enigmi interessante e diversificato. Esploriamo come.
Gli algoritmi evolutivi in genere funzionano generando in modo casuale un'ampia popolazione di risultati, quindi selezionando i risultati “più adatti” utilizzando un'euristica e infine prendendo quei risultati “più adatti” e generando successive popolazioni casuali. Si ispirano alla teoria della selezione naturale di Darwin, secondo la quale gli animali di una popolazione che hanno maggiori probabilità di sopravvivere hanno anche maggiori probabilità di trasmettere i propri tratti alla generazione successiva. Dopo molte generazioni, a volte centinaia di migliaia, la popolazione converge verso un risultato ottimale. Allora come possiamo applicare questo agli scacchi?
Con gli scacchi, possiamo creare una popolazione di posizioni legali casuali simulando partite in cui il programma, a turno, gioca mosse casuali per il bianco e il nero un numero casuale di volte. Ripetendo questo processo decine di migliaia di volte, è possibile analizzare grandi campioni di posizioni casuali per verificarne l'idoneità.
Di seguito puoi vedere una funzione dal mio file Asse class, che restituisce un elenco di mosse.
public List<(int() from, int() to)> GetAllPotentialMoves(Colour currentColour)
{
var activePieces = ActivePieces.Find(p => p.colour == currentColour);
var allLegalMoves = new List<(int() from, int() to)>();foreach (var piece in activePieces.pieces)
{
var moves = piece.GetLegalMoves(this);
allLegalMoves.AddRange(moves);
}
return allLegalMoves;
}
Una volta generata una popolazione di posizioni, inizia la vera parte difficile. La chiave di qualsiasi algoritmo evolutivo è il modo in cui valuti la tua euristica. Nel mio caso, per un puzzle sono state considerate solo le posizioni in cui un'unica soluzione portava allo scacco matto. Dopo aver ristretto questi risultati, l'euristica è una misura di quanto sia difficile scegliere le mosse corrette per vincere la partita. Ma come può un programma per computer stimare quanto sia difficile per un essere umano interpretare una posizione negli scacchi?
Un'opzione è guardare la struttura del puzzle. Il re è salvo? Ci sono mosse che non risolvono il puzzle, ma sembrano belle? Sacrifichiamo qualche materiale? Quali pezzi stiamo muovendo? Valutando molti fattori, possiamo creare una misura della difficoltà. Il problema con questo approccio è che è davvero difficile decidere come creare un punteggio finale partendo da così tanti fattori. Inoltre, le regole rigide ignorano completamente i pregiudizi nella percezione umana. Potrebbe darsi che anche piccoli cambiamenti alla posizione degli scacchi rendano molto più difficile per alcuni individui scegliere la mossa corretta.
Quindi, come possiamo avere un’idea migliore delle prestazioni umane? Utilizzando grandi database pieni di giochi reali, i modelli di apprendimento automatico sono stati addestrati a giocare a scacchi come giocatori di determinati livelli. Attraverso questi modelli possiamo avere un'idea migliore di come i giocatori con abilità diverse potrebbero tentare un puzzle. Riuscirà un'IA addestrata su 1200 giocatori classificati a risolvere il puzzle? E che dire del 1600, 1900? Il vantaggio di questo approccio è che scava più a fondo nella mente dei giocatori reali. Tuttavia, i modelli di apprendimento automatico non sono privi di inconvenienti. Queste IA non giocano come un giocatore reale, giocano come un'approssimazione di un giocatore. Sono anche addestrati su giochi reali e regolari, il che significa che potrebbero essere inaffidabili nel valutare posizioni di scacchi casuali.
Combinando i modelli di machine learning con una valutazione complessa e dettagliata basata su regole, ho creato uno scenario di tipo migliore di entrambi i mondi. Un’euristica che comprende sia la composizione del puzzle, sia allo stesso tempo considerando il modo in cui gli esseri umani potrebbero affrontarlo.
Una volta trovati i migliori enigmi di una popolazione, il passo successivo è creare nuove generazioni. Questo può essere fatto attraverso molte tecniche ispirate all’evoluzione. Ho scelto di utilizzare crossover e mutazione.
Il crossover prevede l'unione casuale delle caratteristiche di due risultati nella speranza che tu possa ottenere le migliori caratteristiche di entrambi. Possiamo incrociare posizioni di scacchi simili tornando indietro di una serie di mosse fino a un punto di partenza condiviso, quindi selezionando le mosse legali utilizzate per raggiungere ciascun risultato. Forse spostare la regina ha dato a un puzzle una proprietà davvero buona, e spostare il cavallo ha reso interessante un altro puzzle. Combinando entrambe queste caratteristiche creiamo un problema ancora più avvincente.
Allo stesso modo, possiamo modificare i puzzle tornando indietro e poi andando avanti di una serie di mosse. A seconda del numero di mosse che fai avanti e indietro, il puzzle può cambiare in modo sottile o massiccio. Troppa mutazione e potresti scoprire che l'algoritmo non migliorerà mai, troppo poca e il tuo miglior risultato potrebbe convergere su un singolo valore troppo rapidamente.
Il problema più comune con gli algoritmi evolutivi è la convergenza troppo rapida. Inizialmente, i puzzle che generavo smettevano di migliorare dopo solo poche generazioni. Nel mondo reale, i confini fisici come montagne, deserti e mari hanno impedito alle popolazioni di oltrepassare il proprio DNA, consentendo la preservazione della diversità genetica. Senza una sufficiente diversità genetica, una popolazione non si evolverà molto. Eseguendo popolazioni più piccole di puzzle di scacchi in parallelo per un po', ho dato loro abbastanza respiro per mantenere una certa diversità ed evitare di convergere troppo presto.
Gli algoritmi evolutivi possono anche essere molto lenti. Gli scacchi non fanno certamente eccezione. L'esecuzione di una valutazione euristica su milioni di posizioni degli scacchi richiede una notevole quantità di elaborazione. In generale, quanto più a lungo si fa funzionare un motore scacchistico su una posizione, tanto più accurato sarà in grado di prevedere la mossa migliore successiva. Trovando il punto giusto nel tempo impiegato ad analizzare ciascuna posizione, selezionando quelle più promettenti e osservandole in modo molto più dettagliato, ho potuto ottimizzare il tempo in modo ragionevole. Anche decidere quando smettere di generare è cruciale. Se un campione ha smesso di migliorare per diverse generazioni, forse è meglio ricominciare con una nuova popolazione casuale, poiché potrebbe non essere in grado di migliorare ulteriormente. Dopo innumerevoli ottimizzazioni, il mio PC di casa è in grado di generare oltre 1000 puzzle impegnativi al giorno utilizzando l'evoluzione.
Infine, diagnosticare gli errori può essere incredibilmente difficile. Con molti programmi puoi aspettarti determinati output dati determinati input. Con l'evoluzione la situazione è diversa. Ho passato molto tempo a grattarmi la testa chiedendomi perché la mia popolazione stesse convergendo troppo rapidamente. Si trattava di generazione di posizione? Erano i metodi evolutivi, forse l'euristica? Può essere facile nemmeno accorgersi se alcune cose non funzionano come previsto quando l'output atteso di un programma non può essere chiaramente definito.
Tuttavia, problemi a parte, la potenza e il potenziale di questa tecnica di intelligenza artificiale brillano affinché tutti possano vederli. Usando solo il mio vecchio PC sono riuscito a generare quasi 50.000 puzzle di scacchi in 3 mesi, contenenti un'abbondanza di posizioni strane e meravigliose.
La natura casuale dell'algoritmo fa sì che crei una serie di puzzle incredibilmente colorati e diversificati. Interessanti problemi tattici che raramente vediamo negli scacchi, come i sacrifici della regina, le promozioni dei cavalieri e l'en passant, sono facili da trovare utilizzando l'evoluzione, ma difficili utilizzando i database di partite reali. Tuttavia, la natura priva di senso degli enigmi li rende meno applicabili agli scenari del mondo reale. Sebbene siano molto divertenti, si potrebbe sostenere che i puzzle basati su giochi reali sono migliori per apprendere schemi comuni nei giochi di scacchi.
Oltre ad essere incredibilmente produttivo, l’algoritmo è anche eccezionalmente flessibile. Shatranj, scacchiere sbilenche, è facile estendere l'EA per funzionare con qualsiasi derivato degli scacchi. Questa natura estensibile è il punto in cui la tecnica evolutiva eccelle davvero. Non puoi farlo con i database dei giochi, perché semplicemente non esistono!
Sebbene per molti sia un angolo dimenticato dell'intelligenza artificiale, ho mostrato come l'evoluzione possa essere utilizzata per creare una nuova soluzione a un problema del mondo reale. C'è molto potenziale inesplorato con questa tecnologia. Con l'intelligenza artificiale generativa in aumento, mi chiedo quali altre applicazioni originali le persone troveranno per gli EA in futuro…
Puoi provare tu stesso i puzzle sul mio sito web, chesspuzzler.com.
Se non diversamente specificato, tutte le immagini sono dell'autore.
Fonte: towardsdatascience.com
