[image]https://leganerd.com/wp-content/uploads/LEGANERD_044397.jpg[/image]
[quote]Gli Scacchi sono il gioco intellettuale per eccellenza. Senza far uso di strumenti casuali (come i dadi o la roulette), che inquinerebbero la contesa, due intelletti vengono contrapposti in una situazione così complessa che nessuno dei due può sperare di comprenderla completamente, e tuttavia il gioco è sufficientemente analizzabile, di modo che ciascuno dei due può sperare di sconfiggere l’altro.
Il gioco è tanto profondo e sottile che ha permesso la nascita di giocatori professionisti, ed ha sopportato senza esaurirsi oltre 200 anni di partite e di studi analitici intensivi. Tali caratteristiche rendono gli Scacchi un’arena naturale per i tentativi di meccanizzazione.
Se si potesse sviluppare un giocatore artificiale vincente, si potrebbe affermare di aver penetrato il nucleo dell’attività intellettuale umana.
Allen Newell, Cliff Shaw and Herbert Simon, 1958[/quote]
Vi siete mai chiesti come cazzo fa Chessmaster a farvi sempre il culo a padella a scacchi? Cosa si nasconde dietro i software scacchistici che battono anche i migliori campioni al mondo? Sono davvero intelligenti o è solo una questione di potenza hardware?
Cercherò di rispondere a queste e altre domande che la vostra fervida immaginazione nerd riuscirà a partorire in una serie di articoli dedicati a scacchi e informatica.
[title]Giochi di guerra[/title]
Nel 1944 il matematico statunitense John von Neumann, insieme all’economista Oskar Morgenstern, pubblicò un libro intitolato [b]Theory of Games and Economic Behavior[/b]. Il tentativo di questi due geni del male fu quello di descrivere matematicamente il comportamento umano nei casi in cui l’interazione fra le parti comporta la vittoria e la sconfitta, o la spartizione di qualche tipo di risorsa. Questo evento può essere considerato la nascita della moderna teoria dei giochi, che vengono studiati in quanto rappresentano la più basilare forma di competizione che l’uomo conosce.
Per gli esseri umani in teoria, e per Dio in pratica (la bravura di Dio nel gioco è stata compromessa dall’ex campione del mondo Wilhelm Steinitz che affermò più volte di aver battuto Dio concedendogli un pedone e una mossa di vantaggio), il gioco degli scacchi si riduce all'[url=http://it.wikipedia.org/wiki/Albero_%28informatica%29]albero[/url], gigantesco ma finito, che comprende tutte le possibili mosse di tutte le possibili partite.
Il primo livello consiste delle 20 possibili aperture del bianco; il secondo livello delle 20 possibili aperture del nero in risposta a ciascuna apertura del bianco, cioè dei [b]400 possibili scambi di apertura[/b]; ogni livello successivo si ottiene dal precedente, aggiungendo a ciascun nodo tutte le possibili risposte dell’avversario. Per queste considerazioni, ciascun ramo dell’albero è finito, e descrive una partita che finisce o in una vittoria del bianco, o in una vittoria del nero, o in una patta.
[title]Il ruolo dei giochi nell’IA[/title]
I primi studi informatici nel campo dei giochi si sono concentrati su particolari classi: giochi con due avversari che alternano le proprie azioni, in cui l’ambiente è [i]deterministico[/i] e [i]completamente osservabile[/i] da entrambi, detto quindi ad [b]informazione perfetta[/b]. Alcuni di questi giochi sono anche a [b]somma zero[/b], cioè la somma dei risultati ottenuti da entrambi i contendenti in funzione delle strategie utilizzate è sempre nulla. Negli scacchi, ad esempio, questo significa che i soli tre risultati possibili (rappresentando la vittoria con 1, la sconfitta con -1 e il pareggio con 0) possono essere: (1,-1) se vince il Bianco; (-1,1) se vince il Nero; (0,0) se pareggiano. Non esiste il caso in cui vincono entrambi o perdono entrambi.
Sono esclusi da questa categoria i giochi solitari, come il Gioco del 15 e il Cubo di Rubik, i giochi che prevedono chance (Backgammon) o incertezze (Bridge), informazioni imperfette (Stratego) o negoziazioni (Monopoli).
Un primo passo per affrontare il problema dei giochi, è quello di classificarli in base alla loro complessità. È sufficiente definire uno spazio cartesiano in cui sull’ordinata viene rappresentato lo [b]spazio degli stati[/b] (l’insieme di tutti gli stati raggiungibili a partire da quello iniziale) e sull’ascissa la [b]complessità dell’albero[/b] di gioco.
[more]
[image]https://leganerd.com/wp-content/uploads/LEGANERD_044396.png[/image]
[/more]
È chiaro che i giochi nella categoria 1 sono molto facili da risolvere; nelle categorie 2 e 3 ci sono giochi risolvibili con differenti metodi a seconda del caso, mentre nella categoria 4 ci sono giochi non risolvibili nella pratica. La ricerca ovviamente si concentra nei giochi di categoria 2 e 3. La risoluzione dei problemi di categoria 2 dipende quasi totalmente dall’incremento della potenza dei computer, mentre la risoluzione dei giochi della categoria 3 dipende dallo sviluppo di nuove tecniche di intelligenza artificiale.
[title]Una questione di numeri[/title]
Come ho accennato prima, le possibili [b]aperture[/b] sono 20 per ciascun giocatore. 2 mosse per ciascuno degli 8 pedoni, 2 per ogniuno dei 2 cavalli. Le mosse successive sono generalmente di più, perché alcuni pezzi non saranno più occlusi, ma anche limitandosi a 20, dopo sole 10 mosse da entrambe le parti si arriva all’astronomica cifra di
[latex]400^{10} = 169\,518\,829\,100\,544\,000\,000\,000\approx10^{23}[/latex]
Il numero massimo di mosse, quando tutti i pezzi sono ancora sulla scacchiera, si ottiene sommando il numero massimo di mosse per ciascun pezzo (cio 8 per il re, 27 per la donna, 14 per la torre, 13 per l’alfiere, 8 per il cavallo, e 2 per il pedone) per il numero di pezzi:
[latex]8 + 27 + (14\times2) + (13\times2) + (8\times2) + (2\times8) = 121[/latex]
Analogamente, il numero medio di mosse si ottiene quando tutti i pezzi sono ancora sulla scacchiera, sommando il numero medio di mosse per ciascun pezzo (cio 6,5 per il re, 22,5 per la donna, 14 per la torre, 8,5 per l’alfiere, 5 per il cavallo, e 1 per il pedone) per il numero di pezzi:
[latex]7 + 22,5 + (14\times2) + (8,5\times2) + (5\times2) + (1\times8) = 92,5.[/latex]
Nella pratica il numero risulterà inferiore, a causa della mancanza di alcuni pezzi o all’occlusione di altri, e una valutazione empirica del numero medio di mosse disponibili durante una partita standard è circa 40.
Un limite assoluto al numero di configurazioni che si possono ottenere sulla scacchiera è ovviamente dato dal numero di possibili disposizioni dei 32 pezzi sulle 64 case della scacchiera, cioè
[latex]64^{32}\approx10^{57}[/latex]
Esso pone un limite alla lunghezza delle possibili partite, perché quando due configurazioni si ripetono esattamente, ciò che è successo nel frattempo non ha più importanza. Il numero delle possibili partite è dunque limitato da
[latex]121^{{10}^{57}}\approx10^{{10}^{58}}[/latex]
Il primo a stimare il numero di partite possibili fu [url=http://it.wikipedia.org/wiki/Claude_Shannon]Claude Shannon[/url], che valutò una cifra di [latex]10^{120}[/latex] partite, che è un numero addirittura maggiore di 1 googol (il numero intero esprimibile con 1 seguito da 100 zeri, pari cioè a [latex]10^{100}[/latex] o [latex]10\,000[/latex] decaexilioni).
Anche considerando solo partite più ragionevoli, di 100 mosse e con una media di 40 mosse possibili ogni volta, si ottiene comunque ancora un limite di
[latex]100^{40}=10^{80}[/latex]
pari circa al numero di particelle subatomiche dell’universo visibile, stimato tra [latex]10^{72}[/latex] e [latex]10^{87}[/latex]. Ora capirete facilmente come mai con la moderna tecnologia, e probabilmente anche con quella futura, non è possibile risolvere completamente il gioco degli scacchi.
[title]Le valutazioni dei pezzi[/title]
Come vedremo più dettagliatamente negli articoli successivi, per affrontare dal punto di vista informatico gli scacchi è necessario analizzare matematicamente le strategie utilizzate dai giocatori reali.
Il primo problema che si affronta è quello di determinare quantitativamente il valore relativo di un pezzo. Questo può essere calcolato valutando la probabilità che, posizionato un pezzo ed il re a caso sulla scacchiera, il primo dia scacco al secondo. Il re può stare in una qualsiasi delle 63 case non occupate dal pezzo in questione e la probabilità è quindi di 1/63. Bisogna valutare il numero medio di case che il pezzo può minacciare e dividerlo quindi per 63.
Il [b]re[/b], in base alle regole del gioco, non può dare scacco e non può essere mangiato e dunque il metodo precedentemente esposto non ha senso in questo caso; si possono comunque calcolare le case minacciate in media dal re a seconda della sua posizione:
– 3 per le 4 case agli angoli della scacchiera;
– 5 per le rimanenti case del bordo;
– 8 per le rimanenti 36 case.
Il risultato è
[latex size=2]\frac{(3\times4)+(5\times24)+(8\times36)}{64}=\frac{105}{16}\approx6.5[/latex]
La [b]donna[/b], impropriamente chiamata regina come traduzione del termine inglese [i]queen[/i], minaccia le case che stanno sulla stessa traversa e sulla stessa colonna, che sono sempre 14, e le case che stanno sulle diagonali che passano per ciascuna delle 64 case in cui essa si può trovare. Queste ultime dipendono dalla sua posizione sulla scacchiera, e sono:
– 7 per le 28 case sul bordo;
– 9 per le 20 case sul secondo bordo;
– 11 per le 12 case sul terzo bordo;
– 13 per le 4 case sul quadrato centrale.
Il valore della donna è dunque
[latex size=2]\frac{14}{63}\cdot\frac{(28\times7)+(20\times9)+(12\times11)+(4\times13)}{64\times63}=\frac{2}{9}+\frac{5}{36}=\frac{13}{36}\approx\frac{1}{3}[/latex]
La [b]torre[/b] minaccia le stesse case in orizzontale e verticale che minaccia la donna, ed il suo valore relativo è dunque 14/63, cioè 2/9. In particolare, poichè
[latex size=2]\frac{2}{9}+\frac{2}{9}=\frac{4}{9}=\frac{16}{36}>\frac{13}{36}[/latex]
due torri valgono più di una donna.
L'[b]alfiere[/b] minaccia le stesse case in diagonale che minaccia la donna, ed il suo valore relativo è
[latex size=2]\frac{5}{36}\approx\frac{1}{7}[/latex]
In particolare, poiché
[latex size=2]\frac{5}{36}+\frac{5}{36}=\frac{10}{36}<\frac{13}{36}[/latex]
due alfieri valgono meno di una donna.
Il [b]cavallo[/b] minaccia le case che si trovano ad L rispetto a quella in cui esso si può trovare. Le L possibili a partire da una casa dipendono dalla posizione di questa sulla scacchiera, e sono:
– 2 per le 4 case agli angoli della scacchiera;
– 3 per le 8 case sul bordo ai lati degli angoli;
– 4 per le rimanenti 16 case sul bordo, o le 4 case agli angoli del secondo bordo;
– 6 per le rimanenti 16 case sul secondo bordo;
– 8 per le 16 case centrali.
Il valore del cavallo è
[latex size=2]\frac{(4\times2)+(8\times3)+(20\times4)+(16\times6)+(16\times8)}{64\times63}=\frac{1}{12}[/latex]
Ora direte voi, esticazzi? Che ce ne facciamo di questi valori? Bene, riducendo al comune denominatore 36, otteniamo un prima, grezza valutazione dei pezzi:
Re: [latex]+ \infty[/latex]
Donna: 13
Torre: 8
Alfiere: 5
Cavallo: 3
dai quali si possono trarre interessanti relazioni sul valore dei pezzi.
[more]
[image]https://leganerd.com/wp-content/uploads/LEGANERD_044395.png[/image]
[/more]
Il disclaimer verso i pro-player scacchisti è che ovviamente questa è una prima, grezza, brutale valutazione dei pezzi, la quale andrà raffinata con moltissimi dettagli aggiuntivi. Lo vedremo nei prossimi articoli.
[title]Il Turco[/title]
Per poter capire appieno il funzionamento di un giocatore artificiale moderno, è necessario capire come si sono evolute nel tempo le tecnologie. Accendiamo dunque il flusso canalizzatore e viaggiamo indietro nel tempo fino al 1769, anno in cui un ingegnoso nobile ungherese di Presburg, Wolfgang von Kempelen, costruì una macchina in grado di giocare a scacchi per Maria Teresa d’Austria. Come già accennato [url=https://leganerd.com/2010/11/14/il-turco/]questo articolo[/url], esso raffigurava un uomo avvolto in abiti orientali, seduto dietro una specie di scrivania chiusa sul davanti da tre sportelli, con due cassetti in fondo; in realtà l’automa era una truffa molto ben congegnata: era azionato nell’interno da un uomo di piccola statura, che manovrava il braccio mobile del Turco.
I veri studi in materia dovranno invece aspettare la metà dell’Ottocento per vedere la luce e il Novecento per avere un sostanziale sviluppo.
[title]Analytical Engine[/title]
Saltiamo avanti con la nostra macchina del tempo fino ai primi anni dell’800. La storia dei giocatori artificiali e dei loro inventori inizia proprio in questo periodo con gli studi del matematico inglese [url=http://it.wikipedia.org/wiki/Charles_Babbage]Charles Babbage[/url], da molti considerato il primo informatico della storia.
Dopo aver progettato (sebbene mai costruito) la cosiddetta Macchina Analitica, cominciò a pensare ad alcune applicazioni risolvibili dalla sua macchina. Le sue attenzioni si concentrarono subito sulle strategie dei giochi. In un articolo scritto nel 1864 Babbage sosteneva che qualsiasi gioco di scacchiera può essere affrontato con successo da un automa.
[quote]Dopo molti studi, ho scelto l’esperimento di costruire una macchina che dovrebbe poter giocare con successo una partita di un gioco di abilità puramente intellettuale, come ad esempio il filetto, la dama, o gli scacchi… L’automa “esamina” una posizione, e poi comincia a porsi una serie di domande:
1. L’ultima mossa fatta dal mio avversario è legale? Se no, protesto.
2. Ho una posizione indifendibile (ovvero, il matto è inevitabile)? Se sì, abbandono.
3. Tra quelle possibili, c’è una mossa che mi dà la vittoria (cioè posso dare scacco matto)? Se sì, la dichiaro.
4. L’avversario sta per fare una mossa vincente? Se sì, la prevengo.
5. Se alla prossima mossa non c’è una mossa vincente per uno di noi due, debbo cercare una mossa che crea una doppia minaccia, in modo che il mio avversario ne possa parare una sola; se c’è, la effettuo.
6. Se i primi 5 test falliscono, esamino le mosse successive e in qualche modo ne scelgo una; la effettuo senz’altro.
[/quote]
Questo primordiale algoritmo è un primo passo verso la determinazione dei ragionamenti che portano alla costruzione del primo giocatore artificiale di scacchi. Certamente le regole inventate da Babbage sono tutt’altro che ben definite: la regola numero 6, ad esempio, si conclude con un poco chiaro “e in qualche modo ne scelgo una”.
Con questo siamo arrivata alla conclusione della prima parte della storia, il word count dell’articolo è schizzato a più di 2000 parole e direi che è ora di darci un taglio. Nei prossimo articolo vedremo come è ulteriormente evoluta la tecnologia dei giocatori artificiali, dagli studi di Shannon e prima partita giocata da Alan Turing, fino ai successi odierni di Deep Blue prima e Fritz poi.
Stay tuned!
[rubrica][url=leganerd.com/tag/hmpc][How machines play chess][/url] è una rubrica tenuta da @ryanvespucci sul funzionamento dei giocatori artificiali di scacchi.[/rubrica]
