mercoledì 31 luglio 2013

Nim — 11. Il Nim Farlocco e la teoria di Sprague-Grundy

«Ricordi quando abbiamo parlato del Poker Nim?».

«Certo, era un Nim in cui potevi anche aggiungere pedine, a patto di possederne».

«Ok, utilizzare pedine serviva principalmente per fissare le idee, ma possiamo generalizzare l'idea senza complicare troppo le cose. Per esempio, cosa mi dici di un gioco fatto così?».

G = {*0, *1, *2, *7, *42}

«Allora, vediamo. Stai usando la notazione che elenca le mosse possibili, vero?».

«Sì. Ogni gioco è un insieme di giochi, ovvero un insieme di possibili mosse. Tu puoi scegliere una delle cinque mosse indicate».

«Se scelgo *0, cosa succede?».

«Succede che tu hai fatto la mossa, e ora tocca a me giocare in *0. Purtroppo *0 è il gioco senza mosse, quindi vinci tu».

«Oh, bene, scelgo quello allora».

«Ok, me lo merito… Vai avanti nell'analisi del gioco, però».

«Potrei scegliere *1, allora».

«Ok, in quel caso tu mi passeresti il gioco *1 che è uguale a {*0}».

«In pratica è un Nim con una pedina sola».

«Esatto, l'unica mossa che potrei fare è *0, e questa volta perderesti tu».

«Vabbé, direi di aver capito. È come giocare a Nim, con due mosse in più, cioè *7 e *42. Praticamente come nel Poker Nim».

«Esatto. Nel Poker Nim le mosse in più dipendono dalla quantità di gettoni che hai, qui invece sono state stabilite a priori senza fare riferimento a una qualche realtà. Possiamo chiamare questo tipo di gioco Nim Farlocco».

«Ma dai».

«Gli inglesi lo chiamano Bogus Nim, figurati se noi non possiamo chiamarlo Nim Farlocco».

«Non discuto».

«Ora, abbiamo visto che per questo tipo di giochi vale la regola del Mex».

«Certo: questo Nim Farlocco è equivalente a una singola pila Nim composta da m elementi, con m uguale al primo intero non negativo non compreso tra i nimeri di cui è composto il gioco. In questo caso *3. Ho capito, G = *3».

«Bene. Adesso facciamo un passo gigante: consideriamo un gioco imparziale qualsiasi:».

G = {A, B, C, …}

«Qualsiasi?».

«Va bene qualunque tipo di gioco, basta che sia imparziale. Entrambi i giocatori hanno a disposizione le mosse A, B, C, e così via. Tieni presente che quell'e così via non sta a significare che le mosse possibili sono finite. Non è detto nemmeno che siano numerabili, ma questo non ci interessa: stiamo sul semplice e immaginiamo pure un numero di mosse finito».

«Non riesco a immaginare un gioco infinito, a dir la verità».

«Giochiamo a chi dice il numero più grande?».

«Ehm».

«Più seriamente, c'è un gioco che si chiama Nim bidimensionale. Si gioca su un quadrante — se vuoi, su una scacchiera infinita andando verso l'alto e verso destra».

«E come si gioca?».

«Ci sono varie pile di pedine sulla scacchiera. Tu puoi muovere una qualunque pedina a sinistra, stando sulla stessa riga, oppure puoi muoverla in una delle righe sottostante in una qualunque posizione».

«Uhm».

«Dopo aver scelto una pedina, se la muovi a sinistra hai a disposizione un numero finito di mosse. Se però la muovi verso il basso, hai infinite caselle a disposizione. E, nonostante questo, il gioco termina dopo un numero finito di mosse».

«Ah».

«Ma non c'è bisogno di pensare a questi giochi complicati. Torniamo al nostro gioco G».

«Ok».

«Come succede in tutti i giochi, la notazione G = {A, B, C, …} sta a significare che A, B, C, eccetera sono tutti giochi più semplici».

«Vero».

«Il concetto di semplicità potrebbe essere chiarito in maniera rigorosa dal punto di vista matematico, ma non ci interessa farlo adesso, l'importante è averne una idea. E l'idea direi che l'abbiamo avuta, abbiamo visto come funzionano questi giochi, no?».

«Direi di sì, ne abbiamo giocati tanti (e io ho sempre perso, a dire il vero)».

«Allora, se uno dei due giocatori sceglie la mossa A, passerà all'altro giocatore un nuovo gioco, più semplice di G».

«E a sua volta l'altro sceglierà una mossa in A, che sarà un nuovo gioco più semplice di A».

«E così via: in questa discesa prima o poi si arriverà al gioco più semplice di tutti, che è *0».

«Ah».

«E quindi quel gioco è associato a un nimero, che è poi sempre lo zero».

«Certamente».

«Quindi, riassumendo, ogni gioco può essere scomposto in parti più semplici, fino ad arrivare ad avere dei nimeri».

«Per esempio, A potrebbe essere uguale a {*0, *1, *2, *7, *42}, il gioco farlocco di prima».

«Sì. E, grazie alle considerazioni fatte sul Poker Nim, sappiamo che A = *3».

«Giusto».

«Ma anche B, C e tutti gli altri giochi prima o poi si semplificheranno, e quindi anche ad essi potrà essere applicata la regola del Mex».

«Ehi, ma allora anche G diventa un insieme di nimeri, e quindi anche ad esso possiamo applicare la regola del Mex».

«Ottimo, questo è proprio il punto: nei giochi esiste un principio di induzione. Grazie a queste successive semplificazioni possiamo dire che ogni gioco imparziale è equivalente a una pila di Nim Farlocco; la regola del Mex ci dice quanto è alta la pila: basta analizzare le opzioni del gioco in questione».

«Se sono opzioni troppo complicate, basta analizzarle a loro volta con la stessa regola, prima o poi si arriverà a giochi semplici di cui si riesce a calcolare il valore, giusto?».

«Giustissimo. Basta creare una tabella di nimeri, e si riesce a risolvere qualunque gioco imparziale. La regola del Nim Farlocco è il fondamento della teoria di Sprague-Grundy per i giochi imparziali».

«Bello».

«La prossima volta vedremo un gioco diverso, così capiremo come viene applicata questa regola».

lunedì 29 luglio 2013

Nim — 10. Mex

«Siamo pronti per enunciare la legge fondamentale».

«Vai».

«Un insieme di nimeri = {*a, *b, *c, …} (cioè un insieme di pile di Nim composte da a, b, c, … pedine) può essere considerato come un nimero *m (cioè un'unica pila Nim composta da m elementi), in cui m è il più piccolo numero naturale (incluso lo 0) che non è compreso tra i valori a, b, c, …».

«Uh, bella roba».

«È chiaro quello che afferma? Abbiamo fatto un sacco di esempi, no?».

«Sì, è il principio del Poker Nim generalizzato come piace tanto fare a voi Veri Matematici».

«Esattamente. I numeri più grandi di m sono inutili, perché quelle mosse sono annullabili quando e come si vuole. Ciò che conta è solo m».

«Ci sono».

«Questa viene detta Minimal Excluded Rule, per gli amici Mex».

«Ok».

«Si può anche definire una funzione Mex: per esempio possiamo scrivere che Mex({0,1,2,5,9}) = 3».

«Il più piccolo intero non negativo che non è compreso nell'insieme».

«Benissimo. E ora ti invito a riguardare, con occhi più consapevoli, la tabella che abbiamo scritto con tanta fatica:».

+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
+---+---+---+---+---+---+---+---+
| 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
+---+---+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
+---+---+---+---+---+---+---+---+
| 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+
| 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
+---+---+---+---+---+---+---+---+
| 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+---+---+---+---+---+---+---+---+

«Mi sembra sempre quella, anche se manca una casella».

«Certo. Facciamo finta di non sapere ancora quale numero debba essere scritto in quella casella».

«Ah, va bene. Sarebbe il risultato di *5 + *1».

«Esatto. Stiamo quindi chiedendoci a cosa è equivalente un Nim composto da una pila da 5 pedine e un'altra pila da una sola pedina».

«Giusto».

«Ora, le possibile mosse che un giocatore può fare giocando a *5 + *1 sono queste:».

(4,1)
(3,1)
(2,1)
(1,1)
(1)
(5)

«Vero».

«Ma noi conosciamo i nimeri relativi a tutti quei giochi, perché possiamo leggerli dalla tabella».

«Anche questo è vero; aspetta che li scrivo tutti:».

(4,1) = *5
(3,1) = *2
(2,1) = *3
(1,1) = *0
(1) = *1
(5) = *5

«Molto bene. Quindi giocare in *5 + *1 significa giocare in G = {*0, *1, *2, *3, *5}».

«Ok, quindi?».

«Quindi ci basta applicare la regola Mex: G è uguale al nimero *m dove m è il più piccolo intero non negativo non compreso nell'elenco 0, 1, 2, 3, 5».

«E quindi è 4!».

«Ottimo. Con questo sistema si può compilare la tabella andando molto più in fretta, rispetto al tempo che abbiamo impiegato noi per farci tutti i calcoletti».

«In pratica mi basta guardare i numeri che si trovano a sinistra e sopra alla casella che voglio riempire: devo prendere il loro Mex».

«Proprio così: ecco una tabella più grande, questa volta calcolata (anzi, fatta calcolare dal computer) utilizzando questo nuovo metodo. Ho dovuto rimpicciolirla, altrimenti non ci sarebbe stata».

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1| 0| 3| 2| 5| 4| 7| 6| 9| 8|11|10|13|12|15|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3| 0| 1| 6| 7| 4| 5|10|11| 8| 9|14|15|12|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3| 2| 1| 0| 7| 6| 5| 4|11|10| 9| 8|15|14|13|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4| 5| 6| 7| 0| 1| 2| 3|12|13|14|15| 8| 9|10|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5| 4| 7| 6| 1| 0| 3| 2|13|12|15|14| 9| 8|11|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 7| 4| 5| 2| 3| 0| 1|14|15|12|13|10|11| 8| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7| 6| 5| 4| 3| 2| 1| 0|15|14|13|12|11|10| 9| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8| 9|10|11|12|13|14|15| 0| 1| 2| 3| 4| 5| 6| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9| 8|11|10|13|12|15|14| 1| 0| 3| 2| 5| 4| 7| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10|11| 8| 9|14|15|12|13| 2| 3| 0| 1| 6| 7| 4| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11|10| 9| 8|15|14|13|12| 3| 2| 1| 0| 7| 6| 5| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12|13|14|15| 8| 9|10|11| 4| 5| 6| 7| 0| 1| 2| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13|12|15|14| 9| 8|11|10| 5| 4| 7| 6| 1| 0| 3| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14|15|12|13|10|11| 8| 9| 6| 7| 4| 5| 2| 3| 0| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|14|13|12|11|10| 9| 8| 7| 6| 5| 4| 3| 2| 1| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

«Devi ancora spiegarmi la faccenda dei colori».

«Tra poco parliamo anche di quelli. Prima, però, il Teorema Fondamentale».

venerdì 26 luglio 2013

Nim — 9. Poker Nim

«Ora modifichiamo un po' le regole del gioco. Prendiamo uno di quei set per giocare a poker, con tanti gettoni colorati».

«Belli, mi piacciono».

«Abbiamo a disposizione una riserva di gettoni, diciamo 50, e giochiamo normalmente a Nim, con una regolina in più».

«Quale?».

«Possiamo aggiungere a una pila un qualunque numero di gettoni, purché li possediamo».

«Possiamo giocare anche quelli che togliamo giocando normalmente?».

«Certo. Allora, 50 gettoni a testa, sul tavolo tre pile che formano, uhm, diciamo un Nim (3,2,1). Vai, comincia tu».

«Allora, so che (3,2,1) è una situazione che mi è sfavorevole, perché è un gioco nullo».

«Quindi vincerei io».

«Sì. Allora provo a modificare la situazione. Uso 10 dei miei gettoni e li metto nella pila da 3: (13,2,1). Tocca a te».

«Bene, tolgo 10 gettoni dalla prima pila. Ecco qua: (3,2,1)».

«Mh, temo di essere stato fregato ancora una volta».

«Già».

«Avere a disposizione delle pedine in più non serve a niente, se un gioco era a tuo favore prima della mia mossa, lo sarà anche dopo, perché tu puoi cancellare tutte le mosse in cui io aggiungo dei gettoni».

«È così. La morale della storia è: è inutile poter aggiungere delle pedine».

«Bene. A cosa serve questa morale, oltre a farmi perdere un'altra volta?».

«Serve per una importante generalizzazione. Dobbiamo formalizzare un po' i ragionamenti fatti fino ad ora. Siamo d'accordo sul fatto che il Nim più semplice è quello composto da una sola pila, vero?».

«Naturalmente».

«Allora, utilizziamo questa notazione: un gioco rappresentato da una singola pila Nim viene scritto mettendo, tra parentesi graffe, l'elenco delle mosse possibili».

«Quindi quello che abbiamo sempre indicato con (3), cioè un Nim che ha una sola pila con tre pedine, come sarebbe scritto?».

«Sarebbe scritto così: (3)={*0, *1, *2}».

«Vedo che non hai scritto delle mosse, ma dei nimeri».

«Sì, ma praticamente è la stessa cosa. Significa che da (3) puoi prendere tutte e tre le pedine, arrivando a (0), il cui nimero è 0, o anche *0».

«Sì, ricordo che lo zero è sempre lo zero».

«Oppure puoi prendere due pedine, arrivando a (1)».

«Il cui nimero è *1, ho capito. Oppure posso prendere una sola pedina, arrivando a (2), cioè *2».

«Bene. Avrai notato che abbiamo scritto un nimero come l'insieme dei nimeri minori di esso».

«Veramente no».

«Ma sì, abbiamo appena scritto che (3) = *3 = {*0, *1, *2}».

«Ah, già».

«Ecco, se questo ti ricorda qualcosa sui numeri ordinali, non è un caso».

«Oh».

«Ma facciamo finta di niente, e andiamo avanti».

«Benissimo».

«Ora, Nim più complicati di quelli appena considerati, cioè con più pile, possono essere visti come somme di Nim più semplici».

«Per esempio?».

«Per esempio il nostro amico (3,2,1) può essere visto come + + K, dove = {*0,*1,*2}, = {*0,*1} e = {*0}».

«Va bene, ma ancora non vedo l'utilità».

«Ci arriviamo subito. Supponi di avere un gioco fatto così: = {*0, *1, *2, *5, *6}».

«Fammi capire».

«Tu puoi fare una delle mosse indicate tra parentesi, cioè puoi scegliere solo uno di quei nimeri».

«Ancora non mi è chiaro, ma che gioco è?».

«È come se tu avessi un Nim con una sola pila, con 3 elementi».

«In quel caso potrei togliere una, due oppure tre pedine».

«Giusto, arrivando a *2, *1 oppure *0. Poi hai a disposizione due mosse in più: potresti aggiungere delle pedine in modo da avere una pila da 5 elementi, oppure una da 6».

«Ah, ok, direi di aver capito la notazione».

«Bene, diciamo che il gioco G fa parte di un gioco più articolato, così come il Nim (3,2,1) è composto da (3) e da altri giochi, cioè (2) e (1)».

«Uhm, ok».

«Possiamo indicare il gioco più articolato con + + +…, senza specificare cosa siano HK e tutto quello che segue».

«Va bene».

«Ora supponi che io possieda una strategia per vincere in *3 + + +…, così come ce l'avevo per *3 + *2 + *1, il nostro amico Nim (3,2,1)».

«Sto seguendo».

«Bene, il ragionamento fatto poco fa sul Poker Nim ci fa capire che la mia strategia vincente funziona anche per + + +…».

«Vediamo: il motivo è dovuto al fatto che se io faccio qualche mossa che sta in G ma non in *3, tu puoi sempre annullarla?».

«Benissimo! Per capire meglio, ti faccio un esempio. Giochiamo a G + *2 + *1. In pratica abbiamo un Nim (3,2,1) in cui sono disponibili due mosse in più: portare la prima pila a 5 oppure a 6 elementi».

«Immagino di dover cominciare io?».

«Certo».

«Ok, tanto questa volta so già come andrà a finire. Allora, da (3,2,1) passo a (5,2,1)».

«Bene. Questo significa che dall'insieme delle mosse possibili di G, cioè {*0, *1, *2, *5, *6}, tu hai scelto *5. Questa è la situazione che tu passi a me, cioè io devo giocare in *5 + *2 + *1».

«Ok».

«Allora scelgo di giocare in *5, che corrisponde all'insieme delle possibili mosse {*0, *1, *2, *3, *4}, e in particolare scelgo *3. In pratica sono passato da (5,2,1) a (3,2,1). Ora tocca a te giocare in *3 + *2 + *1».

«E mi hai fregato ancora».

«Sì, ho usato la strategia del Poker Nim, generalizzando un po' l'idea. Il concetto fondamentale che abbiamo imparato è questo: {*0, *1, *2, *5, *6} è equivalente a {*0, *1, *2}, cioè *3».

«Eh, sì, se io provo ad aumentare la pila tu la diminuisci subito».

«Ok. Ti lascio digerire un po' il tutto, la prossima volta scriviamo per bene la legge, che sarà una legge fondamentale per la teoria dei giochi».

«Wow».

mercoledì 24 luglio 2013

Nim — 8. Tabella completa

«Ormai abbiamo capito il meccanismo, quindi direi di andare un po' più spediti del solito nello studio del Nim (7,4,3)».

«Va bene, spero di riuscire a seguire».

«Omettiamo l'analisi delle posizioni ovvie, cioè quelle in cui viene cancellata una pila, o si creano due pile uguali. Abbiamo già detto che sono mosse da non fare, se il primo giocatore vuole avere speranza di vincere».

«Giusto».

«Non rimangono allora molte mosse. Se il primo giocatore porta una delle due pile più grandi a 2 oppure a 1, il secondo può portare a 1 oppure a 2, rispettivamente, l'altra pila più grande».

«Vediamo… Le mosse che potrebbe fare il primo giocatore sono queste, se non sbaglio:».

(2,4,3)
(1,4,3)
(7,2,3)
(7,1,3)

«Giusto. In ognuno di questi quattro casi il secondo può ricondurre il gioco a (3,2,1)».

«Che è una delle posizioni buone, quindi in questo caso vince il secondo».

«Sì. Il primo giocatore potrebbe però muovere diversamente. Per esempio, potrebbe muovere in (6,4,3) oppure (7,4,2)».

«Mh, allora il secondo non potrebbe giocare (3,2,1), però può utilizzare un'altra delle posizioni buone. Può muovere in (6,4,2), e vincere».

«Bene. Rimangono gli ultimi due casi: (5,4,3) e (7,4,1)».

«In questo caso il secondo giocatore se la cava con (5,4,1)».

«Perfetto, quindi anche questo Nim è a favore del secondo, cioè è nullo. Ecco un riassuntino:».




«Quindi possiamo aggiungere qualcosa alla tabella della somma dei nimeri».

«Certo: ora sappiamo che *7 + *4 + *3 = 0, e quindi la somma di due qualunque di quei nimeri è uguale al terzo».

«Uhm, però mi sa che ancora non basta».

«Perché?».

«Non riesco a riempire tutte le caselle. Per esempio, non so quanto fa *2 + *5».

«Bé, calcolalo!».

«Ah, posso provarci. Vediamo un po', *2 + *5 = *3 + *1 + *5. Ho usato il fatto che *2 = *3 + *1».

«Bene. Sai anche quanto fa *1 + *5, no?».

«Fa *4, quindi ho trovato che *2 + *5 = *3 + *4, e quest'ultima somma fa *7. Bene, quindi *2 + *5 = *7».

«E tutte le relazioni gemelle, naturalmente. Ti manca solo un calcolo, poi la tabella è completa».

«Quale?».

«*1 + *6».

«Provo subito: *1 + *6 = *1 + *2 + *4 = *3 + *4 = *7. Facile!».

«Ottimo! Ora puoi riempire la tabella».

«Eccola:».

+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+
| 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
+---+---+---+---+---+---+---+---+
| 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
+---+---+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
+---+---+---+---+---+---+---+---+
| 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+
| 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
+---+---+---+---+---+---+---+---+
| 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
+---+---+---+---+---+---+---+---+
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+---+---+---+---+---+---+---+---+


«Con un po' di fatica, ce l'abbiamo fatta».

«Mi chiedo se ci sia una regola».

«Naturalmente».

«Capirai».

lunedì 22 luglio 2013

Nim — 7. Manca qualcosa

«Per capire cosa inserire nelle caselle rimaste vuote nella tabella dell'altra volta, dobbiamo studiare un altro gioco».

«Quale?».

«Ecco qua: (6,4,2)».

«Uh, le pedine cominciano ad aumentare».

«Eh, sì. Ma cominciamo a mettere un po' di ordine: il secondo giocatore deve ricordarsi quali sono le posizioni buone per lui. Finora ne abbiamo trovate due, e cioè (3,2,1) e (5,4,1). Se il secondo giocatore riesce a muovere in una di quelle due posizioni, l'altro non ha speranze».

«Vero, quelle posizioni sono nulle, se le passa al suo avversario è sicuro di vincere».

«Ok. Provando a elencare le possibili mosse che si possono fare a partire da (6,4,2), otteniamo uno schema del genere».



«Vedo che non ci sono tutte le possibili mosse».

«No, ho omesso quelle in cui si ottengono due pile uguali, perché sappiamo che sono nulle, e quindi il primo giocatore deve evitarle, se vuole avere qualche speranza. Ho anche tralasciato quelle in cui il primo giocatore cancella una pila intera, perché sappiamo già che sono mosse perdenti».

«Provo a riassumere: se il primo giocatore si trova di fronte a (6,4,2), qualunque mossa egli faccia il secondo giocatore può sempre arrivare a (3,2,1) oppure (5,4,1); a parte i casi ovvi in cui il primo giocatore gli serve la vittoria in mano».

«Giusto. Quindi il gioco (6,4,2) è sempre a favore del secondo giocatore. In formule *6 + *4 + *2 = 0».

«Ah, quindi *6 + *4 = *2, e poi *6 + *2 = *4, e anche *4 + *2 = *6».

«Molto bene. Possiamo quindi riempire qualche altra casella della nostra tabella. Purtroppo notiamo che essa si ingrandisce, perché ora abbiamo introdotto anche il nimero 6».

+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
| 1 | 0 | 3 | 2 | 5 | 4 |   |
+---+---+---+---+---+---+---+
| 2 | 3 | 0 | 1 | 6 |   | 4 |
+---+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 |   |   |   |
+---+---+---+---+---+---+---+
| 4 | 5 | 6 |   | 0 | 1 | 2 |
+---+---+---+---+---+---+---+
| 5 | 4 |   |   | 1 | 0 |   |
+---+---+---+---+---+---+---+
| 6 |   | 4 |   | 2 |   | 0 |
+---+---+---+---+---+---+---+

«Vedo. Bisogna provare qualche altro gioco, per riempirla?».

«Bisognerà fare anche questo, sì. Ma per adesso possiamo fare un po' di aritmetica. Per esempio, siamo in grado di calcolare il valore di *3 + *5».

«E come facciamo?»
.
«Ci ricordiamo che *3 = *2 + *1, e così possiamo scrivere».

*3 + *5 = *2 + *1 + *5

«E questo a cosa ci serve?».

«Sappiamo che *1 + *5 = *4, e andiamo a sostituire:».

*2 + *1 + *5 = *2 + *4

«Ehi, *2 + *4 lo sappiamo calcolare, fa *6».

«Ed ecco quindi una nuova relazione: *3 + *5 = *6. Naturalmente ci saranno anche le altre relazioni gemelle: *3 + *6 = *5 e *5 + *6 = *3».

«Ho capito! Aggiorno la tabella, allora:».

+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
| 1 | 0 | 3 | 2 | 5 | 4 |   |
+---+---+---+---+---+---+---+
| 2 | 3 | 0 | 1 | 6 |   | 4 |
+---+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 |   | 6 | 5 |
+---+---+---+---+---+---+---+
| 4 | 5 | 6 |   | 0 | 1 | 2 |
+---+---+---+---+---+---+---+
| 5 | 4 |   | 6 | 1 | 0 | 3 |
+---+---+---+---+---+---+---+
| 6 |   | 4 | 5 | 2 | 3 | 0 |
+---+---+---+---+---+---+---+

«Come vedi, rimane ancora qualche casella vuota. Per riempirle dovremo studiare un altro gioco; prima di concludere, però, facciamo un riassunto dei giochi nulli trovati fino ad ora:».

(3,2,1)
(5,4,1)
(6,4,2)
(6,5,3)

«Per la prossima volta dobbiamo studiare (7,4,3)».

venerdì 19 luglio 2013

Nim — 6. Lente progressioni

«Allora, hai scoperto qualcosa sul Nim (5,4,1)?».

«Mah, mi sono fatto uno schemino, e ho visto che in alcuni casi si riesce a ricondurre il gioco a (3,2,1), che abbiamo già studiato».

«Bene, bene, fammi vedere questo schemino».

«Eccolo».



«Molto bene! Questo significa che se il primo giocatore fa una delle mosse che hai scritto, il secondo giocatore riesce a riportare la situazione a (3,2,1), che è un gioco nullo e quindi gli assicura la vittoria».

«Sì, però non ho analizzato tutti i casi, mi sembrano tanti».

«Vediamo… Per adesso hai stabilito che se uno dei due giocatori riduce una delle due pile maggiori a 3 oppure a 2, allora l'altro giocatore riduce l'altra delle due pile maggiori a 2 oppure a 3, ottenendo (3,2,1). Ora proviamo a procedere sistematicamente per cercare di capire qualcosa degli altri casi. Che succede, per esempio, se il primo giocatore ottiene (5,1,1)?».

«Uhm, se applico la proprietà che dice che due pile uguali sono cancellabili, quel gioco dovrebbe essere uguale a (5)».

«Esatto, e quindi vince il secondo giocatore».

«Eh, sì. Questo succede anche se il primo giocatore passa da (5,4,1) a (4,1,1)».

«Certo, stessa cosa. Quindi non solo al primo giocatore non conviene ridurre una delle due pile maggiori a 3 oppure a 2, ma non gli conviene nemmeno ridurla a 1».

«Eh, no».

«Cosa gli rimane da fare?».

«Potrebbe ridurre una delle pile a 0».

«In questo caso potrebbe ottenere (5,1), oppure (4,1), oppure (5,4). Cosa sappiamo dei Nim con due pile diverse?».

«Che sono giochi fuzzy, per la regola 3».

«E quindi anche in questo caso vince il secondo giocatore».

«Eh, sì».

«Direi che abbiamo analizzato tutto, no?».

«Già: qualunque mossa faccia il primo giocatore, il secondo vince».

«Quindi il gioco (5,4,1) è nullo. Come scriveresti l'operazione con i nimeri?».

«Scriverei *5 + *4 + *1 = 0».

«Bene. Esistono poi altri tre modi equivalenti, no?».

«Ah, sì: *5 + *4 = *1, oppure *5 + *1 = *4, oppure ancora *4 + *1 = *5».

«Benissimo: possiamo allargare la tabella, allora. Eccola qua».

+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+
| 1 | 0 | 3 | 2 | 5 | 4 |
+---+---+---+---+---+---+
| 2 | 3 | 0 | 1 |   |   |
+---+---+---+---+---+---+
| 3 | 2 | 1 | 0 |   |   |
+---+---+---+---+---+---+
| 4 | 1 |   |   | 0 | 1 |
+---+---+---+---+---+---+
| 5 | 4 |   |   | 1 | 0 |
+---+---+---+---+---+---+

«E nelle caselle vuote cosa ci mettiamo?».

«Lo scopriamo tra un po'».

mercoledì 17 luglio 2013

Nim — 5. Somme di nimeri

«Riassumiamo quello che abbiamo scoperto finora, ragionando su questi nimeri. Vediamo di costruire la tabella della somma, partendo da qui:».

+---+---+---+---+
| 0 | 1 | 2 | 3 |
+---+---+---+---+
| 1 |   |   |   |
+---+---+---+---+
| 2 |   |   |   |
+---+---+---+---+
| 3 |   |   |   |
+---+---+---+---+

«Uhm, spiega un po'».

«Per prima cosa, ho scritto 0, 1, 2, 3 invece di 0, *1, *2, *3».

«Perché 0 e non *0?».

«È la stessa cosa, lo zero è universale, *0 è il numero che corrisponde al gioco (0) che si comporta come lo 0».

«Va bene».

«Ora vediamo di riempire un po' la tabella. Come vedi non ho messo uno 0 per la riga e uno per la colonna perché lo 0 è davvero l'elemento neutro, quindi ne basta uno. Possiamo dire una volta per tutte che *k + 0 = *k e non ci pensiamo più».

«Ok».

«Ora sfruttiamo la seconda regola: due pile uguali formano un gioco nullo».

«Quindi cosa facciamo? Mettiamo 0 sulla diagonale?».

«Esatto, ecco qua:».

+---+---+---+---+
| 0 | 1 | 2 | 3 |
+---+---+---+---+
| 1 | 0 |   |   |
+---+---+---+---+
| 2 |   | 0 |   |
+---+---+---+---+
| 3 |   |   | 0 |
+---+---+---+---+

«E adesso?».

«Ci ricordiamo quello che abbiamo detto sul gioco (3,2,1)».

«Ah, vero. Se sommo due numeri — oops, nimeri — qualsiasi ottengo il terzo».

«E quindi possiamo compilare le altre caselle:».

+---+---+---+---+
| 0 | 1 | 2 | 3 |
+---+---+---+---+
| 1 | 0 | 3 | 2 |
+---+---+---+---+
| 2 | 3 | 0 | 1 |
+---+---+---+---+
| 3 | 2 | 1 | 0 |
+---+---+---+---+


«Bello».

«Ora ti faccio notare una cosa: se avessimo a disposizione solo il gioco nullo, dovremmo utilizzare solo la casella nell'angolo in alto a sinistra».

«Certo».

«Se possiamo usare una pedina (e quindi abbiamo a disposizione anche il gioco (1), cioè star), usiamo una griglia 2×2».

«Naturalmente».

«Se introduciamo il gioco *2, per completare la tabella abbiamo bisogno anche di *3».

«Vero, a causa della relazione *1 + *2 + *3 = 0».

«Infatti. Provo a usare dei colori per farti visualizzare meglio questo fatto».

+---+---+---+---+
| 0 | 1 | 2 | 3 |
+---+---+---+---+
| 1 | 0 | 3 | 2 |
+---+---+---+---+
| 2 | 3 | 0 | 1 |
+---+---+---+---+
| 3 | 2 | 1 | 0 |
+---+---+---+---+

«Carino, ma perché l'hai fatto?».

«Perché prossimamente tornerà utile. Per adesso prova a elaborare una strategia per il Nim (5,4,1)».

lunedì 15 luglio 2013

Nim — 4. Nimeri

«Abbiamo detto che il Nim (3,2,1) è un gioco uguale a zero».

«E cioè vince il secondo giocatore, mi ricordo».

«Bene, adesso convertiamo tutto in termini numerici».

«In che senso?».

«Vedrai. Partiamo dall'inizio, il Nim più facile di tutti, questo: (0). Comincia tu».

«Ma dai, cosa vuol dire? Non ci sono pedine, cosa tolgo?».

«Niente, perciò hai perso».

«Ah, certo, grazie».

«In un gioco nullo vince il secondo, no? Il gioco nullo più semplice è (0), che è nullo in tutti i sensi. Dunque (0) = 0».

«Argh».

«Ora analizziamo questo: (1). Questa volta comincio io, tolgo la pedina, e ti passo (0)».

«Ma basta!».

«Nel gioco (1) vince il primo giocatore, e quindi è un gioco fuzzy. Abbiamo detto che si scrive (1)║0».

«Uhm, avrei detto 1>0».

«Effettivamente 1 è maggiore di 0, ma qui non stiamo parlando del numero 1, ma del Nim con una pedina, cioè di (1). Ti ricorderai che il Nim, essendo un gioco imparziale, non potrà mai essere né positivo né negativo. Se non è zero, è fuzzy».

«Ma i numeri sono tutti o positivi, o negativi, o nulli, questa faccenda del fuzzy non mi torna».

«Infatti il gioco (1) non lo rappresenteremo con un numero, ma con un simbolo che si comporta come un numero che però deve soddisfare a determinate regole. Vedilo come generalizzazione dei numeri».

«Andiamo bene… E che simbolo si usa?».

«Questo: (1) = *».

«Un asterisco?».

«Sì, si chiama star, e viene anche indicato come *1».

«Vabbé».

«Ora, ricordi la nostra regola numero 1?».

«Sì, quella che dice che una pila è fuzzy».

«Esatto. Daremo a una pila composta da n elementi il valore *n. Per esempio, (2) = *2, (3) = *3, e così via».

«Ah. E perché?».

«Perché così siamo in grado di fare dei conti. Ad esempio, l'ultima volta abbiamo visto che (3,2,1) = 0».

«Sì, mi ricordo».

«E allora scriviamo questa operazione: *3 + *2 + *1 = 0».

«E ha senso?».

«Non secondo le usuali regole dell'aritmetica, perché quei simboli non sono numeri. Ma esistono altre regole, ben precise e definite, con le quali si può fare un'aritmetica dei nimeri».

«Dei nimeri?».

«Sì, questi nuovi numeri (che non sono numeri) vengono detti nimeri, proprio per il fatto che derivano dal Nim».

«…».

«Ehm. Ora facciamo un passo avanti: pensiamo al Nim (3,2,1) come se fosse la composizione di due giochi Nim, e cioè (3,2) e (1)».

«In che senso?».

«Nel senso che tu puoi decidere, ogni volta che sta a te, se giocare sul primo Nim oppure sul secondo».

«Ma non cambia niente, no? Tanto io tolgo pedine da una singola pila, cosa mi importa sapere se sto giocando a (3,2,1) oppure alla composizione di (3,2) con (1)?».

«Nulla, è proprio questo il punto: ogni Nim complesso può essere pensato come la somma di giochi Nim più semplici».

«Ah, ecco. Ma allora la somma *3 + *2 + *1 potrebbe essere interpretata come la somma di tre semplici Nim, cioè (3), (2) e (1), no?».

«Proprio così. E il fatto che (3,2,1) = 0 significa che quella composizione, come anche la composizione di (3,2) con  (1), è uguale a 0».

«Va bene».

«Per evitare di dire sempre che stiamo componendo due Nim, utilizziamo una notazione più comoda e certamente efficace: (3,2) + (1) = 0».

«Uh, una somma di giochi?».

«Proprio così: una somma di giochi è un gioco nel quale tu puoi scegliere dove fare la mossa: nel primo o nel secondo dei due giochi componenti. Ora pensa alla regola 2: quando succede che la somma di due pile è uguale a zero?».

«Quando le due pile sono uguali».

«Perfetto. Allora noi diciamo che i due giochi (3,2) e (1) sono uguali, nel senso che il secondo giocatore ha una strategia vincente».

«Aspetta, mi sono perso».

«Se due giochi sono uguali la loro somma è zero, se la somma è zero il gioco è vinto dal secondo giocatore».

«Ho capito».

«Ok, quindi (3,2) + (1) = 0. Nel linguaggio dei nimeri, possiamo dire che *3 + *2 = *1».

«Abbiamo applicato la regola 2, vero?».

«Sì, è come se avessimo a che fare con due pile uguali. Naturalmente la suddivisione di (3,2,1) in (3,2) + (1) è arbitraria, avremmo potuto dire che (3,2,1) è la somma di (3,1) e (2)».

«E quindi anche *3 + *1 = *2?».

«Esattamente. O anche *2 + *1 = *3».

«Direi di aver capito».

«Perfetto. La prossima volta facciamo una tabella e vediamo qualche gioco più complicato».

venerdì 12 luglio 2013

Nim — 3. Una partita un po' più seria

«Prima di andare avanti, riassumiamo le regole scoperte fino ad ora:».

1. Una pila è fuzzy (cioè vince il primo giocatore)

2. Due pile uguali sono uguali a zero (cioè vince il secondo giocatore (cioè due pile uguali riportano alla situazione iniziale prima di muovere (cioè possiamo cancellare due pile uguali e semplificare l'analisi del gioco)))

«Ok, fin qua ci sono».

«Ora studiamo questo gioco: (42,3)».

«Chi comincia?».

«Io. Tolgo 39 pedine alla prima pila, e ti passo questo gioco: (3,3)».

«Ehi, sono due pile uguali».

«Quindi questo gioco è nullo, vince il secondo giocatore. In questo momento sei tu il primo…».

«…e quindi vinci tu, uff».

«Quindi abbiamo trovato una terza regola:».

3. Due pile diverse sono fuzzy (il primo giocatore porta la situazione a due pile uguali, diventa il secondo giocatore, e vince).

«Ok, ci sono».

«Stiamo facendo dei passi avanti: abbiamo studiato completamente qualunque gioco Nim con una e con due pile: sappiamo chi vince e sappiamo come si fa a vincere».

«Vero. Siamo pronti per passare ai giochi con tre pile?».

«Sì, lo siamo. Pensiamo a giochi con tre pile composte da numeri diversi di pedine, altrimenti potremmo utilizzare la regola 2 e semplificarli. Prendiamone uno facile, per esempio questo: (3,2,1). Cosa succede se un giocatore cancella una delle tre pile?».

«Vediamo: potrebbe arrivare a (2,1), oppure (3,1), oppure ancora (3,2)».

«Ora applica la regola 3».

«In ogni caso abbiamo due pile diverse, quindi il gioco è fuzzy. Cioè vince il primo».

«Ma il primo è quello che deve muovere adesso, quindi quello che ha fatto la prima mossa, passando da (3,2,1) a una delle tre configurazioni dette prima, perde».

«Quindi mai vuotare una pila in un Nim a tre pile».

«Mai. Che altre mosse rimangono?».

«Mah, si potrebbe passare da (3,2,1) a (2,2,1), oppure a (3,1,1), oppure ancora a (2,1,1)».

«In ogni caso otterresti due pile uguali, no?».

«Sì, che in virtù della regola 2 potrei cancellare».

«Rimanendo quindi con una pila sola».

«Che, secondo la regola 1, è fuzzy, quindi vince il primo giocatore».

«Attenzione che il primo giocatore è quello successivo a quello che ha fatto la prima mossa».

«Vero, quindi anche queste mosse sono proibite, chi le fa perde. Ma allora non rimangono mosse possibili da fare!».

«Non rimangono mosse possibili vincenti. Quindi (3,2,1) è un gioco nullo, vince il secondo giocatore. Le mosse sono ancora molto poche, possiamo anche rappresentarle in uno schemino:».



«Ah, bello. Si vede bene che vince sempre il secondo giocatore».

«Già. Ed ecco la nuova regola che abbiamo appena scoperto:».

4. Con tre pile (diverse), il primo che vuota una pila oppure ne uguaglia due perde (se vuota una pila, si applica la regola 3, se ne uguaglia due, si applica la regola 2 e, successivamente, la 1).

«Ce ne sono ancora molte di queste regole sul Nim?».

«No, la prossima volta faremo un salto di qualità, e potremo parlare di nimeri».

«Numeri?».

«Tipo».

mercoledì 10 luglio 2013

Nim — 2. I personaggi in gioco

«Abbiamo detto cosa significa che un gioco è uguale a zero».

«Sì: vuol dire che vince il secondo giocatore».

«Esatto. Tieni presente che nella teoria dei giochi il secondo giocatore non è fisso, come nei giochi a cui siamo abituati».

«In che senso?».

«Per primo giocatore si intende quello che sta per fare la mossa, mentre il secondo giocatore è l'altro. Nel momento in cui tocca a me, io sono il primo giocatore, mentre quando tocca a te io sono il secondo».

«Ah».

«E, in effetti, un Nim con due pile uguali è un gioco nullo perché chi si trova di fronte alle due pile uguali perderà sicuramente, indipendentemente dal fatto che sia stato lui o no a iniziare il gioco».

«Ho capito. Primo e secondo giocatore sono concetti relativi».

«Esatto».

«E ci sarà un modo per definire il primo che ha iniziato?».

«Mh, no, perché non è importante: immagina che ogni volta che qualcuno fa una mossa si entra in un nuovo gioco, in cui il primo giocatore è l'altro. È comunque importante distinguere i due giocatori: esistono addirittura alcuni tipi di giochi in cui ogni giocatore può fare alcune mosse, inibite all'altro, e viceversa».

«Mh? Davvero?».

«Sì, pensa agli scacchi. Un giocatore può muovere solo le pedine bianche, l'altro le nere».

«Ah, ma certo. Il primo è il bianco, e il secondo il nero».

«A inizio partita, sì. Però abbiamo detto che primo e secondo sono concetti relativi al momento attuale, quindi nella teoria dei giochi non si usano questi termini per distinguere i due giocatori».

«E cosa si usa?».

«I due giocatori vengono chiamati Sinistra e Destra (o, meglio, Left e Right, dato che il Testo Fondamentale che parla di questi argomenti è scritto in inglese)».

«Mi sembra giusto».

«I giochi che sono vinti da Left vengono detti positivi, mentre quelli vinti da Right…».

«Negativi».

«Esatto».

«Chissà perché».

«È naturalmente una convenzione, si potrebbe invertire positivo con negativo e non cambierebbe nulla. Si usa questa terminologia perché essa è strettamente legata ai numeri surreali, per i quali i concetti di numero positivo e numero negativo hanno un ben preciso significato matematico».

«Dobbiamo addentrarci nei numeri surreali?».

«No, per l'analisi del Nim non ce n'è bisogno. Cioè, lo facciamo in minima parte, facendo finta di niente».

«Ehm».

«Non ti preoccupare. Riassumendo: un gioco G in cui vince Left si dice positivo, e si scrive G>0».

«Immagino che un gioco G in cui vince Right si scriva G<0».

«Proprio così. Un gioco in cui vince sempre il secondo giocatore si dice uguale a zero».

«E si scrive G=0».

«Naturalmente. Un gioco in cui vince il primo si dice fuzzy…».

«E come si scrive?».

«Utilizzando una meravigliosa simmetria di simboli, si scrive G║0».

«Bellissimo».

«Vorrei sottolineare un fatto: il Nim è un gioco imparziale, il che significa che i due giocatori hanno le stesse mosse».

«Vero».

«Come abbiamo detto prima, scacchi o dama non sono imparziali: uno dei due giocatori può muovere solo alcuni pezzi, e l'altro può muovere gli altri».

«Vero anche questo».

«In un gioco imparziale non è possibile che vinca sempre Left oppure che vinca sempre Right».

«Perché?».

«Immagina che esista un gioco del genere in cui è certo che vince Left, e supponi che Left sia il primo giocatore. Right osserva la partita, fa le sue mosse, e perde. A questo punto Right chiede di rigiocare, e questa volta comincia lui. Replicando le stesse mosse di Left, deve vincere».

«E quindi non è possibile che vinca sempre Left, ho capito».

«Sì, questo ragionamento si basa sul fatto che Left e Right hanno a disposizione le stesse mosse. Non potremmo ripetere il ragionamento con gli scacchi o la dama. Non è difficile pensare a situazioni, negli scacchi o nella dama, in cui vince sempre uno dei due giocatori, non importa chi sia quello che deve muovere».

«Vero, per esempio se negli scacchi ci fosse il re bianco messo sotto scacco matto da qualche pedina nera che deve stare ferma lì, per controllare appunto il re, e se ci fosse una ulteriore pedina nera libera di muoversi, vincerebbe comunque il nero indipendentemente da chi deve muovere».

«Esatto. Quando vedi la rappresentazione di una partita, ti accorgi subito se uno dei due re è sotto scacco matto, non hai bisogno di sapere chi deve muovere.».

«Quindi i giochi imparziali non sono né positivi né negativi?».

«Esatto. Possono essere uguali a zero, e quindi vince il secondo, o essere confusi con lo zero (cioè né positivi né negativi, ma nemmeno nulli) se vince il primo».

«Ed ecco spiegato il termine fuzzy».

«Esattamente. La prossima volta analizziamo qualche partita di Nim un po' più complicata».

lunedì 8 luglio 2013

Tutto quello che so sul Nim, con una meravigliosa generalizzazione — 1. Le regole del gioco

C'è un gioco, che si chiama Nim, di cui ho sentito parlare per la prima volta molti anni fa, leggendo il mio primo libro di Martin Gardner. Mi incuriosì il fatto che di quel gioco fosse nota la strategia vincente.

Le regole del gioco sono molto semplici: si creano alcune pile composte da un numero variabile di oggetti (generiche pedine, non importa il loro tipo), e ogni giocatore può togliere le pedine che vuole (almeno una, comunque, deve essere tolta) da una delle pile. Perde chi non ha più mosse da fare — e cioè vince chi toglie l'ultima pedina.

Il libro non parlava di dimostrazioni, né di come si fosse arrivati a trovare la strategia. Qui è dove scrivo quello che ho capito sul Nim, sul suo funzionamento, sulle dimostrazioni, e sulle sorprendenti generalizzazioni.

«Capirai».

«Cosa?».

«Capirai se non dovevi metterti a studiare delle dimostrazioni su un gioco».

«Eh, oh».

«Gioco totalmente inutile, naturalmente».

«Come tutti i giochi intelligenti, apre la mente, fa pensare, tiene in allenamento il cervello…».

«Vabbé, ho capito: inutile. Comunque, cosa hai scoperto su questo gioco?».

«Tante cose, ma cominciamo dall'inizio, vediamo di capire come funziona. Partiamo da un esempio molto semplice, una sola pila composta da 42 pedine».

«Ok».

«Comincio io: prendo 42 pedine. Tocca a te».

«Ma non ci sono più pedine!».

«Bene, ho vinto».

«Tu non sei mica tanto normale, ma che gioco è questo?».

«Un gioco molto semplice, per scaldarci un po'. Abbiamo imparato una prima, importante, regola».

«Se c'è una pila sola, vince il primo giocatore».

«Esatto. I Veri Matematici dicono che un gioco in cui vince il primo giocatore è un gioco fuzzy».

«Fuzzy? Cioè confuso?».

«Sì, confuso con lo zero».

«E lo zero è un gioco o un numero?».

«Entrambe le cose».

«Lo sai che non sto già capendo assolutamente nulla, vero?».

«Eh, immagino. Possiamo lasciare perdere un attimo, per passare a un altro esempio? Dopo che abbiamo capito cosa voglia dire zero nella teoria dei giochi, possiamo tornare indietro e cercare di capire qualcosa in più sui giochi fuzzy».

«Va bene».

«Allora, eccoti un gioco più complicato: ci sono due pile composte da 42 elementi. Simbolizziamo il gioco in questo modo: (42,42). Questa volta comincia tu».

«Uhm, boh, provo a togliere 3 elementi dalla prima pila».

«Quindi ci portiamo a questa situazione: (39,42), giusto?».

«Sì, va bene».

«Ok, anche io tolgo 3 elementi, ma dalla seconda pila. Ecco qua: (39,39). Tocca a te».

«Tolgo 10 elementi dalla seconda pila, così velocizziamo un po': (39,29)».

«Bene, anche io ne tolgo 10, dalla prima: (29,29). Tocca a te».

«Ehi, ma…».

«Sì?».

«Stai copiando le mie mosse?».

«Io? Sono innocente!».

«Mh. Tolgo 20 pedine dalla prima pila: (9,29)».

«E io ne tolgo 20 dalla seconda: (9,9). Tocca di nuovo a te».

«Vabbé, ho capito, copi le mie mosse».

«E quindi?».

«E quindi tu farai sempre l'ultima mossa, e vincerai».

«E tu perderai di nuovo. Hai imparato la lezione?».

«Sì: non giocare con te».

«Non dire così… Hai capito la morale di questa partita?».

«Sì, se ci sono due pile uguali, vince il secondo che gioca, perché può replicare le mosse del primo e fregarlo sempre».

«Ok, ottimo. Un gioco in cui vince il secondo giocatore si dice che è uguale a zero».

«E perché mai?».

«Pensa a un nuovo gioco, composto da due pile uguali e una terza diversa dalle prime due. Le due pile uguali sono, in un certo senso, inutili: se uno gioca su una delle due, l'altro replica la mossa sull'altra pila. Alla fine è come se non ci fossero, si possono cancellare».

«Fammi capire meglio».

«Pensa a questo gioco: (3,42,42). Quello che voglio dirti è che questo gioco è equivalente a (3), le due pile da 42 sono inutili».

«Ma prima abbiamo detto che in un gioco tipo (3) vince il primo giocatore, no?».

«Esatto, cancellando la pila intera. E, infatti, se tocca a me muovere io cancello la prima pila, e ti passo questo: (0,42,42), cioè (42,42)».

«Che è il gioco di prima».

«Nel quale vince il secondo giocatore».

«Ma siccome il primo sono diventato io, vinci tu».

«Proprio così. Il gioco su due pile uguali può essere simmetrico, e quindi alla fine quelle due pile sono inutili. Potremmo dire che la somma (3) + (42,42) è uguale a (3)».

«E quindi (42,42) è come se fosse nullo! Ecco perché si dice che quel gioco è uguale a zero».

«Esatto. La prossima volta vediamo di capire la faccenda del fuzzy».

venerdì 5 luglio 2013

Sono una persona anzyana

C'è una cassettiera, piccolina, di quelle per componenti elettronici, coi cassettini verdi componibili, che possiedo da quando ero alle medie, e che ho usato sempre pochissimo. Mi ha sempre seguito nei traslochi, è sempre stata posizionata in un luogo nascosto ma noto.

In uno di quei cassetti ho conservato cose che potrebbero sempre servire, nel senso più ampio possibile del termine. Ovvero: bigliettini che mi ero fatto a scuola per aiutare la memoria durante le situazioni impreviste. Ne ho trovati tre che meritano di essere immessi nella memoria globale del pianeta.

Eccoli.



Questo era per il compito finale di quinta di letteratura latina, direi.


Questo, delle dimensioni di un francobollo, ha quel colorino marroncino-grigino perché è stato per un po' di tempo dentro al mio astuccio, in mezzo alle matite e alla grafite.



Si noti, in questo reperto, una frase in basso non scritta dal sottoscritto, frase che recita TUA DEL 4 S. R.


Questo è il retro del precedente. Si noti l'ottimizzazione dello spazio.