De Econometrist

De Econometrist neemt een statistische kijk op de wereld.

Wiskunde

Kamertje Verhuren met Nimbers

  • Het spel kamertje verhuren is equivalent aan een ander spel. Dit spel heet “Strings and Coins”. Strings and Coins werkt door middel van touwtjes die vastzitten aan muntjes. De bedoeling hierbij is om uiteindelijk aan het eind 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. Een voorbeeld van een spel kamertje verhuren omgezet naar een spel Strings and Coins is hieronder te zien.  

Ieder kamertje correspondeert met een muntje en ieder lijntje met een doorgeknipt touwtje.

Nimstring

Het spel Nimstring heeft precies dezelfde vorm als Strings and Coins. Echter is het doel van het spel wel anders. Bij Nimstring is het de bedoeling dat je degene bent die niet het laatste muntje pakt. Bij Kamertje Verhuren is dit een erg belangrijk onderdeel, denk aan The Long Chain Rule (zie eerste artikel uit de serie Kamertje Verhuren). Door delen van het spel kamertje verhuren om te zetten in een spel Nimstring is het 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 (zie tweede artikel uit de serie Kamertje Verhuren).

Grijpbare muntjes

In het spel Nimstring is onderscheid te maken tussen de muntjes. Het ene muntje is grijpbaar, het andere muntje niet. Een grijpbaar muntje is een muntje die door middel van een touwtje weg te knippen vrij komt. Het muntje heeft vervolgens geen touwtje meer aan zich gebonden. Er zijn zes situaties die één of meerdere grijpbare muntjes bevatten. Hieronder volgen 4 van deze situaties.

In de verschillende situaties is het spel G een willekeurig Nimstringveld.

In de eerste situatie is te zien dat door touwtje X door te knippen het muntje vrij komt. Vervolgens moet een zet gedaan worden in het speelveld G. In dit geval is het volkomen overbodig voor de speler om te weten of spel G een N- of P-positie heeft. Wanneer hij namelijk er voor kiest om niet X door te knippen moet hij alsnog in spel G beginnen. Het kan geen kwaad om het muntje te pakken, er wordt door de speler geen nadeel aan ondervonden.

Voor de tweede situatie geldt hetzelfde. Door touwtje X niet door te knippen moet de speler alsnog beginnen in spel G. De speler ondervindt er geen nadeel van om de grijpbare muntjes te pakken.

In de derde situatie geldt dit ook. Zowel touwtje X als Y kan worden doorgeknipt zonder er nadeel van te ondervinden.

Ook in de vierde situatie geldt dat de speler op den duur tóch de eerste zet in spel G moet gaan doen, ook hier kan hij/zij zonder problemen het grijpbare muntje pakken.

Kortom, in deze vier situaties zijn de grijpbare muntjes door de speler te pakken, zonder dat hij/zij daar nadeel van ondervindt. De speler moet uiteindelijk toch de eerste zet in spel G gaan doen.

De resterende 2 situaties zijn een stuk interessanter. In deze twee situaties bevindt de speler zich namelijk in een luxe positie. Zie de afbeelding hieronder.

In beide situaties heeft de speler niet 1, maar 2 opties. Dit was echter niet zo in de voorgaande 4 situaties. Daarin was er voor de speler eigenlijk geen keuze. Nu wel.

In situatie 5 heeft de speler de volgende 2 opties;

– De speler knipt touwtje X door, vervolgens knipt hij het touwtje dat vastzit aan de grond (Y) door. Daarna doet hij de eerste zet in spel G.

– De speler knipt het touwtje dat vast zit aan de grond door (Y). De andere speler wordt zo gedwongen om als eerste van de twee een zet te doen in spel G.

In situatie 6 heeft de speler de volgende 2 opties;

-De speler knipt touwtje X door, vervolgens knipt hij Y door enz. Daarna doet hij de eerste van de twee spelers een zet in spel G.

-De speler knipt touwtje Y door. De andere speler wordt zo gedwongen om als eerste van de twee spelers een zet te doen in spel G.

Kortom, in deze situaties heeft de speler de keuze om touwtje X door te knippen en te beginnen in G, óf om touwtje Y door te knippen en de andere speler te laten beginnen in G. In deze 2 situaties is het daarom wél van belang om te kijken naar spel G. De winnende strategieën voor deze situaties zijn dus afhankelijk van de N/P-positie van spel G;

– Wanneer spel G een N-positie is, is de winnende strategie om touwtje X door te knippen zodat de speler begint in G.

– Wanneer spel G een P-positie is, is de winnende strategie om touwtje Y door te knippen zodat de andere speler geforceerd wordt te beginnen in G.

Nimbers in Nimstringvelden

Aan elk Nimstringveld kan een waarde worden gegeven. Deze waarde is een nimber. De nimber van een Nimstringveld kan worden bepaald door de MEX van de waardes die boven ieder afzonderlijk lijntje staat. Deze waarde correspondeert met de nimber van het totaalspel die verkregen wordt door dit touwtje weg te knippen.

Om de waarde van een Nimstringveld te berekenen geldt:

  1. De nimber van een leeg veld is 0 (★0)
  2. De nimber van een Nimstringveld met grijpbare munten als die uit de eerste
    vier beschreven situaties is de nimber uit het spel G.
  3. De nimber van een Nimstringveld met grijpbare munten als de laatste twee
    situaties is een loony (☽)
  4. De nimber van een Nimstringveld zonder grijpbare muntjes is gelijk aan de
    MEX van de waardes van de afzonderlijke lijntjes

De nimber geeft zetten aan waarin de andere speler kan kiezen of hij muntjes pakt of zijn tegenstander dwingt om de muntjes te pakken.

Een kan in de MEX functie worden gezien als ∞. De loony kan dus buiten beschouwing worden gelaten bij de MEX functie. Immers: MEX(0,1,2,3,4,5,∞) = MEX(0,1,2,3,4,5) = 6. Zo geldt in het algemeen voor MEX(a,b,c,☽) = MEX (a,b,c).

Nimber berekening Nimstringveld

Om de nimbers van Nimstringvelden te berekenen is het belangrijk om de basis goed te snappen. Om de nimber te berekenen kijk je steeds een stap vooruit. Bij grote Nimstringvelden is het daarom lastig de nimber te bepalen. Dit komt omdat je voor ieder afzonderlijk touwtje de nimber moet bepalen. En om deze waarde te bepalen is het nodig om te weten wat de nimber is van het veld wat wordt gevormd wanneer dit touwtje wordt weggeknipt. Maar om de nimber van dat gevormde veld te bepalen, is het nodig om de nimbers van de afzonderlijke touwtjes te weten enz. Om de nimber van het Nimstringveld te berekenen is het dan ook nodig om het Nimstringveld in steeds kleinere en meer velden onder te verdelen. Hieronder volgen drie eenvoudige nimstringvelden (A, B, C) waar de nimber van bepaald wordt:

Toelichting A:

De nimber van het touwtje aan het muntje is te zien als . De MEX van het veld is dan; MEX{} =  0. Hieruit volgt dat de nimber van het totaal veld gelijk is aan  0. Omdat de nimber van het nimstringveld 0 is, bevindt men zich in een P-positie, ofwel de verliezende positie. Het is in deze situatie niet mogelijk om het spel te winnen.

Toelichting B:

Door één van beide touwtjes weg te knippen ontstaat het nimstringveld A. De nimber van A is 0, zoals hierboven reeds beschreven. Dus beide touwtjes hebben nimber 0. De MEX van het veld is dan; MEX(0, 0)  = 1. Hieruit volgt dat de nimber van het totaalveld gelijk is aan 1.  Omdat de nimber van het nimstringveld 1 is (1 ≠ 0), bevindt men zich in een N-positie, ofwel de winnende positie. De winnende zet is dan om één van de twee touwtje met nimber 0 weg te halen, zodat de tegenstander zich in een P-positie bevindt.

Toelichting C:

Door het middelste touwtje weg te knippen ontstaat 2x veld A met nimber 0 . Dus de nimber van het touwtje is 0. Door één van de twee andere touwtjes weg te knippen ontstaat een veld waarin de volgende speler de keuze heeft om de grijpbare muntjes te pakken, óf ze af te wijzen. De Mex van het veld is dan; MEX{0, ☽, ☽ } = 1. Hieruit volgt dat de nimber van het totaalveld gelijk is aan 1. Omdat de nimber van het nimstringveld 1 is (1 ≠ 0), bevindt men zich in een N-positie, ofwel de winnende positie. De winnende zet is dan om het touwtje met nimber 0 weg te halen, zodat de tegenstander zich in een P-positie bevindt.

Het is goed voor te stellen dat naarmate het nimstringveld groter is, het meer tijd kost om de nimber van het totaalveld te bepalen. Gelukkig zijn de nimbers van verschillende basisvelden al een keer uitgewerkt. Er hoeft daardoor gelukkig niet iedere keer worden berekend wat de nimber is van het totaalveld.

Kortom, bij het spel Kamertje Verhuren draait het om controle en hoe deze controle te behouden. Soms moet je kamertjes opofferen om er voor te zorgen dat je niét degene bent die de lange ketens opent. De tactieken die er voor zorgen dat dit lukt is de relatief eenvoudig toe te passen Long Chain Rule, óf de uitgebreide complexe manier a.d.h.v nimbers. Welke tactiek heeft jou voorkeur?

—————————————————————————————————————————–

Dit artikel is geschreven door Mark Woelders

 

 

Deel dit artikel:

By Daniele Zedda • 18 February

← PREV POST

By Daniele Zedda • 18 February

NEXT POST → 34
Share on