Laboratorio: Il Gioco del Nim
scopo: Usare le nozioni di bit di parità in un gioco di strategia
materiale necessario:
Penne, carte o fiammiferi... Qualsiasi oggetto purché se ne abbiano a disposizione almeno 16...
argomenti avanzati:
algoritmi, OR esclusivo, controllo di parità
il Gioco del Nim appartiene alla tradizione dei giochi "poveri": bastano 16 fiammiferi (o carte o sassi o qualsiasi altro oggetto).
Si dispongono gli oggetti come in figura, si gioca in due e le regole sono molto semplici:
- Si muove a turno.
- Ad ogni mossa si prelevano quanti fiammiferi si vuole, purché stiano sulla stessa linea.
- Perde chi pende l'ultimo fiammifero dal tavolo.
Esistono diverse citazioni di questo gioco anche nel cinema. Vedi una scena presa da "L'anno scorso a Marienbad":
La strategia vincente ha ancora a che fare con il sistema binario... (vedi sotto)
Ma il gioco del Nim ha un'altra importante connessione con l'informatica: il primo Computer Game della
storia, il Ferranti NIMROD, fu creato proprio per giocare (e vincere) a Nim. Fu esposto al "Festival of Britain" nel 1951. Era largo 3,6 metri (12 feet), profondo 2,7 metri (9 feet) e alto 1,5 metri (5 feet).
La mossa vincente necessita la conversione in binario di ogni riga. Si esegue poi l'OR esclusivo (XOR) dei bit in colonna
e si tolgono gli oggetti in modo da azzerare tutti gli XOR.
Il pannello del Nimrod (vedi figura sotto), infatti, riporta sia le lampadine che rappresentano gli oggetti (sezione centrale), sia il pannello di lampadine con la rappresentazione
binaria delle lampadine accese (block schematic).
Sulla sinistra, invece, è riportato l'algoritmo che decide la mossa della macchina che viene riportato di seguito.
Per provare a giocare si vada allo script NimRod
Nota: Nella versione "che prende l'ultimo perde", quando una sola riga conta pià di un oggetto, si deve invertire la strategia!
