Cosa devi sapere sui giochi a due

Nim

Il Nim si gioca fra due giocatori, che a turno, tolgono da tre file orizzontali di oggetti (che possono essere monete, pedine, gettoni, fiammiferi, ecc.) quanti oggetti si vuole ma sempre, in una mossa, da una sola fila. Vince chi togli l'ultimo oggetto. Generalmente gli oggetti sono 12 posti su tre file composte da 3, 4, 5 oggetti.

In questo gioco esistono delle configurazioni vincenti e il giocatore che riesce a lasciare dopo una sua mossa una di queste configurazioni e poi in seguito se gioca razionalmente può vincere facilmente. Ad esempio, un giocatore può sempre vincere se dopo una sua mossa riesce a far rimanere 0 pedina in una fila, 1 pedine in una seconda e 1 nella terza oppure 0 pedine in una fila 2 pedine in una seconda e 2 pedine nella terza oppure 0 pedina in una fila, 3 pedine in una seconda e 3 nella terza. In generale, un giocatore può sempre vincere se dopo la sua mossa lascia due file con lo stesso numero di pedine in ciascuna.

Può ancora vincere se dopo una sua mossa riesce a far rimanere 1 pedina in una fila, 2 pedine in una seconda e 3 nella terza

Di questo gioco il matematico Charles Leonard Bouton ha scoperto una strategia vincente basata sul sistema binario. Per Bouton ogni configurazione di pedine è o sicura o pericolosa. Per un giocatore una configurazione è sicura se gli garantisce la vittoria altrimenti è pericolosa. Per stabilire se una configurazione è sicura o pericolosa bisogna scrivere il numero delle pedine di ciacuna riga in notazione binaria. Se ogni colonna, sommata nel modo decimale, da per totale zero o un numero pari la configurazione è sicura altrimenti è pericolosa. Inoltre, è sempre possibile ottenere una configurazione sicura a partire da una pericolosa, mentre è impossibile farlo partendo da una configurazione sicura. Secondo Bouton la vittoria del primo giocatore dipende dalla configurazione iniziale: se questa ha almeno una colonna somma dispari allora vince se gioca razionalmente. Vediamo praticamente come il primo giocatore può vincere la partita applicando il metodo di Bouton:

• Consideriamo la situazione iniziale e scriviamo in notazione binaria il numero delle pedine di ciascuna riga e eseguiamo la somma delle colonne:

  

  Per il primo giocatore, la configurazione iniziale, è pericolosa perchè la somma della colonna intermedia è dispari. Per rendere sicura la configurazione delle pedine il primo giocatore deve togliere due pedine nella prima fila:

  

• Ora, qualunque mossa faccia il secondo giocatore non riuscirà a ottenere una configurazione sicura per se. Ad esempio supponiamo che tolga 2 pedine dalla terza fila.

  

• Per rendere sicura la configurazione delle pedine il primo giocatore deve togliere due pedine nella seconda fila:

  

• Anche in questo caso, qualsiasi mossa effettua il secondo giocatore non riuscirà a ottenere una configurazione sicura per se. Ad esempio supponiamo che tolga 1 pedine dalla terza fila.

  

• Per rendere sicura la configurazione delle pedine il primo giocatore deve togliere una pedine nella prima fila:

  

• Naturalmente, il secondo giocatore con una qualsiasi sua mossa non può rendere la configurazione sicura per se e il primo giocatore vincerà facendo mosse simmetriche rispetto alle mosse del secondo giocatore.