Intelligenza artificiale

Struttura del post

1. Intro
2. Come fa un computer a risolvere problemi che necessitano di intelligenza? (quindi non solo calcoli)
3. Come fa un computer a giocare a scacchi?
4. Come fa un computer a ragionare?
5. Conclusioni

Intro

L'intelligenza artificiale (di seguito anche IA) è una disciplina dell'informatica. Essa presenta diverse definizioni.
La più famosa e operativa dice che l'intelligenza artificiale è una disciplina che ha come obiettivo la costruzione di agenti razionali (vedi Russel-Norving, Intelligenza artificiale: un approccio moderno - l'approccio degli agenti razionali, appunto). Qui per agente si intende un programma per computer che fa qualcosa (agente = che agisce). Potremmo guardare agli agenti razionali come agenti che fanno la cosa giusta. La cosa giusta da fare è, il più delle volte, ovvia dal contesto: la cosa giusta da fare davanti a un edificio in fiamme è evacuarlo e spegnere l'incendio, la cosa giusta da fare davanti a una partita a scacchi è fare la miglior mossa possibile, e così via, Questo è una definizione operativa perché si occupa di cosa fanno gli agenti.
Il termine intelligenza artificiale, quindi, da questo punto di vista, non è ovvio come le cose da fare davanti a un incendio (ovvio qui non è sinonimo di facile, scusate amici pompieri): per la verità, l'intelligenza non è la proprietà di saper fare qualcosa, bensì il complesso di facoltà psichiche e mentali che consentono all’uomo di pensare, comprendere o spiegare i fatti o le azioni, elaborare modelli astratti della realtà, intendere e farsi intendere dagli altri, giudicare, e che lo rendono insieme capace di adattarsi a situazioni nuove e di modificare la situazione stessa quando questa presenta ostacoli all’adattamento; propria dell’uomo, in cui si sviluppa gradualmente a partire dall’infanzia e in cui è accompagnata dalla consapevolezza e dall’autoconsapevolezza, è riconosciuta anche, entro certi limiti (memoria associativa, capacità di reagire a stimoli interni ed esterni, di comunicare in modo anche complesso, ecc.), agli animali (e, perché no a questo punto, ai computer).
Questa definizione del vocabolario Treccani mette in luce diversi aspetti che l'agente razionale non ha, secondo le definizioni. (Nota: non voglio però tralasciare niente. Russel e Norvig parlano di apprendimento dell'agente dell'ambiente circostante: dalle percezioni che si hanno dell'ambiente, un agente razionale può capire cosa fare, imparare cosa va fatto in situazioni future simili, o capire la situazioni in cui si trova. Questo assomiglia all'intelligenza com'è presentata da Treccani: capacità di adattarsi a situazioni nuove e di modificare la situazione stessa. Lo scopo del post non è mettere in crisi l'intelligenza artificiale o insultarla a priori, ma analizzarla un po' - e, perché no, con spirito critico)
L'intelligenza, come si vede, è quell'insieme di facoltà che rende chi ne è dotato capace di elaborare e costruire modelli, spiegare cosa c'è attorno, percepire situazioni, e forse anche emozioni e sentimenti (anche se il vocabolario non lo dice).
Certo è che la nozione di agente razionale approssima molto della definizione, e magari un giorno arriveremo ad avere agenti che possono quasi fare tutto quello che fanno gli uomini.
Ma rimane Pablo Picasso che puntella: "I computer sono inutili. Sanno dare solo risposte".
D'altra parte, Douglas Richard Hofstader, filosofo e accademico, ha detto nel suo famoso Gödel, Escher, Bach - Un'eterna ghirlanda brillante (libro impegnativo; l'autore ha vinto il Pulitzer per la saggistica grazie ad esso) che "i calcolatori sono per loro intrinseca natura gli esseri più rigidi, privi di desideri e ubbidienti che ci siano (...) Sono l'essenza dell'inconsapevolezza. Come può allora essere programmato un comportamento intelligente? Non è questa la più appariscente delle contraddizioni?". Qui si apre davvero una questione interessante. L'IA è figlia di questo paradosso. Tuttavia, molti passi sono stati avanti verso l'approssimazione dell'intelligenza.
In questo articolo proverò a rispondere a tre domande, che magari stuzzicheranno il lettore.

1. Come fa un computer a risolvere problemi che necessitano di intelligenza? (quindi non solo calcoli)
2. Come fa un computer a giocare a scacchi?
3. Come fa un computer a ragionare?

Rispondiamo alle domande, con ordine, una per una. Ovviamente non è mia intenzione rispondere in maniera esaustiva e completa, ma almeno tentare di capire un po' di più di cosa si sta parlando.

Come fa un computer a risolvere problemi che necessitano di intelligenza? (quindi non solo calcoli)

Proviamo prima a formulare bene questa domanda: cosa vuol dire che un problema necessita di intelligenza? Probabilmente, che esso necessita di un po' di tempo per essere risolto. Questo è dovuto al fatto che le azioni possibili per arrivare all'obiettivo sono molteplici. Il problema può dirsi difficile nel senso computazionale del termine (vedi il post precedente dove si parla di complessità computazionale), perché il numero totale di azioni che si possono svolgere è veramente alto.
L'informatica è figlia della matematica: problema è qualcosa di cui dobbiamo parlare con precisione, ma leggendo tra le righe l'analisi informale appena fatta si intravede qualcosa che si può formalizzare.
Un problema è un insieme di quattro oggetti:

1. stato da cui parte il problema
2. azioni che si possono svolgere quando si è in uno stato
3. obiettivo da raggiungere
4. una funzione di transizione che, dato uno stato e un'azione, finisce in un nuovo stato, che è quello che risulta applicando l'azione allo stato.

Un po' di esempi (i primi due presi dal Russel-Norvig):

• nel gioco del 15, gli stati sono la posizione delle caselle, le azioni spostare le caselle, l'obiettivo mettere le caselle in fila
• nel problema di pulire una casa, lo stato è la stanza in cui sono, le azioni pulire la stanza o cambiare stanza, l'obiettivo avere tutte le stanze pulite
• nel problema di spegnere un incendio che divampa in un edificio, gli stati sono il punto che stiamo "spegnendo", le azioni erogare acqua o spostare la pompa, l'obiettivo spegnere l'incendio
• nel problema di giocare a calcio, le azioni sono molteplici (passare la palla, marcare un avversario, chiamare un compagno, dire all'allenatore che ci si è fatti male, ...), lo stato è complesso (dove sono nel campo? Sono stanco? Quanto disto dalla porta?), l'obiettivo segnare, fare un assist, vincere la partita

L'ultimo problema è definito in modo piuttosto confuso. Questo lo si deve un po' a me, ma anche perché il gioco del calcio non è facile da modellare, o, per usare una parola cara agli informatici, da astrarre (attività per cui ci vuole una certa intelligenza, appunto). Infatti, a parte il calcio per robot (si legge nel Russel-Norvig), l'IA non ha fatto molta strada nei giochi fisici. 

Ora che abbiamo definito un problema, come fa un computer a risolverlo? Una persona che non è molto ferrata, farebbe così:

1. prendo un foglio di carta, e mi scrivo lo stato da cui voglio partire (facile)
2. disegno una freccia per ogni azione che posso fare, e all'estremo di ogni freccia lo stato in cui vado (facile)
3. scelgo un altro stato tra questi e ricomincio da capo (facile!)

In una parola: facile! Questa persona, oltre a non essere molto ferrata, dovrà armarsi di pazienza e disegnare un bell'albero di stati per trovare, prima o poi, l'obiettivo. Ma le operazioni rimangono semplici da svolgere una per una.

Vi sembrerà strano forse, ma i computer non fanno altro che questo, per risolvere un problema: i passi che vengono eseguiti sono proprio quelli appena descritti.

L'unica cosa che cambia da metodo a metodo è il terzo punto: come scelgo il successivo stato da analizzare. Ecco qui che l'intelligenza dell'uomo entra in gioco.

Questo problema che stiamo risolvendo è sottoposto ad una ricerca della soluzione. Un algoritmo di ricerca prende in input un problema e da in output la sequenza di azioni necessaria per risolverlo.

Gli algoritmi di ricerca differiscono solo per il punto 3, com'è stato già detto. Di seguito una lista non esaustiva, e puramente divulgativa (Russel-Norvig va molto più a fondo): 

• L'algoritmo di ricerca per ampiezza prende ogni stato in ordine, così come lo trova, e lo analizza.
• L'algoritmo di ricerca per profondità prende lo stato più a sinistra che c'è, e va fino in fondo ad analizzare, fermandosi quando non può più fare niente. Dopodiché, torna su.
• L'algoritmo di ricerca a costo uniforme sceglie gli stati secondo il costo delle azioni (perché non tutte le azioni costano uguale: alzare un peso da 1 kg è diverso che alzarlo da 100), prendendo lo stato che costa meno raggiungere
• L'algoritmo di ricerca ID (iterative deepening, approfondimento iterativo) è un algoritmo impaziente che applica un massimo di d azioni, con d dato in input. 

Gli algoritmi di ricerca informata, oltre al problema, prendono in input una funzione che aiuta a capirci qualcosa di più (diciamo, un po' più di intelligenza): se devo risolvere il problema di andare da Torino a Milano, è ragionevole passare dalle città che si avvicinano sempre di più a Milano. Per questo, posso sfruttare, ad esempio, la distanza in linea d'aria e scegliere come città successiva a quella in cui sono la città che dista di meno in linea d'aria da Milano, oppure quella città che minimizza il percorso complessivo. La funzione che da più intelligenza all'algoritmo è detta euristica.

• L'algoritmo di ricerca ingordo analizza lo stato che ha minor valore euristico, ossia lo stato avente il minimo valore che la funzione assegna allo stato.
• L'algoritmo di ricerca A* analizza lo stato che ha il minimo valore risultante dalla somma dei costi delle azioni che hanno portato ad esso (presi uno per uno) più il valore euristico dello stato immediatamente successivo (vi gira la testa? Ci viene incontro la matematica: se mi trovo in uno stato s e ho n stati dopo s, cioè applicando ogni azione che posso, e per arrivare a s ci ho impiegato m, allora scelgo di analizzare lo stato s' avente minima somma m + h(s), dove h(s) è il valore euristico di s). A* poi aggiorna i valori degli stati che ha già incontrato, se per caso ha scoperto a questo punto di arrivare ad uno stato già "visitato" in meno tempo. 
• L'algoritmo di ricerca best-first ricorsivo (che nome! Meglio RBFS) è un algoritmo che agisce più o meno come quello in profondità, ma tiene traccia di un cammino alternativo da prendere al bisogno, sempre aiutandosi con l'euristica.

Questi algoritmi differiscono per la velocità con cui arrivano all'obiettivo. Sono praticamente dati in ordine dal più lento al più veloce. Attenzione però: La complessità temporale di questi algoritmi di ricerca è praticamente sempre esponenziale, quindi dal punto di vista teorico del numero di operazioni sono tutti uguali! C'è da dire poi che la velocità dipende spesso dal problema. I problemi NP-completi, come quelli che ho analizzato nel post precedente, saranno sempre difficili da risolvere, anche trovando una tecnica perfetta che prende ispirazione da queste appena descritte. 

Come fa un computer a giocare a scacchi?

Era il 10 febbraio del 1996. Io avevo due anni.
A Filadelfia si disputa la prima partita di scacchi del mondo in cui è un computer a vincere.
Garri Kasparov, all'epoca il più forte giocatore del mondo, abbandona la partita dopo circa 40 mosse. La situazione in cui si trova la partita è la seguente

Non sono un grande intenditore di scacchi, ma se il campione del mondo ha abbandonato in questa situazione, un motivo ci dovrà pur essere.
Il motivo si chiama Deep Blue, ed è stato un computer progettato appositamente per giocare a scacchi. Costruito da IBM, fu oggetto anche di numerose critiche, alcune delle quali fondate, riguardo ad una manovra dell'azienda per risollevarsi, e riguardo a sospetti che fecero pensare a Kasparov che dietro quel computer ci fosse una persona.
Kasparov spesso dichiarò di vedere nelle mosse del computer intelligenza e creatività così profonde da non riuscire a comprenderle (vedi Wikipedia qui): una bella pubblicità per l'IA.
Come funzionava Deep Blue? Come ha fatto a battere in una partita il campione del mondo di scacchi in carica? Come sempre, bisogna mettere i puntini sulle i.
Deep Blue è sì un computer, ma il suo funzionamento è dato semplicemente da un programma. E' più giusto dire, quindi, che è il programma Deep Blue ad aver battuto Kasparov. Certo, l'hardware del computer (la CPU, la RAM, le risorse fisiche in pratica...) ha ovviamente giocato un ruolo importante (abbiamo già detto che la maggior parte dei problemi di ricerca hanno complessità esponenziale, e quindi avere delle buone risorse hardware spesso è determinante).
Come funziona quindi questo programma? Non è troppo diverso dagli algoritmi di ricerca della domanda precedente. C'è però una differenza fondamentale tra cercare una soluzione a un problema in cui siamo soli soletti, e risolvere un problema in cui sai che davanti a te c'è un'altra entità (una persona in questo caso, ma anche un altro agente razionale, oppure una scimmia che ribalta la scacchiera) che tenta di metterti i bastoni tra le ruote. L'algoritmo che è alla base dei programmi che giocano a scacchi, ma in generale dei programmi che sanno giocare*, ha un nome ben preciso.
Prima di svelarlo, proviamo a pensare alla solita persona non troppo ferrata (ma molto tempo e molta pazienza a disposizione) che tenta di giocare a un gioco più semplice, come il gioco del tris. Una persona del genere potrebbe

1. elencare tutte le situazioni in cui il gioco è finito, e segnare ogni situazione con tre numeri: +1 se è lei a vincere, 0 se è pareggio, -1 se ha perso. Questa operazione è possibile, perché la persona sa se è una X o un O e può arrivare in questo modo a determinare i numerini. 
2. andare all'indietro, cioè eliminare una casella, e fare finta nella situazione in cui ci si ritrov ora (quella dove la casella manca), tocchi all'avversario.

Dobbiamo già fermarci, perché questo discorso non è molto semplice.

Ricapitolando un attimo, stiamo elencando tutte le situazioni in cui il gioco è finito, che chiamiamo terminali, e stiamo segnando con numerini (ma potremmo farlo anche con disegnini) lo stato del gioco: ho vinto, ho perso oppure ho pareggiato? Questo valore si chiama utilità.

Ora, si fa l'assunzione che in quella situazione il gioco sia finito dopo che l'avversario (chiamiamolo tizio) ha effettuato l'ultima mossa. Eliminando quindi una casella, ci si ritrova alla situazione in cui era il turno di tizio.

Ora, con un po' di intelligenza si può fare un'assunzione. Che mossa farebbe tizio per vincere, o almeno per mettermi in difficoltà il più possibile? Anche questa risposta è semplice: sceglie la mossa che porta a una situazione avente minima utilità tra tutte le situazioni sottostanti, ovvero la mossa che porta allo stato con il numerino più piccolo! Fatto questo, segna questo numerino vicino alla sua tabella.
Ora che abbiamo "predetto" cosa farà tizio, si torna indietro come al punto 2. E quindi tocca a me!
Cosa sceglierò io per vincere? (almeno che io non voglia perdere, ma allora che sto giocando a fare?)

Sceglierò il valore più grande sottostante, così da minimizzare la perdita a cui tizio vuole inevitabilmente portarmi! In pratica, stiamo minimizzando la massima perdita (che voli pindarici!!).
Alla fine di questo algoritmo avremo un albero di gioco. Il primo stato in alto dell'albero sarà la situazione di partenza, ed ecco che abbiamo un albero che ci dice cosa fare in ogni situazione del tris, supponendo che il mio avversario sia il più forte possibile, ovvero che scelga ogni mossa minimizzando il mio punteggio finale.
Se si nota che io sceglierò sempre il massimo dei valori sottostanti nell'albero di gioco, e che il mio avversario sceglierà sempre il minimo, ecco che possiamo chiamare me stesso max  e il mio avversario min. Abbiamo un algoritmo che possiamo chiamare minmax, ma, non si sa bene il perché, si chiama minimax (forse è più simpatico, non saprei).
minmax dunque è un algoritmo che suggerisce al programma che decisione prendere in ogni stato del gioco. Se togliamo la griglia del tris e mettiamo una scacchiera coi pezzi sopra, una volta che abbiamo detto al gioco quali sono le regole degli scacchi, egli può giocare benissimo. Da una scacchiera, può creare tutte le situazioni possibili, ovvero tutte le mosse possibli a scacchi. Ogni cammino in tale albero forma una partita. Quindi il gioco degli scacchi è completamente descritto dal suo albero delle mosse. Sapete quante sono?  10¹²³. Sono tantine: è un 1 seguito da 123 zeri.
Ovviamente, Deep Blue non ha giocato in questo modo, altrimenti sarebbe ancora qui a pensare alla prima mossa da fare contro Kasparov, che avrebbe vinto per timeout. Il ragionamento di fondo, però, è questo.
Per la verità, Deep Blue non arrivava per forza a costruire tutto l'albero delle mosse possibili da uno stato, ma con una tecnica chiamata potatura sceglieva la migliore mossa da fare, aiutandosi con funzioni di valutazione che gli comunicavano il vantaggio di portarsi in una situazione piuttosto che in un altra. Russel-Norvig mostra bene l'algoritmo minimax e anche la variante con potatura, e dedica a Deep Blue qualche parola.
Date queste considerazioni tecniche, si potrebbe dire che un computer sta giocando davvero? Io, personalmente, non credo. Il computer non sta giocando, ma sta prendendo decisioni in relazione al gioco, massimizzando il valore delle perdite che un ipotetico avversario invincibile fa. Ovviamente l'IA ha portato a modificare minimax per portare a varianti umane, che tengono conto della distrazione, degli errori, e di altri fattori, per così dire, umani. Ma è meglio giocare con una persona in carne e ossa. Almeno ci puoi parlare.
Ecco cosa ha detto un filosofo di nome John Rawls riguardo alle decisioni minimax (le decisioni prese dall'algoritmo). Quelle di seguito sono testuali parole di Wikipedia che puoi trovare qui.
"Se si pone un individuo dietro un "velo di ignoranza" (la cosiddetta posizione originale) sulla propria situazione esistenziale, egli formulerà il concetto di società giusta usando il principio del minimax. Secondo questo principio, gli individui dovrebbero scegliere il tipo di società che offre "il miglior caso peggiore", cioè in cui gli individui più sfortunati siano nella condizione meno disperata."

* i giochi che abbiamo considerato sono i cosiddetti giochi a somma zero a informazione perfetta, ovvero giochi in cui la somma delle utilità degli stati terminali è sempre costante, e in cui tutti sanno in che stato è il gioco (non vi sono carte coperte, ad esempio). In pratica sono giochi in cui alla fine si ha un vincitore, e l'altro giocatore deve necessariamente perdere. E' inoltre previsto il pareggio.
Non abbiamo trattato giochi in cui entra in gioco (scusate il GIOCO di parole) la probabilità (tirare i dadi, distribuire le carte), e a più di due giocatori.

Come fa un computer a ragionare?

Ragionare è, sempre secondo Treccani, Condurre un discorso secondo la logica, oppure argomentare, trattare e discutere di un soggetto in modo razionale. Questa bella definizione già include il metodo che viene utilizzato per far "ragionare" i computer: la logica.
Aristotele, filosofo greco, formalizzò il ragionamento tramite la tecnica del sillogismo. Famoso esempio è

A) Tutti gli uomini sono mortali
B) Socrate è un uomo
C) Socrate è mortale

A e B in questo contesto si dicono premesse e C la conclusione del sillogismo.
Il sillogismo è una forma di ragionamento molto semplice, si potrebbe dire primitiva, che pone le basi della logica classica, e arriva a formare l'informatica agli inizi del '900. La logica è molto importante per la disciplina che stiamo trattando.
Possiamo affermare che il sillogismo è valido, poiché la verità della conclusione segue dalla verità delle premesse. Questa forma di discorso quasi banale è la base dei ragionamenti per computer.
Per arrivare a una conclusione i computer utilizzano principalmente tre sistemi formali, ovvero tre strategie per derivare conclusioni dalle premesse.
Innanzitutto, chiamiamo con lettere quelle proposizioni di cui trattiamo (A, B, e C, sopra, stanno per le tre frasi del discorso, che chiameremo appunto proposizioni).
La logica proposizione è quella branca della logica che tratta oggetti costituiti da lettere che possono essere vere o false. Qui non trattiamo discorsi più complicati come

Per ogni uomo esiste un lavoro che l'aspetta

Che parla di ogni uomo, e di un lavoro che esiste per esso. Anche se non cambia poi molto*, è comunque meglio partire da semplici lettere come A, B, C, ...

Torniamo dunque ai tre sistemi formali, che sono nell'ordine

1) la risoluzione;

2) il concatenamento in avanti;

3) il concatenamento all'indietro.

La risoluzione parte da un semplice ragionamento come

Piove e non piove

Il quale significa affermare praticamente nulla: non può esistere infatti una tale situazione, ovvero piovere e non piovere contemporaneamente. Questa è la più netta e più semplice contraddizione che esiste.

Così se affermo, delirando

Oggi sono felice, piove, non piove e potrei andare al parco

Posso dire la stessa cosa affermando

Oggi sono felice e potrei andare al parco

Perché in mezzo al mio discorso ho posto due affermazioni contraddittorie (piove e non piove), che possono essere eliminate (o, meglio, risolte) poiché, come affermato prima, non significano nulla.

Il ragionamento per risoluzione funziona proprio in questo modo: risolvo, ovvero elimino, le lettere che si contraddicono, per arrivare piano piano ad una conclusione.

Così posso far arrivare a una conclusione un computer, semplicemente dicendo

Se piove non vado al parco
Non piove

Si lascia al lettore il piacere di arrivare alla facile conclusione.

Un momento, però: abbiamo parlato di affermazioni di lettere del tipo A e B e C, ... e non del tipo Se A allora B. Poco importa: ogni affermazione, anche complessa come se A allora B, può essere espressa come un elenco di lettere legate da un e. Si veda Russel-Norvig per i dettagli (che qui non sono importanti).

* La logica che tratta oggetti del tipo Per ogni uomo esiste un lavoro che l'aspetta si chiama logica del prim'ordine e tratta variabili che rappresentano qualunque oggetto (in questo caso l'uomo) o il particolare oggetto (il lavoro che aspetta l'uomo) di cui si sta parlando, oltre a facili lettere che rappresentano frasi. Si introducono poi altre lettere per spiegare che questi oggetto hanno proprietà, e funzioni che preso un oggetto ne restituiscono un altro. La cosa interessante è che i computer trattano queste frasi complicate, con particolari "trucchetti", quasi allo stesso modo delle facili affermazioni del tipo A e B e C

Un altro tipo di ragionamento che utilizza il computer è quello che chiameremo concatenamento, in avanti o all'indietro. Qui i discorsi che vengono fuori sono praticamente sillogismi.

Innanzitutto, il computer qui si aspetta solo frasi che sono lettere, oppure sono del tipo

Se A, B, C, ... allora O

A,B,C,... si chiamano premesse, O l'obiettivo. Ora, il ragionamento per arrivare a O può prendere solo una strada: se riesco a dire al computer A, B, C, ... allora esso può affermare O. Non vi possono essere altre strade a questo punto.

Come fa il computer ad arrivare alle premesse?
Per far ragionare un computer bisogna partire da fatti che esso sa già, e che utilizza per derivare i facili sillogismi. Questi fatti possono essere contenuti in una base di conoscenza, una specie di cervello che l'uomo da in dotazione al computer. Quando poi esso risolve il primo sillogismo, mette la conclusione (l'obiettivo) nella base di conoscenza, e ricomincia da capo.

Russel-Norvig è pieno di esempi di ragionamenti, anche abbastanza complessi, che il computer riesce a fare grazie a queste strategie.

Il concatenamento presentato ora (chiamato così perché concatena, ovvero mette insieme, le premesse per arrivare all'obiettivo) è chiamato in avanti perché parte dalle premesse e arriva alla conclusione. Il concatenamento all'indietro fa esattamente la cosa opposta: parte dalla conclusione, e cerca di derivare le premesse, per poter dire finalmente di aver ragionato bene.

Conclusioni

Ecco che abbiamo "risposto" alle nostre domande. In verità, abbiamo solo abbozzato le risposte.

Ho cercato di presentare questi argomenti in maniera semplice, quasi banale, tralasciando il più possibile ogni dettaglio matematico, salvo quando utile o divertente.

L'intelligenza artificiale è una materia che è stata molto venduta come l'abilità che un computer possiede nel fare cose che possono fare gli uomini. Lo stesso termine suggerisce un intelligenza che è stata inventata. Ognuno può tirare le conclusioni che vuole, e io vorrei tirare le mie: l'intelligenza non si inventa, semmai si proietta su di un sistema per farlo lavorare. 

Trovo un contrasto netto tra questa materia e molte altre branche, per così dire più umili, dell'informatica. La calcolabilità e la complessità, ad esempio, mettono l'accento sul limite chiamato computer: non potremo mai calcolare tutto. Si potrebbero sprecare fiumi d'inchiostro, ma basti fare un esempio famoso, che è quello delle Torre di Hanoi, un gioco che v'invito a cercare su Google per non annoiarvi troppo: non potrà mai esistere qualcuno (e mai vuol dire proprio mai) che risolverà il gioco per 64 dischi, perché questo vuol dire, anche con un computer potentissimo, attendere svariati miliardi di anni. 

Attenzione: limite non vuol dire pessimismo, bensì un discorso ben preciso sul fatto che il computer non può salvare il mondo: fa quel che può.

Certo: l'IA aiuta l'uomo in ogni fronte, da quello medico a quello logistico. L'IA, e non credo di sbagliarmi, ha anche salvato delle vite, contribuito alla costruzione di protesi, aiutato persone a trasportare milioni di oggetti in giro per il mondo. Questo è bello: questo è ciò che i computer possono aiutare a fare.

Però, a questo punto si potrebbe puntellare come Picasso, contestualizzando un po': un computer non potrà mai ragionare da solo, ma far risparmiare tempo all'uomo nel farlo lui, così come ha fatto risparmiare tempo nei calcoli che oggi i computer fanno, e che aiutano lo stesso uomo a vivere meglio. 

Inoltre, un computer non sta giocando a scacchi, ma sta provando a farlo, con grandi risultati per carità, ma senza pensare: la maggior parte dei motori scacchistici ha aperture (fasi iniziali del gioco) prese da altri campioni di scacchi, ha valutazioni matematiche che a un uomo non potranno mai venire in mente. Il computer non gioca, è solo un pozzo di memoria che fa ricerche cieche (sì, va bene la ricerca informata, ma si sta solo risparmiando tempo) su quali mosse fare!

Il computer, inoltre, non risolve problemi in fondo, cercando le soluzioni: tutto ciò che fa si riduce a calcoli, miliardi di calcoli (non possiamo immaginare quanti ne faccia) che si ritrovano in una CPU, in un codice difficile da decifrare per l'uomo, e che tornano a essere numeri, solo numeri, che decifrati danno una risposta.

Non me ne voglia chi sogna un futuro con robot e case intelligenti: l'intelligenza è solo dell'uomo. Facciamone buon uso.

Pokémon, calcolabilità e complessità

Delle tre parole del titolo di questo post, probabilmente vi è nota solo la prima. I Pokémon sono un gruppo di mostriciattoli nati sul Gameboy. E' un marchio sorprendentemente prolifico (ha venduto più di 275 milioni di unità, lo batte solo Super Mario), che ha dato vita a cartoni, giocattoli, magliette, e ben venti lungometraggi.

Pokémon, sebbene abbia dato origine a tutte queste entità, rimane un videogioco, ovvero un programma per computer, ovvero, a dirla tutta, una funzione matematica. 
Tutti hanno bene in testa (davvero?) il concetto matematico di funzione, ovvero un sottoinsieme di tutte le coppie ordinate tra due insiemi A e B, tale che ogni elemento di A appare in una coppia una e una sola volta. Più facile pensare a una funzione come a una macchinetta che prende elementi dell'insieme A e associa un solo elemento di B, che poi può essere lo stesso elemento che la funzione associa ad un altro (se questo non avviene, la funzione è iniettiva; se poi ottieniamo tutti gli elementi di B associando ogni elemento di A, la funzione è suriettiva. Ma qui stiamo divagando.)
I programmi sono funzioni in quanto prendono in input elementi di un insieme, che possono essere i tasti del joystick, numeri naturali, immagini, frasi, e chi più ne ha più ne metta. Se si pensa che i programmi che usiamo tutti i giorni o che abbiamo utilizzato (Facebook, Google, Pokémon, ... sono tutti programmi) sono funzioni matematiche, ecco che ci viene in mente almeno un motivo (ma potremmo trovarne tanti) per cui la matematica è studiata a scuola, o almeno un motivo per cui la matematica è davvero utile.
Non tutte però le funzioni che posso scrivere sono in verità programmi. Guardiamo tre esempi di funzione:

f(x) = x
f(x) = pigreco
f(x,y) = 1 se la funzione x termina su input y, 0 altrimenti

La prima funzione è la più semplice che esiste: è la funzione identità. Essa prende in input un elemento, e, semplicemente, non fa nulla: lo restituisce così com'è.

La seconda è altrettanto semplice: restituisce pigreco, un numero irrazionale, ottenibile dividendo una qualsiasi circonferenza per il suo diametro. 

La terza prende in input due elementi, e risponde a una domanda: la funzione x (dunque x non è un numero, è una funzione!) termina su input y? Ovvero, se ho un programma x e do ad esso in pasto il dato (ora sì: è un numero) y, questo programma crasha, si pianta, o succede qualcosa? Detta in questi termini, forse la terza è la funzione più interessante di tutte.

Questi argomenti a cui ci stiamo avvicinando pian piano fanno parte di una branca dell'informatica teorica, e della matematica, denominata calcolabilità. Questa branca tenta di rispondere a una domanda: "Cosa precisamente posso calcolare con un computer?". Non parliamo del computer più potente del mondo, né dei computer che appariranno tra qualche secolo, né in verità di un computer particolare. Parliamo di ogni computer: anche quello con cui state leggendo queste righe (che sia uno smartphone, un tablet, una tv, una lavastoviglie... qualsiasi cosa abbia CPU, RAM e forse un po' di memoria secondaria, ovvero un hard disk, è un computer. Se poi avete una lavastoviglie per leggere un post su un blog, fatemi sapere il modello che mi piacerebbe valutare l'acquisto).
Quindi la calcolabilità, presa una funzione, può rispondere a una domanda: è calcolabile? Ovvero, posso scrivere un programma che calcola questa funzione?
Cosa vuol dire questo? Semplicemente, un programma che per ogni input della funzione, restituisce esattamente ciò che la funzione matematicamente calcola. Facciamo un esempio (chi ha capito può saltarlo): la funzione identità restituisce 1 se l'input è 1, 2 se l'input è 2, 3 se l'input è 3, ecc. se il mio programma per ogni input su cui è definita la funzione (ovvero i numeri naturali) risponde quello che deve rispondere, ovvero quello stesso numero dato in input, questa funzione calcola esattamente l'identità. (Forse a qualcuno sarà sorto un dubbio: ma se i numeri sono infiniti... come faccio a provare che il mio programma calcola l'identità? Per ora, auguri.)
Ora posso porvi una domanda che ho in testa da un po': quale delle tre funzioni date prima sono programmi? Ovvero, possono essere calcolate? Ovvero, ed ora in poi userò questo termine, sonocalcolabili? Si accettano scommesse.
Al di là dei dettagli tecnici, come: quale linguaggio di programmazione uso per mostrare che l'identità è calcolabile? Come faccio a mostrarlo? Mando al foto del monitor a qualcuno? Ma i numeri sono infiniti...
Al di là di tutti questi dettagli, una persona ci viene incontro, e il suo nome è Alan Turing.

Alan Turing è stato uno scienziato geniale, vissuto durante la prima metà del XX secolo, che diede contributi enormi all'informatica, ancora prima che il computer fosse inventato. Anzi, si dice che i computer veri, quelli che gli ingegneri e altri matematici come Von Neumann costruirono (cerca ENIAC su Google), a Turing stavano un po' antipatici. Alan Turing era un duro e puro, e arrivò a parlare di calcolabilità prima che la gente scoprisse cosa volesse dire calcolare automaticamente. Turing è famoso per aver decrittato, assieme a un equipe di matematici, il codice Enigma che i nazisti utilizzavano per le loro comunicazioni durante la seconda guerra mondiale, facendosi aiutare da una macchina denominata Colossus, che costruì per l'occasione (vedi il film The Imitation Game che dà una versione un po' romanzata della storia - basti pensare che la macchina nel film si chiama Christopher...).

Tornando al problema delle funzioni calcolabili, Turing arrivò a pensare a macchine che calcolano in risposta a un problema che David Hilbert, un altro matematico, formulò durante la prima metà del XX secolo per discutere i fondamenti della matematica (che in quegli anni attraversò una profonda crisi - vedi il libro interessante Il calcolatore universale di Martin Davis che ne parla ampiamente): è possibile scrivere un algoritmo che data una formula logica dica se essa è vera? Questo problema è chiamato in tedesco entscheidungsproblem, ovvero problema di decisione. Turing inventò per l'occasione una macchina per mostrare che tale algoritmo non poteva essere scritto.
Per algoritmo qui si intende una procedura eseguibile del tutto meccanicamente, poiché non esistendo i computer è difficile pensare che Hilbert avesse pensato a un programma per computer che eseguito rispondesse sì se la formula fosse stata vera e no altrimenti. Ma gli algoritmi furono inventati molto prima dei computer: uno dei più antichi fu quello di Euclide per calcolare il massimo comune divisore (stiamo parlando del 300 a.C.!).
Turing inventò dunque una macchina, che oggi porta il suo nome, che sorprendentemente fa tutto quello che un computer può fare: essa è la Macchina di Turing (di seguito anche MdT), ed è veramente molto semplice. Contiene:

·         un nastro infinito a quadretti su cui si può leggere e scrivere un quadretto alla volta; 

·         una testina che può leggere e scrivere sul quadretto;

·         un piccolo display su cui è scritto in che stato è la macchina;

·         un piccolo cervello che capisce cosa c'è scritto sul quadretto letto, e può scrivere un nuovo simbolo e cambiare eventualmente stato sul display

Una tesi chiamata di Church-Turing dice che una funzione è calcolabile solo se è calcolabile tramite una MdT. Questo è veramente sorprendente.

In pratica stiamo dicendo che un qualsiasi programma per computer (sì: Google, Facebook,Pokémon...) può essere scritto per la macchina di Turing, ovvero potrei controllare i post su Facebook, cercare su Google e giocare a Pokémon anche con una MdT!

La MdT è così importante che oggi per provare diverse questioni nell'informatica teorica si fa ancora ricorso ad essa. Grazie alla tesi di Church-Turing, comunque, per mostrare che una funzione è calcolabile basta esibire un algoritmo che la calcola, scritta in un linguaggio più o meno umano. 

Così, posso mostrare un algoritmo per calcolare l'identità (return è usato per esprimere restituisci, ovvero esibisci in output):

id(x): return x

o che calcoli pigreco

pi(x): return pigreco

Certo è che pigreco è un numero irrazionale. Questo è un problema: il numero di cifre dopo la virgola è infinito, e qualsiasi computer non ha abbastanza spazio per contenerlo tutto. E' il solito problema dei numeri infiniti. 

Tuttavia, quel pigreco è un'approssimazione abbastanza adeguata del numero: a nessuno servirà mai avere tutte le cifre di pigreco in mano. Quindi la funzione pi è sì calcolabile, ma sempre tenendo conto che non avrò mai una risposta completa dalla funzione, bensì una risposta di cui mi devo accontentare.

Turing grazie alla MdT mostrò che la terza funzione di cui abbiamo parlato, quella che restituisce1 se la funzione x termina su input y, non è calcolabile. Infatti, se si potesse scrivere una funzione del genere, si andrebbe facilmente in contraddizione. Chi è interessato può vedere il libro Teoria della calcolabilità e complessità di Toffaroli et al. edito da McGraw-Hill.

Le MdT dunque offrono un modello di calcolo universalmente riconosciuto: i computer di oggi ne sono addirittura un approssimazione (infatti nessun computer può avere memoria infinita come la MdT). Vi sono altri modelli di calcolo, come il lambda-calcolo di Church (che dà il nome alla tesi vista prima) e le funzioni ricorsive di Kleene. Ma vi possono essere altri modelli di calcolo, o per così dire sistemi di calcolo.
Un modello di calcolo si dice turing-completo se fa tutto quello che la MdT può fare. Un sistema di calcolo può essere dato anche da un linguaggio di programmazione, che permette una certa espressività nel definire funzioni. Per esempio, un linguaggio che abbia il costrutto while è turing-completo, mentre non lo è uno che fornisca solo il for (come scrivo un ciclo infinito?). Cerca le definizioni su Google se sei interessato.

Una domanda a cui non risponde la calcolabilità è: "Quanto tempo impiego a calcolare una funzione?". Ovvero, quanto è complessa la mia funzione? A questo ci pensa la teoria dellacomplessità, la quale si occupa di analizzare le funzioni calcolabili dal punto di vista dell'utilizzo delle risorse (tempo, spazio e ultimamente anche energia).

Il tempo di esecuzione di una macchina dipenda da quante cose fa la macchina mentre calcola. Ad esempio, per calcolare l'identità la MdT praticamente non fa nulla. Sta nel suo stato, e basta. Quindi si può dire che la MdT calcola il suo output in un tempo costante, ovvero che non dipende dall'input.

Per la funzione pi la situazione è la stessa: infatti anche se devo scrivere pigreco, questo tempo non dipende dall'input, bensì da quante cifre di pigreco voglio scrivere. Il numero di operazioni è sempre costante, e dipende da tale numero.

Introduciamo una funzione un po' più complicata ma abbastanza celebre:

max(x,y) = il massimo tra x e y

per calcolare questa funzione (che è ovviamente calcolabile) devo fare un numero di passi che dipende dal massimo dei due numeri dati in input. Infatti una MdT dovrebbe verificare quale dei due è più grande, e quindi esaminarli entrambi! Si dice che una funzione del genere è lineare nei suoi input. infatti deve fare un numero di passi che dipende linearmente da essi.

Dipende linearmente vuol dire che la funzione che descrive quanti passi deve fare la MdT calcolando max non ha esponenti, ovvero è un polinomio in un numero n, che rappresenta lalunghezza (non il valore!!) dei numeri dati in input. 

Si possono avere polinomi più complicati? Certo che sì: possiamo avere polinomi con esponente 2, 3, 4, ... , e in generale qualsiasi esponente che sia un numero naturale.

Ad esempio, un algoritmo quadratico (ovvero la cui complessità è rappresentata da un polinomio di grado 2) anch'esso abbastanza celebre è l'ordinamento per inserimento, che ordina gli elementi di una lista di oggetti in un modo particolare (vedi insertion sort su Wikipedia).

La complessità divide i problemi che possono essere calcolati facilmente da un computer da altri che invece non possono esserlo (per ora...): la classe P è la classe dei problemi che possono essere risolti da una MdT in un tempo al più polinomiale.

Una tesi, questa volta di due signori che sono Cook e Karp (i padri di questa materia, praticamente hanno fatto tutto loro), dice che un computer può calcolare una funzione in maniera efficiente se essa appartiene a P, ovvero se essa ammette algoritmo di calcolo polinomiale. In P ci sono i problemi visti fin qui: l'identità, pigreco, max, insertion sort, ma anche Google e Facebook (certo che è da dimostrare ma intuitivamente questi ultimi due servizi sono molto "facili" da fruire, e forse il loro successo lo si deve anche a questo).
Una domanda che si può fare è: Pokémon appartiene a P? Ognuno può provare a rispondere, per ora.

Se ci sono problemi per così dire trattabili, ovvero che un computer può risolvere senza troppi problemi, ve ne sono anche di intrattabili, ovvero quelli che ammettono algoritmo di calcolo che non è polinomiale, ma almeno esponenziale. 

Esiste un'altra classe di problemi interessante, che è la classe NP, ovvero la classe dei problemi che ammettono una verifica polinomiale. Questo vuol dire che ci metto tanto a risolvere il problema, ma una volta risolto verificare che la soluzione è quella giusta è questione di un attimo!

La classe NP contiene i più celebri rompicapo: il Sudoku, alcuni problemi di enigmistica, ma anche la battaglia navale e Candy Crush.

Uno dei più importanti problemi aperti (= a cui nessuno ha dato ancora una risposta) dell'informatica è determinare se la classe P sia uguale o meno alla classe NP. Su due piedi uno direbbe di no.

Tuttavia, il problema che consiste nel chiedersi se un numero dato in input è primo o meno è stato in NP fino al 2002. Infatti, cosa fareste voi per verificare che un numero è primo, intuitivamente? 

"Semplicemente", prendete tutti i numeri prima del numero dato e provate a dividere il vostro numero per ognuno di questi. Se trovate un divisore, potete fermarvi, altrimenti no. Ecco quindi che fate n passi, dove n è il numero dato in input (non la sua lunghezza, però: il suo valore!), e in ogni passo fate una divisione, il cui tempo potremmo chiamarlo d. I passi in tutti sono n per d, man è il valore del numero dato in input, che dipende esponenzialmente dalla sua lunghezza. Ecco quindi che l'algoritmo è esponenziale! Per niente polinomiale, la funzione esponenziale cresce più di qualsiasi polinomio. Se provate a verificare se 123 è primo ci mettete già un po' di tempo. 

Tre ricercatori hanno scritto questo articolo in cui dimostrano che questo problema, chiamato PRIMES, è in P. Questo può alimentare i dubbi sulla questione P = NP. Uno scienziato ha detto poeticamente che se P fosse uguale NP verificare che una soluzione è quella giusta e trovare la soluzione sarebbe uguale: chiunque capisca la bellezza di una sinfonia sarebbe Mozart, chiunque comprenda una dimostrazione matematica sarebbe Gauss, chiunque ammiri una bella punizione dal limite dell'area sarebbe Del Piero. Guarda qui una discussione sull'argomento.

Esistono problemi poi che sono più difficili di tutti quelli che stanno in NP. Questi problemi in qualche modo rappresentano tutti i problemi in NP, e si chiamano problemi NP-completi. In pratica, se p è un problema NP-completo, preso un qualsiasi problema p2 in NP esso può essere trasformato in p, ovvero se risolvo p con i dati che ho fornito a p2, risolvo anche p2. Guarda quiuna lista di problemi NP-completi. 

Se qualcuno è arrivato a leggere fin qui, potrebbe benissimo chiedere: ma cosa c'entra Pokémon con tutto questo? Forse l'autore è impazzito?

A mia discolpa, voglio dirvi che Pokémon calza a pennello con tutti questi argomenti. Quindi forse il vero interesse arriva qui, ma la lunga premessa era necessaria. A questo punto possiamo enunciare due proposizioni:

Proposizione 1. Pokémon Giallo è turing completo

A sostegno di questa proposizione, vi è un bell'esperimento che puoi trovare qui, e che riassumerò spero agilmente. L'autore parla di com'è possibile scrivere un qualsiasi programma utilizzando Pokémon Giallo. L'ispirazione, racconta lui stesso, gli venne guardando questa speedrun su Youtube, in cui un giocatore riusciva a finire Pokémon Giallo in meno di due minuti, creando una warp door dalla casa del protagonista e saltando direttamente alla fine del gioco. Sostanzialmente, il giocatore prende in giro il gioco stesso, facendo in modo che lui stesso creda di essere finito. Si può fare facilmente lo stesso con i Pokémon della serie Game Boy Advance, come Rubino e Zaffiro, visto i molteplici software che sono a disposizione per modificare il gioco dal computer: è infatti possibile creare una porta come quella che ha creato l'autore della speedrun, saltando direttamente alla fine.
L'autore, Robert McIntyre, parla del gioco da un punto di vista piuttosto generale. Ogni gioco presenta delle regole, che il giocatore deve rispettare per risolverlo. Per la verità, un sistema automatico volto ad eseguire questo gioco non permette di modificare le regole dello stesso. Così, un gioco di scacchi per computer non permette di trasformare gli scacchi in dama, o in Tetris. Sorprendentemente, in Pokémon Giallo è diverso. Si mostra com'è possibile programmare il Gameboy attraverso Pokémon Giallo, semplicemente sfruttando un piccolo bug presente nel videogioco, che crea una specie di assurdo nella funzione (perché ricordate che di funzione si tratta;
quando si crea l'assurdo in informatica o in matematica, succedono sempre cose molto interessanti...)
Se si va oltre alla regole di tenere 20 strumenti nello zaino, si fa andare in contraddizione tutto quanto. I programmatori, evidentemente, questo non lo avevano previsto.
Così, chiunque può creare un programma parlando direttamente al Gameboy interagendo con la lista di oggetti. Un po' più approfonditamente, il Gameboy ha istruzioni lunghe 8 bit, che rappresentano essenzialmente comandi a basso livello (prendi questo dato e mettilo nel registro B, verifica che è stato premuto il tasto A, ...). Se qualcuno è sufficientemente esperto, può, acquisendo i giusti strumenti, trasformare Pokémon nel gioco che vuole. Questo poiché gli strumenti sono codificati tramite numeri a 8 bit, e possono essere interpretati come istruzioni.
I dettagli tecnici sono piuttosto difficili da comprendere. Questo video mostra com'è possibile scrivere una canzone MIDI e disegnare una figura utilizzando questa procedura.

Arrivati fin qui, si potrebbe dimostrare la proposizione 1 formalmente, partendo da un linguaggio turing completo come C, o un linguaggio giocattolo (tipo il linguaggio WHILE), e mostrando che i costrutti esprimibili in Pokémon sono equivalenti a quelli presenti in esso. 

Dunque, tirando le somme, Pokémon Giallo crea un ambiente di sviluppo in grado di descriverequalsiasi algoritmo: è possibile scrivere in questo modo qualsiasi programma vi venga in mente!

La seconda proposizione che enunciamo non riguarda l'alterazione delle regole del gioco di Pokémon, bensì una loro diretta conseguenza.

Proposizione 2. Pokémon è NP-completo

Ebbene sì: tutti quelli che hanno giocato a Pokémon ci hanno messo parecchio a finirlo, la prima volta. Tuttavia, una volta che si sa dove si deve andare e quali strumenti acquisire, il gioco diventa piuttosto banale. Si dimostra, questa volta formalmente, che Pokémon è NP-completo. La tecnica per fare questo, essenzialmente, è una tecnica di riduzione da un altro problema NP-completo. Infatti, se si riduce un problema NP-completo a un altro problema in NP, quest'ultimo diventa NP-completo.
Il primo problema importante che è stato dimostrato essere NP-completo è SAT, o problema della soddisfacibilità di formule booleane: data una formula booleana, ovvero scritta utilizzando connettivi logici quali AND, OR e NOT, trovare un'assegnazione delle variabili che rende vera la formula. Dimostrare che questo problema è NP-completo richiede molta fatica, ma qualcuno l'ha fatto.
Per dimostrare che Pokémon è NP-completo si riduce da SAT quest'ultimo, utilizzando unacostruzione che già è stata utilizzata per risolvere un altro gioco, che è PUSH, che consiste nel spostare scatole in punti precisi di una mappa. Anche questo gioco è NP-completo.
La dimostrazione è tutto tranne che banale. Sostanzialmente, si implementano dei gadget, come li chiamano gli autori, tali per cui ogni situazione del gioco è riducibile a questi ultimi. Guardatel'articolo originale se siete curiosi.
Come si vede dall'articolo, non solo Pokémon è NP-completo, ma anche Super Mario, Metroid, Zelda, Donkey Kong. Molti giochi famosi sono NP-completi.
Questa NP-completezza è legata alla questione P = NP. Infatti c'è un teorema che dice che se S è un problema NP-completo e S sta in P, allora P è uguale a NP. La dimostrazione è banale.
Tuttavia, suggerisce una tecnica per dimostrare che P è uguale a NP. Se si mostra una procedura veloce per finire Pokémon rispettando le sue regole (quindi niente warp room!), allora P è uguale a NP! Questo è alquanto sorprendente. Lo stesso vale per ogni problema NP-completo, quindi Super Mario, Metroid, Zelda, ...
Che dire? Per dimostrare P = NP (e portarsi a casa 1 milione di dollari!), magari si scoprirà che la strada giusta è studiare i videogiochi della Nintendo!

Molte delle cose scritte in questo post sono state prese dal libro di Toffalori et al. citato più su. Ho linkato agli articoli citati.

Come fare convivere otto regine

Esiste un famoso rompicapo, chiamato Rompicapo delle otto regine, che consiste nel posizionare otto regine in una scacchiera 8x8 in modo tale che non si mangino.
Insomma, far convivere otto regine in una scacchiera tipica degli scacchi.
E' un rompicapo affascinante, che ha fatto infatuare diversi matematici, tra cui Gauss.
La regina è il pezzo più potente degli scacchi, perché include le possibilità di movimento di tutti gli altri: può muoversi come una torre (quindi lungo la sua riga e la sua colonna) e come un alfiere (in diagonale).
Provare già a posizionare 4 regine in una 4x4 non è semplice, pensate 8 in una 8x8, o addirittura 16 in una 16x16! In effetti, il rompicapo si estende a un qualsiasi numero N (N regine, in una NxN).
Se provate a risolvere meccanicamente il problema, sicuramente utilizzereste un metodo simile a quello che ho provato a utilizzare io: inizio a posizionare la prima regina nella prima casella, dopodiché la seconda in modo tale che non possa mangiare la prima. Vado avanti, posizionando la terza, e via via fino all'ottava. Quando vedo che non posso più posizionare una regina, torno indietro a quella precedente e vedo dove posso metterla in maniera diversa da come avevo fatto. Vado avanti così, finché non risolvo il problema.
Certo, in una 4x4 questo procedimento non porta via tanto tempo, ma già in una 8x8 dovreste stare minuti a segnarvi le caselle che avete già provato, per non parlare del fatto che noi non siamo macchine, e ci stufiamo in fretta.
Guardate un po' questa animazione che cerca di risolvere il problema così come abbiamo descritto:

Prima o poi, questo procedimento porta sempre a una soluzione.
Invece di provare noi stessi, perché non fare provare a una macchina? In un momento di entusiasmo, ho scritto un programma in Java che cerca la soluzione.
La soluzione adottata è comunque una soluzione molto lenta. Il programma sta in questo momento ancora provando a risolvere il rompicapo 16x16, e non ne ho idea di quando finirà.
Questo programma impiega molto tempo a risolvere il problema proprio perché, anche se non sembra, è un programma piuttosto stupido: infatti prova tutte le soluzioni, tornando indietro quando non sa più che pesci pigliare. Questo lo rende estremamente lento. Si può fare di meglio? Bè, tutte le soluzioni al rompicapo sono note, quindi basterebbe caricarle in un programma e darle in output quando richiesto! Ma questo grazie a qualcheduno che lungo la storia si è messo carta e matita a studiare il problema.
Di questo rompicapo esistono (finora?) 92 soluzioni, ricavabili da 12 di partenza pasticciando un po' con la scacchiera.
Sebbene questo problema possa risultare per certi versi inutile da un punto di vista pratico, uno dei più grandi informatici della storia, Edsger Dijkstra, ha illustrato attraverso questo problema la potenza di una tecnica di programmazione. Ma questa è un'altra storia.

Mentre finivo di scrivere questo post, il programma ha inaspettatamente terminato di risolvere una 16x16:

Un algoritmo per il campionato

Vi siete mai chiesti come si creano i calendari dei campionati di calcio? Credo di no.
Se però la prima riga di questo post vi ha messo un po' di curiosità, posso dirvi subito come NON si fa: non si sorteggia. Insomma, non si pescano da un cappello le squadre per abbinarle, creare la prima giornata, e poi si rifà l'operazione stando attenti a non ricreare le giornate precedenti, e per di più alternando casa e trasferta. Così facendo, sarebbe molto lungo creare calendari anche solo per quadrangolari di provincia.
La risposta alla necessità di creare calendari per campionati anche di 20-30 squadre è la seguente: l'algoritmo di Berger.

Un algoritmo è una serie di passi eseguibili da una macchina (o da un esecutore "stupido", ovvero che non sa in realtà quello che sta facendo) per risolvere un problema. Vi sono problemi che inconsapevolmente risolviamo ogni giorno con l'aiuto di algoritmi di vario tipo: dal parcheggio, al regolare l'acqua calda della doccia.
Per creare i calendari dei campionati si può utilizzare un facile algoritmo creato da uno scacchista austriaco, Berger, che si può descrivere come segue: dato un numero pari di squadre (diciamo A,B,C,D; potrebbero anche essere dispari, ma per ora restringiamoci a questo caso), se ne toglie una e si dispongono le rimanenti in questo modo:

A B C

partendo dal fondo, prendiamo le prime due squadre: B-C sarà la nostra prima partita.
La squadra rimanente, A, la abbiniamo a quella rimasta fuori: D.
La prima giornata sarà:

C-B

A-D

Ora procediamo in questo modo: "ruotiamo" le squadre, spostando la C in testa. Otteniamo

C A B

Ecco che possiamo ripetere il procedimento: dal fondo prendiamo A e B, e creiamo A-B, per poi abbinare C a D. La seconda giornata è: 

B-A

C-D

Resta solo una giornata, ma ormai il giochino l'abbiamo imparato:

B C A

E la giornata diviene:

A-C

B-D

Così facendo abbiamo creato il nostro calendario:

Giornata I

C-B

A-D

 Giornata II

B-A

C-D

 Giornata III

A-C

B-D

L'algoritmo non alterna automaticamente casa e trasferta, ma è un buon punto di partenza!

Possiamo fare qualche affermazione matematica? Ma credo di sì: date n squadre, abbiamo n-1 giornate, e in ogni giornata n/2 partite, ma questo lo si può capire guardando 90° minuto!

E se le squadre sono dispari? Niente paura. A rotazione una riposa, e può fare un'amichevole.

La internet key alternativa: Alcatel One Touch X060S

Quante volte abbiamo sentito parlare delle tanto famose "chiavette internet"? Forse anche troppo. La propaganda dove le protagoniste sono queste 4 chiavi usb è ormai troppa, e ha sempre gli stessi marchi protagonisti. Gli spot delle chiavette Tim, Vodafone, Wind e Yahoo! (distribuite dal marchio 3) ci hanno letteralmente "rincoglionito", e scusate il termine. Ma non esistono solo queste 4 opportunità per essere collegati a internet fuori casa e senza fili. La TV e la radio ci hanno nascosto l'esistenza del marchio Alcatel anche in questo campo, e di come questa ditta abbia reso possibile la possibilità di collegarsi al web con le SIM Vodafone, Wind, Tim e 3 anche senza le apposite chiavette. E' questa in poche righe la definizione del modem USB HSDPA (High Speed Downlink Packet Access, letteralmente "pacchetto di accesso all'alta velocità senza fili") "One Touch X060S". Io ho personalmente provato l'efficienza della chiavetta con una SIM Vodafone normalissima, infilata nell'apposito scomparto presente nel modem USB, e posso assicurare che funziona alla perfezione, dato che sto scrivendo questo post collegato al web con questa chiavetta, direttamente da una borgata sperduta in montagna (la copertura infatti non è delle migliori, ma riesco comunque a connettermi e a visualizzare le pagine).

Ora vorrei mettere a confronto la pennetta Alcatel configurata con una SIM Vodafone, e la internet key originale Vodafone.

Una nota: La chiavetta Alcatel viene 69 € (non scontata, prezzo di fabbrica), quella Vodafone costa sui 100 € (99 € per l'esattezza).

Per configurare la penna Alcatel bisogna soltanto collegarla al PC, Windows farà il resto. In pochi minuti la chiavetta girerà perfettamente sul sistema Microsoft. Per MAC OS bisognerà fare qualche passo in più, ma è tutto descritto sul PDF contenuto nella chiavetta, che pur non funzionando come normale "USB Dati", viene riconosciuta dal sistema come tale. Con l'inserimento di una Micro SD nell'apposito scomparto, la chiavetta funzionerà anche come una "normale" usb key. Per collegarmi ad internet io ho personalmente configurato la SIM Vodafone chiamando l'apposito servizio clienti (190) e attivando la promozione "Internet Key", che permette con un costo d'attivazione di 5 € di navigare per 3 mesi a 1 € al giorno, su pc e cellulare (nonchè smartphone o I-Phone). Inserita la SIM nella key, con un'attesa di massimo 1 ora, navigo già in internet, con una velocità sì lentissima, ma in un posto sperduto che neanche è ben coperto dalla rete HSDPA. Facendo bene i conti, si possono arrivare a questi risultati:

Chiavetta Alcatel:
costo 69 €;
costo configurazione sim per navigazione: 5 €
navigazione giornaliera per 1 giorno: 1 €
costo totale: 75 €

Chiavetta Vodafone:
costo: 99 €
costo configurazione sim per navigazione: 5 €
costo totale: 104 €

Comprando quindi la chiavetta Alcatel, è quindi possibile risparmiare circa 30 €, sempre navigando sul web come se si avesse una normale usb key Vodafone, con costi più ridotti.

I marchi, le immagini e i nomi presenti in questo post sono di proprietà delle rispettive società e dei rispettivi siti.

Sexy Lena: clicca e mi spoglio...

Eccola qui, l'ennesima cazzata del secolo, l'ennesima catena di Sant'Antonio, l'ennesimo sito fasullo che attira gente di vario tipo da ogni angolo del web...Sexy Lena. Simile al fenomeno Sonya, è una ragazza, che, secondo una storiella che c'è nel sito, ha lasciato il fidanzato perchè lui stava troppo lontano da lei, dopo 4 anni di relazione. Il ragazzo, super-arrabbiato, decise di uploadare su un sito delle foto piccanti in cui la ragazza in questione è sempre più "senza veli", arrivando persino a 4 video hard, il tutto da sbloccare. Per sbloccare il materiale in questione, bisogna invitare quante più persone possibili e fargli cliccare un link personale che viene dato ogni volta che si entra in questo sito. Più persone entrano, e più le foto diventano sempre più piccanti. Ma, in tutto ciò, qual è la più grande fregatura? La fregatura sta nel fatto che le foto erano su internet già da tempo, e, dopo pochi giorni dalla "messa in web" del sito, è apparso un bel annuncio, riportato qui sotto nella sua lingua originale (inglese):

Hot tip: Just CLICK To Fast Track and unlock EVERYTHING immediately!

L'annuncio sovrastante dice che bisogna cliccare sulla scritta "Just CLICK To Fast Track" (basta un click per il passaggio veloce, letteralmente) per sbloccare il tutto subito. Il link porta direttamente ad un'altra serie di scritte, che dice di iscriversi a "Adult FriendFinder", noto sito di annunci erotici, per poi sbloccare foto e video. Da ciò si capisce che i nostri dubbi non erano infondati, infatti, nonostante apprezziamo tutti lo sforzo del ragazzo nel farci vedere una bella ragazza in delle belle pose, abbiamo capito che è tutto a scopo pubblicitario. Il mio dubbio è che AdultFriendFinder abbia comprato il dominio del sito e abbia messo un modo per sbloccare il tutto subito, per i navigatori più accaniti, e obbligandoli perciò ad iscriversi al sito, e quindi a subire le torture da parte di AdultFriendFinder via e-mail e in tutti i modi possibili. Bella roba...

L'infogio su New Service di Ramundo

Da oggi "L'infogio" è raggiungibile tramite questo sito (New Service Ramundo). In questo sito potrete trovare molti servizi interessanti, come le informazioni su una nota squadra di calcio torinese (Rapid Torino, dove gioco ankio :)) e come raggiungere il New Service, per riparare qualsiasi tipo di oggetto elettronico tra cellulari, televisori, pocket pc e navigatori.