mercoledì 24 febbraio 2016

Scacchi e astronomia

Secondo un’antica leggenda, l’inventore degli scacchi si presentò un giorno al palazzo reale, e chiese di poter presentare il gioco al sovrano. Il re lo ricevette e rimase tanto affascinato che si dichiarò pronto a offrire qualsiasi ricompensa al suo ospite. Questi disse però che si sarebbe accontentato di un chicco di grano per la prima casella della scacchiera, di due chicchi per la seconda, di quattro per la terza, e così via. Il sovrano si meravigliò di tanta modestia, e gli ricordò che poteva avere molto di più: una provincia del regno, un castello, una rendita a vita per lui e isuoi discendenti. Ma l’inventore non si mosse dal suo proposito. Il re diede ordine al tesoriere di provvedere, ma l’indomani ricevette la spiacevole notizia: non sarebbe bastato il raccolto annuale di tutto il regno, e nemmeno i raccolti di dieci anni di tutto il mondo. In effetti il geniale inventore aveva richiesto più di diciotto miliardi di miliardi di chicchi di grano: un numero decisamente astronomico.

Le connessioni tra scacchi e astronomia non si fermano certo qui. Nel trattato duecentesco noto come “Libro de los juegos” venivano descritti gli "scacchi astronomici", da giocare su una scacchiera composta di sette cerchi concentrici, uno per ogni pianeta del modello geocentrico. La struttura dell’universo tolemaico, d’altra parte, sembra essere stata determinante anche nell’origine (indiana e successivamente araba) degli scacchi classici: la scacchiera 8×8, infatti, si ricondurrebbe alle otto sfere concentriche presenti in quel sistema cosmologico.

In tempi recenti, molti astronomi, per esempio Arthur Eddington, Eugene Antoniadi e Fred Hoyle, sono stati anche ottimi giocatori di scacchi. Ma alfieri e cavalli si muovono anche nello spazio: nel giugno 1970, i cosmonauti Vitaly Sevastyanov e Andrian Nikolayev giocarono una partita contro la sala controllo mentre erano a bordo della Soyuz 9. Sette anni dopo, Sevastyanov divenne presidente della federazione di scacchi dell’URSS. Nel 1999 Sergei Andeyev si portò sulla stazione spaziale
Mir un notebook con un programma di scacchi, per non rinunciare al suo passatempo preferito durante la lunga permanenza nello spazio. L’astronauta americano Gregory Chamitoff giocò a scacchi contro la stazione di controllo mentre si trovava sullo Space Shuttle e quando era a bordo della ISS: una delle sue partite Spazio-Terra, nel maggio 2011, venne ufficialmente sponsorizzata dalla NASA e resa pubblica attraverso i social network.

Anche la fantascienza ha messo in scena partite di scacchi, giocate su astronavi o su pianeti immaginari. Memorabile, a questo proposito, la sonora sconfitta che nel film “2001: Odissea nello spazio” il supercomputer HAL 9000 infligge all’astronauta Frank Poole. Nell’universo di Dune esiste una complicata variante del gioco degli scacchi, denominata “Cheops”. Oltre a pezzi familiari come il re, la regina, la torre e il cavallo, ve ne sono alcuni di peculiari come il primo ministro e i ministri, il duca e la duchessa, il barone e la baronessa, l’assassino, il falco, il soldato, il pastore, la spia.
Ma soprattutto il gioco si svolge su una scacchiera dalla forma piramidale (ecco spiegato il nome). Obiettivo dei giocatori è portare la propria regina sul vertice, al nono piano della piramide, e mettere sotto scacco il re avversario.


Immaginate ora una mini-scacchiera 3×3, con due cavalli bianchi agli angoli superiori e due cavalli neri agli angoli inferiori. Esiste, secondo voi, una sequenza di mosse che porti da questa configurazione di partenza a quella indicata a destra nella figura, con i cavalli di sinistra scambiati tra di loro?

Naturalmente, i cavalli possono muoversi secondo le regole classiche degli scacchi, e una casella non può essere occupata da due pezzi. Buon divertimento!

sabato 13 febbraio 2016

La matematica del Kama Sutra

Normalmente il Kāma Sūtra, libro indiano scritto dal filosofo Vātsyāyana in sanscrito intorno al secondo secolo dopo Cristo, viene associato all'amore e in particolare alle tecniche per raggiungere il piacere sessuale.
Non tutti sanno, però, che una parte di questo testo, precisamente il capitolo 3, è dedicata alle 64 arti che una donna doveva conoscere per poter trovare marito: e tra queste sono citate il canto e l'uso di strumenti musicali, la legatura di libri, la falegnameria, la conoscenza di miniere e cave, ma anche i giochi matematici, gli scacchi e "l'arte di interpretare scritture cifrate e di scrivere parole in
modi particolari".

In altre parole, l'uso della crittografia per cifrare i messaggi segreti che devono essere scambiati tra due amanti.
L'arte di celare i messaggi è antichissima. Il cifrario di atbash, in cui la prima lettera dell'alfabeto viene sostituita con l'ultima e viceversa, la seconda con la penultima e viceversa, e così via, viene utilizzato perfino nella Bibbia, nel Libro di Geremia.
Anche Giulio Cesare occupa un posto rilevante nella storia della crittografia: il suo cifrario è un po' più sofisticato dell'atbash, perchè ogni lettera non viene sostituita da quella che si trova in posizione speculare nell'alfabeto, ma da una lettera che nell'alfabeto si trova N posizioni dopo. Il bello è che il numero N, noto a chi invia e a chi riceve il messaggio, può essere un numero qualsiasi, il che rende la decodifica del messaggio più ardua rispetto al caso dell'atbash.
Per esempio, la parola CESARE viene cifrata in FHVDUH se scegliamo N=3. Se avessimo scelto per N un valore molto grande, avremmo potuto, per alcune lettere, superare la fine dell'alfabeto: in questi casi avremmo dovuto ricominciare dall'inizio, come se la lettera A fosse immediatamente successiva alla lettera Z.

Ma anche il cifrario di Cesare è facilmente attaccabile da un malintenzionato che volesse spiare i messaggi dei due poveri amanti desiderosi di privacy: basterebbe provare tutti i numeri compresi tra 1 e il numero di lettere dell'alfabeto meno 1, e prima o poi il messaggio verrebbe decodificato.

Ecco che il Kāma Sūtra propone una tecnica ancora migliore (come racconta l'ottimo Marcus Du Sautoy nel suo celebre "L'equazione da un milione di dollari"): il trucco è non utilizzare lo stesso numero N per tutte le lettere dell'alfabeto, ma prevedere una sostituzione diversificata per ogni lettera.
Per esempio, se ogni lettera A diventa una lettera E (posta 4 lettere dopo), possiamo tranquillamente sostituire ogni lettera B con una I (situata 7 lettere dopo), e così via. In altre parole, creiamo una tabella di sostituzione del tutto arbitraria, in cui ogni lettera viene fatta corrispondere con un'altra.
Quante possibili tabelle di cifratura possiamo creare? Dal punto di vista della spia, che non conosce la chiave di cifratura, alla lettera A potrebbe corrispondere una qualsiasi delle lettere dell'alfabeto: se ci basiamo sull'alfabeto inglese, abbiamo quindi 26 possibilità. La lettera B potrebbe essere sostituita da tutte le lettere, tranne quella già impiegata per cifrare la A, quindi in tutto abbiamo 25 possibilità. E così via. Le possibili tabelle di cifratura sono allora 26 × 25 × 24 × ... × 2 × 1. Questo prodotto che coinvolge tutti i numeri interi compresi tra 1 e 26 viene chiamato fattoriale di 26, e si indica con 26! (che non viene pronunciato come una esclamazione, ma semplicemente "26 fattoriale" oppure semplicemente "fattoriale di 26").
Si tratta di un numero molto grande, pari a circa 403 milioni di miliardi di miliardi.

Di quali armi può disporre il malvagio impiccione desideroso di conoscere i messaggi scambiati tra i due amanti? Certamente non potrà esaminare tutti queste possibili chiavi di cifratura: perfino a un supercomputer non basterebbe l'età dell'universo per analizzare tutte queste tabelle e trovare quella utilizzata dagli amanti.
Come fare, allora? Conoscendo quali sono le lettere più frequenti in un tipico messaggio redatto in una certa lingua. Per esempio, lettere come la A e la E sono molto comuni in italiano, mentre la Z e la Q sono molto più rare. Analizzando il messaggio cifrato, a condizione che sia abbastanza lungo, si possono trovare quali sono le lettere che compaiono con maggior frequenza, e quali invece le lettere presenti in poche occorrenze: con ogni probabilità le prime sono la versione cifrata di lettere comuni (come la A o la E), mentre le seconde sono la trasformazione di lettere rare (come la Z o la Q).
Grazie a ragionamenti di questo tipo, la spia potrà, prima o poi, decodificare il messaggio. Evidentemente, però, non si tratta di un lavoro banale come quello necessario a chi desiderasse svelare un messaggio codificato attraverso il cifrario di atbash o quello di Cesare.
Ovviamente la crittografia ha fatto passi da gigante dopo il Kāma Sūtra: cifrari come questo fanno sorridere al giorno d'oggi, in quanto immediatamente violabili dal più scadente tra i software di crittoanalisi.
In ogni caso, se consideriamo che stiamo parlando di un testo di quasi duemila anni fa, non possiamo fare troppo gli schizzinosi. E inoltre adesso non dite più che la matematica non c'entra niente col sesso.

lunedì 8 febbraio 2016

I premi Turing: Alan Newell e Herbert Simon

Che l'intelligenza artificiale sia un campo di ricerca estremamente complesso, posto all'intersezione tra discipline tra loro molto diverse come informatica, matematica, ingegneria, psicologia e filosofia, è cosa ben nota. Non deve stupire, quindi, che tra i maggiori studiosi di questa materia vi siano stati non soltanto matematici e informatici puri, ma anche scienziati eclettici il cui background includeva ambiti apparentemente eterodossi come la psicologia.
Alan Newell e Herbert Simon sono stati un ottimo esempio di questa categoria. Nel 1975, per la prima volta dalla nascita del premio Turing, il prestigioso riconoscimento venne assegnato a due ricercatori anziché uno solo, e la scelta ricadde su questi due americani.
Newell si laureò in matematica a Stanford nel 1949, e lavorò alla RAND Corporation per progetti legati all'aeronautica militare. Pochi anni dopo cominciò ad appassionarsi ad una disciplina che stava muovendo i suoi primissimi passi: l'intelligenza artificiale. Un campo così nuovo che non aveva ancora un nome, visto che la fortunata espressione venne coniata solo al celebre seminario del Darmouth College del 1956. In quegli anni scrisse "The Chess Machine: An Example of Dealing with a Complex Task by Adaptation", uno dei primi libri della storia dell'intelligenza artificiale.
Qui entra in scena Herbert Simon, di 11 anni più vecchio di Newell. Simon si era laureato nel 1936 in scienze politiche, aveva conseguito il dottorato nella stessa materia nel 1943, e aveva iniziato una brillante carriera universitaria in diverse università, occupandosi di scienze politiche ed economia.
I suoi interessi di ricerca, tuttavia, spaziavano anche in molti altri ambiti, dalla psicologia all'informatica, dalla sociologia alla filosofia. Dopo aver letto il libro di Newell, Simon ricontattò il giovane scienziato che aveva conosciuto qualche anno prima a Pittsburgh, e i due cominciarono a collaborare conseguendo alcuni dei risultati più importanti della storia della nascente intelligenza artificiale.
Il "Logic Theorist", da loro realizzato nel 1956 con l'aiuto del programmatore J. C. Shaw, fu il primo programma "intelligente" mai scritto: si dimostrò in grado di dimostrare alcuni dei teoremi enunciati nei Principia Mathematica di Russell e Whitehead, in alcuni casi attraverso dimostrazioni originali.
Altri settori di ricerca studiati da Newell furono l'elaborazione di liste e lo sviluppo di euristiche.
Al seminario del Darmouth College, oltre a Marvin Minsky (da pochi giorni scomparso) e a John McCarthy, già premi Turing rispettivamente nel 1969 e nel 1971, c'erano anche loro, Newell e Simon.
Negli anni successivi la magnifica coppia implementò, sempre in collaborazione con Shaw, un altro programma di intelligenza artificiale, denominato "General Problem Solver": era capace di risolvere problemi di geometria e di giocare a scacchi.
Sia il "Logic Theorist" che il "General Problem Solver" erano scritti in un particolare linguaggio di programmazione ideato dagli stessi Newell e Simon: l'Information Processing Language (IPL).
Nonostante fossimo agli albori della programmazione, questo linguaggio consentiva già alcuni costrutti e meccanismi avanzati, come la gestione di liste, l'allocazione dinamica della memoria, i tipi di dati, le funzioni passate come argomenti, la ricorsione, e molti altri.
Newell continuò, negli anni successivi, a fornire importanti contributi nel campo dell'intelligenza artificiale, ma si occupò anche di psicologia e di modelli cognitivi.
Il suo amico Simon fece anche di più: scrisse di psicologia, di sociologia, di economia, di pedagogia, di scienza del management. Il tema unificante che lo affascinava era il processo cognitivo della decisione.
Il percorso straordinario di questo scienziato così poliedrico culminò nel 1978 con il premio Nobel per l'Economia, ricevuto per aver descritto il concetto di decisione organizzativa in un contesto di incertezza.
Che io sappia, si tratta ad oggi dell'unica persona ad aver vinto il premio Turing e anche il premio Nobel.