Ga naar hoofdinhoud

Minimax — het idee

Bronvermelding — dit hoofdstuk is een afgeleide bewerking van CS50 AI Project 0: Tic-Tac-Toe van Harvard University, gelicenseerd onder CC BY-NC-SA 4.0. Wij hebben het vertaald naar het Nederlands, opgeknipt in PRIMM-stappen en aangevuld met conceptuele uitleg. Het hele hoofdstuk wordt onder dezelfde licentie verspreid.

Leerdoel: je begrijpt het kernidee van minimax: als jij je beste zet doet en je tegenstander ook zijn beste zet doet, welke zet is dan voor jou de beste? Nog geen code.

Het verhaal​

Je speelt boter-kaas-en-eieren (tic-tac-toe) tegen iemand die net zo goed nadenkt als jij, zonder blunders en zonder mazzel. Welke zet doe je?

De eerste gedachte van de meeste mensen is: de zet die mij het snelst laat winnen. Maar je tegenstander ziet dat plan ook, en blokkeert het. De vraag die je wilt beantwoorden is een andere: welke zet zorgt dat ik niet verlies, ook als mijn tegenstander daarna zijn allerbeste tegenzet kiest? Dat is minimax in één zin.

Twee spelers, twee doelen​

In een spel zijn er twee perspectieven:

  • Max-speler (wij, X in tic-tac-toe) wil de uitkomst maximeren: voor ons is winnen = +1, gelijk = 0, verliezen = -1.
  • Min-speler (de tegenstander, O) wil dezelfde uitkomst minimeren: hij wil dat wij verliezen.

De spelers zijn om de beurt, en allebei kiezen ze telkens de zet die voor hén het best is. Minimax rekent uit waar dat op uitkomt.

Een game tree​

Een game tree is een boom van toekomstige zetten. Aan de top staat de huidige positie. Elke "tak" is een mogelijke zet. Aan de bladeren (blaadjes) staan eindposities (winst, verlies, of remise) met hun utility: +1, -1, of 0.

Een kleine boom, nog geen echt spel:

               ▲ MAX (wij kiezen)
              ╱            ╲
             A              B
             │              │
           ▼ MIN          ▼ MIN
           ╱ ╲             ╱ ╲
         +1   -1         0    +1

Een MAX-knoop tekenen we als een driehoek omhoog (▲), want die wil omhoog, en een MIN-knoop als een driehoek omlaag (▼). Zo tekent CS50 ze ook, en zo staan ze in de rest van dit hoofdstuk.

Wij (MAX) kiezen tussen tak A en tak B. Daarna kiest de tegenstander (MIN) tussen zijn twee opties.

Redeneer eerst als de tegenstander. Onder tak A kiest MIN uit +1 en -1, en hij pakt het laagste: -1. Onder tak B kiest hij uit 0 en +1, dus 0.

Nu wij. Tak A levert -1 op, want daar pakt MIN de -1. Tak B levert 0 op. Wij nemen het hoogste, dus B. Beter een gegarandeerde remise dan een gegarandeerd verlies.

Het sleutelwoord: gegarandeerd​

Minimax denkt van het einde naar het begin. Pas als de uitkomst van een blad bekend is, kun je terugrekenen wat het niveau erboven waard is, en zo verder, helemaal terug naar de zet van nu. Dat heet terug-redeneren (in het Engels backwards induction), en het werkt omdat we aannemen dat beide spelers optimaal spelen.

Waarom tic-tac-toe?​

Tic-tac-toe heeft een klein aantal mogelijke spellen, zo'n 250.000 als je alles meerekent. Een computer rekent die hele game tree in een seconde door; een mens niet, wij spelen op patronen en gevoel.

Voor schaken, met meer dan 10⁴⁰ posities, is de hele tree te groot. Daar gebruik je slimmere varianten zoals alpha-beta pruning of Monte Carlo Tree Search, maar het fundament blijft minimax.

Waar minimax echt is gebruikt​

  • Claude Shannon beschreef in 1950 hoe een computer zou kunnen schaken: een game tree doorrekenen met precies het minimax-idee van deze pagina. Er bestond nog geen computer die het kon.
  • Arthur Samuel bouwde in de jaren vijftig een damprogramma op minimax dat van zijn eigen partijen leerde, en versloeg er in 1962 een sterke speler mee.
  • Deep Blue van IBM won in 1997 een match van wereldkampioen Garry Kasparov. Binnenin: minimax met alpha-beta pruning, op speciale chips die zo'n 200 miljoen posities per seconde bekeken.
  • Chinook rekende in 2007 dammen (op het 8×8-bord) helemaal uit: bij optimaal spel is het remise, net als tic-tac-toe. Dezelfde game tree, alleen achttien jaar rekenwerk.
  • Stockfish, de sterkste open-source schaakengine van nu, zoekt nog steeds met alpha-beta. De code is openbaar.

Go is de uitzondering: daar is de tree zó groot dat AlphaGo in 2016 met een andere zoekmethode won, Monte Carlo Tree Search, gestuurd door een neuraal netwerk. De uitleg in dit hoofdstuk volgt lecture 0 van CS50 AI, die minimax voor het eerst voordoet.

Wat we gaan bouwen​

Aan het eind van dit hoofdstuk heb je tien Python-functies die samen een tic-tac-toe-AI vormen die nooit verliest. Als beide spelers optimaal spelen, eindigt tic-tac-toe altijd in remise, en jouw AI speelt optimaal. Eerst met pen en papier.

Zo bouw je het op​

De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":

  1. Bouwsteen 1 — initial_state()
  2. Bouwsteen 2 — player(bord)
  3. Bouwsteen 3 — actions(bord)
  4. Functies in functies
  5. Bouwsteen 4 — result(bord, zet)
  6. Bouwsteen 5 — winner(bord)
  7. Bouwsteen 6 — terminal(bord)
  8. Bouwsteen 7 — utility(bord)
  9. Bouwsteen 8 — max_value en min_value
  10. Draai het zelf — buiten de browser
  11. Bouwsteen 9 — minimax(bord)

De laatste bouwsteen is meteen het complete algoritme; daarna volgen de veelgemaakte fouten en de cheatsheet.

Door naar pen en papier →.