I computer giocano a scacchi: a che punto siamo?

Sarà forse inevitabile che i computer diventino imbattibili, con gli scacchi, nel prossimo futuro ma per adesso gli uomini - i campioni naturalmente - sono ancora all'altezza della sfida. Com'è possibile che il cervello umano, che ha solo una piccola frazione delle capacità di calcolo dei computer, sia ancora in grado di mettere a segno delle vittorie? La risposta sta nelle differenze tra l'uomo e i metodi artificiali di calcolo e nella conoscenza che un astuto giocatore ha delle debolezze del computer.

L'origine degli scacchi

Shaturanga - l'antenato di tutti i giochi come gli scacchi - è stato sviluppato circa 1600 anni fa da un filosofo indiano. Da allora, si è diffuso in tutto il mondo e si è evoluto in moltissime forme differenti. In Cina, Giappone, Corea, Tailandia e Europa si svilupparono nel Medioevo metodi di gioco simili ma distinti. Gli scacchi europei ebbero il loro maggior sviluppo verso la fine del '400 quando furono modificate le caratteristiche di gioco di diversi pezzi. Il pezzo denominato fers diventa il pezzo più potente della scacchiera, unendo il movimento dell'alfiere e quello della torre e diventa la regina. Alcune delle regole più familiari utilizzate oggi sono state introdotte allora (come l'arrocco, l'avanzamento di due caselle del pedone).

Per altri 250 anni, tuttavia, nessuno pubblicò un approfondito e sistematico ragionamento sulle strategie degli scacchi europei. L'Analyze des Áchecs, scritto da François- André Philidor nel 1748, introduce alcuni concetti (come le mosse preventive e le posizioni sacrificali) e include uno studio delle chiusure classiche. Il libro fu cruciale nello sviluppo dello studio degli scacchi e della loro nomenclatura, che ora include alcuni termini esotici come difesa stonewall, variante del camaleonte, i tranelli di Noah e il pedone avvelenato di Najdorf.

Parlando di una rivoluzione

I giocatori di livello internazionale passano le ore per pensare a una singola mossa durante il gioco e spendono la loro carriera analizzando e perfezionando tattiche per le prime mosse di un'apertura. Ma il gioco sta andando incontro a una nuova rivoluzione. Le capacità di calcolo dei computer sono cresciute esponenzialmente dal 1950 quando comparve sulla scena il primo programma per giocare a scacchi. Dalla metà delgli anni '80, i computer si sono avvicinati al livello dei campioni (grandmaster) e nel 1997 Garry Kasparov, allora campione del mondo, venne sconfitto in una famosa partita con un supercomputer dell'IBM chiamato Deep Blue (il computer vinse due partite, ne perse una e pareggiò le altre tre).

È solo una questione di tempo e le macchine diventeranno imbattibili ma anche Kasparov è ottimista sul futuro dei giocatori umani. I computer saranno allora degli eccellenti strumenti di aprrendimento o di preparazione alle partite.

Nel linguaggio della Teoria dei giochi gli scacchi sono un gioco finito senza elementi random, giocato da due giocatori ognuno con a disposizione informazioni complete. È anche un gioco a somma-zero, che significa che il vantaggio di un giocatore è necessariamente lo svantaggio dell'avversario. Come conseguenza, è teoricamente possibile giocare una partita a scacchi perfetta, in cui cioè entrambi i giocatori possono sempre calcolare l'esatta sequenza di mosse migliori. Durante una partita perfetta, i giocatori conoscono in ogni istante la miglior mossa In funzione di come risponde l'avversario, il quale potrebbe anche essere sempre previsto.L'intero gioco sarà trasparente, con entrambi i giocatori a conoscenza esattamente di come la partita finirà 10, 30 o 100 mosse dopo.

Può essere razionale e divertente allo stesso tempo?

Per esempio, all'inizio di una partita a tris c'è una scelta tra nove possibili mosse. Solo 512 (2⁹) differenti combinazioni di O e di X possono essere riprodotte in una scacchiera 3x3. Il numero massimo di partite differenti è tuttavia ancora minore poiché la simmetria rotazionale dimostra l'identicità tra alcune di queste possibilità. Inoltre, molte di queste disposizioni sono vincenti e finiscono prima che tutte le nove caselle siano riempite. Si possono pertanto conoscere tutte le possibili partite ed essere in grado di rispondere nel miglior modo alle mosse dell'avversario. A tris, una partita pari e patta è l'unico risultato possibile tra due giocatori razionali.

Gli scacchi, sono molto più complessi e i pezzi possono essere arrangiati su 64 caselle della scacchiera in 10⁴⁴ differenti posizioni. Un matematico ha calcolato che ci sono circa 10^{(10^50)} differenti partite possibili, che è maggiore del numero di particelle dell'intero universo visibile. È di fatto un numero di permutazioni effettivamente infinito e così è impossibile giocare a scacchi perfettamente.

In termini di Teoria combinatoria dei giochi descritta nel libro Games people play, non è chiaro se il valore di una partita a scacchi sia fuzzy o se la partenza sia a posizione-zero. In effetti, questa potrebbe essere la vera ragione per cui Dio non gioca parafrasando Einstein (che disse "Dio non gioca a dadi", esprimendo la sua incredulità nei confronti dell'indeterminazione inerente alla Meccanica quantistica). Egli potrebbe conoscere il risultato di ogni partita prima di iniziare il gioco e allora dove sarebbe il divertimento?

Durante il gioco, il giocatore può scegliere quale pezzo muovere e spesso anche in quale casella muoverlo. Dalla posizione iniziale, il Bianco può scegliere solamente tra 20 mosse permesse, ma questo pallone si gonfia in molte centinaia di possibilità, o candidati, a metà partita quando più pezzi sono liberi di muoversi. L'avanzamento del gioco può pertanto essere pensato come un cespuglio fiorente, con numerose frasche che spuntano da uno stesso punto sul ramo per indicare ognuna delle differenti mosse permesse disponibili in una data posizione. Ad ogni turno, ognuna di queste frasche fiorisce in molte altre possibili diramazioni. Il numero di possibilità, che deve essere analizzato, cresce esponenzialmente. Il trucco per giocare a scacchi in modo efficiente è quello di ignorare le linee di gioco che non sembrano migliorare la propria posizione e focalizzare la propria analisi su un piccolo numero di candidate promettenti per poter potare l'albero del gioco. Il calcolo è particolarmente difficile poichè bisogna trovare una mossa che, non solo serva al giocatore per migliorare il suo stato, ma anche limiti le opzioni positive disponibili per l'avversario. Il nodo da sciogliere, nella differenza tra uomo e computer, è la diversità di modi in cui vengono potati questi cespugli.

Il cervello di un giocatore esperto sembra in grado di potare la ricerca in modo abbastanza intuitivo. I campioni, tipicamente, studiano solo una decina di possibilità per ogni turno. Attraverso questa focalizzazione è possibile, sulle linee di azione selezionate, raggiungere una maggior profondità di analisi. I giocatori esperti hanno un buon senso della scacchiera: senza analizzare esplicitamente una posizione, identificano quali pezzi siano in posizioni dominanti, quali combinazioni di pedoni siano forti, dove stanno le debolezze dell'avversario e così via. Il computer, invece, gioca come un principiante. Un principiante - sia ben chiaro - in grado di valutare milioni di mosse al secondo. I computer applicano al gioco degli scacchi la tecnica della forza bruta e non hanno idea di cosa sia questo feeling con la scacchiera. Un computer può solamente vagabondare ciecamente lungo tutte le diramazioni ipotetiche di una partita, fino a trovare una sequenza di mosse considerate positive. Un buon giocatore, invece, identifica un pericolo o un obiettivo e pensa lateralmente e creativamente su come usare i pezzi a disposizione in modo combinato per raggiungere il risultato desiderato.

Sebbene le procedure programmate, o algoritmi, che il computer usa per ridurre lo spazio di ricerca continuino a migliorare, le differenze appena citate rappresentano ancora il lato debole di un computer che gioca a scacchi.

Ci sono altri due metodi che i programmatori utilizzano per migliorare il gioco delle macchine. Il primo è una libreria, che contiene una sequenza stabilita di mosse per i primi turni. Questa conoscenza è il risultato di secoli di analisi dei modi migliori per muovere i propri nelle fasi iniziali di una partita.

Il secondo metodo è conosciuto come approccio bottom-up. Molti scenari di fine gioco sono noti per la possibilità di uno dei giocatori di forzare la vittoria (per esempio il solo re contro la regina, o le due torri, o una torre e un pedone contro l'alfiere). Un computer può allora "non muovere" alcuni pezzi, o tornare indietro, per trovare tutte le posizioni da cui può essere raggiunto uno degli scenari conosciuti.

Questo approccio ha prodotto un enorme data-base di finali di partita in modo che, se un computer raggiunge una delle posizioni incluse, può giocare una partita essenzialmente perfetta. Tutti i finali di partita con meno di sei pezzi sono già stati analizzati esaustivamente. Nel complesso, queste analisi svolte dai computer sono in accordo con le analisi svolte da giocatori esperti attraverso i secoli. Alcuni risultati sorprendenti sono stati trovati, tuttavia, come quello del finale di torre e cavallo contro due cavalli. Questa è generalmente pensata come una partita patta ma, per alcune posizioni, è possibile per il Bianco catturare senza rischio uno dei cavalli e assicurarsi così la vittoria.

La posizione mostrata qui a sinistra richiede la più lunga sequenza nota, prima della cattura: 243 mosse. Questa esatta posizione è veramente improbabile da raggiungere. Una partita reale può finire con solo 50 mosse senza una singola cattura o promozione.

Chinook e la Dama

Come si può notare dal diagramma, è da quando si esce dalla libreria (degli inizi di partita) finché non si arriva al data-base dei finali che il computer può diventare inefficiente. Questo è il momento in cui la focalizzazione della situazione e l'inventiva della mente umana è un vantaggio e i computer fanno errori che possono costare la partita.

Questo attacco a tre livelli (con l'efficienza degli algoritmi di ricerca, le libreria delle aperture, e il database delle chiusure) è stato già applicato con successo alla Dama. Un programma chiamato Chinook ha recentemente giocato 220 partite contro un campione di dama e le ha vinte tutte, tranne una. Le macchine hanno quindi già raggiunto l'invincibilità in questo più semplice gioco.

La dama ha solo 10¹⁸ posizioni di gioco ottenibili e il data-base di Chinook di 400000 miliardi di posizioni, con otto o meno pezzi, gli assicura di poter giocare perfettamente una buona parte della partita. Nell'unica partita che ha perso, il suo avversario umano ha forzato il programma fuori dalla libreria di aperture conosciute, quasi alle prime mosse. In tal modo, il computer ha dovuto spendere più tempo nella regione di vulnerabilità prima di rientrare nel data-base delle chiusure. Chinook non ha potuto calcolare alla profondità delle 25 mosse successive richieste e quindi ha perso.

Ma Chinook è un programma che impara ogni volta e il giorno in cui perderà la sua ultima partita è vicino. In un futuro molto vicino, il data-base di Chinook potrà coprire tutte le mosse permesse e giocare in modo matematicamente perfetto tutta una partita. Avrà allora risolto ogni nodo.

La maggior complessità degli scacchi implica che i computer non siano affatto allo stesso livello di invincibilità. Ma, se anche un home computer può ora analizzare più posizioni nel corso di una partita, rispetto a quelle che un giocatore medio può vedere in tutta la sua vita, com'è possibile per l'uomo poter ancora vincere? Come detto sopra, i computer non sono giocatori intelligenti e mancano della creatività della mente umana. È possibile studiare lo stile di gioco di un computer, valutare i suoi punti di forza e di debolezza e giocare su questi. I giocatori umani hanno anche diversi altri assi nella manica.

Tattiche per battere un computer a scacchi

Siccome un computer si basa su un approccio strettamente matematico nella parte centrale della partita, esso può vedere in anticipo solo un numero limitato di mosse e non riesce a ricordare strutture o manovre generali. Questa visione a corto raggio è chiamata orizzonte. Proprio giocando sull'orizzonte della macchina il giocatore può attirarla in una trappola mortale. Oppure può lentamente preparare un assalto e colpire solo quando è troppo tardi perché il computer riesca a difendersi efficacemente.

Un altro motivo per il quale i giocatori umani hanno successo, è che i computer valutano le posizioni di gioco come se avessero appena iniziato. Il computer analizzerà milioni di rami nell'albero del gioco ogni volta, anche se ha visto posizioni quasi identiche. Un uomo riconoscerà che alcune mosse non cambiano fortemente la situazione e quindi non si preoccupa di rianalizzarle. Questa differenza può naturalmente esplodere nei giochi a tempo, dove i giocatori devono fare le loro mosse in un tempo ben definito. L'umano può, a volte, vincere semplicemente muovendo avanti e indietro tra le stesse due caselle mentre il computer sperpera tutto il suo tempo riesaminando ogni posizione.

 Un'altra tattica comune in un gioco a tempo è di giocare mosse veloci che sono mediocri ma innocue, nel senso che non c'è il rischio di perdere un pezzo o lasciare il re a rischio di scacco. Un mossa particolarmente efficace è quella che complica le posizioni sulla scacchiera e figura come se fosse la parte di un attacco molto elaborato. Il computer non lo sa e spende molto del suo tempo analizzando con attenzione la posizione. Questa tattica è nota come enough rope.

Alberi e orizzonti

L'effetto orizzonte è diventato meno importante con lo sviluppo di processori più veloci e di algoritmi di potatura degli alberi più efficienti. Ma il miglior programma può essere sensibile al problema inverso.

La posizione (vedi figura successiva) proviene da una partita con un umano, che gioca il Bianco, e un computer. Il bianco ha messo il Re nero sotto scacco con la sua Regina in a8.

Il computer muove la sua Torre in e8 e il pubblico ride, pensando che il programma abbia avuto un malfunzionamento per giocare una mossa così debole. Nonostante il controllo sia stato bloccato, la Torre è completamente indifesa e la Regina bianca può immediatamente catturare questo importante pezzo. La risposta più naturale dovrebbe essere, invece, quella di muovere il Re in g7, via dallo scacco.

Finche il programma non è stato testato, non è stato possibile spiegare la sua scelta. La macchina ha realizzato che, se il re fosse stato messo in g7, allora il computer non sarebbe più stato in grado di prevenire la forzatura del Bianco verso un elegante scacco matto cinque mosso dopo.

Ma, attraverso il sacrificio della Torre, lo scaccomatto è stato ritardato (cosa che il computer valuta come utile). Ogni giocatore umano, tuttavia, avrebbe mosso il Re poiché c'è una possibilità che l'avversario - imperfetto - possa non aver visto questa sequenza di scacco. Sacrificare la Torre è un atto suicida, che implica buttar via la partita. Così, paradossalmente, in certe situazioni un computer può comportarsi meglio contro un umano se gioca ciò che lui ritiene mosse deboli!

La programmazione di un computer, per il gioco degli scacchi, è una normale estensione dell'utilizzo della Matematica nell'analisi delle posizioni. Gli scacchi sono matematicamente complessi e ancora - tra umani e computer - c'è la possibilità di sfidarsi, usando tuttavia metodi differenti.

Malgrado la nuda e cruda potenza di calcolo dei computer, l'intelligenza umana può ancora battere le macchine durante la parte centrale del gioco. Il nostro tempo è tuttavia già in fase calante e i computer sono vicini alla soluzione del gioco.