NIM
In Pythagoras 60-6 werd het spel Nim aangehaald. In dit artikel gaan we met een variant van Nim aan de slag, om te zien of we met behulp van Python een optimale strategie kunnen bepalen.
In het traditionele spel Nim spelen de spelers $A$ en $B$ tegen elkaar. Er liggen $20$ lucifers op tafel. Om de beurt mogen $A$ en $B$ $1$ of $2$ lucifers wegnemen. Degene die de laatste lucifer(s) wegneemt verliest het spel. Wat is de beste strategie om te winnen?
Variant met een NimSet
Stel dat de spelregels enigszins worden aangepast. Vooraf spreken $A$ en $B$ af dat ze slechts $c$ lucifers mogen wegnemen voor $c \in NimSet$, waarbij $NimSet$ een eindige verzameling is. Bij het traditionele spel is $NimSet = {1,2}$. Maar nu gaan we $NimSet$ variëren. We spreken af dat $A$ altijd begint. $A$ en $B$ beginnen met $N$ lucifers. Wie wint wanneer? Opmerking: Als $1 \in NimSet$ dan zal altijd één van beiden winnen. Als $1 \notin NimSet$ kan in principe ook remise voorkomen, en dat maakt het Nimspel ingewikkelder. Daarom nemen we aan dat $1 \in NimSet$. $A$ en $B$ zijn aan elkaar gewaagd.
Hoe kunnen $A$ en $B$ een strategie bedenken om te winnen? We werken van klein naar groot. We lossen het probleem achtereenvolgens op voor $N = 1, 2, 3, \ldots$. Voor $N = 1$ is duidelijk dat $A$ verliest.
Het basisprogramma
In het specifieke voorbeeld hieronder kiezen we $NimSet = {1, 4, 9, 10}$. Als $N = 1$ dan verliest $A$, want $A$ moet $1$ lucifer weghalen. Hij neemt dus de laatste lucifer weg. Als $N = 2$, dan wint $A$. Door $1$ lucifer weg te halen ontstaat er een situatie waarbij $B$ zal verliezen. Zo kun je onderstaande tabel vullen.
| $\color{\white}{\ NimWinst\ }$ | $\color{\white}{2}$ | $\color{\white}{4}$ | $\color{\white}{5}$ | $\color{\white}{7}$ | $\color{\white}{9}$ | $\color{\white}{10}$ | $\color{\white}{11}$ | $\color{\white}{12}$ | $\color{\white}{13}$ | $\color{\white}{15}$ | $\color{\white}{\ldots}$ |
| $\color{\white}{\ NimVerlies\ }$ | $\color{\white}{1}$ | $\color{\white}{3}$ | $\color{\white}{6}$ | $\color{\white}{8}$ | $\color{\white}{14}$ | $\color{\white}{19}$ | $\color{\white}{21}$ | $\color{\white}{26}$ | $\color{\white}{32}$ | $\color{\white}{34}$ | $\color{\white}{\ldots}$ |
Het wordt steeds ingewikkelder om na te gaan of je zult winnen of verliezen. Tussen $26$ en $32$ zul je als beginspeler altijd winnen als volgt:
- $27$ betekent winst want $27 - 1 = 26$ betekent verlies
- $28$ betekent winst want $28 - 9 = 19$ betekent verlies
- $29$ betekent winst want $29 - 10 = 19$ betekent verlies
- $30$ betekent winst want $30 - 9 = 21$ betekent verlies
- $31$ betekent winst want $31 - 10 = 21$ betekent verlies
Je kunt ook in een hele lange rij met nullen en enen bijhouden of $A$ wint ($0$) of verliest ($1$). Zo’n lijst ($L$) ziet er als volgt uit:
| $\color{\white}{N}$ | $\color{\white}{1}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{4}$ | $\color{\white}{5}$ | $\color{\white}{6}$ | $\color{\white}{7}$ | $\color{\white}{8}$ | $\color{\white}{9}$ | $\color{\white}{10}$ | $\color{\white}{11}$ | $\color{\white}{12}$ | $\color{\white}{13}$ | $\color{\white}{14}$ | $\color{\white}{15}$ | $\color{\white}{16}$ | $\color{\white}{\ldots}$ |
| $\color{\white}{L}$ | $\color{\white}{1}$ | $\color{\white}{0}$ | $\color{\white}{1}$ | $\color{\white}{0}$ | $\color{\white}{0}$ | $\color{\white}{1}$ | $\color{\white}{0}$ | $\color{\white}{1}$ | $\color{\white}{0}$ | $\color{\white}{0}$ | $\color{\white}{0}$ | $\color{\white}{0}$ | $\color{\white}{0}$ | $\color{\white}{1}$ | $\color{\white}{0}$ | $\color{\white}{0}$ | $\color{\white}{\ldots}$ |
Mogelijk helpt deze voorstelling je om het onderstaande beter te begrijpen.
In de praktijk blijkt alleen $NimVerlies$ van belang om bij te houden. De waarden van $N$ die niet behoren tot $NimVerlies$ behoren automatisch tot $NimWinst$. Per waarde van $N$ controleren we of één van de waarden $N - c$ is bevat in $NimVerlies$, waarbij $c \in NimSet$. In dat geval is $N$ bevat in $NimWinst$, zo niet dan voegen we $N$ toe aan $NimVerlies$.
We gaan uit van de eindige verzameling $NimSet$. Laat $M$ de grootste waarde van $NimSet$ zijn. Of een zekere $N$ zal worden toegevoegd aan $NimVerlies$ is uitsluitend afhankelijk van de waarden $\{N-M, \ldots, N-1\}$ die bevat zijn in $NimVerlies$. Voor deze laatste $M$ waarden geldt dat iedere waarde al dan niet bevat zijn in $NimVerlies$. Er zijn hooguit $2^M$ verschillende mogelijkheden. Dat betekent dat hooguit na een lengte van $2^M$ zal de rij waarden van $NimVerlies$ in een herhaling terecht komen. Meestal zal de bovengrens van $2^M$ niet worden bereikt. We zijn uiteraard geïnteresseerd in de lengte van de periode, die we aanduiden met $PeriodeLen$. Daarnaast kan in principe in het begin nog een onregelmatigheid zitten (net zoals bij een breuk die gaat repeteren). Daarna ontstaat een herhalend patroon. Een interessante vraag is hoe groot dat eerste onregelmatige deel is. De lengte noteren we met $StartLen$. Een voorbeeld waarbij $StartLen$ groter dan $0$ is, is $NimSet = \{1, 6, 9\}$.
Het is natuurlijk nog wel de vraag hoe je $StartLen$ en $PeriodeLen$ berekent.
Berekening van StartLen en PeriodeLen
Als in $NimVerlies$ twee opeenvolgende en identieke intervallen te vinden zijn van een lengte groter dan $M$ dan heb je de periode gevonden. Maar in principe kan de periode kleiner zijn dan $M$. Om te controleren dat twee intervallen identiek zijn moeten de elementen van $NimVerlies$ in de twee intervallen op een afstand $PeriodeLen$ van elkaar vandaan liggen, maar ook de elementen van $NimWinst$. We maken gebruik van een slim trucje. We gaan kijken naar opeenvolgende verschillen van de elementen van $NimVerlies$. We bekijken eerst even het voorbeeld van hierboven met $NimSet = \{1, 4, 9, 10\}$.
| $\color{\white}{\ Verschil\ }$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{2}$ | $\color{\white}{6}$ | $\color{\white}{5}$ | $\color{\white}{2}$ | $\color{\white}{5}$ | $\color{\white}{6}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{2}$ | $\color{\white}{6}$ | $\color{\white}{5}$ | $\color{\white}{2}$ | $\color{\white}{5}$ | $\color{\white}{6}$ |
Nu is het een kwestie van zoeken naar een rij verschillen met som minimaal $M$ zo dat deze rij zich oneindig vaak herhaalt. In het voorbeeld hierboven is dat de verzameling $PeriodeDD = \{2, 3, 2, 6, 5, 2, 5, 6\}$. (We geven verschillen (in variabelennamen) consequent aan met $DD$ in de naam om het programma enigszins leesbaar te houden.) De som van deze verschillen is $31$, dus $PeriodeLen = 31$.
De procedure $CheckPeriodeDD$ controleert of de verschillen die voorkomen in $PeriodeDD$ minimaal tweemaal terugkeren in $NimDD$. Hierbij kan het voorkomen dat een aantal verschillen vooraan in de rij worden overgeslagen, omdat hier nog sprake is van onregelmatigheden.
Bijvoorbeeld in het geval $NimSet = \{1, 6, 9\}$:
| $\color{\white}{\ Verschil\ }$ | $\color{\white}{2}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{5}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{2}$ | $\color{\white}{3}$ | $\color{\white}{2}$ | $\color{\white}{3}$ |
Het eerste deel is onregelmatig, en dat moet dus worden overgeslagen. We vinden uiteindelijk $StartDD = {2, 2, 3, 5}$ en $PeriodeDD = {2, 3}$. In de praktijk gaat het om een minderheid van alle gevallen. In het programma maken we tevens gebruik van $StartDDLen = 4$, het aantal elementen van $StartDD$ en $PeriodeDDLen = 2$, het aantal elementen van $PeriodeDD$.
Alle verzamelingen NimSet doorlopen
Naarmate $M$ groter wordt neemt ook het aantal verzamelingen $NimSet$ toe. Bijvoorbeeld als $M = 10$, dan geldt $1, 10 \in NimSet$. De tussenliggende getallen $2, \dots, 9$ kunnen al dan niet voorkomen. Daarvoor zijn $2^8 = 256$ mogelijkheden.
ReCords
Hieronder staat een overzicht van spelletjes met bijzondere verzamelingen $NimSet$ met de grootste $PeriodeLen$ voor $M$ (de grootste waarde van $NimSet$).
Kortom je kunt nog vele spelletjes Nim spelen!
| $\color{\white}{NimSet}$ | $\color{\white}{PeriodLen}$ | $\color{\white}{PeriodeVerschillen}$ |
| $\color{\white}{\{1\}}$ | $\color{\white}{2}$ | $\color{\white}{\{2\}}$ |
| $\color{\white}{\{1, 2\}}$ | $\color{\white}{3}$ | $\color{\white}{\{3\}}$ |
| $\color{\white}{\{1, 2, 3\}}$ | $\color{\white}{4}$ | $\color{\white}{\{4\}}$ |
| $\color{\white}{\{1, 3, 4\}}$ | $\color{\white}{7}$ | $\color{\white}{\{2, 5\}}$ |
| $\color{\white}{\{1, 4, 5\}}$ | $\color{\white}{8}$ | $\color{\white}{\{2, 6\}}$ |
| $\color{\white}{\{1, 5, 6\}}$ | $\color{\white}{11}$ | $\color{\white}{\{2, 2, 7\}}$ |
| $\color{\white}{\{1, 4, 6, 7\}}$ | $\color{\white}{13}$ | $\color{\white}{\{2, 3, 5, 3\}}$ |
| $\color{\white}{\{1, 4, 7, 8\}}$ | $\color{\white}{25}$ | $\color{\white}{\{2, 3, 6, 3, 2, 9\}}$ |
| $\color{\white}{\{1, 4, 8, 9\}}$ | $\color{\white}{17}$ | $\color{\white}{\{2, 2, 3, 7, 3\}}$ |
| $\color{\white}{\{1, 4, 9, 10\}}$ | $\color{\white}{33}$ | $\color{\white}{\{2, 2, 3, 8, 3, 2, 2, 11\}}$ |
| $\color{\white}{\{1, 2, 6, 9, 10, 11\}}$ | $\color{\white}{39}$ | $\color{\white}{\{3, 4, 8, 4, 3, 5, 7, 5\}}$ |
| $\color{\white}{\{1, 6, 11, 12\}}$ | $\color{\white}{61}$ | $\color{\white}{\{2, 2, 3, 2, 8, 5, 2, 2, 5, 8, 2, 3, 2, 2, 13\}}$ |
Opgaven
|
|
Mail ze naar [email protected]. |
De redactie is geïnteresseerd in jullie programma's!
Bij [Bekijk Oplossing] is de bijbehorende Pythoncode te vinden.
Bekijk oplossing