Mastermind les 3

• Wiskunde
• Beroepsopleiding

Huiswerk: Verklaar AABB (0,2)

Huiswerk: Verklaar ABCD (0,1)

Wat gaan we vandaag doen?

• Wat is de volgende stap bij algoritme van Knuth?
• Speciale spelvariant uit 1975, 5 gaats 8 kleuren
• Wat is de meeste gunstige startcode bij deze variant van Mastermind?

Leerdoelen van deze minilessen:

Ik kan vertellen hoe het algoritme van Knuth werkt.

Ik kan verklaren waar de getallen in de tabellen van Knuth vandaan komen.

Wat hebben to dusver gedaan.

• Kennis gemaakt met het spel Mastermind
• Een strategie bedenken om het spel altijd te winnen
• Worst case, avarege case en best case
• Het algoritme van Knuth
  

Knuth's algoritme

Minimizing the maximum number of remaining possibilities

vertaling:

Het minimaliseren van de maximale overgebleven mogelijkheden.

Wat is volgens Knuth de eerste zet?

Wat wordt de tweede zet?

Resultaat eerste zet: AABB (0,0)

Welke verschillende zetten zijn er nu mogelijk?

CCCC

CCCD

CCDD

CCDE

CDEF

Deels ingevuld. Deze tabellen per antwoord invullen en nieuwe zet bepalen.

Spel van het jaar 1975

5 gaten, 8 kleuren

Speciale variant, 5 gaats 8 kleuren

Aantal mogelijkheden:  8⁵=32.768

Best case: 1

Worst case: 32.768

Average case: 32.768 / 2 = 16.384

Welke verschillende startcodes zijn er bij de speciale versie 5 gaats, 8 kleuren?

Wat zijn de reacties/getallenparen die je kunt krijgen? Bv (0,0) (z,w)

Waarom zijn er geen mogelijkheden bij antwoord (0,1)?

Vul de eerste rij van de tabel verder in.
Antwoord (0,0) 5 gaats, 8 kleuren.

Kun je nu al weten wat volgens het algoritme van Knuth de eerste zet is?

Hoeveel mogelijke codes zijn er nog over al je AAAAB invult en als reactie het getallenpaar (0,1) krijgt?

Conclusie:

Het algoritme van Knuth is ook te gebruiken bij Mastermind superieur.

Om het algoritme te kunnen gebruiken moet je veel tabellen invullen.

Terugkoppeling leerdoel:
Leg in je eigen woorden uit hoe het algoritme van Knuth werkt.