«Bel nome».
«Abbiamo un cavaliere (cioè un cavallo degli scacchi) che si può muovere su una scacchiera, che possiamo immaginare infinita andando a destra e verso il basso».
«Ok, e perché è distratto?».
«Perché perde le cose. Al momento ha perso sei scatole, che abbiamo messo da parte. Scopo del gioco è quello di fare arrivare il cavaliere in una delle quattro caselle d'angolo in alto a sinistra e raccogliere tutte le scatole. Le caselle in questione sono queste:».
+---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 3 | 4 | 5 | 6 | 7 | +---+---+---+---+---+---+---+---+ | 0 | 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 | +---+---+---+---+---+---+---+---+
«Lo zero all'interno cosa significa?».
«Ho già messo il nimero corrispondente a quella posizione: lì il gioco relativo alle mosse del cavaliere è finito».
«Ma si possono ancora raccogliere scatole?».
«Sì, in pratica abbiamo due giochi: una pila di 6 scatole, e il cavaliere sulla scacchiera. Ogni giocatore può muovere in uno dei due giochi, o prende delle scatole o muove il cavaliere».
«Ok».
«E, naturalmente, del gioco riguardante la presa delle scatole sappiamo tutto, è un Nim composto da una pila di sei elementi, quindi vale *6».
«Bene».
«Il problema è capire quali nimeri associare alle posizioni del cavallo sulla scacchiera, ma con la teoria di Sprague-Grundy non abbiamo problemi a fare i calcoli. Rispetto agli scacchi, però, c'è una restrizione: il cavallo non può muovere dove vuole, ma solo nelle due caselle sopra di lui e nelle due alla sua sinistra. Questo per fare in modo che il gioco prima o poi termini».
«Insomma, se il cavallo si trova nella casella blu, può solo andare sulle caselle rosse, giusto?».
+---+---+---+---+---+ | | | 2 | | 4 | +---+---+---+---+---+ | | | 3 | 2 | 5 | +---+---+---+---+---+ | 2 | 3 | X | 1 | 6 | +---+---+---+---+---+ | | 2 | 1 | 0 | 7 | +---+---+---+---+---+ | 4 | 5 | 6 | 7 | 0 | +---+---+---+---+---+
«Giusto. Ora proviamo a calcolare il nimero corrispondente alla casella rossa».
+---+---+---+---+---+---+---+---+ | 0 | 0 | | 3 | 4 | 5 | 6 | 7 | +---+---+---+---+---+---+---+---+ | 0 | 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 | +---+---+---+---+---+---+---+---+
«E come facciamo?».
«Facciamo un elenco delle caselle in cui il cavallo può muoversi».
«Ce n'è una sola, quella arancione in seconda riga, prima colonna».
«Bene, quindi il cavallo nella casella rossa corrisponde a un gioco fatto così: G = {*0}».
«Uhm».
«Ricorda che un gioco è definito dalle sue mosse, se il cavallo si trova nella casella rossa c'è una sola mossa possibile, il cui valore è 0».
«Ah, già».
«Ora, applicando la regola del Mex, possiamo calcolare il valore della casella: quanto vale Mex({*0})?».
«È il minimo intero non negativo non compreso nell'elenco delle mosse del gioco, quindi direi 1».
«Più precisamente, *1. Ma nella tabella mettiamo solo 1. Per simmetria mettiamo 1 anche nella casella alla terza riga, prima colonna».
+---+---+---+---+---+---+---+---+ | 0 | 0 | 1 | 3 | 4 | 5 | 6 | 7 | +---+---+---+---+---+---+---+---+ | 0 | 0 | | 2 | 5 | 4 | 7 | 6 | +---+---+---+---+---+---+---+---+ | 1 | 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 | +---+---+---+---+---+---+---+---+
«Sì, giusto, i calcoli sono gli stessi. Ora calcoliamo il valore della nuova casella rossa?».
«Sì, vai».
«Vediamo: ci sono due caselle verso le quali il cavallo può muoversi: quella nell'angolo in alto a sinistra, di valore 0, e quella in terza riga, prima colonna, di valore 1».
«Vuoi dire *1».
«Ah, già. Quindi se il cavallo si trova nella casella rossa siamo di fronte a un gioco G = {*0, *1}. Quindi il Mex dovrebbe essere 2».
«Dici bene: mettiamo il valore nella tabella. Già che ci sono te la riempio un po' io, e ti faccio fare un altro calcolo. Cosa mettiamo ora nella casella rossa?».
+---+---+---+---+---+---+---+---+ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 1 | 2 | 2 | 2 | 3 | 7 | 4 | 5 | +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | | 7 | 6 | 5 | 4 | +---+---+---+---+---+---+---+---+ | 0 | 0 | 3 | 7 | 0 | 1 | 2 | 3 | +---+---+---+---+---+---+---+---+ | 0 | 0 | 7 | 6 | 1 | 0 | 3 | 2 | +---+---+---+---+---+---+---+---+ | 1 | 1 | 4 | 5 | 2 | 3 | 0 | 1 | +---+---+---+---+---+---+---+---+ | 1 | 1 | 5 | 4 | 3 | 2 | 1 | 0 | +---+---+---+---+---+---+---+---+
«Ah, ora sono possibili tutte e quattro le mosse del cavallo. Stiamo giocando a un gioco G = {*0, *2, *2, *0}; ho scritto i nimeri due volte perché anche se a due a due sono uguali, le caselle su cui posso muovere sono diverse».
«Va bene, non c'è problema. Ora il Mex: quanto vale?».
«Mex(G) = *1, quindi in quella casella ci va un 1, vero?».
«Molto bene! Ecco la tabella completa:».
+---+---+---+---+---+---+---+---+ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 1 | 2 | 2 | 2 | 3 | 2 | 2 |...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 1 | 4 | 3 | 2 |...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 3 | 4 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 3 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 2 |...|...|...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 |...|...|...|...|...|...| +---+---+---+---+---+---+---+---+
«Non è proprio completa, eh».
«Eh, no, per sapere cosa mettere nelle caselle coi puntini dovrei prolungare un po' le prime righe e le prime colonne».
«E perché hai colorato quelle quattro caselle con un colore diverso?».
«Perché, anche se ancora non si vede tanto, la tabella ricomincia uguale a sé stessa a partire da quelle quattro caselle».
«Ah, Ma ora giochiamo anche?».
«Sì, ti lascio scegliere dove posizionare il cavallo, e io farò la prima mossa.».
«Vabbé, tanto so già che perderò».
«Ehm».
«Diciamo che metto il cavallo qua:».
+---+---+---+---+---+---+---+---+ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 1 | 2 | 2 | 2 | 3 | 2 | 2 |...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 1 | 4 | 3 | 2 |...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 3 | 4 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 3 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 2 |...|...|...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 |...|...|...|...|...|...| +---+---+---+---+---+---+---+---+
«Allora io tolgo 3 elementi dalla pila delle scatole: ora ne rimangono 3».
«Uhm, allora tolgo un elemento anche io dalla pila delle scatole».
«Ok, allora rimangono due elementi, e io muovo qua:».
+---+---+---+---+---+---+---+---+ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 1 | 2 | 2 | 2 | 3 | 2 | 2 |...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 1 | 4 | 3 | 2 |...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 3 | 4 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 3 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 2 |...|...|...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 |...|...|...|...|...|...| +---+---+---+---+---+---+---+---+
«Allora io muovo in questa casella:».
+---+---+---+---+---+---+---+---+ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+ | 1 | 2 | 2 | 2 | 3 | 2 | 2 |...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 1 | 4 | 3 | 2 |...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 3 | 4 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 0 | 0 | 2 | 3 | 0 | 0 |...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 | 2 | 2 |...|...|...|...| +---+---+---+---+---+---+---+---+ | 1 | 1 |...|...|...|...|...|...| +---+---+---+---+---+---+---+---+
«E io tolgo una scatola, ora ne rimane una».
«E io ho perso: se prendo la scatola, tu muovi il cavallo in una delle quattro caselle di valore zero, se invece faccio io quella mossa, tu prendi la scatola. Come hai fatto?».
«Ho usato la teoria di Sprague-Grundy. Quando tu hai scelto la posizione del cavallo, in pratica mi hai lasciato un gioco G1 = {*0, *1, *2, *2}».
«Corrispondente alle quattro possibili mosse che poteva fare il cavallo, giusto».
«E poi mi hai lasciato anche le sei scatole, cioè un gioco G2 = *6».
«Una pila Nim da 6 elementi, giusto».
«Per la teoria di Sprague-Grundy, anche G1 è equivalente a una pila Nim, no?».
«Vero anche questo, si usa il Mex: G1 = *3, il valore scritto nella casella».
«Perfetto. In pratica stavamo giocando a un Nim con due pile: (3,6)».
«Ah! Sappiamo che vince il primo giocatore».
«Certo, per questo ho cominciato. E la strategia è stata quella di passarti sempre due pile uguali. Se riguardi le mosse, ho fatto in modo che G1 e G2 avessero sempre lo stesso valore».
«E siccome un Nim con due pile uguali è nullo, ho perso…».
«Infatti».
«Bella roba. Ma qual è la strategia vincente per un Nim un po' più complicato?».
«Bella domanda».
Nessun commento:
Posta un commento