Geschreven voor het vak:
Wiskunde gedoceerd door H. Mommaerts
Onderzoekscompetentie
Mastermind met acht kleuren Auteurs:
Tom Demeulemeester Pieter Van Walleghem Thibaut Winters 6LWIi
22 april 2014
1
Inleiding
In de volgende paar pagina’s presenteren wij onze onderzoeksopdracht over Mastermind. Wij hebben dit onderwerk gekozen omdat wij Mastermind een interessant spel vinden en omdat wij graag wouden weten of er wiskunde in dit simpel spelletje zit. En die wiskunde zit er zeker in: als je Mastermind degelijk wilt spelen, moet je constant aan kansrekenen doen en kom je soms zelfs een paar ingewikkelde fomules tegen. Tijdens ons onderzoek hebben we ons vooral geconcentreerd op ideale zetten: de optimale beginzet, de optimale tweede zet na het krijgen van een eerste antwoord en de optimale derde zet, rekening houdend met de vorige 2 antwoorden. Het verschil tussen ons onderzoek en het meeste voorafgaande onderzoek is dat wij ons op de Mastermindversie met acht verschillende kleuren hebben geconcentreerd, terwijl het vorig onderzoek altijd ging over de versie met zes verschillende kleuren. Die twee extra kleuren zorgen ervoor er veel meer mogelijkheden bestaan, waardoor er ook meer rekenwerk is. Onze onderzoeksopdracht bestaat eigenlijk uit drie delen: in het eerste deel leggen we de regels van Mastermind uit en leggen we de termen uit die doorheen deze onderzoeksopdracht gebruikt zullen worden. Daarna leggen we de meest bekende reeds bestaande technieken uit om Mastermind in zo weinig mogelijk beurten uit te spelen en daarna presenteren wij ons eigen onderzoek. Het doel van onze onderzoeksopdracht is dubbel: ten eerste hopen wij dat na het lezen van deze paar pagina’s je meer inzicht hebt in de werking van het spel Mastermind en ten tweede wouden we een boekje maken met daarin alle ideale zetten voor alle mogelijke scenario’s voor de eerste drie beurten.
1
2
Regels en notatie
Mastermind is een gezelschapsspel voor twee spelers, uitgevonden door Mordecai Meirdowitz in 1970. Om te beginnen kiest Speler 1 een geheime code die bestaat uit vier al dan niet verschillende kleuren. Vervolgens moet Speler 2 in een minimum aantal beurten die code proberen te raden door middel van gokken. Op elke gok krijgt hij dan een antwoord van Speler 1 waardoor hij iets meer te weten komt over de code. Dit antwoord bestaat uit een aantal rode en/of witte pinnetjes: • Het aantal rode pinnetjes komt overeen met het aantal kleuren dat in de code voorkomt en op de juiste plaats staat. • Het aantal witte pinnetjes komt overeen met het aantal kleuren dat in de code voorkomt, maar niet op de juiste plaats staat; Deze formulering om het aantal witte pinnetjes te berekenen, is voor ons het makkelijkst om te begrijpen, maar wanneer men dit wil programmeren zodat een computer ook het aantal witte pinnetjes kan berekenen, is dit een zeer omslachtige werkwijze. Een alternatief is om het aantal rode en witte pinnetjes te berekenen als volgt 1 : 0
0
rood + wit = min(n1 , n1 0 )+min(n2 , n2 )+...+min(n6 , n6 ) 0
Hierbij is ni het aantal keer dat symbool i voorkomt in het codewoord en ni het aantal keer dat symbool i voorkomt in de gok. Het aantal rode en witte pinnetjes stellen we voor door (rood,wit). Doorheen deze onderzoeksopdracht zullen we codes op twee verschillende manieren voorstellen. De eerste manier is door middel van de getallen 1, 2, 3... Elk getal stelt een bepaalde kleur voor en wanneer een code op deze manier is voorgesteld, wordt er verwezen naar ´e´en concrete code, met de getallen op de overeenkomstige posities. Als de code 1234 is bijvoorbeeld en de gok is 1345, dan staat alleen 1 op de juiste plaats en is er dus maar ´e´en rood pinnetje. 3 en 4 komen ook in de code voor, maar staan op de verkeerde plaats. Dus zijn er twee witte pinnetjes en noteren we dit resultaat als (1, 2). Dit wordt ook wel het antwoord genoemd. Maar soms zal het ook nodig zijn om een verzameling codes weer te geven en dit zullen we doen door middel van de letters A, B, C... Ook hierbij stelt elke letter een verschillende kleur voor. Wanneer men echter over meerdere kleuren evenveel weet, worden deze kleuren voorgesteld door dezelfde letter. Bovendien staan bij deze notatie de letters niet noodzakelijk in de correcte volgorde, maar zal Speler 2 deze volgorde bepalen door rekening te houden met de antwoorden op de vorige beurten. 1 Donald
E. Knuth, 1976
2
Stel dat we als eerste gok een code van de vorm ABCD nemen (bijvoorbeeld 1234) en stel dat het antwoord hierop (1,2) is. ABEF en ABGH zijn dan gelijke gokken in de tweede beurt. Om het eenvoudiger te houden gebruiken we de letters altijd in alfabetische volgorde en zullen we hier ABEF noteren. Concreet zou de tweede beurt er dan kunnen uitzien als 1526, maar evengoed als 6281, 6437... Deze notaties zullen door elkaar gebruikt worden.
3 3.1
Reeds bekende strategie¨ en The Simple Strategy
Bij de Simple Strategy is er voor Speler 2 weinig denkwerk vereist, vandaar ook de naam. Deze strategie is bedacht door Shapiro in 1994. Voor deze strategie heeft Speler 2 een lijst nodig met daarop alle mogelijke combinaties. De eerste combinatie op deze lijst wordt zijn eerst gok. Nadat hij het antwoord krijgt, bv (1,1), zoekt hij op zijn lijst naar de eerstvolgende combinatie die aan de gekregen voorwaarden voldoet. Die combinatie wordt dan zijn volgende gok. Dit blijft Speler 2 herhalen totdat zijn gok het juiste antwoord is. Deze strategie zal absoluut niet de snelste strategie zijn, omdat er niet veel informatie uit de antwoorden gehaald wordt. Als Speler 2 namelijk zijn gokken nauwkeurig zou uitkiezen, dan zou hij veel meer informatie kunnen halen uit ´e´en gok. Verder is dit ook geen goede strategie omdat hij veel te veel tijd vergt: als we spelen met een code bestaande uit 4 kleuren en er keuze is uit 8 kleuren, die herhaald mogen worden, dan zou de lijst van mogelijke combinaties 84 of 4096 lijntjes lang moeten zijn. Het is logisch dat zo een lange lijst nogal onhandig is om mee te spelen en om de combinaties te vinden die wel nog voldoen aan te voorwaarden.
3
3.2
The Worst-Case Scenario
Wanneer Speler 2 een gok doet, dan verdeelt hij de 4096 mogelijke combinaties eigenlijk in verschillende groepen: de combinaties die voldoen aan (0,0), die voldoen aan (0,1)... Zo verkleint hij het aantal combinaties die nog eventueel de juiste code kunnen zijn. Instinctief voelen we dus aan dat het voor Speler 2 voordelig is als de groep waartoe de juiste combinatie behoort, zo klein mogelijk is. Antwoord (0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (3,0) (4,0)
AAAA 625 0 0 0 0 500 0 0 0 150 0 0 20 1
AAAB 256 308 61 0 0 317 156 27 0 123 24 3 20 1
AABB 256 256 96 16 1 256 208 36 0 114 32 4 20 1
AABC 81 276 222 44 2 182 230 8 4 105 40 5 20 1
ABCD 16 152 312 136 9 108 252 136 8 96 48 6 20 1
De bovenstaande tabel geeft het aantal resterende mogelijkheden weer voor Speler 2 na een bepaald antwoord op de eerste gok van de vorm AAAA, AAAB... Deze tabel is enkel geldig voor een code bestaande uit 4 kleuren gekozen uit 6 kleuren. In deze tabel kunnen we duidelijk zien dat het voor Speler 2 niet zo zinvol is om met de zet AAAA te beginnen, omdat hij dan de mogelijkheid heeft dat hij heel veel resterende mogelijkheden heeft. Zo heeft hij nog altijd 625 mogelijke combinaties over als hij (0,0) als antwoord krijgt. De Worst-Case Scenario is op dit principe gebaseerd: bij deze strategie houdt met rekening met het ergste dat er voor Speler 2 kan gebeuren, namelijk het grootste aantal resterende combinaties na binnen een bepaalde kolom. Daarom kiest men bij deze strategie als gok de combinatie die leidt tot een zo klein mogelijke grootste groep van combinaties. Bij 6 kleuren kan Speler 2 dus best beginnen met een combinatie in de vorm van AABB, want die heeft de kleinste grootste groep. Er zitten namelijk maar 256 combinaties in de groep met de meeste combinaties bij AABB.
4
3.3
The Expected-Size Strategy
In plaats van naar het ergst mogelijke geval te kijken, kunnen we ook kijken naar de verwachte waarde (Expected-Size) van een bepaalde gok. Om de verwachte waarde van ´e´en groep te berekenen, vermenigvuldigen we de kans dat het antwoord in deze groep ligt met het aantal elementen uit deze groep. Concreet betekent dit dat de Expected-Size van bv (1,1) met AAAB als eerste gok gelijk is aan 156/1296 ∗ 156 of anders geschreven gelijk is aan 1562 /1296 Met behulp van deze verwachte waarde kunnen we ook gaan bepalen wat de ideale beginzet is. We kunnen namelijk ook de Expected-Size van een beginzet bepalen. Dit doen we door alle verwachte waardes van de verschillende groepen van ´e´en zet op te tellen. De Expected-Size van AAAA is dan gelijk aan (6252 +5002 +1502 +202 +12 )/1296 wat ook gelijk is aan 511.9 Eerste zet AAAA AAAB AABB AABC ABCD
Verwachte waarde 511.9 235.9 204.5 185.3 188.2
Uit de bovenstaande tabel kunnen we de Expected-Sizes aflezen die we berekend hebben op dezelfde manier als bij AAAA. Met behulp van deze waardes kunnen we bepalen wat de ideale beginzet is: hoe kleiner de verwachte waarde is, hoe kleiner we gemiddeld de groepen van een bepaalde zet gaan verwachten. De zet met de kleinste verwachte waarde zal dus waarschijnlijk het snelst tot een correcte oplossing leiden. We kunnen hieruit dus aflezen dat volgens deze methode AABC de beste eerste zet is.
5
3.4
Most Parts
2
Bij de vorige twee strategie¨en hebben we gemerkt dat het aantal antwoorden waarbij er resterende mogelijkheden zijn vaak van cruciaal belang is. Een antwoord waarvoor er resterende mogelijkheden zijn in de volgende beurt noemen we een groep. Bij de Worst-Case Scenario bevatte de grootste groep minder combinaties naarmate er meer groepen waren die wel elementen bevatten. Bij de Expected-Size Strategy zorgden veel groepen voor kleinere kwadratische waarden, waardoor de verwachte waarde kleinder werd. We kunnen dus concluderen dat het aantal groepen een bepalende factor is voor een eventuele ideale beginzet. Daarom stellen we ook nog deze laatste strategie voor: de Most Parts Strategy. Deze strategie is volledig gebaseerd op het aantal groepen een bepaalde zet heeft. Het is eigenlijk een zeer simpele strategie: je neemt gewoon de zet met de meeste groepen als ideale zet. Uit de gegevens uit de tabel van 3.2 kunnen we de volgende tabel maken: Eerste zet AAAA AAAB AABB AABC ABCD
aantal groepen 5 11 13 14 14
We zien dus dat de zet AAAA maar 5 groepen heeft en daarom een zeer domme eerste zet zou zijn, als je het spel in zo weinig mogelijk zetten wilt winnen. We kunnen ook vaststellen dat zowel AABC als ABCD het maximaal aantal groepen heeft, namelijk 14. Volgens deze strategie zouden AABC en ABCD dus allebei ideale eerste zetten zijn.
3.5
Conclusie
We kunnen dus vaststellen dat er veel verschillende methodes bestaan om een ideale beginzet te selecteren, de ene al wat ingewikkelder dan de andere. Voor ons onderzoek hebben we gekozen om gebruik te maken van de Expected-Size Strategy, omdat deze het meest wiskundig is en volgens ons het meest correcte resultaat weergeeft. Het is ook de makkelijkste Strategy om te berekenen via computerprogramma’s.
2 Barteld
Kooi, 2005
6
4
Uitleg onderzoek
In de originele versie van Mastermind bestaat de code uit vier (al dan niet verschillende) kleuren en er is keuze uit zes verschillende kleuren. Dit is in Amerika veruit de populairste versie van Mastermind, maar in Belgi¨e wordt er vooral gespeeld met een variant waarbij er keuze is uit acht verschillende kleuren. Over deze variant is er, in tegenstelling tot de originele versie, nog maar weinig onderzoek uitgevoerd. Wij hebben dus geprobeerd om een winnende strategie te vinden voor deze variant en dit hebben we gedaan aan de hand van een computerprogramma dat we zelf geschreven hebben. Bij ons onderzoek hebben we gekozen voor dus de Expected-Size strategie. Deze waarde hebben we voor alle zinvolle mogelijkheden in de eerste drie beurten berekend. We hebben niet gekozen om zoals Donald E. Knuth in zijn onderzoek (zie bijlage 1) een schema te maken met de exacte combinatie die Speler 2 moet zetten omdat dit voor acht kleuren veel te uitgebreid zou worden. Daarentegen formuleren wij de code altijd onder de vorm van letters, waarbij elke letter een andere kleur voorstelt. Deze letters zijn echter nog niet in de juiste volgorde geplaatst. Speler 2 bepaalt dus zelf in welke volgorde de kleuren staan, door rekening te houden met de antwoorden uit de vorige beurten. Met 1234 als eerste gok en (1,1) als antwoord hierop zal de gok in beurt twee van de vorm ABEF moeten zijn. Dit betekent dat 1526, 5216... goede gokken zijn, maar 5612 niet omdat deze gok niet kan voldoen aan de voorwaarde uit het antwoord op de eerste beurt, namelijk dat er ´e´en rode is en ´e´en witte. Het doel van ons eigen onderzoek was om een soort boekje te hebben waarmee men in de eerste drie beurten duidelijk kan zien van welke vorm het antwoord moet zijn.
5
Uitleg programma
Ons eigen onderzoek hebben we gevoerd met behulp van een Excel-programma dat we zelf geschreven hebben. Dit programma berekent het aantal resterende mogelijkheden na een bepaald aantal zetten wanneer de code bestaat uit vier kleuren en er in totaal acht verschillende kleuren zijn, die worden voorgesteld door nummers van 1 tot 8. Het bepalen van het aantal witte en rode pinnetjes gebeurt met behulp van de formule die Donald E. Knuth geformuleerd heeft 3 : 0
0
rood + wit = min(n1 , n1 0 )+min(n2 , n2 )+...+min(n6 , n6 ) Het is ook mogelijk om de zetten die nog gezet kunnen worden te bekijken; daarvoor moet er een beetje naar rechts gescrold worden. De overblijvende mogelijkheden zijn dan aangegeven door een groen vakje. 3 Donald
E. Knuth, 1976
7
6
Beurt 1
De gok voor de eerste beurt kan maar vijf verschillende vormen aannemen. De tabel met het aantal overblijvende mogelijkheden ziet er als volgt uit:
Antwoord 0,0 0,1 0,2 0,3 0,4 1,0 1,1 1,2 1,3 2,0 2,1 2,2 3,0 4,0 Expected-Size
AAAA 2401 0 0 0 0 1372 0 0 0 294 0 0 28 1 1888,28
AAAB 1296 978 127 0 0 991 342 39 0 255 36 3 28 1 932,60
AABB 1296 864 216 24 1 864 456 52 0 242 48 4 28 1 852,58
AABC 625 1160 546 68 2 682 558 128 4 229 60 5 28 1 705,25
ABCD 256 976 936 224 9 500 660 204 8 216 72 6 28 1 665,14
We merken dat ABCD de laagste Expected-Size heeft en we zullen de rest van het onderzoek dus voortbouwen op ABCD als eerste zet.
7
Beurt 2
De optimale keuzes voor beurt twee zien er als volgt uit: Resultaat beurt 1 0,0 0,1 0,2 0,3 0,4 1,0 1,1 1,2 1,3 2,0 2,1 2,2 3,0 4,0
Gok beurt 2 EEFG AEFG ABEF ABEF ABCD AEFG ABEF ABEF(rw) ABCD AEFG ABEF(rw) ABCD AEFG ABCD
8
Expected-Size 30,83 145,51 136,55 35,68 2,78 74,82 99,61 36,29 3,25 35,75 11,61 3 7,64 1
Vanaf deze beurt moet Speler 2 dus zelf de volgorde bepalen waarin hij de kleuren plaatst. Wanneer deze volgorde niet eenduidig te bepalen is, staat er in de tabel vermeld welke kleuren van de eerste beurt Speler 2 moet overnemen. Wanneer de eerste gok 1234 is bijvoorbeeld en het antwoord (1,2), dan volgt uit de tabel dat het antwoord van de vorm ABEF is. Dit betekent dat zowel 1526 (´e´en rode en ´e´en witte uit de eerste beurt), 5126 (twee witte uit de eerste beurt) en 1256 (twee rode uit de eerste beurt) goede mogelijkheden zijn voor de tweede gok. De Expected-Size van elk van deze mogelijkheden is: Gok beurt 2 1526 5126 1256
Expected-Size 36,29 38,37 38,35
De Expected-Size van 1526 is het laagste, en het blijkt dus dat het voordeliger is om een rode en een witte uit de eerste beurt over te nemen. Dit wordt in de tabel weergegeven door (rw). Het blijkt uit deze resultaten dat het niet voordelig is om een kleur meerdere keren in de gok op te nemen tijdens de eerste twee beurten. Dit is wel opmerkelijk aangezien de code wel degelijk meerdere keren dezelfde kleur kan bevatten. Dit is ook in contrast tot de originele versie van Mastermind, waar volgens de meeste onderzoeken AABC als de optimale eerste zet beschouwd wordt.
8
Beurt 3
Vanaf de derde beurt wordt het iets moeilijker om de ideale zetten te berekenen, omdat er gewoonweg veel meer mogelijkheden zijn. Op elke ideale tweede zet, kun je weer 10-14 verschillende mogelijke antwoorden krijgen. Hierdoor was het al wat meer werk om voor elke mogelijkheid een ideale zet te vinden Vanaf de derde beurt wordt het ook wat moeilijker voor Speler 2. Hij moet nu rekening houden met de twee voorafgaande antwoorden voordat hij een nieuwe combinatie kiest. Bovendien moet hij de volgorde van de kleuren nog bepalen rekening houdend met de antwoorden op de vorige twee beurten. De optimale zetten in de derde beurt zijn te vinden in de tabellen achteraan dit document.
9
9
Beurt 4 en verder
Vanaf beurt 4 zijn we gestopt met het zoeken naar ideale zetten. Dit hebben we gedaan om twee redenen. Ten eerste is het vanaf beurt 4 echt bijna onmogelijk om alle mogelijke gevallen te bespreken. Ten tweede blijven er meestal, na het krijgen van drie antwoorden, voor Speler 2 niet veel mogelijkheden meer over om uit te kiezen, waardoor een normale speler wel in staat moet zijn om vanaf dan zelf de ideale zetten te kiezen.
10
Slot
We hebben nu dus gevonden wat er in de eerste 3 beurten moet gedaan worden om zo snel mogelijk de oplossing te vinden. De vraag is nu: wat is zo snel mogelijk? We hebben enkele simulaties uitgevoerd. Op die manier zijn we te weten gekomen dat we gemiddeld 5,125 beurten nodig hebben om de code te kraken. Het maximum aantal beurten is acht. We kunnen ons resultaat moeilijk vergelijken met anderen, want er zijn amper strategie¨en gevonden voor 8 verrschillende kleuren. Wel kunnen we dit vergelijken met ’s werelds beste strategie voor 6 kleuren. Dit is de strategie van Koyoma en Lai. Met behulp van hun strategie kon je de code kraken in gemiddeld 4,340 beurten. Dit komt overeen met 0,7233... beurten per kleur. Ons resultaat zorgt voor 0,640625 beurten per kleur en is in dat opzicht dus zelfs iets beter. Ons onderzoek heeft dus niet veel verschillende aantallen kleuren onderzocht, maar heeft zich geconcentreerd op 1 onderdeel. En dit met een verbluffend resultaat.
11
Bronvermelding
• KOOI, B., Yet Another Mastermind Strategy, ICGA Journal, jaargang 28, januari, nr. 1, p. 13-20 • KNUTH, D.E., The Computer As Master Mind, Journal Recreational Mathematics, jaargang 9, nr. 1, pagina’s onbekend
10
