Bouwsteen 8 — max_value en min_value
Leerdoel: je schrijft twee recursieve functies die voor elke
positie uitrekenen wat de beste haalbare utility is voor X (max_value)
of voor O (min_value). Het zijn de boom-doorlopers van de
pen-en-papier-pagina, maar dan in code.
Wat doen deze functies?
Op de pen-en-papier-pagina rekende je de waarde
van elke knoop van onderop terug naar boven. Die vraag, wat is deze
positie waard, is precies wat max_value en min_value beantwoorden.
max_value(bord) neemt aan dat X aan zet is en zegt hoe goed het
maximaal voor X kan uitpakken. min_value(bord) neemt aan dat O
aan zet is en zegt hoe laag O de uitkomst voor X kan drukken. Allebei
geven ze 1, -1 of 0 terug.
Ze geven dus niet de zet terug, alleen het getal dat de positie waard
is. De zet zelf bepaal je straks in minimax.
Wat is recursie?
Een functie die zichzelf aanroept. Een klein voorbeeld dat niets met tic-tac-toe te maken heeft:
def aftellen(n):
if n == 0:
print("Klaar")
return
print(n)
aftellen(n - 1)
aftellen(3)
3
2
1
Klaar
De functie roept zichzelf aan met een kleinere input, tot de
stopconditie n == 0 bereikt is. Recursie heeft drie ingrediënten: een
base case, een geval waarin het antwoord meteen bekend is zonder
nieuwe aanroep; een recursieve aanroep, waarin de functie zichzelf
aanroept op een kleinere input; en de zekerheid dat die kleinere input
uiteindelijk bij de base case uitkomt.
Het recept, in woorden
Zo beschrijft CS50 de twee functies, nog zonder Python:
max_value(bord):
is het bord klaar? → geef utility(bord) terug
v = min oneindig
voor elke zet die kan:
v = het hoogste van v en min_value(bord na die zet)
geef v terug
min_value(bord):
is het bord klaar? → geef utility(bord) terug
v = plus oneindig
voor elke zet die kan:
v = het laagste van v en max_value(bord na die zet)
geef v terug
Leg dat naast het recept van de pen-en-papier-pagina. De base case is
een terminal bord: daar is de utility al bekend, dus daar stopt de
recursie, met terminal(bord) en utility(bord) uit bouwsteen 6 en 7.
De recursieve aanroep is "kijk wat de tegenstander daarna doet": na een
zet van X is O aan de beurt, dus max_value vraagt het aan min_value,
en andersom. Dat is de afwisseling van MAX- en MIN-lagen in de boom. En
je komt er, omdat elke aanroep één cel meer gevuld heeft; na hoogstens
negen stappen is het bord vol.
De twee functies zijn elkaars spiegelbeeld: max_value begint op min
oneindig en houdt het hoogste bij, min_value begint op plus oneindig
en houdt het laagste bij. Voor "oneindig" heeft Python math.inf, na
import math. Je begint zo laag dat elke echte uitkomst hoger is.
Kijk hoe de recursie de boom doorloopt
Dit is de positie van de pen-en-papier-pagina. De twee functies
hieronder zijn af, met één toevoeging: ze printen bij elke aanroep waar
ze zijn, ingesprongen per laag van de boom. De extra parameter diepte
dient alleen voor dat inspringen. Gebruik hier de knop Voer uit en niet
Stap voor stap: die neemt hoogstens duizend stappen op, en deze
wandeling door de boom heeft er meer. De uitvoer hieronder ís de
wandeling.
Wat zie je?
MAX XXO OOX ...
X speelt (2, 0)
MIN XXO OOX X..
O speelt (2, 1)
MAX XXO OOX XO.
X speelt (2, 2)
klaar: XXO OOX XOX utility 0
MAX geeft 0
O speelt (2, 2)
MAX XXO OOX X.O
X speelt (2, 1)
klaar: XXO OOX XXO utility 0
MAX geeft 0
MIN geeft 0
X speelt (2, 1)
MIN XXO OOX .X.
O speelt (2, 0)
klaar: XXO OOX OX. utility -1
O speelt (2, 2)
MAX XXO OOX .XO
X speelt (2, 0)
klaar: XXO OOX XXO utility 0
MAX geeft 0
MIN geeft -1
X speelt (2, 2)
MIN XXO OOX ..X
O speelt (2, 0)
klaar: XXO OOX O.X utility -1
O speelt (2, 1)
MAX XXO OOX .OX
X speelt (2, 0)
klaar: XXO OOX XOX utility 0
MAX geeft 0
MIN geeft -1
MAX geeft 0
Lees de uitvoer naast de boom, met bij elke knoop het bord:
- ▲ 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
Het is dezelfde wandeling als op de pen-en-papier-pagina, in dezelfde
volgorde: eerst de linkertak helemaal naar beneden tot een klaar, dan
de waarde weer omhoog, dan de volgende tak. Elke regel MAX of MIN is
één aanroep van max_value of min_value, en elke inspringing is een
laag dieper in de boom. Pas helemaal onderaan, als alle drie de takken
terug zijn, kent de wortel zijn waarde: MAX geeft 0.
Specificatie
- Input voor beide: een
bord. - Output voor beide: een geheel getal
1,-1of0.
Voorspel
Wat geeft min_value terug op dit bord, waar X net gewonnen heeft?
bord = [["X","X","X"], ["O","O",None], [None]*3]
Antwoord
1, de utility van een bord waar X wint.
Het bord is terminal, dus de functie gaat meteen de base case in en geeft
utility(bord) terug, en dat is 1. Geen recursie, geen min of max. Op
een terminal bord is min_value(bord) == max_value(bord) == utility(bord).
Bouw zelf en test
Schrijf beide functies uit het recept, zonder de prints. Boven de starter staan de zeven bouwstenen die je al hebt.
Tip
Begin met de base case:
if terminal(bord):
return utility(bord)
Daarna een lus over actions(bord) die v bijwerkt. Twee dingen om
dubbel te checken: in max_value roep je min_value aan, niet
max_value (zie ook er gaat iets mis), en de startwaarde
moet zo zijn dat elke echte uitkomst beter is, dus -math.inf voor
max en math.inf voor min.
Antwoord
def max_value(bord):
if terminal(bord):
return utility(bord)
v = -math.inf
for zet in actions(bord):
v = max(v, min_value(result(bord, zet)))
return v
def min_value(bord):
if terminal(bord):
return utility(bord)
v = math.inf
for zet in actions(bord):
v = min(v, max_value(result(bord, zet)))
return v
Precies het recept, regel voor regel. max_value roept min_value aan
en andersom; die afwisseling is de boom.
Door naar draai het zelf →.