Research and Development 1/^Archief/2008-2009/Solver/Fase 2

Algoritme

Ons algoritme heeft als basis het algoritme van Donald Knuth, die dit algoritme als eerst in 1977 demonstreerde. En dit algoritme maakt gebruik van een handige eigenschap, namelijk het verband tussen de verschillende mogelijkheden en de aantal verschillende score-mogelijkheden. Hieronder meer hierover. Je hebt altijd een beperkt aantal mogelijke "codes": een verzameling. De goede code zal altijd in deze verzameling zitten. Deze verzameling kan je steeds kleiner maken door een poging te doen en vervolgens met behulp van de score verscheidene codes schrappen. Hierbij komt de handige eigenschap ter pas, stel je doet een poging, die fout is, daar krijg je een bepaalde score voor (aantal zwarte en witte pinnetjes). Je kijkt vervolgens welke codes (uit je verzameling) precies dezelfde score zou krijgen als je je poging als de te kraken code opvat. De rest schrap je en je herhaalt dit tot je de code gekraakt hebt. Hierbij wordt de verzameling steeds kleiner, en er zal uiteindelijk maar één overblijven. De code waarmee je begint mag van alles zijn, maar 0011 blijkt het efficients te zijn, dus deze gebruiken wij.

Dus:

• De eerste poging is altijd 0011.
• Vervolgens wordt de score berekent (aantal zwarte en witte pinnetjes).
• Als de code niet gekraakt is ga voor alle andere mogelijkheden na welke codes precies dezelfde score zou geven als je de vorige poging als de te kraken code opvat.
• Kies één van deze codes, en ga terug naar de tweede stap.

Voorbeeld 1

Om het iets makkelijker te maken gebruiken we nu echte kleuren in plaats van nummers, en er zijn maar vier verschillende kleuren (R(red) G(green) Y(yellow) B(lue) , en 3 "pinnetjes", dus een code zou bijvoorbeeld RRB kunnen zijn. Verschillende mogelijkheden: 4^3= 64.


We nemen als te kraken code YGR, eerste poging is YRY, de score hiervoor is: 1 zwarte en 1 witte. Vervolgens worden uit de aantal mogelijkheden (dit zijn er inmiddels 64-1) de codes geplukt die dezelfde score zouden geven als YRY de goede code zou zijn. Dit zijn er in dit geval maar acht, namelijk: RGY, YGR , RBY, YBR, YYG, YYB, GYY, BYY (merk op dat de goede code hierbij zit!).

We kiezen uit deze acht random één code: "YBR". Deze gebruiken we als poging en levert de volgende score op: 2 zwarte en 0 witte. Nu wordt er uit de resterende zeven codes de codes geschrapt die niet 2 zwarte en 0 witte zou opleveren als YBR de code zou zijn. Nu blijft er nog maar één code over, namelijk YGR. De te kraken code!

Ons Programma

Wij hebben dit algoritme geïmplementeerd in ons programma (dit is helemaal in console). Het programma kan een code van de gebruiker zelf oplossen of een zelf gegenereerde code oplossen, tevens kan de gebruiker ook een zelf ingevoerde code of een gegenereerde code proberen op te lossen. Als het programma via het algoritme een code oplost dan zal dit altijd binnen zes beurten gebeuren. Via uitvoer zal het programma uitleg geven over de te nemen stappen, en de hoeveelheid mogelijkheden.

In ons programma hebben we gebruikt gemaakt van nummers in plaats van kleuren (die het originele Mastermind spel gebruikt), dit vonden wij makkelijker te implementeren, en er zit in feite geen verschil tussen.

Voorbeeld 2

Een voorbeeld met zes verschillende kleuren (rood, blauw, geel, groen, zwart en wit (als respectievelijk 0,1,2,3,4 en 5) en vier pinnetjes, zoals in het originele Mastermind spel. We hebben nu 1296 (6^4) mogelijkheden. Dit zijn teveel mogelijkheden om dit uit te schrijven dus gebruiken we onze bot. De te kraken code is blauw, geel, rood, groen. Onze eerste poging is rood rood blauw blauw. En daar krijgen we de volgende score op: 2 witte. Nu kijkt de bot welke codes nog mogelijk zijn, dit zijn alle codes die dezelfde score zou krijgen als je de vorige poging als de te kraken code beschouwt in dit geval dus rood rood blauw blauw. Zwart blauw rood wit is een van deze codes. Want als we deze code loslaten op rood rood blauw blauw zou je ook 2 witten krijgen. Maar nu laten we dit los op de te kraken code en deze geeft 1 zwarte en 1 witte als score. Nu doet de bot weer precies hetzelfde het kiest uit de verzameling (die nu kleiner is geworden) één code die voldoet aan de voorwaarde: blauw geel rood groen in dit geval. Deze voldoet aan de voorwaarde dat deze poging dezelfde score heeft als we de vorige code als de te kraken code opvatten. In dit geval is dit ook de goede code.