{"id":161,"date":"2011-03-07T03:15:23","date_gmt":"2011-03-07T02:15:23","guid":{"rendered":"http:\/\/julia2.lucaamore.com\/?p=161"},"modified":"2025-12-01T18:24:17","modified_gmt":"2025-12-01T16:24:17","slug":"ai-giocatore-artificiale-di-reversi","status":"publish","type":"post","link":"https:\/\/www.lucaamore.com\/?p=161","title":{"rendered":"AI: sviluppo di un giocatore artificiale di Reversi"},"content":{"rendered":"

Nei 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\u00e0 contro forza, tensione tra grande visione d’insieme ed imponente valutazione di ogni dettaglio. <\/em>L’epilogo pu\u00f2 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.<\/p>\n

\"\"<\/a><\/p>\n

Sfide dove a vincere \u00e8 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.<\/p>\n

In questo articolo<\/a>, ho trovato una citazione degli autori del programma scacchistico\u00a0Deep Throught<\/a> (precursore di Deep Blue<\/a>) sullo stile di gioco del calcolatore:<\/p>\n

\n

“… 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\u00e0. Eppure talvolta produce intuizioni che sfuggono anche a grandi maestri.”<\/p>\n<\/blockquote>\n

(Hsu<\/a>, F., Anantharaman, T., Campbell, M., Nowatzyk, A. – “A Grandmaster Chess Machine<\/em>“, Scientific American, Ottobre 1990)<\/p>\n

realizzazione di Reversi42 in Python<\/strong><\/p>\n

\"Reversi42<\/a>

Reversi42 screenshot<\/p><\/div>\n

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: “<\/em>The Ultimate Question of Life, the Universe and Everything<\/em><\/a>“)<\/em>.<\/p>\n

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

Reversi42, come altre mie realizzazioni, \u00e8 un software libero<\/a> rilasciato sotto la licenza GNU\/GPL<\/a>; siete incoraggiati a studiarne il sorgente, migliorarlo e farci tutto ci\u00f2 che desiderate; ogni commento o contributo sar\u00e0 gradito.<\/p>\n

\"Il<\/a><\/p>\n

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

\"Reversi42<\/a>

Reversi42 screenshot<\/p><\/div>\n

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\u00e0 l’albero delle possibili mosse valutando la bont\u00e0 di ogni posizione ottenuta; si assume, inoltre, che l’avversario risponda sempre con la migliore mossa disponibile.<\/p>\n

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.<\/p>\n

Citando\u00a0Donald E. Knuth<\/a>:<\/p>\n

\n

\u201cWe should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil<\/strong>. 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\u201d.<\/p>\n<\/blockquote>\n

\"GRhino<\/a>

screenshot sfida tra GRhino e Reversi42 (test)<\/p><\/div>\n

Ho comunque introdotto alcune metriche (certamente migliorabili) per valutare efficienza e sensitivit\u00e0 (rispetto a modifiche) dei punti critici dell’algoritmo.<\/p>\n

La guida di riferimento che ho adottato \u00e8: “Stategy Game Programming”<\/a> 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).<\/p>\n

Le problematiche affrontate nella realizzazione del prototipo sono:<\/p>\n