Ga naar hoofdinhoud

Doe het met pen en papier

Leerdoel: je voert minimax zelf uit op twee voorbeelden: een abstracte boom met cijfers, en dan een echt tic-tac-toe-eindspel waarvan je de hele boom tekent en doorloopt. Geen Python.

Deel 1 — een abstracte boom​

Eerst een boom waar de bladeren al cijfers hebben; de uitkomst is gegeven, en jij rekent alleen de MIN- en MAX-knopen uit.

                 ▲ MAX
              ╱    │    ╲
             A     B     C
             │     │     │
            ▼MIN  ▼MIN  ▼MIN
            ╱╲    ╱╲    ╱╲
           3  5  2  9  6  0

MAX heeft drie keuzes: tak A, B of C. Onder elk staat MIN met twee opties. De cijfers onderaan zijn utilities (hoger = beter voor MAX, lager = beter voor MIN).

Stap 1 — reken van onderop elk MIN-niveau uit​

Een MIN-knoop kiest het laagste kind. Onder tak A is dat min(3, 5), dus 3; onder B min(2, 9), dus 2; onder C min(6, 0), dus 0.

De boom wordt:

                 ▲ MAX
              ╱    │    ╲
              3    2    0

Stap 2 — MAX kiest het hoogste kind​

max(3, 2, 0) = 3. De beste zet voor MAX is tak A, en de waarde van het spel bij optimaal spel is 3.

Wat had je verwacht?​

Op het eerste gezicht lijkt tak B aantrekkelijk: daar staat de 9, het hoogste blad van de hele boom. Maar MIN kiest daar nooit voor, die pakt de 2. Alleen tak A garandeert MAX een 3. Het hoogste blad is dus misleidend, want het kind dat MIN kiest is niet het hoge maar het lage.

Deel 2 — de boom van een echt eindspel​

Nu een echt spel. Een positie waar nog drie vakjes leeg zijn, en X is aan zet.

 X | X | O
-----------
 O | O | X
-----------
 . | . | .          (. = leeg)

Een vakje noemen we bij (rij, kolom), met (0,0) linksboven. De drie lege vakjes zijn (2,0), (2,1) en (2,2).

Kijk eerst even naar het bord. O heeft twee stenen op de diagonaal van rechtsboven naar linksonder, (0,2) en (1,1); nog één O op (2,0) en O wint. Onthoud dat, maar reken het niet als regel mee. Minimax kent geen "blokkeren", het rekent alleen.

Winst voor X is +1, winst voor O is -1, en een vol bord zonder winnaar is 0.

Stap 1 — teken de boom​

Bovenaan staat het bord van nu, met X aan zet: een MAX-knoop. Elke tak eronder is een zet van X, en bij elke tak hoort het bord ná die zet. Daaronder komt O aan zet: een MIN-knoop met twee takken. Nog een laag lager is er één vakje over, dus X's laatste zet ligt vast. Zo ziet de boom eruit, met bij elke knoop het bord maar nog zonder waardes:

  • ▲ X aan zetXXO/OOX/...?
    • (2,0)▼ O aan zetXXO/OOX/X..?
      • (2,1)▲ X aan zetXXO/OOX/XO.?
        • (2,2)klaarXXO/OOX/XOX?
      • (2,2)▲ X aan zetXXO/OOX/X.O?
        • (2,1)klaarXXO/OOX/XXO?
    • (2,1)▼ O aan zetXXO/OOX/.X.?
      • (2,0)klaarXXO/OOX/OX.?
      • (2,2)▲ X aan zetXXO/OOX/.XO?
        • (2,0)klaarXXO/OOX/XXO?
    • (2,2)▼ O aan zetXXO/OOX/..X?
      • (2,0)klaarXXO/OOX/O.X?
      • (2,1)▲ X aan zetXXO/OOX/.OX?
        • (2,0)klaarXXO/OOX/XOX?

Elk vraagteken is een waarde die je zo uitrekent. De borden met een stippellijn zijn klaar: daar staat drie op een rij, of het bord is vol.

Stap 2 — loop de linkertak af: X speelt (2,0)​

 X | X | O
 O | O | X
 X | . | .

Geen drie op een rij, dus O is aan zet (MIN), met twee opties.

O speelt (2,1). Dan blijft alleen (2,2) over, en X moet daar spelen:

 X | X | O
 O | O | X
 X | O | X

Geen drie op een rij en het bord is vol: remise, utility 0.

O speelt (2,2). X vult (2,1):

 X | X | O
 O | O | X
 X | X | O

Weer geen drie op een rij en een vol bord, utility 0.

MIN kiest het laagste van 0 en 0: 0. De tak waarin X (2,0) speelt is dus 0 waard.

Stap 3 — de middentak: X speelt (2,1)​

 X | X | O
 O | O | X
 . | X | .

O is aan zet. O speelt (2,0):

 X | X | O
 O | O | X
 O | X | .

De diagonaal (0,2) (1,1) (2,0) is O O O: O wint. Terminal, utility -1, geen verdere zetten.

O speelt (2,2). X vult (2,0):

 X | X | O
 O | O | X
 X | X | O

Vol, geen winnaar, utility 0.

MIN kiest min(-1, 0) = -1. De tak waarin X (2,1) speelt is -1 waard: als X daar speelt, wint O.

Stap 4 — de rechtertak: X speelt (2,2)​

 X | X | O
 O | O | X
 . | . | X

O speelt (2,0): diagonaal O O O, O wint, utility -1.

O speelt (2,1). X vult (2,0):

 X | X | O
 O | O | X
 X | O | X

Vol, geen winnaar, utility 0.

MIN kiest min(-1, 0) = -1.

Stap 5 — terug naar de wortel​

Nu staan er waardes onder alle drie de takken. Dit is dezelfde boom, nu ingevuld van de bladeren naar boven:

  • ▲ X aan zetXXO/OOX/...0
    • (2,0)▼ O aan zetXXO/OOX/X..0
      • (2,1)▲ X aan zetXXO/OOX/XO.0
        • (2,2)klaarXXO/OOX/XOX0
      • (2,2)▲ X aan zetXXO/OOX/X.O0
        • (2,1)klaarXXO/OOX/XXO0
    • (2,1)▼ O aan zetXXO/OOX/.X.-1
      • (2,0)klaarXXO/OOX/OX.-1
      • (2,2)▲ X aan zetXXO/OOX/.XO0
        • (2,0)klaarXXO/OOX/XXO0
    • (2,2)▼ O aan zetXXO/OOX/..X-1
      • (2,0)klaarXXO/OOX/O.X-1
      • (2,1)▲ X aan zetXXO/OOX/.OX0
        • (2,0)klaarXXO/OOX/XOX0

X kiest het hoogste:

X-zetMIN kiest daaronderwaarde van de tak
(2,0)min(0, 0)0
(2,1)min(-1, 0)-1
(2,2)min(-1, 0)-1

X speelt (2,0) en de uitkomst bij optimaal spel is 0: remise.

X blokkeert de diagonaal van O, maar niet omdat iemand die regel heeft geprogrammeerd. De boom wijst de blokkade vanzelf aan: onder de twee andere zetten hangt een -1, en MIN pakt die.

Het recept in woorden​

1. Begin onderaan met posities die "klaar" zijn (terminal).
2. Bereken voor elke terminal de utility: +1 / -1 / 0.
3. Ga één niveau omhoog:
   - Was MAX aan zet? → neem het hoogste kind.
   - Was MIN aan zet? → neem het laagste kind.
4. Herhaal tot je bij de wortel bent.
5. De zet die de waarde van de wortel opleverde, is de beste zet.

Wat dit oplevert voor het coderen​

In Python wordt dit een recursieve functie: max_value(bord) roept min_value aan op elk kind, en die roept weer max_value aan, tot een terminal bord. Dezelfde boom, in dezelfde volgorde: eerst de linkertak helemaal naar beneden, dan de middentak, dan de rechter. Bij bouwsteen 8 loop je precies deze boom nog een keer, maar dan met de code.

info

Deze berekening bestaat ook als printbare werkvorm in tweetallen, op een andere positie: De perfecte speler — minimax op papier.

Door naar de stellingen →.