Motore scacchistico

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

Un motore scacchistico (o, con locuzione inglese ampiamente utilizzata, chess engine) è un programma informatico che può giocare a scacchi. 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.

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.

I software scacchistici tradizionali si basano su ricerca ad albero con potatura 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, motivo alla base della nascita degli scacchi avanzati. 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 Montecarlo 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.

Funzionamento[modifica | modifica wikitesto]

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

La rappresentazione della posizione è il modo in cui il motore codifica al proprio interno la posizione sulla scacchiera: questo è in genere ottenuto attraverso un array, con varie codifiche possibili, mentre nei motori più vecchi era ottenuto semplicemente con una lista dei pezzi presenti e delle rispettive posizioni. Deve inoltre memorizzare il giocatore a cui spetta la prossima mossa, se sono possibili gli arrocchi e la cattura en passant e il numero di mosse necessario a far scattare la regola delle cinquanta mosse.

L'algoritmo di ricerca ha la funzione di analizzare le possibili mosse e sceglierne una. Tutte le possibili evoluzioni di una partita vengono rappresentate con un albero (informatica) e il motore vi naviga con algoritmi minimax: ogni mossa viene scelta in modo da ridurre al minimo il massimo dei vantaggi che l'avversario potrà conseguire. Per velocizzare questa procedura e permettere una ricerca più approfondita nelle mosse più promettenti vengono utilizzati algoritmi di "potatura", come la potatura alfa-beta, che riducono il numero di mosse che vengono analizzate.

Poiché la ricerca non può arrivare fino allo scacco matto, è necessario che il motore possa valutare una posizione senza effettuare calcoli: questa valutazione si basa sia sul materiale presente nella scacchiera sia su considerazioni posizionali, ad esempio la presenza di pedoni doppiati o passati, ed è espressa con un numero positivo se la posizione è favorevole al Bianco negativo in caso contrario, in cui un'unità corrisponde circa ad un pedone.

La mossa scelta viene comunicata in forma testuale, attraverso la notazione algebrica; se il programma è dotato di un'interfaccia grafica (GUI), può rappresentarla anche con il movimento del pezzo sulla scacchiera. Generalmente l'interfaccia grafica è indipendente dal motore e comunica con esso attraverso dei protocolli; in questo caso un'interfaccia può supportare diversi motori e viceversa un motore può essere utilizzato attraverso varie interfacce. Alcune fra le interfacce più diffuse sono XBoard/WinBoard per i sistemi Unix-like e Microsoft Windows che usano l'omonimo protocollo di comunicazione e Arena che usa il protocollo UCI (Universal Chess Interface).[1]

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 delle aperture, in inglese opening book) ottenuto selezionando i tratti iniziali di un gran numero di partite. Spesso gli sviluppatori di un motore costruiscono un libro specifico per il loro programma; esistono anche libri, non legati ad un particolare programma, che possono essere installati all'interno di un qualsiasi motore.

Nel finale i motori usano le tablebase che consistono in un elenco di posizioni, del risultato a gioco corretto, ovvero senza errori, e della mossa da effettuare in ciascuna posizione. Al febbraio 2012 esistono tablebase che contengono tutte le posizioni con sei pezzi (compresi i due re) o meno, anche se quelle a sei pezzi richiedono molto spazio per essere memorizzate e quindi non vengono usate. In alternativa esistono le bitbase che omettono la mossa corretta. Le tablebase più note sono quelle di Nalimov e le EGTB.

Ogni motore ha alcune opzioni che possono essere configurate, permettendo di ottenere uno stile di gioco più o meno aggressivo, oppure di diminuire la forza di gioco per adeguarsi al livello dello sfidante umano. È inoltre possibile variare le risorse hardware richieste dal programma, come la dimensione della memoria usata.

Forza di gioco[modifica | modifica wikitesto]

I motori scacchistici, al pari dei giocatori umani, sono classificati per forza di gioco ed hanno un proprio rating Elo, ottenute facendo giocare i motori l'uno contro l'altro con lo stesso hardware e a volte con lo stesso libro delle aperture. Esistono diverse classifiche che si differenziano, oltre che per la configurazione hardware, anche per la cadenza di gioco.

Sebbene sia usato il punteggio Elo come per i giocatori umani, le classifiche dei motori e quella degli uomini non possono essere confrontate direttamente, così come non possono essere confrontati fra loro rating provenienti da diverse classifiche di motori in quanto non vi è nessuna corrispondenza e i valori evolvono indipendentemente in ogni classifica.

Rating list Cadenza di gioco
(mosse/minuti)
Anno
d'inizio
Ultimo aggiornamento Motori/Piattaforme
ammessi
Partite
giocate
I tre motori più forti Rating
CCRL[2] 40/40[3] 2005 11 gennaio 2017 1.813 681.664 Komodo 10.3 64-bit 4CPU
Stockfish 8 64-bit 4CPU
Houdini 5.01 64-bit 4CPU 1.6.3
3402
3391
3378
CEGT 40/20[4] 40/20[5] 2006 8 gennaio 2017 3365 991.575 Stockfish 8.0 x64 4CPU
Houdini 5.0 x64 4CPU
Komodo 10.2 x64 4CPU
3414
3380
3365
CSS[6] 10 min +
10 s per mossa
2001 18 marzo 2007 189 67.242 Rybka 2.2 mp 32-bit 2CPU
Deep Fritz 10 2CPU
Deep Shredder 10 2CPU
3008
2909
2891
SSDF[7] 40/120 + 20/60 1984 27 luglio 2017 353 138.040 Komodo 11.01 MP x64 16GB 1800X 3,6 GHz
Deep Shredder 13 x64 16GB 1800X 3,6 GHz
Stockfish 6 MP x64 2GB Q6600 2,4 GHz
3406
3385
3331
WBEC[8] 40/40 2001 22 settembre 2009 850+[9] 84,000+ Rybka 3-x64-2CPU
Naum 4.0-2CPU-x64
Thinker 5.4j-x64-2CPU
3090
3039
2994

Motori cloni[modifica | modifica wikitesto]

Alcuni motori, come Strelka ed Ippolit, vennero accusati di essere dei cloni di Rybka, ovvero di essere stati creati illegalmente a partire da porzioni di codice probabilmente ottenute disassemblando e decompilando i binari di Rybka e risalendo approssimativamente al suo codice sorgente; a ogni modo gli autori di questi motori negarono di aver clonato Rybka, ma la questione sull'argomento è tuttora aperta. Dopo l'uscita di Ippolit sono stati creati altri motori da esso derivati, quali Robbolito, IvanHoe, Fire ed altri, tutti molto forti. Molti di questi motori non vengono considerati nelle classifiche ufficiali per la loro dubbia origine, inoltre i nomi di alcuni autori sono degli pseudonimi.
Anche l'autore di Rybka finì a sua volta sotto accusa perché sospettato di aver copiato dal codice di due motori open source (Fruit e Crafty), ma Vasik Rajlich smentì tutto dicendo che il suo codice era assolutamente originale.
Nel giugno 2011 la ICGA (International Computer Games Association) ha posto fine a quest'ultima diatriba avendo ritenuto, dopo varie indagini, che Rybka è effettivamente un clone di Fruit e Crafty. Rybka è stato perciò squalificato a vita e bandito dalle competizioni organizzate dalla stessa ICGA. Ovviamente l'autore di Rybka ha espresso il suo disaccordo, ma ha deciso di non difendersi dalle accuse e di non discutere la questione pubblicamente.
Inoltre anche l'autore di Houdini, fra i motori più forti attualmente in circolazione che però non ha mai partecipato a competizioni ufficiali, ha ammesso di aver preso spunto dal codice di motori open source quali Ippolit/Robbolito e Stockfish, così come riportato nel suo sito ufficiale.
Alcuni motori cloni si sono così evoluti, che sono diventati dei prodotti commerciali di alto livello, come ad esempio lo stesso Houdini (dalla versione 2.0), Rybka (dalla versione 3) e Vitruvius (dalla versione 1.0).

Note[modifica | modifica wikitesto]

  1. ^ (EN) Tim Mann e H.G.Muller, Chess Engine Communication Protocol, su gnu.org. URL consultato il 28 settembre 2016.
  2. ^ CCRL 40/40 - Lista completa, su computerchess.org.uk, 6 marzo 2010. URL consultato il 13 gennaio 2017.
  3. ^ Disponibile anche: 40 mosse in 4 minuti
  4. ^ CEGT 40/20[collegamento interrotto], Chess Engines Grand Tournament, 28 marzo 2010. URL consultato il 13 gennaio 2017.
  5. ^ Disponibile anche: 40 mosse in 4 minuti, 40 mosse in 120 minuti
  6. ^ Computerschach und Spiele - Eternal Rating, Computerschach und Spiele, 18 marzo 2007. URL consultato il 21 maggio 2008.
  7. ^ SSDF Rating List, SSDF, 26 settembre 2008. URL consultato il 13 gennaio 2017.
  8. ^ BayesianElo Ratinglist of WBEC Ridderkerk, su wbec-ridderkerk.nl. URL consultato il 20 luglio 2008.
  9. ^ http://home.scarlet.be/vincentlejeune/Ratings-WBEC-Ed-11-to-16.txt

Bibliografia[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]

  • (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.
  • (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
Scacchi Portale Scacchi: accedi alle voci di Wikipedia che trattano di scacchi