«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».
Nessun commento:
Posta un commento