roxon.best

Come funzionano i computer per gli scacchi

Scacchi per computer Hardware

e software per computer in grado di giocare a scacchi

Per altri usi, vedi Computer Chess (film).

Gli scacchi per computer includono sia hardware (computer dedicati) che software in grado di giocare a scacchi. Gli scacchi al computer offrono ai giocatori l'opportunità di esercitarsi anche in assenza di avversari umani, e offrono anche opportunità di analisi, intrattenimento e allenamento. Le applicazioni di scacchi per computer che giocano al livello di un grande maestro di scacchi o superiore sono disponibili su hardware che va dai supercomputer agli smartphone. Sono disponibili anche macchine per giocare a scacchi autonome. Stockfish, Leela Chess Zero, GNU Chess, Fruit e altre applicazioni open source gratuite sono disponibili per varie piattaforme.

Le applicazioni scacchistiche per computer, siano esse implementate in hardware o software, utilizzano strategie diverse da quelle umane per scegliere le loro mosse: Utilizza metodi euristici per costruire, cercare e valutare alberi che rappresentano sequenze di mosse dalla posizione corrente e cerca di eseguire la migliore sequenza durante il gioco. Tali alberi sono in genere piuttosto grandi, da migliaia a milioni di nodi. La velocità di calcolo dei computer moderni, in grado di elaborare da decine di migliaia a centinaia di migliaia di nodi o più al secondo, insieme all'euristica di estensione e riduzione che restringe l'albero ai nodi per lo più rilevanti, rendono efficace un tale approccio.

Le prime macchine scacchistiche in grado di giocare a scacchi o di giocare a scacchi ridotti erano programmi software in esecuzione su computer digitali all'inizio dell'era dei computer a tubo a vuoto (anni '50). I primi programmi funzionavano così male che anche un principiante poteva sconfiggerli. Nel giro di 40 anni, nel 1997, i motori scacchistici che giravano su super-computer o hardware specializzato erano in grado di sconfiggere anche i migliori giocatori umani. Entro il 2006, i programmi in esecuzione su I PC desktop avevano raggiunto la stessa capacità. Nel 2006, Monty Newborn, professore di informatica alla McGill University, ha dichiarato: "la scienza è stata fatta". Tuttavia, risolvere gli scacchi non è attualmente possibile per i computer moderni a causa del numero estremamente elevato di possibili varianti del gioco. [1]

Gli scacchi informatici erano un tempo considerati la "Drosophila dell'IA", il confine dell'ingegneria della conoscenza. Il campo è ora considerato un paradigma scientificamente completo e giocare a scacchi è un'attività informatica banale. [2]

Le

macchine/programmi scacchistici sono disponibili in diverse forme: macchine scacchistiche autonome (di solito un microprocessore che esegue un programma scacchistico software, ma a volte come una macchina hardware specializzata), programmi software che girano su PC standard, siti web e applicazioni per dispositivi mobili. Programmi eseguiti su tutto, dai super-computer agli smartphone. I requisiti hardware per i programmi sono minimi; le app non sono più grandi di pochi megabyte su disco, utilizzano pochi megabyte di memoria (ma possono utilizzarne molti di più, se disponibili) e qualsiasi processore da 300 Mhz o superiore è sufficiente. Le prestazioni variano modestamente con la velocità del processore, ma una memoria sufficiente per contenere una tabella di trasposizione di grandi dimensioni (fino a diversi gigabyte o più) è più importante per la potenza di riproduzione rispetto alla velocità del processore.

La maggior parte dei programmi e delle macchine scacchistiche commerciali disponibili possono giocare a livello di super-grandmaster (Elo 2700 o più) e sfruttare le architetture CPU multi-core e hyperthreaded dei computer. I migliori programmi come Stockfish hanno superato anche i giocatori del calibro di campioni del mondo. La maggior parte dei programmi di scacchi comprende un motore scacchistico collegato a una GUI, come Winboard o Chessbase. La forza di esecuzione, i controlli del tempo e altre impostazioni relative alle prestazioni sono regolabile dalla GUI. La maggior parte delle GUI permette anche al giocatore di impostare e modificare le posizioni, di invertire le mosse, di offrire e accettare patte (e abbandonare), di richiedere e ricevere raccomandazioni sulle mosse e di mostrare l'analisi del motore man mano che la partita procede.

Ci sono migliaia di motori scacchistici come Sargon, IPPOLIT, Stockfish, Crafty, Fruit, Leela Chess Zero e GNU Chess che possono essere scaricati (o il codice sorgente altrimenti ottenuto) da Internet gratuitamente.

Tipi e caratteristiche dei software scacchistici

Forse il tipo più comune di software scacchistico sono i programmi che semplicemente giocano a scacchi. Un giocatore umano fa una mossa sul tabellone, l'IA calcola e gioca una mossa successiva e l'umano e l'IA si alternano fino alla fine del gioco. Il motore scacchistico, che calcola le mosse, e l'interfaccia utente grafica (GUI) sono a volte programmi separati. Diversi motori possono essere collegati alla GUI, permettendo di giocare contro diversi stili di avversari. I motori hanno spesso una semplice interfaccia a riga di comando testuale, mentre le GUI possono offrire una varietà di set di pezzi, stili di scacchiera o persino pezzi 3D o animati. Poiché i motori recenti sono così capaci, i motori o le GUI possono offrire un modo per ostacolare la capacità del motore, per migliorare le probabilità di vittoria da parte del giocatore umano. I motori UCI (Universal Chess Interface) come Fritz o Rybka possono avere un meccanismo integrato per ridurre il punteggio Elo del motore (tramite i parametri uci_limitstrength e uci_elo dell'UCI). Alcune versioni di Fritz hanno una modalità Handicap e Fun per limitare il motore attuale o cambiare la percentuale di errori che commette o cambiarne lo stile. Fritz ha anche una modalità Amico in cui durante il gioco cerca di eguagliare il livello del giocatore.

I database scacchistici consentono agli utenti di cercare in una vasta libreria di partite storiche, analizzarle, controllare le statistiche e formulare un repertorio di apertura. Chessbase (per PC) è un programma comune per questi scopi tra i giocatori professionisti, ma ci sono alternative come Shane's Chess Information Database (Scid) [3] per Windows, Mac o Linux, Chess Assistant [4] per PC, [5] Chess PGN Master di Gerhard Kalab per Android [6] o Chess-Studio di Giordano Vicoli per iOS. [7]

Programmi come Playchess permettono ai giocatori di giocare l'uno contro l'altro su Internet.

I programmi di allenamento scacchistico insegnano gli scacchi. Chessmaster ha avuto tutorial di gioco dell'IM Josh Waitzkin e del GM Larry Christiansen. Stefan Meyer-Kahlen offre Shredder Chess Tutor basato sui libri di testo Step di Rob Brunia e Cor Van Wijgerden. L'azienda Play Magnus dell'ex campione del mondoMagnus Carlsen ha rilasciato un'app Magnus Trainer per Android e iOS. Chessbase ha Fritz e Chesster per bambini. Convekta fornisce un gran numero di app di allenamento come CT-ART e la sua linea Chess King basate sui tutorial dei GM Alexander Kalinin e Maxim Blokh.

Articolo

principale: Partite di scacchi uomo-computer

Dopo aver scoperto lo screening di confutazione - l'applicazione della potatura alfa-beta per ottimizzare la valutazione delle mosse - nel 1957, un team della Carnegie Mellon University predisse che un computer avrebbe sconfitto il campione del mondo umano entro il 1967. Non ha previsto la difficoltà di determinare l'ordine giusto per valutare le mosse. I ricercatori hanno lavorato per migliorare la capacità dei programmi di identificare l'euristica killer, mosse con punteggi insolitamente alti da riesaminare quando si valutano altri rami, ma negli anni '70 la maggior parte dei migliori giocatori di scacchi credeva che i computer non sarebbero stati presto in grado di giocare a livello di Master. [9] Nel 1968, il Maestro Internazionale David Levy fece una famosa scommessa che nessun computer di scacchi sarebbe stato in grado di batterlo entro dieci anni, [10] e nel 1976 il Maestro Senior e professore di psicologia Eliot Hearst dell'Università dell'Indiana scrisse che "l'unico modo in cui un programma per computer attuale potrebbe mai vincere una singola partita contro un giocatore maestro sarebbe per il maestro, forse in uno stato di torpore da ubriaco mentre giocavo 50 partite contemporaneamente, per commettere qualche errore grossolano una volta all'anno". [9]

Alla fine degli anni '70 i programmi di scacchi iniziarono improvvisamente a sconfiggere giocatori umani altamente qualificati. [9] L'anno della dichiarazione di Hearst, il Chess 4.5 della Northwestern University al livello di Classe B del Paul Masson American Chess Championship è diventato il primo a vincere un torneo umano. Levy vinse la sua scommessa nel 1978 battendo Chess 4.7, ma ottenne la prima vittoria al computer contro un giocatore di classe Master a livello di torneo vincendo una delle sei partite. [10] Nel 1980, Belle iniziò a sconfiggere spesso Masters. Nel 1982 due programmi giocati a livello Master e tre erano leggermente più deboli. [9]

L'improvviso miglioramento senza una svolta teorica fu inaspettato, poiché molti non si aspettavano che la capacità di Belle di esaminare 100.000 posizioni al secondo, circa otto strati, sarebbe stata sufficiente. Gli Spracklens, creatori del programma per microcomputer di successo Sargon , stimarono che il 90% del miglioramento derivava da una maggiore velocità di valutazione e solo il 10% da valutazioni migliorate. New Scientist ha dichiarato nel 1982 che i computer "giocano a scacchi terribili ... goffi, inefficienti, diffusi e semplicemente brutti", ma gli esseri umani hanno perso contro di loro commettendo "orribili errori, errori sorprendenti, sviste incomprensibili, grossolani errori di calcolo e simili" molto più spesso di quanto si rendessero conto; "In breve, i computer vincono principalmente attraverso la loro capacità di trovare e sfruttare gli errori di calcolo nelle iniziative umane". [9]

Nel 1982, i programmi di scacchi per microcomputer potevano valutare fino a 1.500 mosse al secondo ed erano forti quanto i programmi di scacchi mainframe di cinque anni prima, in grado di sconfiggere la maggior parte dei giocatori dilettanti. Sebbene fossero in grado di guardare avanti solo di una o due volte in più rispetto al loro debutto a metà degli anni '1970, così facendo hanno migliorato il loro gioco più di quanto gli esperti si aspettassero; Miglioramenti apparentemente minori "sembrano aver permesso il superamento di una soglia psicologica, dopo la quale diventa accessibile un ricco raccolto di errori umani", ha scritto New Scientist. [9] Nel 1984, recensendo SPOC, BYTE scrisse che "i computer - mainframe, mini e micro - tendono a giocare a scacchi brutti e ineleganti", ma notò l'affermazione di Robert Byrne che "tatticamente sono più liberi da errori rispetto al giocatore umano medio". La rivista descriveva SPOC è un "programma scacchistico all'avanguardia" per il PC IBM con un livello di gioco "sorprendentemente alto", e ha stimato il suo punteggio USCF a 1700 (Classe B). [11]

Al North American Computer Chess Championship del 1982, Monroe Newborn predisse che un programma di scacchi avrebbe potuto diventare campione del mondo entro cinque anni; il direttore del torneo e Maestro Internazionale Michael Valvo predisse dieci anni; Spracklens predisse 15; Ken Thompson ne aveva previsti più di 20; e altri hanno predetto che non sarebbe mai successo. L'opinione più diffusa, tuttavia, affermava che si sarebbe verificata intorno all'anno 2000. [12] Nel 1989, Levy fu sconfitto dai Deep Thought in un match di esibizione. Deep Thought, tuttavia, era ancora considerevolmente al di sotto del livello del Campionato del Mondo, come il campione del mondo in carica, Garry Kasparov, dimostrò in due ottime vittorie nel 1989. Fu solo nel 1996 in un match con i Deep Blue dell'IBM che Kasparov perse la sua prima partita al computer ai controlli orari del torneo in Deep Blue contro Kasparov, 1996, gara 1. Questa partita è stata, infatti, la prima volta che un campione del mondo in carica ha perso contro un computer utilizzando i normali controlli di tempo. Tuttavia, Kasparov si è riorganizzato vincendo tre e pareggiando due delle restanti cinque partite della partita, per una vittoria convincente.

Nel maggio 1997, una versione aggiornata di Deep Blue sconfisse Kasparov 31/2-21/2 in un match di ritorno. Nel 2003 è stato realizzato un documentario principalmente sullo scontro, intitolato Game Over: Kasparov and the Machine .

Con l'aumento della potenza di elaborazione e il miglioramento delle funzioni di valutazione, i programmi di scacchi in esecuzione su workstation disponibili in commercio iniziarono a competere con i giocatori di alto livello. Nel 1998, Rebel 10 ha sconfitto Viswanathan Anand, che all'epoca era al secondo posto nel mondo, con un punteggio di 5-3. Tuttavia, la maggior parte di queste partite non sono state giocate ai normali controlli orari. Delle otto partite, quattro sono state blitz giochi (cinque minuti più cinque secondi di ritardo di Fischer per ogni mossa); questi ribelli vinsero 3-1. Due erano partite semi-blitz (quindici minuti per parte) che Rebel vinse pure (11/2-1/2). Infine, due partite sono state giocate come normali partite di torneo (quaranta mosse in due ore, un'ora di morte improvvisa); qui fu Anand a vincere 1/2-11/2. [13] Nei giochi veloci, i computer giocavano meglio degli esseri umani, ma nei classici controlli di tempo, in cui viene determinata la valutazione di un giocatore, il vantaggio non era così chiaro.

Nei primi anni 2000, programmi disponibili in commercio come Junior e Fritz sono stati in grado di pareggiare partite contro l'ex campione del mondo Garry Kasparov e il campione del mondo classico Vladimir Kramnik. Nell'ottobre

2002, Vladimir Kramnik e Deep Fritz hanno gareggiato nel match di otto partite Brains in Bahrain, che si è concluso con un pareggio. Kramnik ha vinto le partite 2 e 3 con tattiche "convenzionali" anti-computer: giocare in modo conservativo per un lungo periodo vantaggio che il computer non è in grado di vedere nella sua ricerca nell'albero dei giochi. Fritz, tuttavia, vinse gara 5 dopo un grave errore di Kramnik. Gara 6 è stata descritta dai commentatori del torneo come "spettacolare". Kramnik, in una posizione migliore all'inizio del mediogioco, ha provato un sacrificio di pezzi per ottenere un forte attacco tattico, una strategia nota per essere altamente rischiosa contro i computer che sono al loro massimo in difesa contro tali attacchi. Fedele alla forma, Fritz ha trovato una difesa a tenuta stagna e l'attacco di Kramnik si è esaurito lasciandolo in una brutta posizione. Kramnik abbandonò la partita, credendo che la posizione fosse persa. Tuttavia, l'analisi umana e informatica post-partita ha dimostrato che era improbabile che il programma Fritz fosse in grado di forzare una vittoria e Kramnik ha effettivamente sacrificato una posizione patta. Le ultime due partite sono state pareggiate. Date le circostanze, la maggior parte dei commentatori considera ancora Kramnik il giocatore più forte della partita. [ citazione necessaria ]

Nel gennaio 2003, Kasparov ha giocato a Junior, un altro programma per computer di scacchi, a New York City. La partita terminò 3-3.

Nel novembre 2003, Kasparov ha giocato a X3D Fritz. La partita è terminata 2-2.

Nel 2005, Hydra, un computer di scacchi dedicato con hardware personalizzato e sessantaquattro processori e vincitore anche del 14º IPCCC nel 2005, sconfisse il settimo classificato Michael Adams 51/2-1/2 in un match di sei partite (anche se la preparazione di Adams fu molto meno accurata di quella di Kramnik per la serie del 2002). [14]

Nel novembre-dicembre 2006, il campione del mondo Vladimir Kramnik giocò contro il Deep Fritz. Questa volta il computer ha vinto; La partita è terminata 2-4. Kramnik è stato in grado di visualizzare il libro di apertura del computer. Nelle prime cinque partite, Kramnik guidò il gioco in una tipica gara posizionale "anti-computer". Ha perso una partita (scavalcando un matto in una) e ha pareggiato le successive quattro. Nella partita finale, nel tentativo di pareggiare la partita, Kramnik ha giocato di più aggressiva difesa siciliana e fu schiacciata.

Si ipotizzava che l'interesse per la competizione scacchistica uomo-computer sarebbe crollato a seguito della partita Kramnik-Deep Fritz del 2006. [15] Secondo Newborn, ad esempio, "la scienza è finita". [16]

Le partite di scacchi uomo-computer hanno mostrato che i migliori sistemi informatici hanno superato i campioni di scacchi umani alla fine degli anni '90. Per i 40 anni precedenti, la tendenza era stata che le migliori macchine guadagnavano circa 40 punti all'anno nel punteggio Elo, mentre gli esseri umani migliori guadagnavano solo circa 2 punti all'anno. [17] Il punteggio più alto ottenuto da un computer in una competizione umana è stato il punteggio USCF di Deep Thought di 2551 nel 1988 e la FIDE non accetta più risultati uomo-computer nelle loro liste di valutazione. Sono stati creati pool Elo specializzati solo per le macchine di valutazione, ma tali numeri, sebbene simili nell'aspetto, non lo sono direttamente confrontati. [18] Nel 2016, la Swedish Chess Computer Association ha valutato il programma per computer Komodo a 3361.

I motori scacchistici continuano a migliorare. Nel 2009, i motori scacchistici che funzionano con hardware più lenti hanno raggiunto il livello di grande maestro. Un telefono cellulare ha vinto un torneo di categoria 6 con un punteggio di prestazioni 2898: il motore di scacchi Hiarcs 13 in esecuzione all'interno di Pocket Fritz 4 sul telefono cellulare HTC Touch HD ha vinto il torneo Copa Mercosur a Buenos Aires, Argentina con 9 vittorie e 1 pareggio il 4-14 agosto 2009. [19] Pocket Fritz 4 cerca meno di 20.000 posizioni al secondo. [20] Questo è in contrasto con i supercomputer come Deep Blue che hanno cercato 200 milioni di posizioni al secondo.

Gli scacchi avanzati sono una forma di scacchi sviluppata nel 1998 da Kasparov in cui un essere umano gioca contro un altro essere umano, ed entrambi hanno accesso ai computer per aumentare la loro forza. Il risultato è Il giocatore "avanzato" era sostenuto da Kasparov per essere più forte di un essere umano o di un computer da solo. Questo è stato dimostrato in numerose occasioni, come ad esempio negli eventi di Freestyle Chess.

I giocatori di oggi sono inclini a trattare i motori scacchistici come strumenti di analisi piuttosto che come avversari. [21] Il grande maestro di scacchi Andrew Soltis ha dichiarato nel 2016 "I computer sono troppo buoni" e che il campione del mondo Magnus Carlsen non giocherà a scacchi al computer perché "perde tutto il tempo e non c'è niente di più deprimente che perdere senza nemmeno essere in partita". [22]

Metodi informatici

Fin dall'era delle macchine meccaniche che giocavano ai finali di torre e re e delle macchine elettriche che giocavano ad altri giochi come l'esagono nei primi anni del 20° secolo, scienziati e teorici hanno cercato di sviluppare una rappresentazione procedurale di come gli esseri umani apprendono, ricordano, pensano e applicano la conoscenza e il gioco degli scacchi, a causa della sua scoraggiante complessità, è diventata la "Drosophila dell'intelligenza artificiale (AI)". [Nota 1] La risoluzione procedurale della complessità divenne sinonimo di pensiero, e i primi computer, anche prima dell'era degli automi scacchistici, erano popolarmente indicati come "cervelli elettronici". Diversi schemi sono stati ideati a partire dalla seconda metà del XX secolo per rappresentare la conoscenza e il pensiero, applicati al gioco degli scacchi (e ad altri giochi come la dama):

utilizzando l'euristica "fini e mezzi" un giocatore di scacchi umano può determinare intuitivamente i risultati ottimali e come raggiungerli indipendentemente dal numero di mosse necessarie, Ma un computer deve essere sistematico nella sua analisi. La maggior parte dei giocatori concorda sul fatto che per giocare bene è necessario guardare almeno cinque mosse avanti (dieci strati) quando necessario. Le normali regole dei tornei danno a ogni giocatore una media di tre minuti per mossa. In media ci sono più di 30 mosse legali per posizione negli scacchi, quindi un computer deve esaminare un quadrilione di possibilità per guardare avanti dieci strati (cinque mosse complete); Uno in grado di esaminare un milione di posizioni al secondo richiederebbe più di 30 anni. [9]

I primi tentativi di rappresentazioni procedurali del gioco degli scacchi precedettero l'era dell'elettronica digitale, ma fu il computer digitale a programma memorizzato che diede spazio al calcolo di tale complessità. Claude Shannon, nel 1949, espose i principi della soluzione algoritmica degli scacchi. In quel documento, il gioco è rappresentato da un "albero", o struttura digitale di dati di scelte (rami) corrispondenti alle mosse. I nodi dell'albero erano le posizioni sulla scacchiera risultanti dalle scelte di mossa. L'impossibilità di rappresentare un'intera partita di scacchi costruendo un albero dalla prima all'ultima mossa è stata subito evidente: ci sono una media di 36 mosse per posizione negli scacchi e un La partita media dura circa 35 mosse prima della rinuncia (60-80 mosse se giocata per scacco matto, stallo o altra patta). Ci sono 400 posizioni possibili dopo la prima mossa di ogni giocatore, circa 200.000 dopo due mosse ciascuna e quasi 120 milioni dopo solo 3 mosse ciascuna.

Quindi è stato proposto un lookahead limitato (ricerca) a una certa profondità, seguito dall'utilizzo di conoscenze specifiche del dominio per valutare le posizioni terminali risultanti. Ne risulterebbe una sorta di posizione intermedia, date buone mosse da entrambe le parti, e la sua valutazione informerebbe il giocatore sulla bontà o meno delle mosse scelte. Le operazioni di ricerca e confronto sull'albero erano adatte al calcolo al computer; La rappresentazione della conoscenza sottile degli scacchi nella funzione di valutazione non lo era. I primi programmi di scacchi soffrivano in entrambe le aree: la ricerca nel vasto albero richiedeva risorse computazionali ben superiori a quelle disponibili, e quali conoscenze scacchistiche erano utili e Ci sarebbero voluti decenni per scoprire come doveva essere codificato.

Gli sviluppatori di un sistema informatico per giocare a scacchi devono decidere su una serie di questioni fondamentali di implementazione. Questi includono:

  • Interfaccia utente grafica (GUI) - come vengono inserite e comunicate le mosse all'utente, come viene registrato il gioco, come vengono impostati i controlli del tempo e altre considerazioni sull'interfaccia
  • Rappresentazione della scacchiera - come viene rappresentata una singola posizione nelle strutture dati;
  • Tecniche di ricerca - come identificare le possibili mosse e selezionare quelle più promettenti per un ulteriore esame;
  • Valutazione foglia – come valutare il valore di una posizione del tabellone, se non verranno effettuate ulteriori ricerche da quella posizione.

Adriaan de Groot ha intervistato un certo numero di giocatori di scacchi di vari punti di forza, e ha concluso che sia i maestri che i principianti guardano circa quaranta o cinquanta posizioni prima di decidere quale mossa giocare. Ciò che rende i primi giocatori molto migliori è che usano abilità di riconoscimento dei modelli costruite dall'esperienza. Ciò consente loro di esaminare alcune linee in modo molto più approfondito di altre, semplicemente non considerando le mosse che possono presumere siano scadenti. Un'ulteriore prova di ciò è il modo in cui i buoni giocatori umani trovano molto più facile ricordare le posizioni delle vere partite di scacchi, suddividendole in un piccolo numero di sottoposizioni riconoscibili, piuttosto che in disposizioni completamente casuali degli stessi pezzi. Al contrario, i giocatori poveri hanno lo stesso livello di richiamo per entrambi.

L'equivalente di questo negli scacchi al computer sono le funzioni di valutazione per la valutazione delle foglie, che corrispondono alle capacità di riconoscimento dei modelli dei giocatori umani, e l'uso di tecniche di apprendimento automatico nell'addestramento, come la sintonizzazione Texel, la discesa stocastica del gradiente e l'apprendimento per rinforzo, che corrisponde alla costruzione di esperienza nei giocatori umani. Questo Permette ai programmi moderni di esaminare alcune linee in modo molto più approfondito di altre, utilizzando la potatura in avanti e altre euristiche selettive per non considerare semplicemente le mosse che il programma presume siano scarse attraverso la loro funzione di valutazione, nello stesso modo in cui lo fanno i giocatori umani. L'unica differenza fondamentale tra un programma per computer e un essere umano in questo senso è che un programma per computer può cercare molto più in profondità di quanto potrebbe fare un giocatore umano, permettendogli di cercare più nodi e bypassare l'effetto orizzonte in misura molto maggiore di quanto sia possibile con i giocatori umani.

I

programmi di scacchi per computer di solito supportano una serie di standard de facto comuni. Quasi tutti i programmi odierni sono in grado di leggere e scrivere mosse di gioco come Portable Game Notation (PGN), e possono leggere e scrivere singole posizioni come Forsyth-Edwards Notation (FEN). I vecchi programmi di scacchi spesso comprendevano solo la notazione algebrica lunga, ma oggi Gli utenti si aspettano che i programmi di scacchi comprendano la notazione scacchistica algebrica standard.

A partire dalla fine degli anni '90, i programmatori hanno iniziato a sviluppare separatamente motori (con un'interfaccia a riga di comando che calcola quali mosse sono più forti in una posizione) o un'interfaccia utente grafica (GUI) che fornisce al giocatore una scacchiera che può vedere e pezzi che possono essere spostati. I motori comunicano le loro mosse alla GUI utilizzando un protocollo come il Chess Engine Communication Protocol (CECP) o l'Universal Chess Interface (UCI). Dividendo i programmi di scacchi in questi due pezzi, gli sviluppatori possono scrivere solo l'interfaccia utente, o solo il motore, senza dover scrivere entrambe le parti del programma. (Vedi anche motore scacchistico.)

Gli sviluppatori devono decidere se collegare il motore a un libro di apertura e/o alle tablebase dei finali o lasciare questo compito alla GUI.

Articolo

principale: Tabellone rappresentazione (scacchi)

La struttura dati utilizzata per rappresentare ogni posizione scacchistica è fondamentale per le prestazioni della generazione delle mosse e della valutazione della posizione. I metodi includono pezzi memorizzati in un array ("cassetta postale" e "0x88"), posizioni dei pezzi memorizzate in un elenco ("elenco dei pezzi"), raccolte di set di bit per le posizioni dei pezzi ("bitboard") e posizioni codificate Huffman per l'archiviazione compatta a lungo termine.

I

programmi di scacchi per computer considerano le mosse degli scacchi come un albero di gioco. In teoria, esaminano tutte le mosse, poi tutte le contromosse a quelle mosse, poi tutte le mosse che le contrastano, e così via, dove ogni singola mossa di un giocatore è chiamata "ply". Questa valutazione continua fino a quando non viene raggiunta una certa profondità massima di ricerca o il programma determina che è stata raggiunta una posizione finale "foglia" (ad es. scacco matto).

Ricerca minimax

Per ulteriori informazioni: Potatura alfa-beta e minimax

One particular Tipo di algoritmo di ricerca utilizzato negli scacchi per computer sono gli algoritmi di ricerca minimax, in cui ad ogni partita viene selezionata la mossa "migliore" del giocatore; Un giocatore sta cercando di massimizzare il punteggio, l'altro di minimizzarlo. Con questo processo alternato, si arriverà a un particolare nodo terminale la cui valutazione rappresenta il valore cercato della posizione. Il suo valore è sostenuto fino alla radice e tale valutazione diventa la valutazione della posizione nel consiglio di amministrazione. Questo processo di ricerca è chiamato minimax.

Un'implementazione ingenua dell'algoritmo minimax può cercare solo a una piccola profondità in un lasso di tempo pratico, quindi sono stati ideati vari metodi per velocizzare notevolmente la ricerca di buone mosse. L'eliminazione alfa-beta, un sistema di definizione dei limiti superiore e inferiore dei possibili risultati di ricerca e di ricerca fino a quando i limiti non coincidono, viene tipicamente utilizzata per ridurre lo spazio di ricerca del programma.

Inoltre, varie ricerche selettive Vengono utilizzate anche euristiche, come la ricerca di quiescenza, l'eliminazione in avanti, le estensioni di ricerca e le riduzioni di ricerca. Queste euristiche vengono attivate in base a determinate condizioni nel tentativo di eliminare mosse ovviamente sbagliate (mosse storiche) o di indagare su nodi interessanti (ad esempio estensioni di controllo, pedoni passati sulla settima traversa, ecc.). Tuttavia, queste euristiche di ricerca selettiva devono essere utilizzate con molta attenzione. Estendendosi eccessivamente, il programma perde troppo tempo a cercare posizioni poco interessanti. Se si pota o si riduce troppo, c'è il rischio di tagliare i nodi interessanti.

Ricerca ad albero Monte Carlo

Ulteriori informazioni: Ricerca ad albero Monte Carlo

La

ricerca ad albero Monte Carlo (MCTS) è un algoritmo di ricerca euristico che espande l'albero di ricerca in base al campionamento casuale dello spazio di ricerca. Una versione della ricerca ad albero Monte Carlo comunemente usata negli scacchi al computer è PUCT, Predictor e Upper Confidence bounds applicato a Alberi.

AlphaZero e Leela Chess Zero di DeepMind utilizzano MCTS invece di minimax. Tali motori utilizzano il batching sulle unità di elaborazione grafica per calcolare le loro funzioni di valutazione e i criteri (selezione dello spostamento) e quindi richiedono un algoritmo di ricerca parallelo poiché i calcoli sulla GPU sono intrinsecamente paralleli. Gli algoritmi di potatura minimax e alfa-beta utilizzati negli scacchi al computer sono intrinsecamente seriali, quindi non funzionerebbero bene con il batching sulla GPU. D'altra parte, MCTS è una buona alternativa, perché il campionamento casuale utilizzato nella ricerca ad albero Monte Carlo si presta bene al calcolo parallelo, ed è per questo che quasi tutti i motori che supportano i calcoli sulla GPU utilizzano MCTS invece di alfa-beta.

Molte

altre ottimizzazioni possono essere utilizzate per rendere più forti i programmi per giocare a scacchi. Ad esempio, le tabelle di trasposizione vengono utilizzate per registrare posizioni che sono state valutate in precedenza, per evitare il ricalcolo di essi. Le tabelle di confutazione registrano le mosse chiave che "confutano" quella che sembra essere una buona mossa; Questi vengono in genere provati prima in posizioni varianti (poiché una mossa che confuta una posizione è probabile che ne confuti un'altra). Lo svantaggio è che le tabelle di trasposizione a profondità di strati profondi possono diventare piuttosto grandi, da decine a centinaia di milioni di voci. La tabella di trasposizione Deep Blue di IBM nel 1996, ad esempio, era di 500 milioni di voci. Le tabelle di trasposizione troppo piccole possono comportare una maggiore perdita di tempo nella ricerca di voci inesistenti a causa della trebbiatura rispetto al tempo risparmiato dalle voci trovate. Molti motori scacchistici utilizzano la ponderazione, la ricerca a livelli più profondi del tempo dell'avversario, in modo simile agli esseri umani, per aumentare la loro forza di gioco.

Naturalmente, un hardware più veloce e una memoria aggiuntiva possono migliorare la forza di gioco del programma scacchistico. Le architetture hyperthreaded possono migliorare modestamente le prestazioni se il programma è in esecuzione su un singolo core o un numero ridotto di core. La maggior parte dei programmi moderni sono progettati per sfruttare più core per eseguire ricerche parallele. Altri programmi sono progettati per essere eseguiti su un computer generico e allocare la generazione di spostamenti, la ricerca parallela o la valutazione a processori dedicati o coprocessori specializzati.

Il

primo articolo sulla ricerca scacchistica fu scritto da Claude Shannon nel 1950. [23] Predisse le due principali possibili strategie di ricerca che sarebbero state utilizzate, che etichettò come "Tipo A" e "Tipo B", [24] prima che qualcuno avesse programmato un computer per giocare a scacchi.

I

programmi di tipo A avrebbero utilizzato un approccio di "forza bruta". esaminando ogni possibile posizione per un numero fisso di mosse utilizzando un algoritmo minimax puramente ingenuo. Shannon credeva che questo sarebbe stato impraticabile per due motivi.

In primo luogo, con circa trenta mosse possibili in una tipica posizione della vita reale, Ci si aspettava che la ricerca delle circa 10 9 posizioni necessarie per guardare tre mosse avanti per entrambe le parti (sei strati) avrebbe richiesto circa sedici minuti, anche nel caso "molto ottimistico" che il computer di scacchi valutasse un milione di posizioni al secondo. (Ci sono voluti circa quarant'anni per raggiungere questa velocità.) Un algoritmo di ricerca successivo chiamato potatura alfa-beta, un sistema di definizione dei limiti superiore e inferiore sui possibili risultati di ricerca e di ricerca fino a quando i limiti non coincidevano, riduceva logaritmicamente il fattore di ramificazione dell'albero di gioco, ma non era ancora possibile per i programmi di scacchi dell'epoca sfruttare l'esplosione esponenziale dell'albero.

In secondo luogo, ha ignorato il problema della quiescenza, cercando di valutare solo una posizione che si trova alla fine di uno scambio di pezzi o di un'altra importante sequenza di mosse ('linee'). Si aspettava che l'adattamento di minimax per far fronte a questo avrebbe aumentato notevolmente il numero di posizioni necessarie da guardare e rallentare ulteriormente il programma. Si aspettava che l'adattamento del tipo A per far fronte a ciò avrebbe aumentato notevolmente il numero di posizioni da esaminare e avrebbe rallentato ulteriormente il programma.

Questo ha portato naturalmente a quella che viene definita "ricerca selettiva" o "ricerca di tipo B", utilizzando la conoscenza degli scacchi (euristica) per selezionare alcune mosse presumibilmente buone da ogni posizione da cercare, e sfoltire le altre senza cercare. Invece di sprecare potenza di elaborazione esaminando mosse sbagliate o banali, Shannon suggerì che i programmi di tipo B avrebbero utilizzato due miglioramenti:

  1. Impiegare una ricerca di quiescenza.
  2. Impiegare la potatura in avanti, cioè guardare solo alcune mosse buone per ogni posizione.

Questo avrebbe permesso loro di guardare più avanti ("più in profondità") le linee più significative in un tempo ragionevole. Tuttavia, i primi tentativi di ricerca selettiva spesso portavano alla potatura della mossa o delle mosse migliori via. Di conseguenza, sono stati fatti pochi o nessun progresso per i successivi 25 anni, dominati da questa prima iterazione del paradigma della ricerca selettiva. Il miglior programma prodotto in questo primo periodo fu Mac Hack VI nel 1967; giocava all'incirca allo stesso livello del dilettante medio (classe C sulla scala di valutazione della United States Chess Federation).

Nel frattempo, l'hardware continuava a migliorare e nel 1974 la ricerca con la forza bruta fu implementata per la prima volta nel programma di scacchi 4.0 della Northwestern University. In questo approccio, vengono cercate tutte le mosse alternative in un nodo e nessuna viene eliminata. Hanno scoperto che il tempo necessario per cercare semplicemente tutte le mosse era molto inferiore al tempo necessario per applicare l'euristica ad alta intensità di conoscenza per selezionarne solo alcune, e il vantaggio di non eliminare prematuramente o inavvertitamente le buone mosse ha portato a prestazioni sostanzialmente più elevate.

Negli anni '80 e '90, il progresso è stato finalmente realizzato nel paradigma della ricerca selettiva, con lo sviluppo della ricerca di quiescenza, della potatura a mossa nulla e di altre moderne euristiche di ricerca selettiva. Queste euristiche presentavano molti meno errori rispetto alle euristiche precedenti e si è scoperto che valeva il tempo extra risparmiato perché potevano cercare più a fondo e ampiamente adottate da molti motori. Mentre molti programmi moderni utilizzano la ricerca alfa-beta come substrato per il loro algoritmo di ricerca, queste euristiche di ricerca selettiva aggiuntive utilizzate nei programmi moderni significano che il programma non esegue più una ricerca "forza bruta". Invece si affidano pesantemente a queste euristiche di ricerca selettiva per estendere le linee che il programma considera buone e sfoltire e ridurre le linee che il programma considera cattive, fino al punto in cui la maggior parte dei nodi sull'albero di ricerca vengono eliminati, consentendo ai programmi moderni di cercare molto in profondità.

Nel 2006, Rémi Coulom ha creato la ricerca ad albero Monte Carlo, un altro tipo di ricerca selettiva di tipo B. Nel 2007, un adattamento della ricerca sugli alberi di Monte Carlo chiamato Upper Confidence bounds applied to Trees o UCT in breve è stato creato da Levente Kocsis e Csaba Szepesvári. Nel 2011, Chris Rosin ha sviluppato una variante dell'UCT chiamata Predictor + Upper Confidence bounds applied to Trees, o PUCT in breve. Il PUCT è stato poi utilizzato in AlphaZero nel 2017 e successivamente in Leela Chess Zero nel 2018.

Conoscenza contro ricerca (velocità del processore)

Negli anni '70, la maggior parte dei programmi di scacchi girava su super computer come Control Data Cyber 176 o Cray-1, indicativo che durante quel periodo di sviluppo per gli scacchi per computer, la potenza di elaborazione era il fattore limitante nelle prestazioni. La maggior parte dei programmi di scacchi faticava a cercare a una profondità superiore a 3 strati. Fu solo con le macchine da scacchi hardware degli anni '80 che divenne evidente una relazione tra la velocità del processore e la conoscenza codificata nella funzione di valutazione.

Si stima che il raddoppio del la velocità del computer guadagna circa cinquanta o settanta punti Elo nella forza di gioco (Levy & Newborn 1991:192).

Per

la maggior parte delle posizioni degli scacchi, i computer non possono guardare avanti a tutte le possibili posizioni finali. Invece, devono guardare avanti di qualche velo e confrontare le possibili posizioni, note come foglie. L'algoritmo che valuta le foglie è chiamato "funzione di valutazione", e questi algoritmi sono spesso molto diversi tra i diversi programmi di scacchi. Le funzioni di valutazione valutano tipicamente le posizioni in centesimi di pedone (chiamato centepiede), dove per convenzione, una valutazione positiva favorisce il Bianco e una valutazione negativa favorisce il Nero. Tuttavia, alcune funzioni di valutazione producono percentuali di vincita/patta/perdita invece di centipedoni.

Storicamente, le funzioni di valutazione artigianali considerano il valore del materiale insieme ad altri fattori che influenzano la resistenza di ciascun lato. Quando si conta il materiale per ogni lato, i valori tipici per i pezzi sono 1 punto per un pedone, 3 punti per un cavallo o un alfiere, 5 punti per una torre e 9 punti per una donna. (Vedi Valore relativo dei pezzi degli scacchi.) Al re a volte viene dato un valore arbitrariamente alto, come 200 punti (carta di Shannon) per garantire che uno scacco matto superi tutti gli altri fattori (Levy & Newborn 1991:45). Oltre ai punti per i pezzi, la maggior parte delle funzioni di valutazione artigianali tiene conto di molti fattori, come la struttura dei pedoni, il fatto che una coppia di alfieri di solito vale di più, i pezzi centralizzati valgono di più e così via. Di solito si considera la protezione dei re, così come la fase del gioco (apertura, metà o finale). Le tecniche di apprendimento automatico come la tornitura Texel, la discesa stocastica del gradiente o l'apprendimento per rinforzo vengono solitamente utilizzate per ottimizzare le funzioni di valutazione artigianali.

Le funzioni di valutazione più moderne utilizzare le reti neurali. La funzione di valutazione più comune in uso oggi è la rete neurale aggiornabile in modo efficiente, che è una rete neurale superficiale i cui input sono tabelle quadrate di pezzi. Le tabelle pezzo-quadrato sono un insieme di 64 valori corrispondenti alle caselle della scacchiera, e in genere esiste una tavola pezzo-quadrato per ogni pezzo e colore, risultando in 12 tavole pezzo-quadrato e quindi 768 input nella rete neurale. Inoltre, alcuni motori utilizzano reti neurali profonde nella loro funzione di valutazione. Le reti neurali vengono solitamente addestrate utilizzando un algoritmo di apprendimento per rinforzo, in combinazione con l'apprendimento supervisionato o l'apprendimento non supervisionato.

L'output della funzione di valutazione è un singolo scalare, quantizzato in centipedi o altre unità, che è, nel caso di funzioni di valutazione artigianali, una somma ponderata dei vari fattori descritti, o nel caso di valutazione basata su reti neurali funzioni, l'output della testa della rete neurale. La valutazione rappresenta o approssima putativamente il valore del sottoalbero sotto il nodo valutato come se fosse stato cercato fino alla terminazione, cioè alla fine del gioco. Durante la ricerca, una valutazione viene confrontata con le valutazioni di altre foglie, eliminando i nodi che rappresentano mosse cattive o scarse per entrambi i lati, per ottenere un nodo che, per convergenza, rappresenta il valore della posizione con il miglior gioco da entrambi i lati.

Articolo

principale: Tablebase dei finali

Il gioco dei finali è stato a lungo uno dei grandi punti deboli dei programmi di scacchi a causa della profondità di ricerca necessaria. Alcuni programmi di livello master non erano in grado di vincere in posizioni in cui anche i giocatori umani intermedi potevano forzare una vittoria.

Per risolvere questo problema, i computer sono stati utilizzati per analizzare completamente alcune posizioni dei finali di scacchi, a partire dal re e dal pedone contro il re. Tali tablebase di finale sono generate in anticipo utilizzando una forma di analisi retrograda, iniziando con le posizioni in cui il risultato finale è noto (ad esempio, dove un lato è stato matto) e vedendo quali altre posizioni sono a una mossa da esse, quindi quali sono a una mossa da quelle, ecc. Ken Thompson è stato un pioniere in questo settore.

I risultati dell'analisi al computer a volte hanno sorpreso le persone. Nel 1977 la macchina scacchistica Belle di Thompson utilizzò la base del tavolo dei finali per un re e una torre contro re e regina e fu in grado di pareggiare quel finale teoricamente perso contro diversi maestri (vedi posizione di Philidor#Regina contro torre). Questo nonostante non seguisse la solita strategia di ritardare la sconfitta tenendo il re e la torre in difesa vicini il più a lungo possibile. Alla richiesta di spiegare le ragioni dietro alcune delle mosse del programma, Thompson non è stato in grado di farlo oltre a dire che il database del programma ha semplicemente restituito le mosse migliori.

La maggior parte dei grandi maestri si rifiutò di giocare contro il computer nel finale di donna contro torre, ma Walter Browne accettò la sfida. È stata stabilita una posizione di donna contro torre in cui la donna può vincere in trenta mosse, con un gioco perfetto. A Browne furono concesse 2 ore e mezza per giocare cinquanta mosse, altrimenti la patta sarebbe stata rivendicata secondo la regola delle cinquanta mosse. Dopo quarantacinque mosse, Browne accettò la patta, non essendo in grado di forzare lo scacco matto o vincere la torre entro le successive cinque mosse. Nella posizione finale, Browne era ancora a diciassette mosse dallo scacco matto, ma non così lontano dalla vittoria della torre. Browne studiò il finale e giocò di nuovo al computer una settimana dopo in una posizione diversa in cui la donna può vincere in trenta mosse. Questa volta, ha catturato la torre alla cinquantesima mossa, dandogli una posizione vincente (Levy & Newborn 1991:144-48), (Nunn 2002:49).

Altre posizioni, a lungo credute conquistate, si sono rivelate Più mosse contro il gioco perfetto per vincere effettivamente di quanto fosse consentito dalla regola delle cinquanta mosse degli scacchi. Di conseguenza, per alcuni anni le regole ufficiali degli scacchi FIDE sono state modificate per estendere il numero di mosse consentite in questi finali. Dopo un po', la regola tornò a cinquanta mosse in tutte le posizioni - ne furono scoperte altre di simili, complicando ulteriormente la regola, e non fece alcuna differenza nel gioco umano, poiché non potevano giocare perfettamente le posizioni.

Nel corso degli anni, sono stati rilasciati altri formati di database di finali, tra cui l'Edward Tablebase, il De Koning Database e il Nalimov Tablebase, utilizzato da molti programmi di scacchi come Rybka, Shredder e Fritz. Sono disponibili basi per tutti i tavoli con sei pezzi. [25] Alcuni finali di sette pezzi sono stati analizzati da Marc Bourzutschky e Yakov Konoval. [26] I programmatori che utilizzano i supercomputer Lomonosov in Mosca ha completato un tavolo di scacchi per tutti i finali con sette pezzi o meno (sono escluse le posizioni banali dei finali, come sei pezzi bianchi contro un re nero solitario). [27] [28] In tutti questi database di finali si presume che l'arrocco non sia più possibile.

Molte tablebase non considerano la regola delle cinquanta mosse, in base alla quale una partita in cui passano cinquanta mosse senza una cattura o una mossa di pedone può essere considerata patta da entrambi i giocatori. Ciò fa sì che la tablebase restituisca risultati come "Matto forzato in sessantasei mosse" in alcune posizioni, che in realtà verrebbero pescati a causa della regola delle cinquanta mosse. Una ragione di ciò è che se le regole degli scacchi dovessero essere cambiate ancora una volta, dando più tempo per conquistare tali posizioni, non sarebbe necessario rigenerare tutte le tablebase. È anche molto facile per il programma che utilizza le tablebase notare e tenere conto di questa 'caratteristica' e In ogni caso, se si utilizza un finale, la base del tavolo sceglierà la mossa che porta alla vittoria più rapida (anche se cadrebbe in contrasto con la regola delle cinquanta mosse con il gioco perfetto). Se si gioca contro un avversario che non utilizza una tablebase, tale scelta darà buone possibilità di vincere entro cinquanta mosse.

Le tablebase Nalimov, che utilizzano tecniche di compressione all'avanguardia, richiedono 7,05 GB di spazio su disco rigido per tutti i finali a cinque pezzi. Per coprire tutti i finali in sei pezzi sono necessari circa 1,2 TB. Si stima che una tablebase di sette pezzi richieda tra i 50 e i 200 TB di spazio di archiviazione. [29]

I database dei finali hanno avuto un ruolo di primo piano nel 1999, quando Kasparov ha giocato una partita di esibizione su Internet contro il resto del mondo. È stato raggiunto un finale di sette pezzi di Donna e pedone con il World Team che lottava per salvare la patta. Eugene Nalimov ha contribuito a generare la base del tavolo finale in sei pezzi in cui entrambi i lati ne avevano due Queens che è stato utilizzato pesantemente per aiutare l'analisi da entrambe le parti.

La base da tavolo per i finali più popolare è syzygy, utilizzata dalla maggior parte dei migliori programmi per computer come Stockfish, Leela Chess Zero e Komodo. È anche di dimensioni significativamente più piccole rispetto ad altri formati, con tablebase da 7 pezzi che occupano solo 18,4 TB. [30]

Per un attuale motore scacchistico all'avanguardia come Stockfish, una base da tavolo fornisce solo un aumento molto piccolo della forza di gioco (circa 3 punti Elo per la sizigia 6men a partire da Stockfish 15). [31]

I

motori scacchistici, come gli esseri umani, possono far risparmiare tempo di elaborazione e selezionare variazioni forti come spiegato dai maestri, facendo riferimento a un libro di apertura memorizzato in un database su disco. I libri di apertura coprono le mosse iniziali di una partita a profondità variabile, a seconda dell'apertura e della variazione, ma di solito alle prime 10-12 mosse (20-24 strati). Poiché il Le aperture sono state studiate in profondità dai Maestri per secoli, e alcune sono note per arrivare fino al Medio Gioco, le valutazioni di variazioni specifiche da parte dei Maestri saranno solitamente superiori all'euristica generale del programma.

Mentre un tempo, giocare una mossa fuori libro per mettere il programma di scacchi sulle proprie risorse poteva essere una strategia efficace perché i libri di apertura degli scacchi erano selettivi per lo stile di gioco del programma, e i programmi avevano notevoli debolezze rispetto agli esseri umani, questo non è più vero oggi. [ quando? ] I libri di apertura memorizzati nei database dei computer sono molto probabilmente molto più estesi anche degli esseri umani meglio preparati, E giocare una mossa fuori libro anticipata può far sì che il computer trovi la mossa insolita nel suo libro e metta in sella l'avversario con un netto svantaggio. Anche se non lo fa, giocare fuori dai libri può essere molto meglio per gli scacchi tatticamente acuti programmi che per gli esseri umani che devono scoprire mosse forti in una variazione sconosciuta sulla scacchiera.

Nei moderni tornei con motore, i libri di apertura sono usati per costringere i motori a giocare aperture intenzionalmente sbilanciate per ridurre il tasso di patta e per aggiungere più varietà alle partite. [32]

Liste di valutazione degli scacchi per computer

Vedi anche: Chess engine § Valutazioni

CEGT, [33] CSS, [34] SSDF, [35] WBEC, [36] REBEL, [37], FGRL, [38] e IPON [39] mantengono elenchi di valutazione che consentono agli appassionati di confrontare la potenza dei motori. Varie versioni di Stockfish, Komodo, Leela Chess Zero e Fat Fritz dominano le classifiche all'inizio degli anni 2020.

CCRL (Computer Chess Rating Lists) è un'organizzazione che mette alla prova la forza dei motori scacchistici per computer giocando il programmi l'uno contro l'altro. Il CCRL è stato fondato nel 2006 per promuovere la competizione tra computer e computer e tabulare i risultati in una lista di valutazione. [40]

L'organizzazione gestisce tre diverse liste: 40/40 (40 minuti ogni 40 mosse giocate), 40/4 (4 minuti ogni 40 mosse giocate) e 40/4 FRC (stesso controllo del tempo ma Scacchi960). [Nota 2] Il pondering (o cervello permanente) è disattivato e il timing è regolato sulla CPU AMD64 X2 4600+ (2.4 GHz) utilizzando Crafty 19.17 BH come benchmark. Vengono utilizzati libri di apertura generici e neutri (al contrario del libro del motore) fino a un limite di 12 mosse nel gioco insieme a tablebase da 4 o 5 uomini. [40] [41] [42]

Storia

Prima dell'era

dei computer

L'idea di creare una macchina per giocare a scacchi risale al XVIII secolo. Intorno al 1769, l'automa che gioca a scacchi chiamato Il Turco, creato dall'inventore ungherese Farkas Kempelen, è diventato famoso prima di essere smascherato come una bufala. Prima dello sviluppo del calcolo digitale, le prove serie basate su automi come El Ajedrecista del 1912, costruito dall'ingegnere spagnolo Leonardo Torres Quevedo, che giocava un finale di re e torre contro re, erano troppo complesse e limitate per essere utili per giocare partite complete di scacchi. Il campo della ricerca scacchistica meccanica ha languito fino all'avvento del computer digitale negli anni '50.

Da

allora, gli appassionati di scacchi e gli ingegneri informatici hanno costruito, con sempre maggiore serietà e successo, macchine per giocare a scacchi e programmi per computer. Uno dei pochi grandi maestri di scacchi a dedicarsi seriamente agli scacchi per computer è stato l'ex campione del mondo di scacchi Mikhail Botvinnik, che ha scritto diverse opere sull'argomento. L'interesse di Botvinnik per gli scacchi al computer iniziò negli anni '50, favorendo gli algoritmi scacchistici basati sulla strategia selettiva di tipo B di Shannon, come discusso insieme a Max Euwe 1958 nella televisione olandese. Lavorando con hardware relativamente primitivo disponibile in Unione Sovietica nei primi anni '60, Botvinnik non ebbe altra scelta che studiare le tecniche di selezione delle mosse software; all'epoca solo i computer più potenti potevano ottenere molto di più di una ricerca a tre strati a tutta larghezza, e Botvinnik non aveva macchine del genere. Nel 1965 Botvinnik fu consulente del team ITEP in una partita di scacchi computerizzata tra Stati Uniti e Unione Sovietica che vinse una partita di scacchi per corrispondenza contro il programma Kotok-McCarthy guidato da John McCarthy nel 1967. (vedi Kotok-McCarthy). In seguito ha consigliato il team che ha creato il programma scacchistico Kaissa presso l'Istituto di Scienze del Controllo di Mosca. Botvinnik aveva le sue idee per modellare la mente di un maestro di scacchi. Dopo aver pubblicato e discusso le sue prime idee sulle mappe di attacco e Nel 1966 trovò Vladimir Butenko come sostenitore e collaboratore. Butenko ha implementato per la prima volta la rappresentazione della scheda degli attacchi vettoriali 15x15 su un computer M-20, determinando le traiettorie. Dopo che Botvinnik introdusse il concetto di Zone nel 1970, Butenko rifiutò ulteriori collaborazioni e iniziò a scrivere il suo programma, soprannominato Eureka. Negli anni '70 e '80, alla guida di un team composto da Boris Stilman, Alexander Yudin, Alexander Reznitskiy, Michael Tsfasman e Mikhail Chudakov, Botvinnik ha lavorato al suo progetto "Pioneer" - che era un progetto scacchistico basato sull'intelligenza artificiale. Negli anni '90, Botvinnik già ottantenne, ha lavorato al nuovo progetto 'CC Sapiens'.

Una

pietra miliare dello sviluppo si è verificata quando il team della Northwestern University, che era responsabile della serie di programmi di scacchi e ha vinto i primi tre ACMComputer Chess Campionati (1970-72), abbandonata la ricerca di tipo B nel 1973. Il programma risultante, Chess 4.0, vinse il campionato di quell'anno e i suoi successori arrivarono secondi sia nel Campionato ACM del 1974 che nel Campionato Mondiale di Scacchi per Computer inaugurale di quell'anno, prima di vincere di nuovo il Campionato ACM nel 1975, 1976 e 1977. L'implementazione di tipo A si è rivelata altrettanto veloce: nel tempo necessario per decidere quali mosse fossero degne di essere cercate, era possibile cercarle tutte. In effetti, gli scacchi 4.0 hanno stabilito il paradigma che è stato ed è ancora seguito essenzialmente da tutti i moderni programmi di scacchi di oggi, e che è stato avviato con successo dall'ITEP russo nel 1965.

L'ascesa delle macchine scacchistiche

Nel 1978, una prima versione della macchina scacchistica hardware di Ken Thompson, Belle, partecipò e vinse il North American Computer Chess Championship contro la dominante Northwestern University Chess 4.7.

La rivoluzione dei microcomputer

I progressi tecnologici di ordini di grandezza nella potenza di elaborazione hanno reso l'approccio della forza bruta molto più incisivo di quanto non fosse nei primi anni. Il risultato è che un giocatore IA molto solido e tattico, aiutato da una conoscenza limitata della posizione incorporata dalla funzione di valutazione e dalle regole di potatura/estensione, ha iniziato a competere con i migliori giocatori del mondo. Si è rivelato produrre risultati eccellenti, almeno nel campo degli scacchi, lasciando che i computer facessero ciò che sanno fare meglio (calcolare) piuttosto che convincerli a imitare i processi di pensiero e la conoscenza umana. Nel 1997 Deep Blue, una macchina a forza bruta in grado di esaminare 500 milioni di nodi al secondo, sconfisse il campione del mondo Garry Kasparov, segnando la prima volta che un computer ha sconfitto un campione del mondo di scacchi in carica nel controllo del tempo standard.

Scacchi sovrumani

Nel 2016, NPR ha chiesto agli esperti di caratterizzare il stile di gioco dei motori scacchistici per computer. Murray Campbell di IBM ha affermato che "I computer non hanno alcun senso estetico... Giocano quella che pensano sia la mossa oggettivamente migliore in qualsiasi posizione, anche se sembra assurda, e possono giocare qualsiasi mossa, non importa quanto brutta sia". I Grandi Maestri Andrew Soltis e Susan Polgar hanno affermato che i computer hanno maggiori probabilità di ritirarsi rispetto agli esseri umani. [22]

Mentre

le reti neurali sono state utilizzate nelle funzioni di valutazione dei motori scacchistici dalla fine degli anni '80, con programmi come NeuroChess, Morph, Blondie25, Giraffe, AlphaZero e MuZero, [43] [44] [45] [46] [47] Le reti neurali non sono state ampiamente adottate dai motori scacchistici fino all'arrivo delle reti neurali aggiornabili in modo efficiente nell'estate del 2020. Aggiornabile in modo efficiente le reti neurali sono state originariamente sviluppate nel computer shogi nel 2018 da Yu Nasu, [48] [49] e hanno dovuto essere prima trasferite su un derivato di Stockfish chiamato Stockfish NNUE il 31 maggio 2020, [50] e integrate nel motore ufficiale di Stockfish il 6 agosto 2020, [51] [52] prima che altri programmatori di scacchi iniziassero ad adottare reti neurali nei loro motori.

Alcune persone, come Venki Ramakrishnan della Royal Society, credono che AlphaZero abbia portato all'adozione diffusa di reti neurali nei motori scacchistici. [53] Tuttavia, AlphaZero ha influenzato pochissimi motori per iniziare a utilizzare le reti neurali, e questi tendevano ad essere nuovi motori sperimentali come Leela Chess Zero, che ha iniziato specificamente a replicare l'articolo di AlphaZero. Le reti neurali profonde utilizzate nella funzione di valutazione di AlphaZero richiedevano una grafica costosa unità di elaborazione, che non erano compatibili con i motori scacchistici esistenti. La stragrande maggioranza dei motori scacchistici utilizza solo unità di elaborazione centrali, e il calcolo e l'elaborazione delle informazioni sulle GPU richiedono librerie speciali nel back-end come CUDA di Nvidia, a cui nessuno dei motori ha accesso. Pertanto, la stragrande maggioranza dei motori scacchistici come Komodo e Stockfish ha continuato a utilizzare funzioni di valutazione artigianali fino a quando le reti neurali aggiornabili in modo efficiente non sono state trasferite negli scacchi per computer nel 2020, che non richiedevano affatto l'uso di GPU o librerie come CUDA. Anche in questo caso, le reti neurali utilizzate negli scacchi al computer sono piuttosto superficiali e i metodi di apprendimento per rinforzo profondo introdotti da AlphaZero sono ancora estremamente rari negli scacchi al computer.

Timeline

  • 1769 - Wolfgang von Kempelen costruisce il Turk. Presentato come un automa che gioca a scacchi, è segretamente gestito da un giocatore umano nascosto al suo interno la macchina.
  • 1868 - Charles Hooper presenta l'automa Ajeeb, anch'esso con un giocatore di scacchi umano nascosto al suo interno.
  • 1912 - Leonardo Torres y Quevedo costruisce El Ajedrecista, una macchina in grado di giocare finali di Re e Torre contro Re.
  • 1941 - Anticipando di almeno un decennio un lavoro analogo, Konrad Zuse sviluppa algoritmi scacchistici per computer nel suo formalismo di programmazione Plankalkül A causa delle circostanze della seconda guerra mondiale, tuttavia, non furono pubblicati, e non vennero alla luce, fino agli anni '70.
  • 1948 - Il libro di Norbert Wiener Cibernetica descrive come un programma di scacchi possa essere sviluppato utilizzando una ricerca minimax a profondità limitata con una funzione di valutazione
  • 1950 - Claude Shannon pubblica "Programming a Computer for Playing Chess", uno dei primi articoli sui metodi algoritmici degli scacchi per computer.
  • 1951 - Alan Turing è il primo a pubblicare un , sviluppato su carta, che era in grado di giocare una partita completa di scacchi (soprannominato Turochamp). [54] [55]
  • 1952 - Dietrich Prinz sviluppa un programma che risolve i problemi scacchistici.
  • 1956 - Gli scacchi di Los Alamos sono il primo programma a giocare a un gioco simile agli scacchi, sviluppato da Paul Stein e Mark Wells per il computer MANIAC I.
  • 1956 - John McCarthy inventa l'algoritmo di ricerca alfa-beta.
  • 1957 - Vengono sviluppati i primi programmi in grado di giocare una partita completa di scacchi, uno da Alex Bernstein [56] e uno da programmatori russi che utilizzano un BESM.
  • 1958 - NSS diventa il primo programma di scacchi ad utilizzare l'alfa-beta algoritmo di ricerca.
  • 1962 - Il primo programma a giocare in modo credibile, Kotok-McCarthy, viene pubblicato al MIT.
  • 1963 - Il Grande Maestro David Bronstein sconfigge un M-20 che esegue un programma di scacchi iniziale.
  • 1966-67 - Viene giocata la prima partita di scacchi tra programmi per computer. L'Istituto di Fisica Teorica e Sperimentale di Mosca (ITEP) sconfigge Kotok-McCarthy all'Università di Stanford per telegrafo in nove mesi.
  • 1967 - Mac Hack VI, di Richard Greenblatt et al. introduce le tabelle di trasposizione e impiega dozzine di euristiche di selezione delle mosse accuratamente sintonizzate; diventa il primo programma per sconfiggere una persona in un torneo. Mac Hack VI giocava a circa il livello di classe C.
  • 1968 - Il campione scozzese di scacchi David Levy scommette con i pionieri dell'intelligenza artificiale John McCarthy e Donald Michie che nessun programma per computer vincerebbe una partita di scacchi contro di lui entro 10 anni.
  • 1970 - Monty Newborn e l'Association for Computing Machinery organizzano il primo North American Computer Chess Championships a New York
  • 1971 - Ken Thompson, un informatico americano presso i Bell Labs e creatore del sistema operativo Unix , scrive il suo primo programma per giocare a scacchi chiamato "chess" per la prima versione di Unix. [58]
  • 1974 - David Levy, Ben Mittman e Monty Newborn organizzano il primo Campionato Mondiale di Scacchi per Computer che viene vinto dal programma russo Kaissa
  • 1975 - Dopo quasi un decennio di progressi solo marginali dal picco del MacHack VI di Greenblatt nel 1967, viene introdotto il Northwestern University Chess 4.5 con ricerca a larghezza intera e innovazioni di bitboard e approfondimento iterativo. Ha anche ripristinato una tabella di trasposizione come visto per la prima volta nel programma di Greenblatt. Fu quindi il primo programma con una struttura moderna integrata e divenne il modello per tutto lo sviluppo futuro. Chess 4.5 ha giocato una classe B forte e ha vinto il 3° Campionato Mondiale di Scacchi per Computer l'anno successivo.