Nim

Het spel Nim is een spel dat waarschijnlijk al een paar duizend jaar geleden bedacht is in het Verre Oosten. Het spel wordt gespeeld door 2 personen. De opstelling van het spel bestaat uit een willekeurig aantal verzamelingen (lucifers, muntjes, papiertjes enz.) met een willekeurig aantal elementen. Het doel van het spel is om er voor te zorgen dat jij degene bent die het laatste element pakt. Het spel heeft ook een misère versie. Hierbij doe je precies het tegenovergestelde, oftewel je moet er voor zorgen dat jij degene bent die niet het laatste element pakt. Er is maar 1 regel in het spel; om de beurt moet een speler een zelfgekozen aantal elementen van maximaal 1 verzameling pakken. Afbeelding 1: Voorbeeld opstelling spel Nim.

Winnende strategie Nim

De winnende strategie voor een spel Nim is relatief eenvoudig. Hieronder volgt het stappenplan voor het winnen van het spel:

1. Zet het aantal elementen per verzameling om in binaire getallen
   • Voorbeeld:
     • 1  is in het binaire stelsel 001
     • 2 is in het binaire stelsel 010
     • 3 is in het binaire stelsel 011
     • enz.
2. Tel het aantal elementen van elke verzameling binair zonder overdracht met elkaar op
3. Zorg er voor dat je één van de verzamelingen zo manipuleert dat de som van de binaire optelling van de verzamelingen 0 is
4. Dat manipuleren kan d.m.v. een X aantal elementen uit een verzameling te pakken
5. Dit blijf je doen totdat voor iedere verzameling G  geldt; G = {G1, G2, … Gk} = ∅, waar G = {G1, G2, … Gk} is gedefinieerd als de verzameling resterende zetten
6. Eenmaal deze strategie gehanteerd behoudt men de leiding in het spel

De leiding in een impartieel spel wordt door wiskundigen vaak beschreven als een N-positie. Een P-positie correspondeert met de verliezende positie. Van een N-positie kan je namelijk naar een P-positie of een andere N-positie, maar van een P- naar een andere P-positie is onmogelijk. Je kunt dit je voorstellen als een balans; als de balans eenmaal in evenwicht is en je moet iets aan één van beide kanten veranderen dan kan je de balans alleen maar uit evenwicht halen. Vandaar dat wanneer een speler zich in een N-positie bevindt, hij altijd de leiding in het spel kan behouden.
Hieronder volgt een voorbeeld van het spel Nim dat bestaat uit vijf verzamelingen, respectievelijk bestaande uit 5, 4, 3, 2, 1 elementen.

Afbeelding 2: Voorbeeld spel Nim waarbij speler 2 de winnende strategie hanteert en daardoor wint
Toelichting afbeelding 2
In de eerste rij van de tabel staan steeds het aantal elementen van elke verzameling in binaire getallen. Dit is gedaan voor verzameling 1 t/m 5. Achter het woord “TOT” staat steeds de som van de binaire getallen van alle verzamelingen. Wanneer de som van de binaire getallen (TOT) gelijk is aan 0 geeft dat een P–positie. Wanneer de som van de binaire getallen (TOT) ongelijk is aan 0 geeft dat een N-positie. Dit is voor elke positie in het spel weergegeven in de tweede  rij van de tabel. Speler 2 bevindt zich altijd in een N-positie en hanteert dan ook de winnende strategie (ervoor zorgen dat na iedere beurt TOT gelijk is aan 0).
In mijn vorige artikel heb ik de wet van Spraque en Grundy geïntroduceerd; “Ieder impartieel spel is equivalent aan het spel Nim.” Het spel Nim vormt dan ook de basis van ieder impartieel spel.

Nimbers

Het spel Nim in zijn simpelste vorm bestaat uit één verzameling elementen. Een voorbeeld van een spel nim in zijn simpelste vorm is de verzameling (0, 1, 2, 3, 4, 5, 6). Zoals reeds beschreven, een spel G is gedefinieerd als het aantal zetten dat gedaan kan worden G = (G1, G2, G3, … , Gk). In dit geval hebben we dus dat G = (0, 1, 2, 3, 4, 5). Je kan immers vanuit een verzameling van 6 elementen in één beurt naar 5, 4, 3, 2, 1 óf 0 elementen. Zo geldt in het algemeen voor het spel G dat bestaat uit 1 verzameling met n elementen; G = (G1, G2, G3, …, G(n-1)). Het spel G heeft dan nimber n, gedefinieerd als ★n. De nimber is dus het kleinste getal dat niet in de verzameling voorkomt. Wiskundig gezien is de nimber dus equivalent aan de “mex” van een verzameling. De “mex” staat namelijk voor de minimal excludent, oftewel het kleinste getal dat niet in een verzameling voorkomt. Hieronder volgen drie voorbeelden van een “mex operatie”:
mex(5, 18) = 0
mex(0, 1, 2, 3, 4, 5, 7) = 6
mex(∅) = 0
Voor nimbers gelden een aantal wetten. Deze zijn als volgt:

1. Het lege spel heeft ★0
2. Nimbers kunnen opgeteld worden d.m.v. binaire optelling zonder overdracht. De regels voor deze optelling zijn als volgt:
   1. 0 + 0 = 0
   2. 0 + 1 = 1
   3. 1 + 0 = 1
   4. 1 + 1 = 0
3. Voor twee spellen met nimber ★n en ★m geldt: ★(M + N)
4. Nimber ★0 correspondeert met een P positie
5. Nimber ★X correspondeert met een N positie, wanneer X niet gelijk is aan 0.

Strings and Coins / Nimstring in relatie met Kamertje Verhuren

Het spel Strings and Coins werkt d.m.v. touwtjes die vastzitten aan muntjes. De bedoeling hierbij is om uiteindelijk aan het einde van het spel de meeste muntjes te hebben. Dit kan je doen door touwtjes weg te “knippen”. Wanneer je het laatste touwtje dat vastzit aan een muntje hebt losgeknipt is het muntje van jou en moet je nog een keer een touwtje doorknippen. Dit spel is eigenlijk equivalent aan het spel Kamertje verhuren; een muntje correspondeert met een kamertje en een touwtje correspondeert met een lijntje.
Een voorbeeld van een spel kamertje verhuren omgezet naar een spel Strings and Coins is hieronder te zien.

Afbeelding 3: Kamertje Verhuren omgezet in Strings and Coins
Het spel Nimstring heeft precies dezelfde vorm als het spel Strings and Coins. Het doel van het spel is echter wel anders. Bij Nimstring is het de bedoeling dat je degene bent die niet het laatste muntje pakt. Bij het spel Kamertje Verhuren is dit een erg belangrijk onderdeel; denk aan het niet willen openen van een lange keten (zie mijn vorige artikel “Kamertje Verhuren”). Door delen van het spel kamertje verhuren om te zetten in een spel Nimstring is het daarom mogelijk geavanceerdere tactieken toe te passen. Dit komt doordat je elk Nimstringveld een waarde kan geven die gelijk is aan een nimber, oftewel een positie binnen het spel Nim. In mijn volgende artikel zal ik verder ingaan op de tactieken voor het spel Kamertje Verhuren aan de hand van Nimstringvelden.

Dit artikel is geschreven door Mark Woelders