NIM
Il "Nim" e un gioco matematico, probabilmente di origine cinese, molto antico che viene giocato dai ragazzi con pezzetti di carta o dai grandi con le monetine sul banco dei bar. Nella versione più popolare del gioco vi sono 12 monetine disposte su tre righe in questo modo:
Le regole sono semplici: i giocatori alternativamente tolgono un o più monete per volta, ogni volta da una sola riga orizzontale; chi prende l' ultima moneta vince. Il gioco può anche essere giocato all' inverso: chi prende l' ultima moneta perde.
Un buon giocatore scopre presto che nell' una o nell' altra forma del gioco egli può sempre vincere se una delle sue mosse fa restare una moneta in una riga, due in una seconda e tre in una terza. Il primo giocatore ha la vittoria sicura se alla prima mossa prende due monete dalla riga superiore e in seguito gioca "razionalmente".
Non c' è nulla di strano nella precedente analisi, ma questo ragionamento può venir generalizzato per un numero qualsiasi di righe contenenti numeri qualsiasi di pedine e che una strategia assurdamente semplice, basata sui numeri binari, avrebbe consentito a chiunque di giocare una partita perfetta. Un' analisi, completa di dimostrazioni, fu pubblicata per la prima volta da Charles Leonard Bouton, professore incaricato di matematica all' università di Harward. Fu lo stesso Bouton a dare il nome di Nim, presumibilmente con riferimento all' arcaico verbo inglese che significa rubare, portar via.
Dato che i computer lavorano con il sistema binario non è difficile fare un programma per fargli giocare una partita perfetta di Nim, o costruire una macchina speciale allo scopo.
Edward U. Condon, già direttore del National Bureau of Standard, ora a capo del Dipartimento della fisica alla Washington University di St. Luis, collaborò all' invenzione della prima di tali macchine. Brevettata nel 1940 sotto il nome di Nimatron, fu costruita dalla Westinghouse Electric Corporation e presentata nell' edificio della Westinghouse alla Fiera mondiale di New York. Essa giocò 100.000 partite e ne vinse 90.000. La maggior parte delle sue sconfitte fu provocata dai suoi assistenti per dimostrare agli spettatori scettici che la macchina poteva esser battuta.
Nel 1941 una macchina giocatrice di Nim molto perfezionata fu progettata da Raymond M. Redheffer, ora assistente di matematica all' Università di California a Los Angeles. La machina di Redheffer ha la stessa capacità di quella di Condon (quattro righe, con sette gettoni al massimo per ciascuna), ma mentre il Nimatron pesava una tonnellata e richiedeva dei costosi rel&eacut, la macchina di Redheffer pesava tre chili ed usava solo quattro interruttori rotanti.
Più recentemente un robot giocatore di Nim chiamato Nimrod è stato presentato al Festival d' Inghilterra e dopo alla Fiera commerciale di Berlino. Secondo una relazione di A. M. Turing, la macchina era tanto popolare che i visitatori «ignoravano completamente un bar all' estremità opposta della sala dove si poteva bere gratuitamente e fu necessario richiedere un particolare servizio d' ordine di polizia per tenere a bada la folla. La macchina divenne ancor più popolare dopo che sconfisse il ministro dell' economia, Dr. Erhard, in tre partite».
Il testo che avete appena letto è stato tratto da Martin Gardner, Mathematical puzzles and diversions.
Ecco ora, in meno di un grammo, un algoritmo in linguaggio Turbo Pascal che implementa una macchina giocatrice di NIM:
Clicca quì per vedere il sorgente!
Strategia
Nella terminologia di Bouton ogni combinazione di pedine nel gioco generalizzato è o "sicura" o "pericolosa". Se la situazione lasciata da un giocatore dopo la propria mossa garantisce la vincita al giocatore, la situazione è sicura. Diversamente è pericolosa. Ogni posizione pericolosa può esser resa sicura con una mossa adatta. Ogni posizione sicura può esser resa pericolosa da qualsiasi mossa. Per giocare razionalmente, perciò, un giocatore deve muovere in modo che ogni posizione pericolosa lasciatagli dall' altro sia cambiata in una posizione sicura.
Per determinare se una posizione è sicura o pericolosa, i numeri di ogni riga vengono scritti in notazione binaria. Se ogni colonna dà per totale 0 o un numero pari, la posizione è sicura. Altrimenti no.
Per applicare l' analisi binaria alla posizione iniziale del Nim a 3, 4, 5 riportiamo dapprima le righe in notazione binaria nel modo seguente:
| Pedine |
Notazione binaria |
| 3 |
0 |
1 |
1 |
| 4 |
1 |
0 |
0 |
| 5 |
1 |
0 |
1 |
| Totali |
2 |
1 |
2 |
La colonna intermedia ha come totale 1, un numero dispari, che ci dice che la combinazione è pericolosa. Deve perciò essere resa sicura dal primo giocatore. Ciò si ottiene prendendo due pedine dalla riga superiore. La mossa trasforma il numero binario superiore in 001, eliminando così il numero dispari dai totali di colonna.
È utile ricordare che è possibile sempre vincere lasciando due righe con lo stesso numero di gettoni ciascuna. Da quel punto in poi basta semplicemente muovere in modo da mantenere uguali le due righe.
Esistono molte varianti di questo gioco: una di queste potremmo definirla Nim-inverso, ovvero le regole rimangono le stesse ma vince chi non prende l' ultima pedina. Non è difficile dimostrare che la strategia sopra descritta (leggermente modificata per lo scopo) funziona anche per questa variante di gioco.
Un' altra variante abbastanza diffusa impone di non poter prendere un numero di pedine superiore ad un fissato k. Anche in questo caso la strategia descritta è valida.
Il Tac Tix è una variante inventata da Piet Hein in cui le pedine vengono disposte a quadrato e possono essere tolte secondo le righe ma anche secondo le colonne (a differenza del Nim). Per questa variante non sono conosciute strategie che portano sicuramente alla vittoria.
