Motore scacchistico

Un motore scacchistico (o, con locuzione inglese ampiamente utilizzata, chess engine) è un programma informatico che implementa il back-end di un software per il gioco degli scacchi. Il motore è la componente che analizza la posizione e produce una lista di mosse ottimali, tramite input e output in formato testuale, e viene tipicamente usato in combinazione con un'interfaccia grafica che implementa invece l'interazione con l'utente, mostrando graficamente la posizione sulla scacchiera e permettendo di eseguire le mosse tramite mouse o tastiera.

Il motore può essere utilizzato per giocare contro un avversario che può essere un umano, un altro motore oppure sé stesso, per analizzare una specifica posizione o per analizzare a posteriori un'intera partita già giocata. Sono disponibili motori commerciali, freeware e open source. Un motore scacchistico è un esempio tipico di intelligenza artificiale debole, ovvero un software di intelligenza artificiale che è in grado di affrontare solo il singolo problema specifico per cui è stato sviluppato.

Storia

Già nel corso del XVIII secolo sono stati realizzati diversi automi dedicati al gioco degli scacchi. Alcuni erano semplicemente delle truffe ben realizzate, guidate in realtà da esseri umani, come "Il Turco", "Mephisto" e "Ajeeb". Altri automi erano invece reali e funzionanti (come "El Ajedrecista"), ma solo in posizioni estremamente semplici.

Il vero sviluppo dell'intelligenza artificiale in campo scacchistico si avrà solamente dopo la nascita dell'informatica. Un pioniere dello sviluppo dell'informatica applicata agli scacchi è stato un ingegnere e, non a caso, uno dei più forti scacchisti del XX secolo: il sovietico Michail Botvinnik.^[1] Botvinnik ha studiato un algoritmo che riuscisse a compiere scelte intelligenti nella selezione delle mosse, ottenendo risultati positivi in situazioni piuttosto complesse ma non sufficienti a realizzare un valido software scacchistico.

Il primo computer in grado di sconfiggere un giocatore umano in condizioni regolamentari è stato Deep Thought. La macchina, progettata dall'informatico cinese della IBM Feng-hsiung Hsu, ha battuto lo scacchista David Levy nel 1989, vincendo una sfida lanciata da quest'ultimo per stimolare lo sviluppo dei computer scacchistici, che consisteva nel trovare un computer capace di batterlo in un match di quattro o sei partite. Deep Thought è stato quindi il primo motore scacchistico a competere ufficialmente al livello di un GM umano. Lo stesso anno Deep Thought ha affrontato Garri Kasparov, dal quale è stato sconfitto con un secco 2-0.

Kasparov è ricordato soprattutto per un altro incontro ufficiale, contro il computer IBM Deep Blue, disputato nel 1996, quando il giocatore russo era campione del mondo in carica e primo nella classifica Elo della FIDE. Fece scalpore la vittoria di Deep Blue nella prima partita, ma Kasparov si aggiudicò la sfida con 3 vittorie e 2 patte.^[2] La rivincita, un match di sei partite disputato l'anno successivo, venne deciso nella determinante ultima partita, vinta dal calcolatore che si aggiudica dunque l'incontro per 3,5-2,5. Il computer fu successivamente ritirato dall'IBM,^[3] rifiutando la richiesta di rivincita di Kasparov.

Un altro match di altissimo livello si è tenuto nell'ottobre 2002, quando Vladimir Kramnik (anch'egli campione del mondo in carica) pareggiò una sfida di otto partite, nota come Brains in Bahrain, contro il motore scacchistico Deep Fritz 7.^[4]

Nel febbraio 2003, sempre Kasparov pareggiò un incontro in sei partite contro il programma Deep Junior, e nel novembre dello stesso anno pareggiò un altro match contro il programma X3D Fritz a New York.^[5] Fritz vinse la seconda partita, Kasparov la terza. La prima e la quarta finirono in patta. È stato il primo incontro di scacchi ufficiale giocato interamente in realtà virtuale.

Tra gli ultimi capitoli riguardo agli incontri uomo-computer, vi è stato il match "evento" tra l'allora campione del mondo Vladimir Kramnik e il software Deep Fritz, tenutosi alla fine di novembre 2006. Il match sulla lunghezza delle sei partite ha visto la vittoria del computer con un risultato di 4 a 2 (quattro patte e due vittorie del computer).^[6] Insolito l'epilogo della seconda partita, in cui il campione del mondo non si è accorto di un'elementare minaccia di matto in una mossa da parte del computer, evento rarissimo a questi livelli.

A partire dalla seconda metà degli anni 2000, i motori scacchistici hanno superato definitivamente le capacità umane, riuscendo a sconfiggere sistematicamente i giocatori più forti, e sono divenuti uno strumento importante nell'analisi e nell'allenamento dei giocatori umani.

Verso la fine degli anni 2010 sono stati sviluppati nuovi approcci nel design di algoritmi per il gioco degli scacchi. La prima dimostrazione di fattibilità di queste nuove tecniche venne presentata nel 2017 da DeepMind con lo sviluppo di AlphaZero, e i risultati sono stati in seguito riprodotti da progetti open source, come Leela Chess Zero, e da prodotti commerciali.

Principi di funzionamento

Un motore scacchistico è formato da tre componenti principali: la rappresentazione della posizione, l'algoritmo di ricerca, e la funzione euristica usata per la valutazione di una posizione.

La rappresentazione della posizione è il modo in cui il motore codifica al proprio interno la posizione sulla scacchiera, in genere attraverso una bitboard, insieme ad informazioni ausiliarie quali tratto, possibilità di arrocco o cattura en passant, e il numero di mosse trascorse dall'ultima cattura (rilevante per l'applicazione della regola delle cinquanta mosse).

La qualità di una posizione è valutata tramite una funzione euristica, che associa ad ogni posizione un valore numerico: zero indica parità, valori positivi indicano vantaggio del Bianco, negativi del Nero, e l'importanza del vantaggio dipende dal valore assoluto. Tipicamente, un valore unitario corrisponde approssimativamente ad un pedone di vantaggio. Tradizionalmente le funzioni euristiche sono implementate manualmente e basate su conoscenza esperta umana del gioco, anche se approcci basati su tecniche di apprendimento automatico stanno trovando applicazione.

I software scacchistici tradizionali si basano su varianti della ricerca ad albero minimax con potatura alfa-beta per determinare la mossa ottimale ad ogni turno, e i principali punti critici dei vari algoritmi che determinano la forza dei singoli motori sono la tecnica di potatura e la funzione euristica. Questo approccio è soggetto all'effetto orizzonte e determina il limite nella visione strategica dei motori: per quanto insuperabili nel gioco tattico, i motori tradizionali faticano ad avere una visione chiara degli effetti a lungo termine di ogni mossa, nella cui analisi gli umani sono invece tipicamente abili.

Tra gli approcci alternativi una possibilità è rappresentata dalle tecniche di apprendimento profondo che hanno visto significativi progressi negli anni 2010. In particolare alcuni risultati promettenti sono stati ottenuti con la ricerca ad albero Monte Carlo guidata da una rete neurale convoluzionale profonda addestrata per rinforzo. Nel dicembre 2017 DeepMind ha introdotto AlphaZero, un algoritmo che implementa questo approccio per competere in una varietà di giochi da tavolo, inclusi gli scacchi, e promette una forza superiore rispetto ai software tradizionali con uno stile più simile al gioco umano.^[7] Tale metodo è stato reimplementato a breve distanza dal motore open-source Leela Chess Zero, progetto avviato all'inizio del 2018 e che in breve tempo ha raggiunto un livello di forza di gioco paragonabile ai più forti motori tradizionali.^[8]

L'input e output delle mosse avviene tipicamente attraverso un protocollo testuale come Universal Chess Interface (UCI) o Chess Engine Communication Protocol^[9], che permette di controllare il motore tramite interfacce grafiche che implementano lo stesso protocollo.

Nelle fasi iniziale e finale della partita il motore può inoltre usare dei database che aumentano la sua forza di gioco. In apertura viene usato un repertorio ("libro di apertura", in inglese opening book) ottenuto selezionando i tratti iniziali di un gran numero di partite. Tra i formati più comuni per il libro di apertura vi sono CTG, formato proprietario di ChessBase, ABK, usato da Arena, e BIN, usato da PolyGlot. Nel finale i motori possono usare le tablebase, che forniscono il risultato a gioco corretto per ogni posizione contenente fino ad un certo numero prefissato di pezzi, insieme alla sequenza di mosse che porta a tale risultato. Esistono tablebase complete fino a sette pezzi, che richiedono tuttavia una quantità notevole di memoria (140 TB), per cui spesso in pratica si fa uso di tablebase a sei pezzi (1,4 TB). In alternativa alle tablebase, il motore può fare uso di una bitbase, che contiene solo l'esito a partire da ciascuna posizione senza riportare le mosse necessarie, richiedendo una quantità molto minore di memoria.

Forza di gioco

I moderni programmi di scacchi hanno una forza di gioco sovrumana. Il primo computer in grado di battere un maestro umano in un incontro in condizioni regolamentari è stato Deep Thought che nel 1989 ha battuto il maestro internazionale David Levy. Punto di svolta è considerato il secondo incontro tra IBM Deep Blue e Garri Kimovič Kasparov, disputato nel 1997, quando per la prima volta un computer batté in un match il campione del mondo in carica. Nei primi anni 2000 si sono svolti diversi incontri in condizioni regolamentari e senza handicap tra motori e giocatori umani ai massimi livelli conclusi in parità, come Brains in Bahrain e X3D Fritz, e negli anni seguenti la crescente forza di gioco dei software e l'aumento della potenza di calcolo dell'hardware commerciale hanno portato i motori scacchistici ad un livello di gioco nettamente superiore ai migliori maestri umani.

Esistono classifiche Elo che confrontano la forza di motori scacchistici, ottenute facendo giocare i motori l'uno contro l'altro con lo stesso hardware. Diverse classifiche si differenziano in genere per la diversa cadenza di gioco. La classifica curata dalla Svenska schackdatorföreningen (SSDF)^[10] è una tra le prime del suo genere e comprende dati a partire dal 1984, documentando l'evoluzione storica della forza di gioco. Altre classifiche includono CEGT,^[11] CCRL,^[12] CSS^[13] e WBEC.^[14] L'Elo delle varie classifiche si evolve indipendentemente e non è comparabile, così come non è comparabile con l'Elo nel gioco umano (e.g. l'Elo FIDE).

Eventi

L'International Computer Games Association, riconosciuta dalla FIDE^[15], organizza dal 1977 il Campionato del mondo di scacchi per computer, e varie organizzazioni nazionali, come Computerschaak Vereniging Nederland (CSVN) e Svenska schackdatorföreningen (SSDF), o altri enti privati organizzano o hanno organizzato tornei internazionali, come l'International Computer Chess Tournament, il Dutch Open Computer Chess Championship, l'International Paderborn computer chess championship e, in Italia, il Campionato italiano per programmi di scacchi. Tali eventi tradizionali prevedono tipicamente la partecipazione in persona degli sviluppatori, l'uso di hardware a discrezione dei partecipanti, e requisiti stringenti di originalità del software. Negli anni 2010 altri eventi indipendenti, con organizzazione più moderna e requisiti di partecipazione meno onerosi, hanno assunto maggiore importanza, in particolare il Top Chess Engine Championship (TCEC), considerato il campionato di scacchi de facto per computer.^[16]

Note

1. (EN) Chess Programming Part III: Move Generation (François Dominic Laramée), su gamedev.net, 6 gennaio 2011. URL consultato il 13 febbraio 2011 (archiviato dall'url originale il 12 febbraio 2009).
2. (EN) IBM Research, su research.ibm.com. URL consultato il 13 febbraio 2011.
3. (EN) IBM Research, su research.ibm.com. URL consultato il 13 febbraio 2011.
4. (EN) Fritz Defends to Draw Game 8 and the Match! Final Score: 4-4, su chessbase.com, ChessBase News. URL consultato il 13 febbraio 2011.
5. (EN) Kasparov vs X3D Fritz match finishes 2-2 after game four draw, su chessbase.com, ChessBase News. URL consultato il 13 febbraio 2011.
6. (EN) Kramnik vs Deep Fritz: Computer wins match by 4:2, su chessbase.com, ChessBase News. URL consultato il 13 febbraio 2011.
7. (EN) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis, A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play, in Science, vol. 362, n. 6419, 7 dicembre 2018, pp. 1140-1144, DOI:10.1126/science.aar6404.
8. TCEC archive, su tcec.chessdom.com. URL consultato il 31 gennaio 2019 (archiviato dall'url originale il 3 maggio 2015).
9. (EN) Tim Mann e H.G.Muller, Chess Engine Communication Protocol, su gnu.org. URL consultato il 28 settembre 2016.
10. SSDF Rating List, su ssdf.bosjo.net, SSDF, 26 settembre 2008. URL consultato il 13 gennaio 2017.
11. CEGT 40/20, su husvankempen.de, Chess Engines Grand Tournament, 28 marzo 2010. URL consultato il 13 gennaio 2017 (archiviato dall'url originale l'8 marzo 2011).
12. CCRL 40/40 - Lista completa, su computerchess.org.uk, 6 marzo 2010. URL consultato il 13 gennaio 2017.
13. Computerschach und Spiele - Eternal Rating, su computerschach.de, Computerschach und Spiele, 18 marzo 2007. URL consultato il 21 maggio 2008.
14. BayesianElo Ratinglist of WBEC Ridderkerk, su wbec-ridderkerk.nl. URL consultato il 20 luglio 2008.
15. ratings.fide.com, https://ratings.fide.com/fide_directory.phtml?list=966 Titolo mancante per url url (aiuto).
16. TCEC: Superfinal Houdini vs Komodo, su en.chessbase.com, ChessBase.
    
    «Over the years the "Thoresen Chess Engines Competition" (TCEC) has become the unofficial Computer World Championship […]»

Bibliografia

• Ciancarini, Paolo. I giocatori artificiali. Milano, Mursia, 1992. ISBN 88-425-1319-9.
• Hsu, Feng-hsiung. Behind Deep Blue : behind the computer that defeated the world chess champion. Princeton, Princeton University Press, 2002. ISBN 0-691-09065-3.
• Opfermann, Hans Carl. Gli scacchi con il computer. Milano, Mursia, 1982.
• Pachman, Ludek e Kuhnmund, Vas I. Computer chess. London, Routledge & Kegan, 1986. ISBN 0-7100-9785-9.

Collegamenti esterni

• (EN) Jim Ablett's Winboard Chess Projects - Download di motori scacchistici free e open source compilati da Jim Ablett
• (EN) WBEC Ridderkerk - Raccolta di motori freeware, nuovo rilasci, tornei, liste di rating e Forum di discussione
• (EN) Chess Programming Wiki, su chessprogramming.wikispaces.com. URL consultato il 9 luglio 2011 (archiviato dall'url originale il 14 luglio 2011).
• (EN) Talkchess - forum
• (EN) CCRL - Rating dei principali motori scacchistici, mensilmente aggiornato
• (EN) IPON - Rating dei principali motori scacchistici nelle varie versioni e per un solo tempo di gioco (5m +3s a mossa). Sempre aggiornato
• (EN) CEGT - Rating dei principali motori nelle varie versioni e per i diversi tempi di gioco
• (EN) ICGA - Sito ufficiale International Computer Games Association

Portale Informatica

Portale Scacchi