martedì 3 agosto 2021

Tesi di laurea a Trento sugli engine per gli scacchi

 






Non è che tutti i giorni si vedono tesi di laurea a tema scacchistico. Ebbene, Andrea Zanin di Arco ne ha discusso una pochi giorni fa alla Facoltà di matematica dell'Università di Trento. L'ex ragazzino combattente nei tornei giovanili provinciali - vedi la foto di una dozzina d'anni or sono - ha centrato con lode la laurea triennale, svolgendo appunto un lavoro dal titolo "Algoritmi e strutture dati per il gioco degli scacchi". Seguito dal professor Alberto Montresor, ordinario di informatica presso il Dipartimento di ingegneria e scienza dell'informazione dell'ateneo, Andrea ha preso le mosse (è il caso di dire...) dai primi algoritmi sviluppati negli anni '50 e '60, citando geni matematici del secolo scorso come Alan Turing e Erns Zermelo, che si sono applicati alle mostruose complicazioni del nostro amato gioco.

Nella sua tesi, che per chi ha fatto studi umanistici ovviamente è scritta in aramaico antico, approfondisce le strutture dati usate per rappresentare la scacchiera, gli algoritmi di esplorazione delle mosse possibili e le euristiche per la valutazione di una posizione di gioco. Il metodo seguito per definire la mossa ottima - scrive Andrea - è quello proposto da Von Neumann nella sua teoria dei giochi, ossia il metodo dell'induzione a ritroso. La tesi evidenzia come gli engine scacchistici chiamano in causa varie branche della matematica: dalle costruzioni algebriche come le sequenze di De Bruijn a metodi di inferenza statistica come in ProbCut e tecniche di calcolo numerico come Spsa.

Chicca finale del lavoro, la "costruzione" di un vero motore scacchistico, realizzato da Andrea in linguaggio Go e con un codice sorgente messo a disposizione on line. L'engine gioca a livello di un amatore, ma funziona! Da ultimo la tesi sintetizza dove sta andando il settore: negli ultimi anni i programmi di scacchi sono diventati più forti per il miglioramento degli algoritmi applicati, più che della potenza "bruta" dei computer. Ultimamente si sono affacciati algoritmi basati sul machine learning e sulla Monte Carlo Tree Search (vedi Alpha Go), ma i più forti engine - vedi Stockfish - adottano un approccio ibrido: metodo tradizionale più metodo avveniristico. Risultato: computer imbattibili dall'uomo.  


Nessun commento:

Posta un commento