AI: sviluppo di un giocatore artificiale di Reversi

Il TurcoNei giochi di strategia a turni, ho sempre ammirato le grandi sfide tra uomo e calcolatore; epiche battaglie tra pensiero strategico umano e forza tattica del calcolatore; equilibrio precario tra sinapsi e silicio, agilità contro forza, tensione tra grande visione d’insieme ed imponente valutazione di ogni dettaglio. L’epilogo può essere violento: il pensiero strategico umano si prende gioco della miopia del calcolatore e lo annichilisce; la forza bruta del calcolatore devasta il giocatore umano conducendolo verso una combinazione di cui ha previsto ogni minima variante.

Sfide dove a vincere è sempre l’uomo: il grande maestro oppure la squadra di progettisti che ha concepito un giocatore artificiale in grado di competere contro la finezza del pensiero umano.

In questo articolo, ho trovato una citazione degli autori del programma scacchistico Deep Throught (precursore di Deep Blue) sullo stile di gioco del calcolatore:

“… il computer non imita il pensiero umano – raggiunge gli stessi obiettivi per vie diverse. Vede lontano, ma osserva poco; ricorda tutto, ma non impara niente. Non fa sbagli clamorosi, ma non si innalza mai al disopra della sua normale abilità. Eppure talvolta produce intuizioni che sfuggono anche a grandi maestri.”

(Hsu, F., Anantharaman, T., Campbell, M., Nowatzyk, A. – “A Grandmaster Chess Machine“, Scientific American, Ottobre 1990)

realizzazione di Reversi42 in Python

Reversi42 screenshot

Reversi42 screenshot

In questi giorni ho provato a realizzare un prototipo di giocatore automatico di Reversi in Python (sto approfondendo ancora la conoscenza di questo linguaggio) che ho battezzato Reversi42 (in onore di Douglas Adams e della famosa domanda: “The Ultimate Question of Life, the Universe and Everything“).

Non finirò mai di ringraziare Donato Barnaba, maestro della FNGO (Federazione Nazionale Gioco Othello), per il suo prezioso aiuto, la sua disponibilità e grande competenza (anche dal punto di vista dei giocatori automatici); senza di lui lo sviluppo di Reversi42 non sarebbe stato così stimolante e divertente! Reversi42, allo stato attuale, è solo un prototipo; eventuali imprecisioni sono da attribuire solo a me!

Reversi42, come altre mie realizzazioni, è un software libero rilasciato sotto la licenza GNU/GPL; siete incoraggiati a studiarne il sorgente, migliorarlo e farci tutto ciò che desiderate; ogni commento o contributo sarà gradito.

Di Reversi esiste un libro di Brian Rose che lo presenta così: “un minuto per imparare… una vita per diventare maestri”; le regole del gioco sono facili da apprendere (e quindi da codificare) ma il gioco può essere estremamente complesso dal punto di vista strategico e tattico (ottima sfida per la realizzazione di un giocatore automatico).

Reversi42 screenshot

Reversi42 screenshot

Nella progettazione del motore AI di gioco, ho deciso di adottare l’approccio classico che viene adottato in tutti i giochi di strategia ad informazione perfetta per due giocatori: si esplora in profondità l’albero delle possibili mosse valutando la bontà di ogni posizione ottenuta; si assume, inoltre, che l’avversario risponda sempre con la migliore mossa disponibile.

Trattandosi di un prototipo, sviluppato principalmente nei ritagli di tempo, ho voluto concentrare la mia attenzione solo sugli algoritmi e non sull’ottimizzazione delle singole procedure.

Citando Donald E. Knuth:

“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified”.

GRhino vs Reversi42

screenshot sfida tra GRhino e Reversi42 (test)

Ho comunque introdotto alcune metriche (certamente migliorabili) per valutare efficienza e sensitività (rispetto a modifiche) dei punti critici dell’algoritmo.

La guida di riferimento che ho adottato è: “Stategy Game Programming” di Martin Fierz che propone un graduale ed avvincente percorso tra le principali tecniche adottate per la costruzione di un buon giocatore automatico per giochi strategici (es. scacchi, dama, Reversi, forza quattro).

Le problematiche affrontate nella realizzazione del prototipo sono:

  • ricerca nell’albero delle posizioni della mossa più efficace
  • realizzazione di una buona valutazione della posizione
  • sintesi delle regole del gioco Reversi

Ricerca nell’albero delle posizioni della mossa più efficace

Lo scopo di questo problema (indipendente dal tipo di gioco) è quello di costruire l’albero di tutte le mosse possibili e percorrerlo in profondità ricercando la mossa migliore; si assume che l’avversario giochi sempre le mosse migliori.

All’aumentare della profondità di analisi (D), che condiziona la forza del giocatore, il numero di mosse da valutare (M) cresce esponenzialmente in funzione del fattore Branch Factor medio (B) tipico di ogni gioco.

M=B^{D}

Valori tipici del Branch Factor medio (B):

GiocoBranch Factor (B)
Reversi7
Forza quattro7
Dama10
Scacchi40
Go300 (!!!)
M=BF^DF

andamento del numero di mosse da analizzare al variare del gioco e profondità (in scala semilogaritmica)

Il mio obiettivo era quello di raggiungere una profondità di gioco (D) di 5-8 al fine di realizzare un giocatore automatico discreto; sul mio netbook riesco a giocare, a profondità (D) pari a 6, con tempi di attesa sempre ragionevoli (inferiori al minuto).

L’algoritmo di ricerca adottato è quello della potatura alfa-beta (in forma negamax), estremamente più efficace del minimax poichè è in grado di escludere dalla ricerca (pruning) interi rami dell’albero che condurrebbero a mosse non convenienti rispetto ad altre già individuate.

Per massimizzare il numero di rami da potare è opportuno introdurre un criterio euristico per ordinare in sequenza le mosse da valutare; le migliori mosse dovrebbero esser analizzate per prime. Rispetto all’algoritmo minimax, che richiede l’analisi di tutto l’albero delle possibili mosse (M=B^{D}), nel caso migliore della potatura alfa beta, ovvero nel caso ideale di ordinamento perfetto (le mosse più forti vengono valutate per prime), le posizioni da analizzare si abbattono a M=\sqrt{B^D}=B^{\frac{D}{2}}; siamo in grado di raddoppiare la profondità di analisi a parità di risorse di calcolo impiegate!

Il criterio euristico, con il quale vengono ordinate le mosse prima dell’alfa-beta su Reversi42, è quello di assegnare una priorità statica a tutte le mosse della scacchiera; le celle che hanno un valore più basso hanno maggiore priorità e vengono esplorate per prime (es. gli angoli).

18766781
89744798
75322357
642246
642246
75322357
89744798
18766781

Da quando è stato adottato questo ordinamento, le prestazioni della ricerca sono aumentate notevolmente; molto spesso la mossa migliore ricade tra le prime analizzate.

Valutazione della posizione

La valutazione della posizione è un elemento cruciale di un giocatore artificiale in quanto  ne condiziona: strategia, tattica ed efficienza. Occorre ponderare due parametri contrastanti: l’accuratezza dell’analisi e l’efficienza computazionale. Riuscire a trovare un compromesso ottimale tra queste due caratteristiche è un arte che si affina con l’esperienza! Un algoritmo di valutazione troppo accurato potrebbe rallentare la ricerca e quindi penalizzare eccessivamente la profondità di analisi; un algoritmo rapido ma poco accurato potrebbe perdere grandi opportunità.

In questo prototipo ho impostato la partita su due momenti distinti:

  • apertura e mediogioco: meno del 70% delle pedine non sono state giocate
  • finale: almeno il 70% delle pedine sono state giocate

In apertura e mediogioco ho cercato di massimizzare la mobilità, ovvero il numero di mosse disponibili che potranno essere utilizzate per dominare il finale; ho anche assegnato dei pesi ad alcune case strategiche che concorrono alla conquista degli angoli (caselle stabili).

10-30000-310
-3-70000-7-3
00000000
00000000
00000000
00000000
-3-70000-7-3
10-30000-310

Vengono assegnati punti di bonus se si occupano angoli mentre, se si conquistano delle case adiacenti agli angoli, vengono assegnate delle penalità poiché sarà più difficile difendere l’angolo dalla conquista avversaria. Le case adiacenti all’angolo perdono la loro penalità quando l’angolo è conquistato.

Nel finale si ricerca la vincita della partita oppure, grazie alla mobilità ottenuta in apertura e nel mediogioco, si inizia a massimizzare il numero di pedine possedute rispetto a quelle dell’avversario. L’errore fatale, tipico di giocatori mediocri di Reversi, è proprio quello di perseguire intuitivamente tale obiettivo sin dalla prima mossa.

Sorgenti

Visualizza o scarica i sorgenti dal repository su github

richiede:
python-pygame – SLD bindings for games development in Python

Share

John Conway’s Game of Life in Python

Come primo progetto in Python, ho deciso di realizzare una semplice versione del famosissimo automa cellulare di Conway: “Game of Life”.

jaGOF - just another Game of Life screenshoot

screenshot di jaGOF

Quick start

Per maggiori informazioni su Life vi rimando alla pagina di Wikipedia in italiano oppure in inglese ed ai vari riferimenti ed approfondimenti che citerò al termine di questo articolo.

Se utilizzate un browser che supporta l’HTML5 potete provare velocemente gameoflife.

The Game of Life

The Game of Life, concepito al termine degli anni 60 dal matematico britannico John Horton Conway, è un automa cellulare che simula l’evoluzione di una popolazione tramite regole che stabiliscono vita, nascita, morte di ogni singolo individuo.

La magia di questo gioco sta nella sua semplicità contrapposta alla profondità e complessità dell’esplorazione dei risultati; piccole variazioni di un solo individuo nella distribuzione della popolazione iniziale possono condurre ad evoluzioni totalmente diverse.

Ogni cella di una popolazione, transitando dallo stato di vita o morte, condiziona l’evoluzione delle celle confinanti; queste interazioni provocano evoluzioni estremamente complesse ed interessanti anche a partire da configurazioni apparentemente banali.

In molti si sono cimentati nella ricerca di configurazioni iniziali con determinate proprietà o nella classificazione sistematica dei possibili schemi o pattern ricorrenti.

Descrizione formale dell’algoritmo di evoluzione

Il mondo è costituito da una griglia rettangolare di N x M celle le quali possono essere in due possibili stati: vive o morte.

Due celle si definiscono confinanti se sono connesse in una delle 8 direzioni possibili (anche in diagonale); i confini del mondo sono tra loro connessi come in un pianeta perfettamente sferico.

Definita una configurazione iniziale di celle, l’automa simula l’evoluzione della vita. In intervalli di tempo discreti tutte le cellule del mondo vengono aggiornate simultaneamente (ogni aggiornamento è definito generazione o epoca) seguendo queste regole:

  • una cella viva rimane in vita se esistono 2 o 3 celle vive confinanti (sopravvivenza)
  • una cella viva muore se confina con meno di due celle vive (isolamento)
  • una cella viva muore se esistono piu’ di 3 celle confinanti (sovraffollamento)
  • una cella morta con esattamente 3 celle vive confinanti nasce e diventa viva (riproduzione)

Evoluzione e classificazione di alcuni schemi

L’evoluzione della popolazione può giungere verso l’estinzione totale della specie oppure verso varie tipologie di configurazioni ricorrenti che possono essere di:

  • tipo statico (blocco, barca)
  • oscillante (lampeggiatore, rospo)
  • in movimento o navicelle spaziali (aliante, astronave leggera LWSS)

Altri schemi estremamente interessanti sono:

  • fucili: stazionari che sparano alianti o navicelle spaziali
  • fumatori: si muovono lasciando in coda frammenti di vita
  • rastrelli: si muovono ed emettono navicelle
  • reattore: lascia una coda di fucili (tasso di crescita quadratico)

Su Wikipedia sono disponibili le configurazioni di questi schemi base oppure su ConwayLife Wiki o su  Life Lexicon è possibile trovare una classificazione ancora più accurata ed estesa.

jaGof: just another Game of Life (la mia realizzazione)

Per realizzare Life in Python ho utilizzato la libreria Pygame (python-pygame) che si basa su SDL. Potete scaricare i sorgenti di jaGof, rilasciati sotto licenza GNU/GPL v.3, e siete incoraggiati a farne quello che desiderate.

Nella directory seeds sono stati inclusi più di 400 pattern iniziali in formato .cell scaricati da Life Lexicon.

Ricordo che si tratta del mio primo progetto in Python.

Visualizza o scarica i sorgenti dal repository su github

Futuri sviluppi

Mi piacerebbe sviluppare un algoritmo automatico per la ricerca di qualche configurazione con determinate proprietà.

Riferimenti

gameoflifeWikipedia(it): “Gioco della vita”
LifeWiki
Life Lexicon Home Page

Share