Impartiële spellen. Marie Beth van Egmond, Lisa Steverink. 12 juli Project wiskunde 2 Begeleiding: dr. Roland van der Veen

Imparti¨ ele spellen Marie Beth van Egmond, Lisa Steverink 12 juli 2013 Project wiskunde 2 Begeleiding: dr. Roland van der Veen

Korteweg-De Vries Instituut voor Wiskunde Faculteit der Natuurwetenschappen, Wiskunde en Informatica Universiteit van Amsterdam

Samenvatting Wiskundigen worden al eeuwen beziggehouden door spelletjes. Behalve een bron van ontspanning levert het ook een heleboel wiskundig onderzoek op. Dit onderzoek heeft als einddoel om een theorie over Dots and Boxes te vormen. Er is gekozen om het spel te benaderen via impart¨ıele spellen. Dit zijn spellen waarvoor de ”normaal spel-regel geldt: de persoon die niet meer kan spelen verliest. Dots and Boxes is geen impartieel spel, maar laat zich wel goed benaderen door een impartiële versie ervan. Impartiële spellen zijn interessant omdat de stelling van Sprague en Grundy zegt dat alle impartiële spellen equivalent zijn aan het spel Nim. De theorie hierover is compleet, dus samen met deze equivalentie kunnen we een heleboel zeggen over impartiële spellen. Door het spel Dots and Boxes gedeeltelijk te zien als een impartieel spel, kunnen we strategieën bewijzen die gelden voor dit spel. Tot slot wordt er nog een open probleem, het zogenaamd 1 × n Greenlandic Dots & Boxes, behandeld met de beschreven theorieën.

Titel: Impartiële spellen Auteurs: Marie Beth van Egmond, [email protected], 6357164 Lisa Steverink, [email protected], 6229751 Begeleiding: dr. Roland van der Veen Einddatum: 12 juli 2013 Korteweg-De Vries Instituut voor Wiskunde Universiteit van Amsterdam Science Park 904, 1098 XH Amsterdam http://www.science.uva.nl/math

2

Inhoudsopgave 1. Inleiding 2. Definities 2.1. Wat is een spel? . . . . . . 2.2. Impartiële spellen . . . . . . 2.3. Getallen zijn spellen . . . . 2.4. Optellen van spellen . . . . 2.5. Equivalentierelaties . . . . . 2.6. De groep impartiële spellen

5

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

6 6 6 8 8 9 10

3. De stelling van Sprague en Grundy 3.1. Inleiding . . . . . . . . . . . . . . . . . . . 3.2. Nimbers . . . . . . . . . . . . . . . . . . . 3.3. Verband mex-operatie en binaire optelling 3.4. De stelling van Sprague en Grundy . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

12 12 12 13 14

. . . . . .

. . . . . .

. . . . . .

4. Equivalente spellen 4.1. Inleiding . . . . . . . . . . . . . . 4.2. Het spel Nim . . . . . . . . . . . 4.2.1. Winnende strategie . . . . 4.2.2. Bewijs winnende strategie 4.3. Poker Nim . . . . . . . . . . . . . 4.4. Silver Dollar Game . . . . . . . . 4.5. Kayles . . . . . . . . . . . . . . . 4.6. Nimstring . . . . . . . . . . . . . 5. Dots and Boxes 5.1. Inleiding . . . . . . . . . . . . . 5.2. Strings and Coins . . . . . . . . 5.3. Strategie Dots and Boxes . . . 5.3.1. Bijzondere zetten . . . . 5.3.2. The Long Chain Rule . 5.4. Typen ketens . . . . . . . . . . 5.5. Benadering van Dots and Boxes 6. 1 × n Dots and Boxes 6.1. Een open probleem . . . . . . 6.2. 1 × n Greenlandic Nimstring 6.2.1. Nimstring . . . . . . . 6.2.2. Kayles-ranken . . . . . 6.3. 1 × n Dots and Boxes . . . .

. . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

16 16 16 16 17 18 19 19 20

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . met nimbers

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

25 25 25 26 27 29 30 33

. . . . .

35 35 35 35 37 38

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

3

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

6.4. Kleine spellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5. Symmetrisch Dots and Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6. Even spellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39 39 40

7. Conclusie Project

43

8. Populaire Samenvatting

44

A. Nimbers in Nimstring

46

Bibliografie

47

4

1. Inleiding Het gebied van de wiskundige spellen is een wondere wereld binnen de wiskunde. Wiskundigen houden zich al eeuwen bezig met schaak, maar om hier iets wiskundigs over te zeggen is bijna onmogelijk. Er zijn namelijk meer mogelijke mogelijke posities in een schaakspel dan dat er atomen op de wereld zijn. Schaak is echter een zogenaamd ’partijdig’ spel, wat betekent dat beide spelers verschillende mogelijkheden hebben. Ze mogen immers alleen met hun eigen stukken spelen. Tegenover de partijdige spellen staan de impartiële spellen. Dit zijn spellen de mogelijkheden tot zetten in een beurt niet afhangt van de speler die aan beurt is. Een van de simpelste impartiële spellen is het spel Nim. Nim is een eeuwenoud Chinees spel, dat overal met een paar kleine voorwerpen gespeeld kan worden. Het werkt als volgt: neem een eindig aantal stenen (lucifers, muntjes, stukjes papier) en verdeel ze in verschillende rijen. Nu mogen de twee spelers om de beurt zoveel stenen pakken als zij willen, maar wel maar van één stapel. Degene die de laatste steen pakt heeft gewonnen. Als je dit spel vaak speelt, kom je er misschien achter dat het uitmaakt of je begint of niet. In 1902 bevestigde wiskundige Bouton inderdaad dat het spel Nim volledig wiskundig kan worden beschreven en je gemakkelijk kunt uitrekenen of je al dan niet moet beginnen om te winnen [1]. Behalve dat Nim een leuk spelletje is en dat je je cafémaatjes ermee kunt imponeren, blijkt het ook een zeer belangrijke rol te spelen in het beschrijven van andere impartiële spellen.Twee wiskundigen, Sprague (1935) [2] en Grundy (1939) [3] hebben beiden bewezen dat er een equivalentie bestaat tussen het spel Nim en elk willekeurig ander impartieel spel. Dit zou in theorie betekenen dat we dus van elk impartieel zouden kunnen uitrekenen of we moeten beginnen of niet om het spel te winnen. Dit blijkt echter niet altijd even makkelijk, omdat sommige impartiële spellen veel extra spelregels hebben waardoor ze nog weinig op Nim lijken. In dit verslag zal het spel Dots and Boxes (Kamertje Verhuren) geanalyseerd worden met behulp van impartiële spellen. Dots and Boxes is geen impartieel spel, want de speler met de meeste hokjes wint. De equivalentie tussen Nim en Dots and Boxes is dan ook nooit volledig beschreven, maar kan benaderd worden via een aantal tussenstappen in de vorm van simpelere spellen die ertussen staan. Ook kunnen er aan de hand hiervan tactieken bepaald worden voor het spel. In dit verslag zal eerst de wiskundige uitleg van impartiële spellen gegeven worden. Vervolgens zal de stelling van Sprague en Grundy worden bewezen. Daarna zullen er verschillende equivalenties beschreven worden die leiden tot een beter inzicht in het spel Dots and Boxes. Uiteindelijk zal er nog gekeken worden naar een bijzondere vorm van Dots and Boxes, dat een open probleem vormt binnen de theorie over impartiële spellen. Dit is de Dots and Boxes met 1 × n hokjes. Dit lijkt een simpel spel, maar blijkt erg ingewikkeld. In dit verslag zal een poging worden gedaan meer inzicht te krijgen in dit specifieke spel door het te vergelijken met een wiskundig opgelost spel. Zo wordt bestaande kennis gebruikt om onbekende terreinen meer te doorgronden.

5

2. Definities 2.1. Wat is een spel? De filosoof Ludwig Wittgenstein was waarschijnlijk de eerste wetenschapper die een definitie probeerde te geven van een spel. In zijn ’Philosophische Untersuchungen’ [4] schrijft hij dat er voor alle elementen die je zou kunnen benoemen van een spel zoals, ’het heeft regels’ en ’er is een winnaar’ wel een uitzondering te vinden is. Hierdoor is er volgens hem geen sluitende definitie te geven voor een spel. Toch is er veel onderzoek naar spellen gedaan en blijft men zijn best doen om de definitie in te dammen.We kunnen een spel zien als een artificieel conflict waartoe spelers zich toeleggen. In de wiskunde zien we dit als een verzameling van zetten die spelers kunnen doen. We vergeten dan als het ware de speler en kijken bijvoorbeeld niet naar de psychologie achter een spel, maar slechts nog objectief naar de stappen die gezet kunnen worden. Een wiskundige definitie voor een spel met twee personen is, volgens Albert, Nowakowski en Wolfe (2007) [5] een paar van verzamelingen van zetten. Dit paar bestaat uit de zetten voor de eerste speler wat we schrijven als G L en de zetten van de tweede speler; G R . Definitie 2.1. Een spel G is {G L | G R }. Elke speler heeft dus een verzameling van mogelijk zetten die hij kan doen. Definitie 2.2. Een verzameling van de k zetten van een speler is: G = {G1 , G2 , ...Gk }. Het verloop van een spel waaiert dus al snel uit tot een heleboel verschillende vervolgsituaties, omdat elke directe vervolgzet weer een verzameling is van de mogelijke secundaire vervolgzetten. We kunnen dit voor Boter-Kaas-en-Eieren weergeven in een onderstaande ”spelboom”, waarin elke tak een mogelijke vervolgzet weergeeft. In Boter-Kaas-en-Eieren mag de eerste speler steeds één kruisje in een hokje zetten, en de tweede speler speelt met een rondje. De speler die als eerste een opeenvolgend rijtje van drie kruisjes òf drie rondjes heeft gevormd, heeft gewonnen. Zie Figuur 2.1, waarin symmetrisch gelijke zetten in dezelfde tak zijn opgenomen. Deze verzamelingstheoretische definitie van een spel is heel breed. In dit verslag beperken we ons tot de deelverzameling van de zogenaamde imparti¨ ele spellen.

2.2. Imparti¨ ele spellen In de wereld van wiskundige spellen met twee spelers kunnen we twee soorten spellen onderscheiden: de partijdige spellen (partisan games) en de impartiële spellen. Een impartieel spel definieren we als een spel waarbij de speler L dezelfde zetten heeft als speler R. Dit maakt de wiskundige definitie iets simpeler. Definitie 2.3. Voor een impartieel spel G geldt G L = G R . Definitie 2.4. Een impartieel spel G wordt gedefinieerd door zijn mogelijke zetten. G = {G1 , G2 , .., Gk }.

6

Figuur 2.1.: Een deel van het mogelijke verloop van het spel Boter-Kaas-en-Eieren. Een voorbeeld van een partijdig spel is schaak. Bij schaak heeft iedere spelen eigen stukken en dus ook zijn eigen mogelijke zetten. Een gebeurtenis in een spel schaak hangt dus af van wie er aan de beurt is. Bij een impartieel spel hangt het hier niet vanaf, de spelers hebben beiden dezelfde mogelijkheden. Een impartieel spel hangt dus alleen af van de spelsituatie. Er zijn nog een paar eisen waar een impartieel spel in onze theorie aan moet voldoen. Dit zijn: I Perfecte informatie: Alle informatie is beschikbaar voor beide spelers. Er wordt geen informatie achtergehouden zoals bij bijvoorbeeld een kaartspel waarbij spelers niet van elkaar weten welke kaarten ze hebben. II Geen kans: Er zit geen kanselement in het spel. III Eindigheid: Het spel moet na een eindig aantal zetten afgelopen zijn. IV Normaal spel: Dit betekent dat degene die niet meer kan spelen maar wel aan de beurt is verliest. V Zetten onafhankelijk van beurt: Beide spelers kunnen precies dezelfde zetten doen. Het enige verschil tussen speler 1 en speler 2 is dat speler 1 begint. VI Optioneel: Om de beurt zetten. In sommige impartiële spellen ben je aan de beurt zodra de andere speler een zet heeft gedaan. In andere spellen mag je nog een keer zetten als je bijvoorbeeld een muntje hebt gepakt, zoals bij Nimstring.

Opmerking. Een leuke manier om IV te onthouden is: het gaat niet om het winnen, het gaat om het meedoen. Dus als je niet meer mee kan doen heb je verloren. Opmerking. Als men niet normaal speelt, heet dit misèrespel. Hier wint juist de speler die geen zet meer kan doen. Het rekenen met deze spellen blijkt echter veel ingewikkelder.

7

In dit verslag worden vaak alle zetten geanalyseerd, maar er wordt ook regelmatig uitgegaan van perfect spel. Dit betekent dat beide spelers de optimale zet doen in elke beurt. Menselijke fouten worden dan uitgesloten. Als het bekend is van een speler dat hij of zij kan winnen, dan zal dit ook gebeuren. Voorbeeld 2.5. Een voorbeeld van een impartieel spel is het spel Nim. Nim is een spel dat wordt gespeeld met een eindig aantal stapels met een eindig aantal stenen. Om de beurt mogen de spelers zoveel stenen van één stapel pakken als ze willen. Een speler die aan zet is moet minstens één steen pakken. Degene die de laatste steen pakt, heeft gewonnen (de volgende speler kan immers niet meer spelen). Nim voldoet aan alle eisen van een impartieel spel. Iedereen weet hoeveel stenen er liggen, dus er is perfecte informatie. Er zit geen kans in het spel en er zijn een eindig aantal stenen dus het spel is in een eindig tijdsbestek afgelopen. Er geldt de regel van normaal spel en beide spelers hebben dezelfde opties. Ook geldt de optionele eis VI, de spelers spelen om de beurt. Het spel Nim blijkt een heel belangrijk impartieel spel te zijn, hier komen we in hoofdstuk 3 nog op terug.

2.3. Getallen zijn spellen J.H. Conway zet in zijn boek ’On Numbers and Games’ [6] volledig uiteen dat elk getal kan worden gezien als een spel. Hij begint met een citaat van Von Schiller: ’Whatever is not forbidden, is permitted’. Vervolgens zet hij de regels uiteen van het spel dat de getallen vormen. We zullen dit nu laten zien voor de natuurlijke getallen. We kunnen een natuurlijk getal zien als de verzameling van zijn voorgangers, bijvoorbeeld 3 = {0, 1, 2}. In het algemeen geldt dus voor een getal n: n = {0, ..., n − 1}. Zo kunnen getallen recursief worden opgebouwd. We beschouwen nu een spel G met een stapel stenen die uit n stenen bestaat, waaruit je willekeurig veel stenen mag pakken. Je moet minimaal één steen pakken. Uit de definitie van een spel volgt nu dat G = {0, ..., n − 1}. We kunnen elk getal n dus zien als dit spel G. Ergo, elk natuurlijk getal is een spel! We kunnen spellen en getallen opbouwen vanuit ”het niets”: de lege verzameling. We noemen het eindspel, dus het spel waarbij niet meer gespeeld kan worden, de lege verzameling. Er zijn immers geen zetten meer. Vanuit het spel met één steen is de enige zet de overgang naar de lege verzameling, dus 1 = {∅}. Vanuit een spel met twee stenen kun je naar een spel met één steen of naar het lege spel, dus 2 = {{∅}, ∅}. We kunnen breuken en negatieve getallen ook zien als spellen. Hiervoor verwijzen we naar Conways gedetailleerde boek [6].

2.4. Optellen van spellen We hebben gezien dat we spellen kunnen zien als een verzameling. Nu kunnen we ook een optelling definiëren voor deze spellen. Het idee van het optellen van twee spellen is dat je deze spellen tegelijkertijd speelt, en iedere speler in zijn beurt kan kiezen of hij een zet doet in het ene spel of een zet in het andere spel. Als het ene spel afgelopen is, wordt er verder gespeeld in het andere spel. Degene die in het laatste spel wint, wint de optelling van het spel. Wie er in het andere spel gewonnen heeft doet er niet toe. Dit kan gedaan worden met elk spel, bijvoorbeeld met Schaak en Go, zoals weergegeven in Figuur 2.2. De optelling van een impartieel spel kan formeel als volgt gedefinieerd worden:

8

Figuur 2.2.: Het optellen van Schaak en Go. Definitie 2.6. Voor impartiële spellen G en H, G + H = {G + h voor h in H} g voor g in G}.

S

{H +

Deze optelling is commutatief en associatief, en de spellen vormen een groep. De impartiële spellen vormen een ondergroep van de spellen. De groepsaxioma’s hiervan zullen hieronder bewezen worden. Opmerking. Omdat dit verslag slechts gaat over impartiële spellen, zal vanaf nu met een spel altijd een impartieel spel bedoeld worden, tenzij anders aangegeven.

2.5. Equivalentierelaties Spellen vormen een dus groep. Op deze groep kunnen we equivalentierelaties definiëren. Elk spel blijkt een uitkomstenklasse te hebben, dit betekent dat je kunt weten of de eerste of tweede speler zal winnen (we gaan immers uit van perfect spel). Uitkomstenklasse Npositie betekent dat de eerste speler zal winnen en uitkomstenklasse P-positie betekent dat de tweede speler zal winnen. Nu kunnen we een equivalentierelatie definiëren aan de hand van de uitkomstenklasse. Definitie 2.7. Voor spellen G en H, G ≈ H ⇔ G en H dezelfde uitkomstenklasse (N-positie of P-positie) hebben. Deze equivalentierelatie vormt twee klassen en is dus een vrij zwakke equivalentieraltie. We kunnen ook een sterkere equivalentierelatie definiëren aan de hand van de optelling van spellen. Twee spellen G en H zijn equivalent dan en slechts dan als de spellen G + I en H + I voor een willekeurig spel I, dezelfde uitkomstenklasse hebben. Definitie 2.8. Voor spellen G en H, G ≡ H ⇔ G en H G ≡ H dan en slechts dan als voor elk ander spel I geldt dat G + I ≈ H + I. Tot slot kunnen we een nog sterkere equivalentierelatie definiëren door te kijken naar de spelboom. Vanuit de definitie van een spel kunnen we dan eigenlijk zeggen dat twee spellen gelijk zijn, want ze hebben exact dezelfde verzameling van zetten. Definitie 2.9. Voor spellen G en H, G = H ⇔ G en H dezelfde spelboom hebben. Voor deze drie equivalentierelaties geldt nu: Lemma 2.10. G = H ⇒ G ≡ H ⇒ G ≈ H.

9

2.6. De groep imparti¨ ele spellen Spellen vormen dus een groep met als ondergroep de impartiële spellen. We zullen nu bewijzen dat de impariële spellen een groep vormen, hiervoor hebben we echter eerst twee lemma’s nodig. Deze lemma’s zullen later ook nog handig blijken bij het bewijzen van de stelling van Sprague en Grundy. Lemma 2.11. Voor elk spel G en spel A, waarbij A is een P-positie, geldt A + G ≡ G. Bewijs. We zullen moeten aantonen dat G + H dezelfde uitkomstklasse heeft als G + A + H. We maken een gevalsonderscheid in de positie van G + H. Als G + H een P-positie is, dan is G + H + A ook een P-positie. De optelling van twee P-positie-spellen is namelijk altijd een P-positie. Doet de eerste speler namelijk een zet in het spel G + H, dan kan de tweede speler de winnende zet doen in hetzelfde spel en dan zijn er weer twee P-positie spellen. Dit geldt ook als de eerste speler een zet doet in het spel G + H + A. De tweede speler kan dus altijd de twee spellen P-positie laten en uiteindelijk is een van de spellen eerder afgelopen, dan kan dat andere spel nog worden afgerond en gewonnen door de tweede speler. Dus G + A + H is een P-positie als G + H een P-positie is. Als G + H een N-positie is, dan is er een winnende strategie voor de eerste speler in het spel G + H + A. Hij begint in het spel G + H + A namelijk met een winnende zet in het spel G + H, waardoor G + H een P-positie wordt. Dan is dus G + H + A ook een P-positie zoals hierboven beschreven. De eerste speler heeft dan dus het hele spel in een P-positie omgezet, en is vanaf dat moment zelf de previous player, dus zal het spel kunnen winnen. G + H + A is dan dus een N-positie. Lemma 2.12. Voor impartiële spellen geldt dat G ≡ G0 ⇔ G+G’ is een P-positie. Bewijs. Het spel G + G is een P-positie, want het is symmetrisch. De tweede speler kan dus steeds ’na-apen’ wat de eerste speler doet totdat het spel is afgelopen. Als G equivalent met G0 dan mag je aan beide kanten G optellen, wegens de equivalentierelatie. Dan is dus G + G ≡ G + G0 en G + G is een P-positie dus G + G0 is ook een P-positie. Als G + G0 een P-positie dan geldt: G ≡ G + (G + G0 ), we mogen immers altijd een P-positie spel erbij optellen volgens Lemma 6.6. Wegens associativiteit geldt G+(G+G0 ) ≡ (G+G)+G0 en omdat G + G een P-positie geldt nu (G + G) + G0 ≈ G0 . Stelling 2.13. Impartiële spellen vormen een Abelse groep Imp onder de optelling van spellen + en de equivalentie ≡. Bewijs. We zullen de groepsaxioma’s afgaan. • Geslotenheid: Neem G, H ⊂ Imp dan geldt G + H ⊂ Imp. G + H voldoet immers aan alle eisen van een impartieel spel, waaronder normaal spel. Degene die niet meer kan zetten in G + H heeft immers verloren. • Associativiteit:: Neem G, H, F ⊂ Imp. Dan moet gelden dat G+(H+F ) ≡ (G+H)+F . Het spel G + (H + F ) betekent dat je bij een zet mag kiezen of je een zet doet in G of in H + F . In het spel H + F mag je ook kiezen of je een zet doet in H of in F . Het spel G + (H + F ) betekent dus dat je een zet mag doen in G, H of F . Bij het spel (G + H) + F mag je kiezen of je een zet doet in F of in G + H, dus of je een zet doet in G,H of F . De spellen G + (H + F ) en (G + H) + F hebben dus dezelfde spelbomen. Wegens Lemma 2.10 geldt dus dat G + (H + F ) ≡ (G + H) + F .

10

• Eenheidselement: Het eenheidselement van Imp is het lege spel ∅. Er moet dan gelden dat G + ∅ ≡ ∅ + G ≡ G. Nu hebben de spellen G en G + ∅ en ∅ + G dezelfde spelbomen, je kunt in de laatste twee spellen namelijk alleen zetten doen in G. Als ze allen dezelfde spelboom hebben geldt ook de gevraagde equivalentie volgens Lemma 2.10. • Invertibiliteit: Elk spel G ⊂ Imp heeft een inverse, namelijk G. Er geldt moet dan gelden G+G ≡ ∅. Hiervoor moeten we bewijzen dat G+G+H dezelfde uitkomstenklasse heeft als het spel H + ∅. Dit doen we met behulp van de hiervoor bewezen lemma’s. Lemma 2.12 zegt dat G + G P-positie is, immers G ≡ G. Dus geldt dat volgens Lemma 2.11 dat G+G+H ≡ H. Nu weten we dat ∅ het eenheidselement is, dus geldt H ≡ H +∅. Dus ook G + G + H ≡ H + ∅ • Commutativiteit: Voor de spellen G en H geldt G + H ≡ H + G. In het spel G + H mag je een zet doen in G of H. In het spel H + G mag je een zet doen in het H of G. G + H en H + G hebben dus dezelfde spelboom, dus zeker G + H ≡ H + G. De verzameling Imp voldoet dus aan de groepaxioma’s en is ook commutatief en is dus een Abelse groep. In het bijzonder is het een ondergroep van de groep van spellen, waarvan we de groepsaxioma’s niet zullen bewijzen. Opmerking. De impartiële spellen vormen dus een Abelse groep, maar in het bijzonder vormen zij ook een lichaam. Er bestaat namelijk ook een vermenigvuldiging op de spellen. Dit wordt uitgebreid beschreven in het boek On Numbers and Games [6].

11

3. De stelling van Sprague en Grundy 3.1. Inleiding We weten nu wat impartiële spellen zijn, hoe we er mee kunnen rekenen en welke equivalenties er zijn. Het is veel werk om van twee impartiële spellen uit te zoeken hoe de equivalentie er concreet uitziet, dus welke zetten equivalente zetten zijn. Gelukkig is hier in de eerste helft van de twintigste eeuw een sterke stelling over bewezen, de stelling van Sprague en Grundy: Stelling 3.1. Elk impartieel spel G is equivalent met een nimber. Dit geeft ons meteen het volgende prachtige resultaat: Gevolg 3.2. Alle impartiële spellen zijn equivalent aan Nim. Dit roept een hoop vragen op. Omdat Nim een simpel en volledig uitgewerkt spel is, geeft ons dit cruciale informatie over elk denkbaar impartieel spel. Hierbij merken we op dat deze stelling geldt voor de impartiële spellen die aan optionele voorwaarde VI voldoen (zie hoofdstuk 2). In hoofdstuk 4 wordt een aantal concrete equivalenties uitgeschreven aan de hand van winnende strategieën. In dit hoofdstuk zal eerst worden ingegaan op de definitie van een nimber. De rekenregels zullen uiteen worden gezet en worden bewezen. Tot slot zullen we aan de hand van een aantal lemma’s de beroemde stelling van Sprague en Grundy bewijzen.

3.2. Nimbers Nimbers zijn gedefinieerd aan de hand van het spel Nim. We bekijken een simpel spel Nim dat uit één rij bestaat. Deze rij bestaat uit n aantal stenen. Dit spel G is volgens de verzamelingstheoretische definitie van een spel gedefinieerd als G = {G1 , G2 , ...Gn−1 } waarbij G1 een rij is met één steen, G2 een rij met twee stenen enzovoorts. We zeggen nu dat spel G nimber n heeft, genoteerd als ?n. We definiëren: Definitie 3.3. ?n = {?0, ?1, ..., ?(n − 1)}. We zien dat de nimber van het spel G het kleinste getal is dat niet voorkomt in de verzameling van nimbers van zetten die vanuit G mogelijk zijn, die namelijk gelijk is aan {?0, ?1, ?2, .., ?(n− 1)}. Volgens de stelling van Sprague en Grundy is ieder impartieel spel equivalent aan een nimber. Deze nimber kan worden bepaald door middel van de zogenaamde mex-operatie. Hierbij is de mex gedefinieerd als ’the minimal excluded number’, dus het laagste natuurlijke getal dat niet in de verzameling zit, inclusief 0. Bijvoorbeeld: mex{0, 1, 2, 4, 158} = 3. De bepaling van een nimber wordt met het volgende lemma bewezen: Lemma 3.4. Neem een spel G = {G1 , G2 , ....Gk }. Dan geldt voor de nimber ?n van G en de nimbers ?ni van Gi , met i ∈ {1, .., k} : ?n = ?mex{n1 , n2 , ..., nk }.

12

Bewijs. Volgens de definities van een nimber en van een spel moet een speler vanuit een spel met nimber ?n kunnen zetten naar vervolgspellen met nimber ?i, i ∈ {0, ..., n − 1}. Als de nimber van een spel niet gelijk zou zijn aan de minimal excluded number van de verzameling van zijn vervolgspellen, dan zou er dus een nimber ?j zijn met j < n die je niet kan bereiken met een zet in het spel met nimber ?n. Dit spreekt de definitie van een nimber tegen. Dit bewijst het lemma. Door het definiëren van de mex volgen een aantal rekenregels ten aanzien van nimbers: • Het lege spel heeft nimber ?0. • Nimbers kunnen we ook op een speciale manier optellen door gebruik te maken van de optelling in vectorruimte (Z/2Z)n oftewel de binaire optelling zonder overdracht: ⊕. De regels voor de binaire optelling zijn als volgt: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, 1 ⊕ 1 = 0. Twee spellen met nimber ?n en ? m hebben de optelling ?m + ?n = ?(m ⊕ n). Dit wordt in de volgende paragraaf bewezen. • Een spel met ?0 heeft altijd de uitkomstenklasse P-positie en een spel met ?n(n 6= 0) is altijd een N-positie. Dit wordt bewezen in hoofdstuk 4. • ?n ⊕ ?n = ?0, hieruit volgt direct dat symmetrische spellen altijd P-positie zijn. De nimbers zijn dus een handige manier om impartiële spellen en hun equivalentie te beschrijven. We zullen in hoofdstuk 4 uitgebreid ingaan op equivalente spellen.

3.3. Verband mex-operatie en binaire optelling Zoals gezegd kunnen we nimbers bepalen met behulp van de mex-operatie. Als we twee spellen optellen, kan het toepassen van de mex-operatie nogal ingewikkeld worden. Gelukkig blijkt het zo te zijn dat nimbers altijd opgeteld mogen worden met de veel simpelere binaire optelling zonder overdracht. We zullen nu bewijzen dat het optellen van nimbers volgens de mex-operatie altijd hetzelfde oplevert als het optellen van nimbers volgens deze binaire optelling. Stelling 3.5. ?a + ?b = mex{?a + ?k(k < b), ?l + ?b(l < a)} = a ⊕ b. Bewijs. We zullen dit bewijzen door middel van inductie. We stellen ons een tabel voor met de binaire optelling ⊕. Basisstap: ?0 + ?0 = ?mex{?0 + ?0} = mex{∅ + ∅} = 0. Er geldt ook dat 0 ⊕ 0 = 0 dus de bassistap ?0 + ?0 = 0 ⊕ 0 geldt. De inductiehypothese is dat alle cellen boven en links van (i,j) al ingevuld zijn door middel van de mex-operatie. Zie Figuur 1 voor een ingevulde nimbertabel. We willen dat i ⊕ j gelijk is aan het kleinste gehele getal dat nog niet in dezelfde kolom of rij gebruikt is. Dus elke c < i ⊕ j moet al gebruikt zijn. i ⊕ j kan niet gelijk zijn aan i ⊕ a of b ⊕ j voor i 6= a en j 6= b, want ⊕ is een groepsoperatie. Immers, de groepsaxioma’s gelden: 1. Associativiteit: a ⊕ b = b ⊕ a want 0 ⊕ 1 = 1 ⊕ 0. 2. Gesloten onder de bewerking: a ⊕ b is weer een geheel getal. 3. Eenheidselement: 0 ⊕ a = a dus 0 is het eenheidselement. 4. Inverse: a ⊕ a = 0 dus elk getal is zijn eigen inverse met de binaire optelling.

13

Beschouw de meest linker positie van de binaire weergave van c die verschilt van i ⊕ j. Omdat c kleiner is dan i ⊕ j moet gelden dat op deze positie in c een 0 staat, en in i ⊕ j een 1. Deze 1 komt van i of van j. Zonder verlies van algemeenheid nemen we aan dat deze 1 in i zit. Door dat getal in een 0 te veranderen krijgen we een getal a0 zodat a0 ⊕ j gelijk is aan c tot en met de eerste bitpositie die verschilt. De bitposities rechts daarvan kunnen we veranderen zodat we een a verkrijgen waarvoor a ⊕ j = c. Er geldt a < i, omdat het eerste verschillende getal vanaf links een 1 is in i en een 0 is in a. Voor elke c < i ⊕ j kan zo’n a gevonden worden. Dus alle c < i ⊕ j zijn gebruikt in de kolommen en rijen. Er moet nu, vanwege de inductiehypothese, gelden dat i ⊕ j = mex{a ⊕ +k(k < b), l ⊕ +b(l < a)}. Immers, voor i ⊕ (j + 1) moet ook weer gelden dat alle d < i ⊕ (j + 1) gebruikt zijn.

Figuur 3.1.: De eerste vijftien rijen en kolommen van de nimbertabel, die kunnen worden ingevuld door de mex-operatie toe te passen op de rijen en de kolommen die respectievelijk boven en links van het in te vullen getal staan.

3.4. De stelling van Sprague en Grundy Sprague en Grundy maken gebruik van de tweede equivalentierelatie. Ze stellen dus dat een spel (en zijn nimber) nog steeds allebei dezelfde uitkomstenklasse hebben als je er een willekeurig ander spel bij optelt. In het bewijs voor deze stelling maken we gebruik van Lemma 2.11 en Lemma 2.12, die zijn bewezen in Hoofdstuk 2. We merken nogmaals op dat deze stelling geldt voor impartiële spellen die aan optionele voorwaarde VI voldoen: de spelers

14

doen om de beurt een zet. Stelling 3.6. De Stelling van Sprague en Grundy: Elk impartieel spel G is equivalent met een nimber, dus voor elk spel G, G ≡ ?n. Bewijs. We beweren dus dat G ≡ ?m. We zullen dit bewijzen door gebruik te maken van inductie. Basisstap: Het lege spel is de basis, we moeten bewijzen dat G ≡ ?0. De equivalentierelatie is gedefinieerd als G ≡ H ⇔ G + I ≈ H + I voor een willekeurig spel I. Stel nu G is het lege spel. Dan geldt G + I = I dus ook G + I ≈ I, je kunt namelijk in beide spellen alleen maar zetten doen in het spel I, dus ze hebben dezelfde spelboom en dus ook dezelfde uitkomstenklasse. Verder weten we dat ?0 uitkomstenklasse P-positie heeft. Volgens Lemma 2.11 geldt nu: ?0+I ≡ I voor elk spel I. Dus voor het lege spel G geldt G+I ≈ I en ?0+I ≈ I. Dus G + I ≈ ?0 + I ⇒ G ≡ ?0. . Inductiehypothese: Voor elk spel G geldt G ≈ ?m. Inductiestap: We weten dat G = {G1 , G2 , ..., Gk }, de k vervolgzetten. We willen nu dus bewijzen dat als voor G1 , G2 , ..., Gk geldt dat G1 ≡ ?n1 , G2 ≡ ?n2 enzovoorts, dan G ≡ ?m. Met m = mex{n1 , n2 , ...nk }, zoals we hiervoor hebben gedefinieerd. We nemen een spel G0 = {?n1 , ?n2 , ..., ?nk }. Eerst bewijzen we G ≡ G0 . Hiervoor moeten we volgens Lemma 2.12 bewijzen dat G + G0 een P-positie is. Dit is makkelijk in te zien als je ziet dat het spel symmetrisch is. Doet de eerste speler een zet in G, waarbij hij de positie Gj zet, dan kan de tweede speler een zet in G0 doen, waarbij hij gaat naar nj , en andersom. Het spel is dus symmetrisch en dus een P-positie. Er geldt dus: G ≡ G0 . Nu willen we laten zien dat G0 ≡ ?m. We hebben m gedefinieerd als m = mex(n1 , n2 , ..., nk ). Volgens Lemma 2.12 moeten we nu bewijzen dat G + ?m een P-positie is. Dit kunnen we doen door een expliciete strategie te geven voor dit spel, waarbij de tweede speler altijd kan winnen. Dit kan hij doen door het spel altijd symmetrisch te maken. Dus door te zorgen dat wat de eerste speler ook doet, hij er weer twee gelijke spellen van maakt. Zo zal de tweede speler altijd eindigen. Dit gaat als volgt: Er zijn voor de eerste speler twee opties, of hij doet een zet in G0 of hij doet een zet in ?m. Stel de eerste speler doet een zet in ?m naar ?m0 . Stel m0 < m. Omdat m = mex(n1 , n2 , ..., nk ) is er dus in het spel G0 zeker een ni waarvoor geldt ni = m0 . De tweede speler kan dus de spellen symmetrisch maken. Stel m < m0 . Dan kan de tweede speler in het spel ?m0 de nimber weer verlagen naar ?m en krijg je weer dezelfde spelsituatie. Dit kan overigens niet altijd want anders zou het spel oneindig zijn en dat is een impartieel spel nooit. Stel nu dat de eerste speler een zet doet in G0 , dan verplaatst hij dus naar een spel met nimber ?ni . Als ni < m dan kan de tweede speler in het spel ?m naar ?ni gaan, omdat m de mex is van alle n0 s, dus ni is zeker een optie. Stel nu dat m < ni dan kan de tweede speler in ?ni naar ?m verplaatsen. Dit kan omdat ni hier ook weer de mex is van al zijn opties, dus ?m is altijd een optie. De tweede speler kan dus het spel in alle gevallen symmetrisch maken. We kunnen dus concluderen dat G0 + ?m een P-positie is, dus geldt G0 ≡ ?m, en G ≡ G, dus G ≡ ?m. Dus elke spel G is equivalent met een nimber, en wel met de mex van de nimbers van zijn mogelijke vervolgspellen. We zullen nu een aantal equivalenties van andere impartiële spellen met Nim beschrijven, onder andere door nimbers expliciet uit te rekenen. Hiervoor definiëren we de functie G. Deze functie zal in het volgende hoofdstuk gebruikt worden. Definitie 3.7. G(G) = de nimber van G.

15

4. Equivalente spellen 4.1. Inleiding We hebben tot nu toe gezien dat er verschillende equivalentierelaties te definiëren zijn tussen spellen. De belangrijkste equivalentierelatie is ≈1 , dus de equivalentie waarbij de spellen G en G’ equivalent zijn wanneer G+H en G’+H dezelfde uitkomstenklasse (N-positie of Ppositie) hebben. Op deze equivalentierelatie is ook de belangrijke stelling van Sprague en Grundy gebaseerd. Deze stelling zegt dat alle impartiële spellen equivalent zijn aan elkaar. Deze equivalentie kan het best beschreven worden met behulp van nimbers. Alle impartiële spellen zijn namelijk equivalent aan een nimber en daardoor ook equivalent aan elkaar. In dit hoofdstuk worden de expliciete equivalenties tussen Nim en een aantal andere impartiële spellen uitgeschreven. Elke paragraaf is gewijd aan een ander impartieel spel. We zullen elk spel eerst uitleggen, dan de equivalentie met nimbers beschrijven en tot slot de toepassing hiervan op het spel beschrijven in de vorm van een winnende strategie.

4.2. Het spel Nim 4.2.1. Winnende strategie Het belangrijkste impartiële spel in de theorie van wiskundige spellen is het spel Nim, zoals beschreven in hoofdstuk 2. Van elk eindig spel Nim kan precies berekend worden of het P- of N-positie is. Hoe dit uitgerekend kan worden en welke zetten de winnende speler naar succes zullen brengen, zal nu behandeld en bewezen worden. Het algoritme voor het berekenen van de uitkomst van een Nim-spel maakt gebruik van binaire getallen. Zet de aantallen objecten van de stapels om in binaire getallen. Tel deze getallen bij elkaar op met de binaire optelling zoals gedefinieerd in hoofdstuk 3. Deze operatie noteren we met ⊕ en noemen we vanaf nu ook wel de nim-som van twee getallen. Bij Nim heeft de eerste speler een winnende positie dan en slecht dan als de nim-som van de stapels ongelijk aan 0 is. Deze stelling zal later bewezen worden. De winnende strategie volgt uit deze stelling. Als de nim-som namelijk gelijk is aan 0, zal de tweede speler winnen. Daarom is de winnende strategie is om een spelpositie met nim-som 0 te creëren. Dit is altijd mogelijk als het spel een positie met nim-som ongelijk aan 0 heeft. Het bewijs voor deze winnende strategie volgt later. De strategie voor een spel met drie stapels gaat als volgt: Stap 1 Zet de grootte van de stapels A, B en C om in binaire getallen, noem deze a, b en c. Stap 2 Tel deze getallen met de binaire optelling zonder overdracht om tot de nim-som, die we X noemen. Stap 3 Tel nu X op bij a, b en c met behulp van dezelfde binaire optelling. Stap 4 Als je deze optellingen weer omzet in gewone getallen, zal er altijd minstens één stapel verlaagd zijn. De zet die je uiteindelijk moet doen is om deze stapel inderdaad terug

16

te brengen naar het getal i + X, met i = a, b of c. Als er meerdere stapels verlaagd zijn mag je kiezen. Dit algoritme zal nu worden toegelicht aan de hand van een voorbeeld. Voorbeeld 4.1. Het NIM-spel heeft drie stapels A, B en C met respectievelijke groottes 1, 3 en 4. Omgezet in binaire getallen geeft dit: Stapel A: 1 = 0 + 0 + 1 = 001 = a Stapel B: 3 = 0 + 2 + 1 = 011 = b Stapel C: 4 = 4 + 0 + 0 = 100 = c De nim-som van de stapels is nu: 001 011 100 ——110 = 4 + 2 = 6 = X We nemen de nim-som van deze uitkomst en de groottes van de stapels: A : 1 ⊕ 6 = 001 ⊕ 110 = 111 = 7 B : 3 ⊕ 6 = 011 ⊕ 110 = 100 = 4 C : 4 ⊕ 6 = 100 ⊕ 110 = 010 = 2 De zet die leidt naar winst is nu om stapel C terug te brengen naar twee stenen, stapel C is namelijk verlaagd. We pakken dus twee stenen uit stapel C. De nim-som van de stapels is nu inderdaad 0. Deze winnende strategie zal nu bewezen worden.

4.2.2. Bewijs winnende strategie Stelling 4.2. Bij Nim heeft de eerste speler een winnende positie dan en slechts dan als de nim-som van de stapels ongelijk aan 0 is. Hieruit volgt uiteraard dat de tweede speler een winnende positie heeft als de nim-som 0 is. Bewijs. De nim-som ⊕ is een associatieve en commutatieve bewerking en er geldt x ⊕ x = 0. Zij x1 , ..., xn de waarden van de stapels voor de zet en y1 , ..., yn de waarden van de stapels na de zet. Zij s = x1 ⊕ ... ⊕ xn en t = y1 ⊕ ... ⊕ yn . Als de zet in stapel k was, dan hebben we xi = yi voor alle i 6= k en xk < yk . Je kunt een stapel namelijk alleen maar verlagen. Nu geldt er:

t=0⊕t =s⊕s⊕t = s ⊕ (x1 ⊕ ... ⊕ xn ) ⊕ (y1 ⊕ ... ⊕ yn ) = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk ) ⊕ ... ⊕ 0 = s ⊕ xk ⊕ yk Als s = 0, dus P-positie, dan geldt t = xk ⊕ yk 6= 0 want xk 6= yk . Dus een P-positie verandert na de volgende zet altijd in een N-positie.

17

Als s 6= 0, dan willen we dat er een zet mogelijk is die t = 0 als gevolg heeft, dit betekent namelijk dat je dan altijd naar een P-positie kan veranderen waardoor je dus wint (na je eigen zet ben je namelijk de previous player). Zij d de meest linker 1 in de binaire represenatie van s en kies k zodat de d-de bit van xk ook 1 is. Zo een k bestaat, want anders zou de d-de bit van s 0 zijn. We stellen nu yk = s ⊕ xk . Alle bits links van d zijn 0 in zowel xk als yk , de stapel kan namelijk nooit verhogen, en bit d verandert van 1 in 0 (1 ⊕ 1 = 0), waardoor de waarde van yk met 2d verlaagd wordt. Elke verandering in de andere bits van yk zal hoogstens een stijging van 2d − 1 opleveren. Er geldt dus yk < xk . Als de eerstvolgende speler nu xk − yk objecten van stapel k pakt, dan geldt: t = s ⊕ xk ⊕ yk = s ⊕ xk ⊕ (s ⊕ xk ) = 0. Dus er is in een spel met N-positie een zet mogelijk waarna het spel P-positie heeft. Dus de eerste speler heeft een winnende positie dan en slechts dan als de nim-som van de stapels ongelijk aan 0 is. Anders heeft de tweede speler een winnende positie.

4.3. Poker Nim Het spel Een subtiele variant op het spel Nim is het spel Poker Nim. Dit spel gaat hetzelfde als Nim, alleen is er als extra mogelijkheid bij een beurt om stenen uit een eindige extra zak te pakken en bij een stapel aan te leggen. De stenen die van een stapel af worden gehaald gaan echter niet terug in de zak. Het spel eindigt als de stapels op zijn en de zak leeg is. Dit spel voldoet aan onze definitie van een impartieel spel. Nimberequivalentie De nimbers van een spel Poker Nim zijn gelijk aan de nimbers van hetzelfde spel Nim zonder de zak. Dit zullen we nu bewijzen voor één stapel. Met inductie kan hetzelde dan bewezen worden voor meerdere stapels. Stel we hebben een spel P (n) Poker Nim met n muntjes. De Nimversie van dit spel heeft dus nimber ?n. Stel de nimber van het spel Poker Nim met n muntjes is G(P (n)) = ?m. We willen bewijzen dat m = n. Je hebt in Poker Nim twee verschillende opties, namelijk een zet doen zoals in het spel Nim of iets uit de zak pakken en toevoegen. Je mag de stapel niet constant houden. Stel dat er k muntjes in de zak zitten. Dan geldt dus dat G(P (n)) = ?mex{0, ..., n − 1, ..., n + 1, ..., n + k}, oftewel dat G(P (n)) = n. Dus de nimber van een spel Poker Nim met één stapel metn stenen is gelijk aan de nimber van het equivalente spel Nim met één stapel met n stenen. Met inductie geldt dan dat de nimbers van het spel Poker Nim gelijk zijn aan die van het Nimspel zonder zak. Strategie Om te zien of je moet beginnen om te winnen, moet je dus kijken naar de nimbers van het Nimspel zonder de zak. Als winnende speler speel je gewoon het spel Nim en leg je nooit stenen aan. Zodra je tegenstander wel stenen aanlegt, moet je deze weghalen in jouw beurt. Het spel is daarna weer zoals het was, alleen is de extra zak iets leger geworden. Uiteindelijk zal het Nimspel eindigen met jouw beurt en is alleen nog de zak over. Als de zak leeg is, heb je gewonnen. Zitten er nog stenen in de zak, zal je tegenstander deze nog moeten opleggen. Maar deze kun je natuurlijk dan steeds weer wegpakken, totdat ook de zak leeg is en het spel eindigt met jouw beurt.

18

4.4. Silver Dollar Game Het spel Een iets ingewikkeldere variant van Poker Nim is de Silver Dollar Game. Dit spel speel je op een strook met eindig veel vakjes, waarop muntjes liggen verspreid. Als je aan de beurt bent mag je een van de muntjes naar links verplaatsen. Je mag hierbij echter niet een ander muntje passeren noch op een vakje gaan liggen waar een ander muntje ligt. Omdat er eindig veel vakjes zijn en je de muntjes alleen naar links mag verplaatsen is dit spel eindig. Het spel is ook equivalent met Nim. Een voorbeeld van Silver Dollar Game is te vinden in Figuur 4.1.

Figuur 4.1.: Een spel Silver Dollar Game dat uit veertien hokjes en vijf muntjes bestaat. Nimberequivalentie In Figuur 4.1 zouden we de ruimtes tussen muntjes als Nimstapels kunnen opvatten. We hebben dan een spel dat bestaat uit nimbers ?1, ?1, ?3, ?2 en ?2. Dit levert echter een probleem op. Het verplaatsen van een muntje kan een Nimstapel verkleinen en tegelijkertijd de Nimstapel die er rechts van ligt vergroten. De subspellen zijn dus niet onafhankelijk. De oplossing voor dit probleem is om de ruimtes tussen de muntjes vanaf rechts te bekijken, en alleen de eerste, derde, vijfde (enzovoorts) ruimtes te bekijken. [7] De overige ruimtes kan je dan opvatten als stenen die bijgelegd kunnen worden uit een zakje, zoals in Poker Nim. In het voorbeeld hebben we dan nimbers ?2, ?3 en ?1. Strategie Bekijk de ”oneven”ruimtes tussen de muntjes als Nimstapels zoals hierboven beschreven. Nu zijn de zetten in Silver Dollar Game op de volgende manier equivalent aan zetten in Nim: het verplaatsen van het tweede muntje van links equivalent met het bijleggen van één muntje op de stapel met nimber ?3. Het verplaatsen van het middelste muntje naar twee hokjes verderop is equivalent met het pakken van twee muntjes uit de stapel met nimber ?3. Door het spel op deze manier te spelen kun je precies uitrekenen of en hoe je kan winnen.

4.5. Kayles Het spel Kayles begint met een rij kegels van willekeurig eindige lengte. Beide spelers gooien met een bowlingbal, zodanig dat ze altijd n kegel of twee aan elkaar grenzende kegels naar keuze perfect omgooien. De speler die geen kegel meer kan omgooien verliest. Kayles is een impartieel spel en volgens de stelling van Sprague-Grundy moet er dus een equivalentie bestaan tussen Kayles en Nim. Nimberequivalentie De equivalentie tussen Kayles en Nim kan worden beschreven door nimbers. De nimber van een spel Kayles met n kegels (notatie: K(n)) kan uitgerekend worden door de volgende formule [8]: G(K(n)) = mex{G(K(a)) ⊕ G(K(b))} met a + b = n − 1 of a + b = n − 2. Immers, in een spel Kayles met n kegels mag je één of twee kegels omgooien. De vervolgspellen van het spel Kayles zullen dus altijd n − 1 of n − 2 kegels bevatten. We zien nu dat bijvoorbeeld het spel met vier kegels (K(4)) equivalent is aan nimber ∗1,

19

namelijk G(K(4)) = mex{G(K(0)) ⊕ G(K(2)), G(K(0)) ⊕ G(K(3)), G(K(1)) ⊕ G(K(2)), G(K(1)) ⊕ G(K(1))} = mex{∗2, ∗3, ∗0} = ∗1 We verkijgen op deze manier de volgende nimbertabel: n nimber = G(n)

0 ∗0

1 ∗1

2 ∗2

3 ∗3

4 ∗1

5 ∗4

Elk moment in het spel kun je beschrijven aan de rijen kegels die er nog over zijn. Als we deze rijen met k kegels, nimber *n geven (zie Tabel 1), hebben we de equivalentie gevonden. Aan het begin van het spel, waar er n rij is met k kegels, is de nimber van het spel dus *n. Als de rij 0 kegels bevat, is de nimber *0 en is het spel dus P-positie. Dit klopt ook want als er 0 kegels zijn heeft de eerste speler verloren (hij kan immers niet spelen). Als de rij k 6= 0 kegels bevat, heeft het spel dus nimber ∗n 6= ∗0 en is het spel dus N-positie. De eerste speler kan dan ook altijd winnen in Kayles, zoals bij de winnende strategie hieronder beschreven zal worden. We kunnen nu elke situatie gedurende het spel Kayles onderscheiden in twee mogelijkheden. De eerste mogelijkheid is een symmetrisch spel. Dit definiëren we als een spel waarin elke rij met k kegels in paren voorkomt. Als we dan in een symmetrisch spel elke rij beschrijven met een nimber *n, is de som van de nimbers altijd nul, immers *n+*n=*0. Een symmetrisch spel Kayles is dus altijd P-positie volgens de nimbers. Een asymmetrisch spel definiëren we nu als een spel waarbij voor tenminste één rij met k kegels, geen andere rij met k kegels voorkomt. De eerste speler kan het spel nu verdelen in paren van rijen met hetzelfde aantal kegels, waarbij de nimber van het spel vanwege symmetrie *0 wordt. Omdat de volgende speler maar één nimber mag veranderen, zal hij de som van de nimbers nooit *0 kunnen houden. Een asymmetrisch spel Kayles is dus altijd N-positie. Met toepassing van deze kennis kan de winnende strategie bepaald worden. Strategie Bij Kayles kan de eerste speler altijd winnen door de ”symmetriestrategie”te gebruiken: hij of zij moet kegels zodanig omgooien dat de rij kegels in twee gelijke kleinere rijen opgedeeld wordt. De eerste speler gooit dus en kegel in het midden om als de beginrij een oneven lengte heeft, en twee kegels in het midden als de rij een even lengte heeft. Daarna kan de eerste speler de zet van de tweede speler altijd kopiren in de andere rij en zal zo de laatste kegel kunnen omgooien.

4.6. Nimstring Het spel Een impartieel spel dat veel te maken heeft met Dots and Boxes is het spel Nimstring. Het wordt op hetzelfde speelveld als Strings and Coins gespeeld, dus met muntjes die aan maximaal vier touwtjes vastzitten. Elke keer als je een muntje losknipt, moet je nog een touwtje doorknippen. De speler die aan zet is maar geen touwtje meer kan doorknippen heeft verloren. Het spel Nimstring is dus een impartieel spel net als Nim, met als extra regel dat je nog een keer mag als je een muntje hebt en dat je daardoor juist wil dat de andere speler het laatste muntje pakt. Het spel Nimstring zal ons helpen meer te begrijpen over Dots and Boxes,

20

doordat we een gedeelte van het spel Dots and Boxes kunnen opvatten als een spel Nimstring. Hier komen we in het hoofdstuk Dots and Boxes uitgebreid op terug. Equivalentie Volgens het lemma van Sprague en Grundy is elk spel Nimstring equivalent met een nimber. De extra mogelijkheid van meerdere zetten per beurt leidt tot een nieuwe nimber, namelijk de loony, Á, hier komen we later nog op terug. We beginnen met het kijken naar grijpbare muntjes. Dit zijn muntjes die nog aan één touwtje vastzitten. Als je een grijpbare munt hebt, heb je twee opties. Je kunt het muntje pakken en een andere zet doen in de rest van het spel, of je kunt het muntje niet pakken en meteen doorgaan in het spel. We kunnen de grijpbare

Figuur 4.2.: Linksboven: grijpbaar muntje. Rechtsboven: Twee grijpbare muntjes. Linksonder en rechtsonder: je mag kiezen of je wel of juist niet in het spel in de wolk wil beginnen. Een touwtje dat aan de grond vastzit wordt als een pijltje weergegeven. muntjes opdelen in verschillende mogelijke situaties, zie Figuur 4.2. Het hangt van de situatie af wat de beste zet is. In de bovenste rij van Figuur 4.2 moet je in de wolk gaan beginnen, dus je kan de grijpbare muntjes net zo goed pakken. In de onderste rij ben je in een luxe positie: je mag bepalen of je in het spel in de wolk wil beginnen. Als het spel in de wolk een N-positie is, dan pak je de munten door touwtjes A en B door te knippen en begin je daarna in de wolk.

21

Als het spel in de wolk P-positie is, dan wil je dat de andere speler in de wolk begint. In de voorbeelden op de onderste rij in Figuur 4.2 moet je dan touwtje B doorknippen. Nu willen we graag nimbers koppelen aan Nimstringspellen en wel zo dat we de gebruikelijke mexregel voor de optelling kunnen gebruiken. De situaties in de onderste gevallen in Figuur 4.2 maken dit alleen iets minder eenvoudig. Zoals we gezien hebben kun je in deze situatie kiezen of je zelf wil beginnen in de wolk, of dat je de andere speler laat beginnen, afhankelijk van de spelsituatie in de wolk. Dit betekent dat welk spel je ook bij dit spel optelt, het is altijd N-positie. Je kunt immers altijd winnen. We weten dat een spel met N-positie equivalent is aan nimber ?n 6= 0. Deze situaties moeten de deelspellen die bestaan uit de muntjes buiten de wolk een nimber ?x hebben waarvoor geldt: • ?x + ?y 6= 0. • In het bijzonder: ?x + ?x 6= 0. Tot nu toe hebben we geen nimber gezien die voldoet aan deze eisen. Daarom introduceren we de loony nimber, met waarde Á. De algemene regel voor de loony nimber is dus: Á+0 = Á+ ? 1 = Á+ ? 2 = ... = Á+Á= Á Merk hierbij op dat we bij het gebruiken van de mexregel, de loony positie als ∞ kunnen beschouwen. Nu we de loony hebben ge¨ıntroduceerd, kunnen we verdergaan met het bepalen van de nimposities. Dit bepalen is een kwestie van stug doorwerken, in de appendix bevindt zich een uitwerking van vele nimposities uit Winning Ways 3. Met betrekking tot de grijpbare muntjes is er een aantal regels dat we kunnen definiëren: • De waarde van een leeg Nimstringspel is 0. • De nimbers van de spellen uit de bovenste voorbeelden in Figuur 4.2 zijn gelijk aan de nimbers van het spel in de wolk. Spellen met slechts grijpbare munten hebben dus nimber ?0. • De waarden van de onderste spellen in Figuur 4.2 zijn Á. • De waarde van een spel zonder grijpbare muntjes kan worden bepaald met behulp van de mexregel. We zullen hier een aantal voorbeelden van geven. In Figuur 4.3 is de enige optie om het touwtje door te knippen. Je bent dan nog een keer aan de beurt omdat je een muntje kan pakken. Er kunnen geen zetten meer gedaan worden, dus je verliest. Dit spel is dus P-positie en heeft nimber ?0. Vanuit Figuur 4.4 kun je naar de spelsituatie in Figuur 4.3. De mex geeft nu dus nimber ?1 aan dit Nimstringspel. We zien zo dat we op dezelfde manier nimbers kunnen geven met de mexregel. De nieuwe nimber ”Á”geeft zetten aan waarin de andere speler kan kiezen of hij muntjes pakt of zijn tegenstander dwingt om de muntjes te pakken. Zoals eerder gesteld telt deze nimber niet mee in de mexregel. We kunnen dus door stevig door te rekenen (of te tekenen) bepalen wat de nimbers zijn van elk spel Nimstring. Zie de Appendix voor een uitgebreid uitgewerkt voorbeeld.

22

0

0

0

0

1

1

Figuur 4.3.: PFiguur 4.4.: Npositie positie

Figuur 4.5.: Werken met loony nimber

de

Er is een specifiek soort Nimstringgraaf waarvan de nimber makkelijk te bepalen is. Deze zal later handig van pas komen bij de koppeling naar Dots and Boxes. Deze zogenaamde rank is een Nimstringgraaf zonder cykels of grijpbare munten waarin alle knooppunten (munten waaruit drie touwtjes lopen) op één pad liggen (de stam). Een keten die een eind (een touwtje dat aan de grond vastzit) verbindt met een knooppunt heet een twijg. Een Kayles-rank is een rank die aan een aantal specifieke voorwaarden voldoet. Ten eerste moet de afstand tussen twee niet aangrenzende stops (dit zijn eindes of knooppunten) lang zijn, dus er moeten minimaal drie munten tussen zitten. Bovendien moeten alle twijgjes kort zijn. Een voorbeeld van een Kayles-rank staat in Figuur 4.6.

Figuur 4.6.: Een voorbeeld van een Kayles-rank. De afstand tussen niet aangrenzende eindes is lang. Zodra een Nimstringspel de vorm van een Kayles-rank heeft, is de nimber met gemak te bepalen. Kayles-ranken hebben namelijk dezelfde nimbers als het spel Kayles, waarbij het aantal knooppunten als het aantal kegels geteld wordt. In Figuur 4.6 hebben we drie knooppunten, dus de nimber van deze Nimstringgraaf is ?3. Er is ook een extra optelregel voor deze Kayles-vines, namelijk: lange ketens knappen. Dat ziet er in een Figuur als volgt uit:

Figuur 4.7.: Een lange afstand tussen twee knooppunten kan worden opgebroken in twee lange afstanden naar een einde. We kunnen een Nimstringgraaf (en in het bijzonder een Kayles-rank) waarin een lange afstand tussen twee knooppunten voorkomt dus opbreken in twee Nimstringgrafen waarvan we de nimber kunnen bepalen. De binaire optelling is dan gewoon weer van toepassing. Zoals we in hoofdstuk 3 gezien hebben, is Kayles een spel met een rij kegels waarvan je steeds één of twee kegels tegelijk moet omgooien. Van deze zetten zijn er equivalente versies in

23

Kayles-ranken. Het omgooien van één kegel is equivalent aan het wegknippen van één twijg en het omgooien van twee kegels is equivalent aan het wegknippen van een touwtje in de stam. Deze zetten zijn te zien in Figuur 4.8 en 4.9. In Figuur 4.8 knapt de lange keten na verwijdering van het middelste einde. Er ontstaan dan twee dezelfde Nimstringgrafen, dus deze zet heeft nimber ?0. In een rij Kayles met drie kegels zou de middelste kegel omgegooid zijn met hetzelfde gevolg. In Figuur 4.9 ontstaan er na het doorknippen van een touwtje in een stam twee Kayles-ranken: de linker heeft één twijg en dus nimber ?1 en de rechter heeft nul twijgen en daarmee nimber ?0. Deze zet heeft dan ook een spelsituatie met nimber ?1 tot gevolg. In Kayles met drie kegels is de equivalente zet om twee aangrenzende kegels te verwijderen zodat er slechts één kegel overblijft.

Figuur 4.8.: In een Kayles-rank is het wegknippen van een twijg equivalent met het omgooien van één kegel in Kayles.

Figuur 4.9.: Het wegknippen van een touwtje uit de stam is equivalent met het omgooien van twee kegels in Kayles. Merk op dat weinig Nimstringgrafen Kayles-ranken zijn, omdat Kayles-ranken aan een strenge voorwaarde moeten voldoen: de afstand tussen twee niet aangrezende eindes moet lang zijn. Dan moeten er dus al een hoop touwtjes weggeknipt zijn. We zullen deze theorie in de volgende twee hoofdstukken toepassen op gedeeltes van het spel Dots and Boxes. Winnende strategie Nu we weten hoe de nimbers van een Nimstringgraaf kunnen bepalen, is de winnende strategie hier direct uit af te leiden. De winnende strategie is om één zet vooruit te kijken en de nimbers van de mogelijke vervolgspellen te bepalen. Indien mogelijk, is de winnende zet om een touwtje weg te knippen dat leidt naar een vervolgspel met nimber ? 0.

24

5. Dots and Boxes 5.1. Inleiding In dit verslag werken we naar het verkrijgen van een beter inzicht in het spel Dots and Boxes, ook wel Kamertje Verhuren genoemd. Dots and Boxes is een spel dat begint met een speelvlak met een aantal punten. Spelers mogen de punten één voor één verbinden door een lijn tussen de punten te tekenen. Als een speler een lijn zet die een hokje (een ”box”) completeert, moet deze speler opnieuw een lijn zetten. Een speler hoeft een hokje niet per se af te maken als daar een kans voor is. Als alle hokjes compleet zijn, is het spel afgelopen. De speler met de meeste hokjes wint. Dots and Boxes is dan ook geen impartieel spel, want de speler die de laatste zet doet wint niet per se. Dots and Boxes is een ingewikkeld spel dat nog niet wiskundig is opgelost. We zullen winnende strategieën bespreken en daarna ingaan op het verband met het impartiële spel Nimstring. Omdat Dots and Boxes kan variëren in het aantal punten, zullen we beginnen bij vierkante spellen met vier hokjes en uitbreiden naar strategieën die werken voor alle (eindige) rechthoekige Dots and Boxes spellen.

5.2. Strings and Coins We zullen van tijd tot tijd gebruik maken van een duale vorm van Dots and Boxes: Strings and Coins. In dit spel wordt er gespeeld met muntjes die vastzitten aan vier touwtjes. Als je aan de beurt bent mag je een touwtje losknippen en als alle vier de touwtjes los zijn, dan mag je het muntje pakken. Degene met de meeste muntjes wint. Je kunt alle spellen van Dots and Boxes omzetten in een spel Strings and Coins, wanneer we de lege vakjes zien als muntjes en de lijntjes die je kunt zetten zien als touwtjes.We zullen van tijd tot tijd Strings and Coins gebruiken omdat het vaak makkelijker te visualiseren is, maar de uitkomsten zijn exact hetzelfde. Zie Figuur 5.1 voor een voorbeeld van deze spellen. Strings and Coins met de regel van normaal spel, waarin de speler die geen zet meer kan doen verliest, is Nimstring. Dit spel is uitgebreid beschreven in hoofdstuk 4.

Figuur 5.1.: Elk spel van Dots and Boxes kan worden omgezet in een spel van Strings and Coins.

25

5.3. Strategie Dots and Boxes We zullen beginnen bij 2 × 2 Dots and Boxes, met 2 bij 2 hokjes, dat volledig is opgelost. Daarna gaan we in op bijzondere zetten en strategieën waarmee spelers in een eindig spel Dots and Boxes winst kunnen afdwingen. Deze strategieën zijn uitgelegd en toegepast op het Nederlands Kampioen Kamertje verhuren op 18 juni 2013. Zie voor meer informatie de website van het NK: http://www.rolandvdv.nl/NKK 2 × 2 Dots and Boxes Een vierkant spel met negen punten en vier hokjes kan altijd gewonnen worden door de eerste speler. Hier is geen simpel bewijs voor maar kan met brute kracht worden uitgerekend, door alle opties na te gaan. De eerste speler moet dan een zet doen aan de rand (waar maakt niet uit want het is volledig symmetrisch). Op alle vervolgzetten van speler 2 zal hij dan zo kunnen reageren dat hij uiteindelijk wint. Zie Figuur 5.2 voor een voorbeeld van een spel met vier hokjes waarbij de beginnende speler wint.

Figuur 5.2.: De eerste speler kan altijd winnen bij Dots and Boxes. Hierboven is een voorbeeld uitgewerkt. Ali (speler 1) en Bob (speler 2) spelen een spelletje Dots and Boxes. Ali wint.

26

5.3.1. Bijzondere zetten Bij een spel met negen hokjes begint strategie een rol te spelen. In deze paragraaf zal een aantal bijzondere zetten besproken woden. Het is van belang om niet altijd ”hebberig”te spelen, maar op het juiste moment hokjes weg te geven. In sommige situaties is het wel goed om hebberig te spelen en een hokje te pakken. Dit kun je vergelijken met de grijpbare muntjes in het spel Nimstring. In Nimstring maakt het niet uit of je deze muntjes pakt of niet, in Dots and Boxes maakt het wel degelijk uit, je wil namelijk de meeste hokjes. Het loont altijd om een vrij hokje oftwel een keten van lengte 1 te pakken. Hetzelfde geldt voor een keten van lengte 2 of 3 met gesloten randen. Zie Figuur 5.3.

Figuur 5.3.: In bovenstaande situaties loont het om de beschikbare hokjes te pakken. In Dots and Boxes ontstaan er vaak lange ketens (waarbij we een lange keten definiëren als minstens drie hokjes) omdat spelers zo lang mogelijk proberen te voorkomen dat ze een hokje moeten weggeven. De kunst is om de andere speler de keten te laten openen. Je kunt dan de hele keten innemen. Als er meerdere ketens zijn, is het verstandig om de laatste twee hokjes aan je tegenstander te geven. De tegenstander moet dan namelijk de volgende keten ook weer openen. Zie Figuur 5.4 voor een voorbeeld waarin deze strategie cruciaal is.

Figuur 5.4.: In de derde spelsituatie had Bob drie hokjes kunnen pakken, maar hij offert twee hokjes op zodat Ali de volgende keten moet openen. Dit gebeurt in spelsituatie 4. Bob wint. Zo een ”opofferingszet” wordt ook wel een double-dealing zet genoemd. Een double-dealing

27

zet wordt (vaak meteen) gevolgd door een zet waarbij twee hokjes met één lijntje dicht gemaakt worden (een double-cross zet). De zet vóór een double-dealing zet heet een loony zet. Dit is een zet die de volgende speler laat kiezen of hij of zij een lange keten of cykel pakt of juist opoffert, afhankelijk van wat de winnende strategie is. Deze zet is equivalent aan een loony zet in het spel Nimstring, uitgelegd in hoofdstuk 4. Voorbeelden van deze drie bijzondere zetten zijn te vinden in Figuur 5.5.

Figuur 5.5.: De groene streepjes geven de speciale zet weer.

Stelling 5.1. Een loony zet geeft de controle aan de volgende speler, die minstens de helft van de overgebleven hokjes kan pakken.

Figuur 5.6.: De controle ligt bij de speler die nu aan zet is. Bewijs: We stellen ons een spel Dots and Boxes voor in de vorm van Strings and Coins. Een loony zet is een zet die leidt naar een spel zoals in Figuur 5.6, waarbij G een willekeurig spel is waarvan je weet of je moet beginnen of als tweede moet gaan om zoveel mogelijk muntjes te pakken. G kan ieder spel zijn behalve een enkel muntje. Stel nu dat de speler die als eerste in het spel G begint, n muntjes kan pakken. Dan heeft de speler van het spel Loony met G twee opties: • Hij pakt de twee muntjes weg van de loony en is vervolgens aan de beurt in G en pakt dus n + 2 muntjes • Hij knipt de twee muntjes van de loony af (dit is een double-dealing zet) en laat de ander beginnen in het spel G. De ander pakt dus n + 2 muntjes en de eerste speler pakt de rest. Dus de speler die begint in de loony positie kan n + 2 muntjes pakken of alles behalve n + 2 muntjes. Een van deze twee opties moet minstens de helft van de overgebleven muntjes zijn. Een loony zet geeft dus de controle aan de volgende speler in Strings and Coins dus ook in

28

Dots and Boxes, waarbij hij minstens de helft van de overgebleven hokjes kan pakken. Het gevolg van deze stelling is dat een loony zet, dus de zet die leidt tot een loony positie, een verliezende zet is. De speler die de loony positie voorgeschoteld krijgt zal namelijk altijd het beste aantal muntjes kunnen kiezen. Beide spelers zullen dus proberen te voorkomen dat ze een loony zet moeten doen. Een strategie bij Dots and Boxes is dan ook om te zorgen dat je tegenstander een loony zet doet. Maar wat doe je in de rest van het spel?

5.3.2. The Long Chain Rule Bij Dots and Boxes hangt de winnende strategie af van het spelnummer dat je hebt: de eerste speler speelt steeds de oneven zetten en de tweede speler speelt de even zetten. Spelers doen er verstandig aan om te spelen volgens de Long Chain Rule, die volgt uit het volgende lemma. Definitie 5.2. Voor spelers 1 en 2 in een spel Dots and Boxes geldt: • p + K + D = 0 mod 2 (speler 1) • p + K + D = 1 mod 2 (speler 2) met p = aantal punten, K = aantal lange ketens, D = aantal double-crosses. Bewijs. In dit bewijs definiëren we de volgende symbolen: Z − = aantal zetten tot nu toe gedaan Z + = aantal mogelijke zetten nog te doen Z = Z − + Z + = aantal zetten mogelijk van de beginpositie B = aantal beurtwisselingen H − = aantal hokjes tot nu toe ingenomen H + = aantal hokjes dat nog ingenomen kan worden H = H − + H + = aantal hokjes in het spel K = aantal lange ketens D = aantal double-crosses S = de speler die aan de beurt is, speler 1 of speler 2 p = aantal punten

Als het spel gereduceerd is tot een aantal lange ketens, geldt er: Z + = K + H + . Immers, in elke keten moet één streepje meer gezet worden (om de keten te openen) dan dat er hokjes zijn. Verder geldt Z − = B + H − − D omdat bij elke zet ofwel een beurt werd afgemaakt, of een hokje werd gecompleteerd, of twee hokjes werden gecompleteerd (double-cross). Door het optellen van deze vergelijkingen volgt: Z = K + B + H − D. Als er slechts lange ketens over zijn, dan moet degene die aan beurt is een loony zet maken. Je wil dus het aantal lange ketens zo manipuleren dat de tegenstander daarna als eerste aan de beurt is. We definiëren nu S als S = 0 voor speler 2 en S = 1 voor speler 1. Als je speler 1 bent, wil je dus dat S = 0, want dan is je tegenstander aan zet en zal hij dus de

29

ketens voor je openen. Evenzo wil speler 2 dat S = 1. Dus wat je wil is dat S = B mod 2. We kunnen nu bewijzen dat S = (p + K) mod 2, wat zoveel zegt als dat de eerste speler wil dat p+K even is (want dan S = 0) en dat de tweede speler wil dat p+K oneven is (dus S = 1). Omdat B = Z − K − H + D geldt: S ≡ (Z + K + H + D)( mod 2). Er geldt (in een rechthoekig n × m Dots and Boxes spel): H = (n − 1) ∗ (m − 1) en Z = (n − 1) ∗ m + n ∗ (m − 1). Dus: H + Z = nm − n − m + 1 + nm − m + nm − n = 3nm − 2m − 2n + 1 = (nm + 1) = (p + 1)

mod 2 mod 2

Samengevoegd geven deze formules: 1 + S = (K + D + p) mod 2. Dit geeft: • 2 = 0 = p + K + D mod 2 voor speler 1 • 3 = 1 = p + K + D mod 2 voor speler 2

Gevolg 5.3 (Long Chain Rule). Het is voor de spelers optimaal om het spel Dots and Boxes respectievelijk te laten voldoen aan: • p + K = 0 mod 2 (speler 1) • p + K = 1 mod 2 (speler 2) Dus speler 1 wil altijd dat er een even aantal ketens plus punten is, en speler 2 een oneven aantal. Bewijs. We kunnen aannemen dat er geen double-crosses zullen onstaan, dus D = 0. De spelers spelen namelijk perfect en zullen dus niet vroegtijdig hokjes weggeven, dus er geldt dan: 1 + S ≡ (K + p) mod 2.

5.4. Typen ketens Omdat het aantal punten van het spel vast ligt, zullen de spelers dus proberen om het aantal ketens te manipuleren. Als je dit aantal op de juiste manier naar je hand gezet hebt, zal de andere speler de ketens moeten openen en kan je door middel van double-dealing zetten in alle ketens het grootste gedeelte van de hokjes pakken. Je hebt dan de controle. Hierbij moet opgemerkt worden dat een cykel niet als lange keten behandeld wordt. Een cykel is een gesloten lus van minstens vier hokjes, zie de figuur hieronder. We tellen een cykel als twee ketens. Immers, er moeten vier hokjes opgeofferd worden (met twee double crosses als gevolg) om de controle te behouden. Als een speler merkt dat hij of zij de controle gaat verliezen, dan doet hij/zij er verstandig aan om de ketens zo kort mogelijk te

30

Figuur 5.7.: Cykels van respectievelijk lengte vier en zes. houden en om 4-cycles (quads) te creëren. De speler die controle wil houden zal je namelijk alle hokjes in een quad geven, omdat jij anders de controle kan overnemen. Zo kan je proberen om alsnog zo veel mogelijk hokjes te bemachtigen. Het manipuleren van het aantal ketens kan op twee manieren: je kunt meer of juist minder ketens maken door hokjes op te offeren. Deze worden toegelicht in onderstaande figuren.

Figuur 5.8.: Het manipuleren van ketens

31

In de linkerfiguur wil de speler die aan zet is een even aantal ketens hebben. Er zijn immers 25 punten en er zijn 19 beurtwisselingen geweest (want er zijn 19 streepjes gezet en nog geen hokjes gecompleteerd), dus speler 2 is aan beurt. Deze speler wil de som van het aantal punten en het aantal ketens oneven hebben. Er is in Figuur 5.4 nu één keten aanwezig. Speler 2 wil dus een extra keten maken. Dit doet hij of zij door een dreigende cykel in een keten te veranderen. Hierbij wordt een hokje opgeofferd. In de rechterfiguur wil de speler die aan zet is (speler 2) een oneven aantal lange ketens in het spel hebben. Speler 1 dreigt twee ketens te creëren. Speler 2 dwarsboomt dit door een potentiële lange keten door te breken. Hij of zij offert daarbij twee hokjes op. Bij het tellen van het aantal ketens dat aanwezig is, moet men ook rekening houden met zogenaamde afhankelijke ketens. We zullen deze term toelichten aan de hand van een paar andere definities. Twee hokjes heten buren van elkaar als de lijn die hen scheidt nog niet getekend is. Stel je nu voor dat er een denkbeeldige ”buitenrand” om het speelveld heen is, waarvan de hokjes aan het begin van het spel buren zijn van de hokjes die aan de buitenkant van het speelveld liggen. Nu heet een keten onafhankelijk als beide uiteinden van de keten buren zijn van de buitenrand. Andere ketens heten afhankelijk. Een hokje waar drie of vier afhankelijke ketens samenkomen heet een joint. We beschouwen een afhankelijke cykel als een afhankelijk keten waarvan begin en uiteinde samenkomen in dezelfde joint. Het aantal lange ketens is triviaal als er alleen onafhankelijke ketens zijn. Wanneer er afhankelijke ketens in het spel komen, kan een zet in een keten ervoor zorgen dat andere ketens als het ware samensmelten. Het tellen van het aantal ketens gaat nu als volgt: • Neem de langste keten als stam. • Als een zijtak uit minstens drie hokjes bestaat, dan telt dit als één additionele keten. Anders kan je de keten negeren, deze hokjes zullen opgeofferd worden. Voorbeelden van spelsituaties met zijketens zijn afgebeeld in Figuur 5.9.

Figuur 5.9.: Voorbeelden van een korte en een lange zijketen. In beide spelsituaties zijn er vier lange ketens aanwezig.

32

Het opofferen van hokjes en de Long Chain Rule zijn voorbeelden van strategieën waarmee een speler winst kan afdwingen. Een spel Dots and Boxes zal uiteindelijk meestal neerkomen op een spelsituatie waarin een aantal ketens van het spel samen genoeg hokjes bevatten om het spel te kunnen winnen. Een voorbeeld hiervan is te vinden in Figuur 5.10. In dit spel wil je dat je tegenstander de eerste zet doet in de lange keten, zodat jij de hele keten kan pakken. We kunnen nu uitrekenen wie er gaat winnen door de theorie van Sprague en Grundy toe te passen. Hierbij maken we gebruik van het impartiële spel Nimstring. Meer manieren om het aantal ketens af te dwingen zijn beschreven in het artikel ’Forcing your Opponent to Stay in Control of a Loony Dots-and-Boxes Endgame’ door Elwin Berlekamp en Katherine Copersino [12]

Figuur 5.10.: Voorbeeld van een vergevorderd spel waarin bekend is wie er gaat winnen.

5.5. Benadering van Dots and Boxes met nimbers We kunnen Nimstring gebruiken om uit te rekenen wie in vergevorderde spellen zoals in Figuur 5.10 kan winnen en welke zet de winnende zet is. De winnende strategie is om het spel buiten de lange keten te zien als een spel Nimstring. Dit is afgebeeld in Figuur 5.11.

Figuur 5.11.: Zie het spel buiten de lange keten als een spel Nimstring.

33

Je wil winnen in dit spel Nimstring, want dan is de andere speler aan zet en zal hij of zij de lange keten moeten openen. Je kan dan genoeg hokjes pakken om het spel te winnen. Zoals we in hoofdstuk 4 gezien hebben, is Nimstring een impartieel spel en kunnen we het spel dus een nimber geven. Dit gaat als volgt:

Figuur 5.12.: De optelling van drie spellen Nimstring Het spel heeft dus nimber ?n+?1+?n = ?1 en zal gewonnen kunnen worden door het middelste touwtje weg te pakken. Het spel is dan symmetrisch gemaakt en heeft dus nimber ?0. De eerste speler kan Nimstring winnen en wint daarmee het hele spel Dots and Boxes. Dit wordt gegeneraliseerd in de volgende figuur:

Figuur 5.13.: Winnen in Nimstring is winnen in het hele spel! Zodra je opmerkt dat er ergens in het spel Dots and Boxes een situatie gaat ontstaan waarbij je genoeg hokjes kan pakken om te winnen zodra er nog één streepje gezet wordt, dan wil je de rest van het spel opvatten als een spel Nimstring. Zorg dat je tijdig oplet of je het spel Nimstring wel kan winnen en gebruik dan nimbers om de winnende zetten te vinden.

34

6. 1 × n Dots and Boxes 6.1. Een open probleem In het hoofdstuk ’Unsolved Problems in Combinatorial Games’ in het boek Games of No Chance 3 [12] beschrijft R. Guy het open probleem van 1×n Icelandic Dots and Boxes.Dit is een veld van 2 bij n + 1 puntjes, dus 1 bij n hokjes. Hierbij zijn de bovenste verticale lijntjes en het linker verticale lijntje al ingevuld. Deze spelsituatie lijkt vrij eenvoudig, maar blijkt

Figuur 6.1.: 1 × n Dots and Boxes heel moeilijk te zijn. Er is niet bekend wie er zou moeten beginnen om het spel te winnen. Rastislav Lenhardt [9] heeft het probleem iets vereenvoudigd naar het zogenaamde Greenlandic Dots and Boxes. Hierbij is ook het rechter verticale streepje ook al ingevuld. Hij heeft een algoritme geschreven waarmee met brute kracht uitgerekend kon worden wat de winnende posities zijn. Wij hebben twee invalshoeken gekozen om dit probleem te benaderen. Ten eerste bekijken we het spel in Nimstring, via Kaylesvines. De tweede invalshoek is het bekijken van de tabel van Lenhardt, die situaties gedeeltelijk uit te werken en iets te zeggen over oneven en even spellen.

6.2. 1 × n Greenlandic Nimstring 6.2.1. Nimstring We hebben gezien dat het spel Nimstring veel kan zeggen over het spel Dots and Boxes. Het kan dus belangrijk zijn om de nimbers van het spel 1×n Greenlandic Nimstring te bekijken. We hebben dit tot en met n = 6 uitgeschreven, zoals in Figuur 6.2 is weergegeven. Aanvankelijk dachten we een patroon gevonden te hebben van ?1 bij een even aantal muntjes en ?2 bij een oneven aantal muntjes. Tot onze verrassing bleek de nimber van n = 6 echter ?3. Het

35

patroon gaat dus niet op, zie ook Figuur 6.2. Verder uitrekenen lijkt met pen en papier bijna onmogelijk te zijn, of in ieder geval heel veel monnikenwerk. Een algoritme met de computer zou eventueel uitkomst bieden voor het vinden van een patroon. Onze resultaten leiden tot de volgende hypothese: Hypothese 6.1. Een spel 1 × n Greenlandic Nimstring met meer dan 1 muntje is altijd een N-positie. Een manier om dit te bewijzen zou kunnen zijn, te bewijzen dat in elk spel er een touwtje is dat vervolgspel ?0 oplevert. Dan is de mex van alle nimbers immers nooit 0 en dus is het spel nooit een P-positie.

0

n=1

0 1

n=2

1

n=3 1

1

2

0

1

n=5

2

n=6

2

1

1

2

0 1

2

1

0

0

1

2

3 3

0 4

2

3 0

1

2

2

2

n=4

2

1

0

4

2

Figuur 6.2.: Nimbers in 1 × n Greenlandic Nimstring

36

3

6.2.2. Kayles-ranken Hoewel er geen mooi patroon lijkt te zijn bij Greenlandic Nimstring, komen iets verder gevorderde spellen van 1 × n Greenlandic Nimstring dikwijls neer op posities in Kayles. Kaylesranken zijn beschreven in Hoofdstuk 4 en zullen nu toegepast wordt op 1 × n Greenlandic Dots and Boxes. Een voorbeeld van een spelsituatie in Greenlandic Dots and Boxes die beschreven kan worden met een Kayles-rank staat in Figuur 6.3. De equivalente versie in Nimstring is weergegeven in Figuur 6.4.

Figuur 6.3.: Een voorbeeld van 1 × n Greenlandic Dots and Boxes waarvan de nimber met behulp van Kayles berekend kan worden.

Figuur 6.4.: De equivalente Nimstringversie van bovenstaand spel in Dots and Boxes Zodra een Nimstringspel de vorm van een Kayles-rank heeft, is de nimber met gemak te bepalen. Kayles-ranken hebben namelijk dezelfde nimbers als het spel Kayles, waarbij het aantal knooppunten als het aantal kegels geteld wordt. Zoals we gezien hebben in Hoofdstuk 4, zijn er in Nimstring equivalente zetten van het omgooien van één of twee kegels in Kayles. Deze zetten zijn nogmaals weergegeven in Figuur 6.5 en 6.6

Figuur 6.5.: In een Kayles-rank is het wegknippen van een twijg equivalent aan het omgooien van één kegel in Kayles.

37

Figuur 6.6.: Het wegknippen van een touwtje uit de stam is equivalent aan het omgooien van twee kegels in Kayles. Deze voorbeelden uit Hoofdstuk 4 kunnen we nu koppelen aan 1 × n Greenlandic Dots and Boxes. Het verwijderen van één of twee kegels is in Figuur 6.7 respectievelijk links en rechts weergegeven.

Figuur 6.7.: Een voorbeeld van 1 × n Dots and Boxes waarvan de nimber met behulp van Kayles berekend kan worden. Merk ook nu weer op dat weinig Nimstringgrafen Kayles-ranken zijn, omdat Kayles-ranken aan een strenge voorwaarde moeten voldoen: de afstand tussen twee niet aangrezende eindes moet lang zijn. Dan moeten er dus al een hoop touwtjes weggeknipt zijn. Als we weer terugkoppelen naar 1 × n Dots and Boxes, moeten er daarin dus al redelijk veel streepjes gezet zijn. Er mogen geen twee lege puntjes naast elkaar staan, want dan is de afstand tussen twee eindes niet meer lang. Ook al heeft het benaderen met nimbers ons niet direct geholpen bij het oplossen van het open probleem van 1 × n Greenlandic Dots and Boxes, was het toch verrassend en interessant hoe twee spellen die zo ver uit elkaar lijken te liggen, in sommige situaties equivalent aan elkaar kunnen zijn. We zullen nu de andere benadering van het open probleem toelichten.

6.3. 1 × n Dots and Boxes Een tweede benadering van het open probleem is het gebruiken van brute kracht. Rastislav Lenhardt heeft een thesis geschreven over het open probleem Greenlandic 1 × n Dots and Boxes [9]. Hij heeft een algoritme geschreven in C++ waarin twee spelers perfect tegen elkaar spelen. Hij geeft de uitkomst van een spel met breedte n weer in een tabel met val(1 × n) (zie ook Tabel 6.1): Definitie 6.2. val(1 × n) = # hokjes speler - # hokjes speler 2 (aan het einde van het spel bij perfect spel).

38

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

val(1 × n) 1 -2 3 0 1 0 3 0 1 0 1 0 1 0 1

Tabel 6.1.: Berekende waarden van val(1 × n)

Uit deze tabel blijkt dat de eerste speler altijd kan winnen of gelijk spelen, behalve in een spel met twee hokjes. De vraag die we ons nu kunnen stellen is of het patroon van 0,1,0,1 ook doorgaat. Als dit zo zou zijn dan kun je in het algemeen stellen dat als je een groot spel Greenlandic 1 × n hebt met een even aantal hokjes, je altijd gelijk zult spelen, en met oneven aantal hokjes wint met 1 hokje verschil. Lenhardt stelt uit deze tabel een tweetal hypotheses op: Hypothese 6.3. Als n is even en n > 2 dan val(1 × n) = 0 Hypothese 6.4. Als n is oneven en n > 7 dan val(1 × n) = 1 Deze hypothesen zullen we nu gedeeltelijk bewijzen. Een derde hypothese die Lenhardt stelt is belangrijk voor ons bewijs. Hypothese 6.5. Als voor twee spellen Dots and Boxes G en G0 G = G0 dan val(G + G0 ) = 0

6.4. Kleine spellen Om dit probleem aan te pakken, beginnen we met het uitschrijven van de kleinste spellen. Hieronder zie je de mogelijkheden van spellen met 1, 2 en 3 hokjes. Zoals je ziet klopt dit met de tabel van Lenhardt. Voor n = 5 en n = 7 is de winnende strategie voor speler 1 uitgewerkt in respectievelijk Figuur 6.9 en Figuur 6.10. Dat speler 1 niet een hogere val(1 × n) kan bereiken is hier niet uitgewerkt.

6.5. Symmetrisch Dots and Boxes We hebben nu in een paar kleine gevallen gezien dat de berekening van Lenhardt klopt. We vroegen ons echter ook af of we de tabel kunnen doortrekken naar het algemene geval. Zoals gezegd heeft Lenhardt een aantal hypotheses opgesteld. Hypothese 6.5 zegt dat een optelling

39

Figuur 6.8.: Uitgetekende mogelijkheden voor n = 1, 2, 3 van twee gelijke spellen altijd gelijk spel zal opleveren. Een iets minder sterke bewering is dat in dit spel de tweede speler altijd minstens gelijk kan spelen. Dit leidt tot het volgende lemma: Lemma 6.6. Voor twee spellen 1 × n Greenlandic Dots and Boxes, G en G0 en G = G0 geldt val(G + G0 ) ≤ 0 Bewijs: Er is een expliciete strategie waarbij de tweede speler altijd gelijk kan spelen. Dit is door precies te volgen wat de eerste speler doet, behalve wanneer er een grijpbaar hokje is. Dan moet de tweede speler dit hokje pakken en in het andere spel ook het hokje openen voor speler één. Als de tweede speler deze strategie toepast, zal het dus altijd gelijk spel worden. Dit betekent dat de eerste speler nooit kan winnen, dus val(1 × n) is nooit positief.

6.6. Even spellen Zoals te zien is in de tabel ontstaat er als n is even (in ieder geval voor 2 < n < 16) altijd gelijk spel. Hypothese 6.3 die hieruit volgt is dat een spel met even n altijd in gelijk spel eindigt. Een iets minder sterke bewering is dat speler 1 altijd kan zorgen voor gelijk spel bij even spellen. Lemma 6.7. Als n even is en n > 2, dan val(1 × n) ≥ 0 Bewijs: Om dit lemma te bewijzen kunnen we gebruik maken van Lemma 6.6. De strategie van speler 1 om dit spel gelijk te spelen is namelijk om het spel precies door midden te hakken.

40

Figuur 6.9.: Je ziet dat bij deze zet speler 1 altijd wint met val(1 × n) = 3 De eerste speler zet dus een streepje in het midden (dit kan omdat het spel even is) en zorgt zo voor een optelling van twee gelijke spellen. In deze optelling is speler 1 nu de tweede speler en kan dus altijd gelijk spelen volgens Lemma 6.6. Dus de tweede speler van het hele spel kan dus nooit meer winnen, dus val(1 × n) is nooit negatief. Dit gaat echter niet goed bij n = 2, omdat dan de eerste speler altijd gedoemd is om te verliezen, zie Figuur 6.8. Om de hypothese dat val(1 × n) = 0 bij even n te bewijzen, moet er worden laten zien dat er geen strategie bestaat waarmee speler 1 kan winnen. Dan zou namelijk gelden val(1 × n) ≤ 0 ⇒ val(1 × n) = 0. Dit gedeelte blijft echter een open probleem.

41

42 Figuur 6.10.: Uitgetekende mogelijkheden voor n = 7. Zoals je ziet zorgt speler 1 er met deze beginzet voor dat hij altijd 3 hokjes meer wint.

7. Conclusie Project Voor dit project hebben we veel boeken over wiskundige spellen doorgespit. Vaak stuitten we op bijna onmogelijk te begrijpen tabellen, tekeningen en allerlei soorten geheimschrift over hoe je welk spel kon winnen. Het doel van dit project was een bondig en leesbaar verslag te maken over een aantal aspecten van dit oerwoud aan wiskunde. We hebben gezien dat spellen niet alleen wiskundig zijn, maar dat de wiskunde eigenlijk ook een spel is: alle getallen zijn een spel. Net als getallen kun je spellen ook optellen en de impartiële spellen vormen zelfs een abelse groep Imp, een ondergroep van alle spellen. Deze groep is equivalent aan een andere groep, de nimbers. Dit hebben we bewezen en dit vormt de stelling van Sprague en Grundy. De bewijzen die hierbij komen kijken zijn niet wiskundig op een manier zoals wij het eerder hebben gezien. Het draait vooral om strategieën waarbij we kijken of de eerste speler of de tweede speler het spel altijd kan winnen, wat leidt tot een N-positie of een P-positie. Nadat we hebben gezien dat impartiële spellen equivalent zijn met nimbers, hebben we voor een aantal spellen de equivalentie expliciet beschreven. Het praktische van deze stelling is immers dat je er spellen mee kunt winnen, en dit kun je doen door te kijken naar de nimbers en het spel te vergelijken met het spel Nim. In de praktijk blijkt echter dat het bepalen van nimbers bij bijvoorbeeld Nimstring echt monnikenwerk is, dus het maakt het winnen van een spel er niet veel makkelijker op. In theorie kunnen we dus van alle impartiële spellen de nimbers bepalen. Eén van onze doelen was ook om hiermee iets te zeggen over het niet-impartiële spel Dots and Boxes (D&B). In dit spel blijkt het vooral te gaan om het maken van lange ketens en wie deze als eerste opent. Hier komen de impartiële spellen weer om de hoek kijken. Je kunt namelijk een spel D&B op een gegeven moment in het spel zien als een spel Nimstring plus een spel met allemaal lange ketens. Dan begint om het gevecht om wie de ketens moet openen, en als je weet wie hoe je wint in Nimstring kun je dus D&B winnen. Ook is er een regel genaamd de Long Chain Rule, waarmee je precies kunt berekenen hoeveel ketens je moet maken om het spel te kunnen winnen. Als afsluiting hebben we het open probleem van 1 × n Greenlandic Dots and Boxes vanuit twee verschillende hoeken benaderd, en fundamenten gevonden voor een aantal hyptoheses. Bij kleine spellen Nimstring kun je als eerste speler altijd winnen, behalve bij het spel met 1 muntje. Sommige spelsituaties zijn equivalent aan Kayles-ranken, en dan is van de Nimstringversie heel makkelijk te bepalen wie er wint. Bij het spel Dots and Boxes kunnen we de tabel die Lenhardt heeft gemaakt met behulp van de computer gedeeltelijk nagaan door uitschrijven. Ook hebben we bewezen dat over het algemeen geldt dat je spellen met een even aantal hokjes als eerste speler altijd gelijk kunt spelen. Over het algemeen kunnen we concluderen dat het bekijken van wiskundige spellen een ingewikkeld, apart soort wiskunde is maar waarbij ook vele gebieden van de wiskunde, met name de algebra en grafentheorie, om de hoek komen kijken. Met het uitwerken van de vele opties van spelletjes kun je je hele leven bezig blijven, maar soms is het beter om het maar gewoon te spelen, zoals we ook hebben gedaan in het NK Kamertje Verhuren. Het blijft immers allemaal maar een spelletje.

43

8. Populaire Samenvatting Wiskundigen houden zich graag bezig met spelletjes, van het schijnbaar simpele spel Kamertje Verhuren tot het oneindig ingewikkelde spel schaak. Spelletjes zijn een goede manier om te ontspannen maar toch je hersenen te blijven trainen. Het leuke is dat de wiskunde eigenlijk ook opgebouwd is uit één groot spel, namelijk de getallen. Je kunt namelijk de getallen zien als een spel. Elk getal is dan een stapel stenen waar je om de beurt stenen van af mag pakken (een speciale versie van het spel Nim, hier komen we zo op terug). Dit klopt met hoe een getal gedefinieerd is, namelijk als de verzameling van al zijn voorgaande getallen. De definitie van een spel is dan de verzameling van al zijn vervolgzetten, G = {G1 , G2 , ..., Gn }. Onder deze definitie blijken spellen een wiskundige groep te vormen. En in een groep kun je ook optellen, dus definiëren we de optelling van spellen. Het idee van de optelling van spellen is dat je twee (of meer) spellen tegelijkertijd speelt en er dus één groot spel van maakt. Als je aan de beurt bent mag je kiezen in welk spel je een zet doet. Je hebt gewonnen als je het laatste spel gewonnen hebt. Een speciale ondergroep van de spellen zijn de impartiële spellen. Dit zijn spellen waarbij twee spelers allebei dezelfde mogelijkheden hebben. Wat er gebeurt in het spel hangt dus niet af van wie er aan de beurt is, maar van de spelsituatie. Schaak is dus geen impartieel spel, want daarbij hebben beide spelers hun eigen stukken. Een andere belangrijke eis voor een impartieel spel is de normaal spel regel. Dit betekent dat de speler die aan de beurt is en niet meer kan spelen, verliest. Andere eisen zijn perfecte informatie, geen kans en eindigheid. Een belangrijk voorbeeld van een impartieel spel is het spel Nim. Het spel Nim bestaat uit een eindig aantal stapels met een eindig aantal stenen. Om de beurt mogen de spelers zoveel stenen uit één stapel pakken als ze willen. Wie de laatste stenen pakt heeft gewonnen, de tegenspeler kan immers niet meer spelen. Er blijkt dat als beide spelers perfect spelen (dus geen domme zetten doen), je bij elk spel Nim kan weten of de eerste of de tweede speler wint. Dit kun je berekenen door door de ’nimber’ van een spel uit te rekenen. Dit is een speciaal getal waaraan je kan zien of het spel een N-positie (de eerste speler wint) of een P-positie (de eerste speler wint) heeft. Het spel Nim en de nimbers zijn belangrijk omdat er blijkt dat je ieder impartieel spel kunt beschrijven met nimbers. We zeggen dan dat ieder impartieel spel equivalent is met een nimber. Dit is de stelling van Sprague en Grundy. Hieruit blijkt dus dat we in theorie van ieder impartieel spel kunnen uitrekenen wie er moet beginnen om te winnen. In de praktijk blijkt dit echter niet zo makkelijk. Dit komt omdat deze nimbers recursief uitgerekend moeten worden, dit betekent dat je bij het lege spel (als het ware bij 0) moet beginnen. Dit betekent dat als je bij het spel Nimstring, een spel met muntjes en touwtjes, de nimber van een spel met 6 muntjes uit wil rekenen, je vele berekeningen zal moeten maken. We kunnen nu dus van elk impartieel spel uitrekenen wat je moet doen om te winnen. De vraag is of dit ook iets zegt over niet-impartiële spellen. Een voorbeeld hiervan is het spel Dots and Boxes (D&B), ofwel Kamertje Verhuren. Je hebt een veld met puntjes, waarin je om de beurt een streepje mag zetten. Als er een hokje omrand is met vier streepjes, mag je nog een streepje zetten. Degene die uiteindelijk de meeste hokjes omrand heeft, heeft gewonnen. Dit voldoet niet aan onze definitie van een impartieel spel, het heeft namelijk niet de normaal

44

spel regel. Degene die niet meer kan zetten heeft niet per se verloren, want hij kan namelijk best de meeste hokjes hebben. De vraag is dus of over een spel D&B iets kunnen zeggen over wie er het spel wint bij perfect spel, net als we dat kunnen bij impartiële spellen. Dit blijkt in sommige gevallen te kunnen, we kunnen namelijk het spel D&B reduceren tot een impartieel spel, door de normaal spel regel toe te voegen. Het gaat er dan niet om wie de meeste hokjes pakt, maar wie niet(!) het laatste hokje pakt. Als we immers de normaal spel regel aanhouden, is degene die het laatste hokje pakt nog een keer aan de beurt, maar kan niet meer spelen dus heeft verloren. We noemen dit spel Nimstring. Het reduceren van D&B tot Nimstring is niet nuttig voor het begin van het spel D&B, het maakt namelijk in D&B niets uit of je het laatste hokje pakt of niet. Maar het is wel handig voor een bepaald moment in het spel. Als je D&B speelt ontstaan er namelijk vanzelf lange ketens, waarbij de andere speler heel veel hokjes kan pakken als de eerste speler het eerste streepje zet (de keten voor hem ’opent’). Een speler wil natuurlijk zorgen dat de ander de ketens voor hem opent zodat hij heel veel hokjes kan pakken. De handigheid van het spel Nimstring is nu dat als de ketens meer dan de helft van het spel bevatten, je de rest van het spel als een spel Nimstring kunt zien. Het enige wat je namelijk wil is dat de ander de ketens voor jou opent, dat betekent dat jij moet winnen in het spel Nimstring, dan moet de andere speler nog een keer zetten, de ketens openen en dan win jij. Zo kun dus in een bepaalde situatie van het spel D&B zorgen dat je wint, door het te zien als de optelling van lange ketens en een spel Nimstring waarin je wil winnen. Deze abstracte theorieen leiden tot allerlei strategieën voor het spel Dots&Boxes, zoals de Long Chain Rule (zie hiervoor het verslag). Deze strategieën zijn ook ruimschoots toegepast tijdens het Nederlands Kampioenschap Kamertje Verhuren. Tot slot zou dit project niet compleet zijn zonder het bekijken van een onopgelost probleem in de wiskunde. Dit is in dit geval een spel Kamertje Verhuren met 2 bij een willekeurig aantal puntjes, dus één lange rij hokjes. Hierbij zijn alle bovenste horizontale streepjes en de zijkanten al gevuld. De vraag is of er iemand in dit spel altijd kan winnen. Via verschillende benaderingen is duidelijk geworden dat de eerste speler een spel met even aantal hokjes altijd gelijk spel kan maken, en een spel met oneven aantal hokjes altijd kan winnen. Behalve het spel met 2 hokjes, dat verlies je als eerste speler altijd automatisch. De conclusie van dit project is dat impartiele spellen in theorie goed wiskundig te benaderen zijn, alhoewel dit in de praktijk een moeizaam proces is. Wel kun je vaak na veel rekenwerk bepaalde regels herkennen, die je zou kunnen gebruiken om het spel te winnen. In de uitkomsten van verschillende spelletjes zijn namelijk veelal mooie patronen te vinden. Als we de wiskunde zien als ’de herkenning van structuren en patronen’ kun je het onderzoek naar wiskundige spelletjes zien als pure wiskunde.

45

A. Nimbers in Nimstring

46

Bibliografie [1] C L Bouton, Nim, A Game with a complete Mathematical Theory, The Annals of Mathematicsl, 3, 35-39, 1902. ¨ [2] R Sprague, Uber Mathematische Kampfspiele, Tohoku Mathematical Journal, 41, 438-444, 1935. [3] P M Grundy, Mathematics and Games, Eureka, 2, 6-8, 1939. [4] L Wittgenstein Philosophische Untersuchungen, Kritisch-genetische Edition, geredigeerd door Joachim Schulte, Wissenschaftliche Buchgesellschaft, 2001. [5] M H Albert, R J Nowakowski and D Wolfe, Lessons in Play: An Introduction to Combinatorial Game Theory, A K Peters, Ltd., 2007. [6] J H Conway, On Numbers and Games, Academic Press, 1976. [7] Winnende strategie Silver Dollar Game: http://www.suhendry.net/blog/?p=1612 [8] E R Berlekamp, J H Conway and R K Guy, Winning Ways For Your Mathematical Plays, Volume 3, A K Peters, Ltd., 2003. [9] R Lenhardt, Closed 1 × n Dots and Boxes Bachelorscriptie aan de Comeniusuniversiteit in Bratislava, 2008. [10] Website met winnende strategieën voor Dots and Boxes: http://mysite.verizon.net/vze16nctz/DotsBoxes/dots strategy [11] R J Nowakowski, More Games of No Chance, Mathematical Sciences Research Institute Publications, 2002. [12] R J Nowakowski, M H Albert, Games of No Chance 3, Cambridge University Press, 2009.

47

Impartiële spellen. Marie Beth van Egmond, Lisa Steverink. 12 juli Project wiskunde 2 Begeleiding: dr. Roland van der Veen

Recommend Documents