Voorspel — waar of niet waar?
Leerdoel: je toetst je intuïtie over minimax met een paar stellingen, voordat je begint te programmeren.
Lees elke stelling. Bedenk eerst je antwoord. Klap dan pas open.
Stelling 1
"Minimax kiest altijd de zet die het meest direct naar winst leidt."
Antwoord
Niet waar.
Minimax kiest de zet die het beste eindresultaat garandeert tegen een optimale tegenstander. Soms is dat een lange, voorzichtige route naar remise in plaats van een gokje op winst dat de tegenstander kan blokkeren.
Stelling 2
"Bij tic-tac-toe wint X altijd als hij Minimax gebruikt."
Antwoord
Niet waar.
X wint als de tegenstander een fout maakt. Spelen beide spelers optimaal, bijvoorbeeld omdat ze allebei minimax gebruiken, dan eindigt het altijd in remise. Tic-tac-toe is een opgelost spel. Straks zie je dat zelf, als je AI tegen zichzelf speelt.
Stelling 3
"De MAX-speler kijkt altijd naar het hoogste blaadje in de tree."
Antwoord
Niet waar.
MAX kijkt naar zijn directe kinderen, en daar zit een MIN-laag tussen: de tegenstander. MAX kiest het kind met de hoogste MIN-uitkomst, niet het hoogste blaadje.
In het deel-1 voorbeeld op de pen-en-papier-pagina was het hoogste
blaadje 9 (onder tak B), maar MAX koos tak A omdat MIN daar min(3,5)=3
opleverde, beter dan de min(2,9)=2 onder tak B.
Stelling 4
"Minimax werkt voor elk spel waar beide spelers om de beurt zetten doen, ook als er dobbelstenen of verborgen kaarten in het spel zijn."
Antwoord
Niet waar.
Minimax rekent elke tak van de boom door alsof de uitkomst van een zet vaststaat en beide spelers alles zien. Dat vraagt twee dingen van het spel. Het moet deterministisch zijn: geen dobbelstenen, kaarten of toeval, een zet heeft een vaste uitkomst. En het moet volledige informatie hebben: beide spelers zien het hele bord, niets ligt verborgen.
Schaken, dammen en tic-tac-toe voldoen daaraan. Poker (verborgen kaarten) en backgammon (dobbelstenen) niet; daar zijn aanpassingen nodig.
Stelling 5
"Om de waarde van een positie uit te rekenen, doet minimax dezelfde berekening nog eens op het bord ná elke mogelijke zet."
Antwoord
Waar — Minimax is recursief.
Om uit te rekenen wat zet X waard is, moet je weten wat de tegenstander daarna zou kiezen. Dat is dezelfde vraag voor het bord-na-X, alleen met de tegenstander aan zet. Die vraagt op zijn beurt "wat doet X dan?", en zo verder tot een terminale positie.
Dat heet recursie: een functie die zichzelf aanroept, of twee functies die elkaar aanroepen. Hier wordt het dat laatste, één functie voor "X aan zet" en één voor "O aan zet"; je bouwt ze in bouwsteen 8.
Stelling 6
"De Minimax-functie hoeft niet de hele tree door te rekenen — alleen de tak die hij uiteindelijk kiest."
Antwoord
Niet waar.
Om te weten welke tak de beste is, moet je alle takken vergelijken; je kunt pas kiezen als je alle alternatieven hebt doorgerekend.
Voor grote spellen als schaken bestaan optimalisaties zoals alpha-beta pruning, die takken overslaan zonder dat de uitkomst verandert. Dat is een truc bovenop minimax. De kale minimax doet alles.
Hierna twee korte pagina's: hoe het bord eruitziet in Python, en hoe functies elkaar aanroepen.
Door naar het bord in Python →.