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».

Nessun commento: