All'apparire sul mercato dei primi calcolatori elettronici (circa quarant'anni fa), nelle mostre specializzate per stupire i visitatori venivano presentati i computer come giocatori imbattibili in particolari giochi basati su deduzioni logiche. Fra i molti in voga in quegli anni, uno di quelli di maggior successo fu senz'altro il gioco del NIM.
Di questo gioco esistono numerose versioni, anche notevolmente diverse, ma prenderemo qui in considerazione solo quella che prevede 3 pile di oggetti dalle quali può essere prelevato un numero qualsiasi di oggetti ma da una sola pila. Vince chi prende l'ultimo oggetto (o quelli rimanenti nell'ultima pila non vuota).
Eccone subito una moderna versione fra quelle disponibili in Internet, che mostra 3 pile di focaccine (da prelevare con un colpo di mouse). Come si diceva vince chi riesce a prendere l'ultima.
L'invito è ovviamente quello di provare ma per quanto vi abbuffiate, sarà difficile che prendiate proprio l'ultima !

La strategia del gioco

Il gioco ha origini antiche, sembra cinesi, e conosciuto in Europa fin dal 16mo secolo. Fu studiato a fondo all'inizio del '900 dal matematico inglese Charles L. Bouton, che fissò le regole della strategia vincente.
La cosa sorprendente è che la strategia vincente si basa sulla rappresentazione binaria dei rispettivi numeri di oggetti presenti nelle pile. Per questo credo che l'argomento sia particolarmente interessante per i frequentatori di EY, che dovrebbero conoscere l'algebra booleana e la numerazione binaria.
Consideriamo un esempio con numeri 6,7 e 5 di oggetti nelle rispettive pile.
Se rappresentiamo questi numeri in sistema binario e di ogni loro bit facciamo una somma binaria senza riporto (operazione nota come somma-NIM) otteniamo un risultato diverso da zero (infatti risulta 4 in decimale).

La strategia vincente è quella di far risultare "zero" questa somma (quindi nel caso specifico di togliere 4 oggetti). Qualsiasi altra mossa faccia l'avversario, non potrà azzerare la somma, quindi nelle mosse successive basterà continuare a riportare a zero tale somma, sino alla fine del gioco.
Per stabilire quanti pezzi e da che pila toglierli, occorre applicare la somma-NIM tra il risultato (S) precedente ed il codice binario delle singole pile (a,b,c).
Vediamo quest'altro caso:

E'evidente che non possiamo togliere 7 (S) da nessuna delle pile!
Procediamo allora alla somma-NIM fra S e la prima pila (a=6). Otteniamo "001",cioè 1.
Fra S e la seconda (b=4). Otteniamo "011", cioè 3.
Fra S e la terza (c=5). Otteniamo "010", cioè 2.
Questo significa che per arrivare alla condizione vincente (S=0) dobbiamo
-far diventare a=1 (togliendo quindi 5 pezzi), oppure
-far diventare b=3 (togliendo quindi 1 pezzo), oppure
-far diventare c=2 (togliendo quindi 3 pezzi)

L' XOR

La somma-NIM è facilmente realizzabile con gli elementi logici noti come XOR e corrispondenti all'operazione di OR esclusivo (eXclusive OR), nella quale viene azzerata l'uscita nel caso di presenza contemporanea dei 2 ingressi. Gli integrati possono essere ad es. del tipo CMOS4070 (quad XOR gates).
Con un simulatore di circuiti (ad es. Multisim) è facile verificare le combinazioni vincenti. Ecco la simulazione del caso della prima tabella, in cui il numero di pezzi nelle rispettive pile a,b,c, vengono codificati in codici binari con dip-switches e "sommati" da XOR. I 3 segnalatori d'uscita indicano, se accesi, ii numero di pezzi da togliere (con la verifica detta) oppure, se tutti spenti, la combinazione vincente.

E' evidente che su queste basi, mettendo contatori al posto dei selettori e file di LED per indicare gli oggetti, potrebbe essere impostato un progetto di giocatore in logica cablata.
(Ecco un'idea per i molti studenti che cercano argomenti insoliti per le "tesine" di fine anno!).

L'implementazione al computer

E' tuttavia molto più semplice fare un programma per calcolatore che, come nell'esempio iniziale, sia praticamente imbattibile da chi non conosce (o non applica correttamente) le regole esposte.
Segnalo che un programma del genere è anche illustrato in Wikipedia (pure se giocato al contrario, cioè perdente chi prende l'ultimo oggetto).
Diversi anni fa ci ho provato anch'io, programmando in VisualBasic3, ed ecco il risultato:

Gli oggetti possono essere tolti uno ad uno, clickando con il mouse sulla base delle singole pile, dopodiché deve essere richiesta la mossa del calcolatore. (chi fosse interessato ad utilizzarlo, può richiederlo al mio indirizzo e-mail nel Sito, ma avverto che è necessario installare anche il programma interprete di VisualBasic3).