9.14 Bouwsteen 8 — max_value en min_value

Leerdoel: je schrijft twee recursieve helper-functies die voor elke positie uitrekenen wat de beste-mogelijke utility is voor X (max_value) of voor O (min_value).

Wat doen deze functies?

Op de pen-en-papier-pagina rekende je MIN-MAX waardes van onderop terug naar boven. Die "wat is de waarde van deze positie?"-vraag — dát is wat max_value en min_value doen.

• max_value(bord): stel X is aan zet, hoe goed kan het maximaal voor X uitpakken? Returnt +1, -1 of 0.
• min_value(bord): stel O is aan zet, hoe slecht kan het minimaal voor X uitpakken? Returnt +1, -1 of 0.

Let op: max_value returnt niet de zet — alleen het getal dat de positie waard is. De zet zelf bepalen we straks in minimax.

Wat is recursie?

Een functie die zichzelf aanroept. Klein voorbeeld dat geen tic-tac-toe is:

def aftellen(n):
    if n == 0:
        print("Klaar!")
        return
    print(n)
    aftellen(n - 1)

aftellen(3) print 3, 2, 1, "Klaar.". De functie roept zichzelf aan met een kleinere input, totdat de stop-conditie geraakt wordt (n == 0).

Drie ingrediënten van recursie:

1. Base case — een conditie die zonder verdere recursie het antwoord teruggeeft.
2. Recursieve aanroep — de functie roept zichzelf aan op een "kleinere" of "simpelere" input.
3. Garantie van convergentie — die "kleinere" input moet uiteindelijk bij de base case uitkomen.

Recursie in max_value

• Base case: het bord is terminal → return utility(bord). Geen zetten meer, het getal is al bekend.
• Recursieve aanroep: voor elke mogelijke zet, kijk wat O daarna zou doen — dat is min_value(result(bord, zet)). Neem het maximum van al die uitkomsten.
• Convergentie: bij elke recursieve aanroep is er één extra cel gevuld. Het bord nadert vanzelf de terminale toestand.

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

v start op -math.inf (oneindig klein) zodat élke gevonden zet sowieso beter is. Voor elke kandidaat: kijk wat de tegenstander zou doen via min_value, en hou het maximum bij.

Recursie in min_value

Spiegelbeeld: O minimaliseert, en in de recursieve laag staat weer X aan zet — dus we roepen max_value aan.

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

Twee functies, samen vormen ze de afwisseling die minimax kenmerkt: max_value roept min_value aan, min_value roept max_value aan.

Specificatie

• Input voor beide: een bord.
• Output voor beide: een geheel getal 1, -1 of 0.

Voorspel

Wat denk je dat min_value returnt op dit bord (waar X net gewonnen heeft)?

bord = [["X","X","X"], ["O","O",None], [None]*3]

Antwoord

1 (de utility van X-wint).

Omdat het bord terminal is, gaat de functie meteen de base case in: return utility(bord) → 1. Geen recursie, geen min/max. Bij terminale invoer is min_value(bord) == max_value(bord) == utility(bord).

Bouw zelf en test

Python

Code-omgeving wordt voorbereid…

Tip

Het patroon is voor beide functies hetzelfde — verschil zit alleen in max vs min, en startwaarde -math.inf vs math.inf.

Begin altijd met de base case:

if terminal(bord):
    return utility(bord)

Daarna een lus die v bijwerkt:

v = -math.inf            # of math.inf voor min_value
for zet in actions(bord):
    v = max(v, min_value(result(bord, zet)))   # of min(...,max_value(...))
return v

Twee dingen om dubbel te checken:

1. In max_value roep je min_value aan in de recursie, niet max_value. Zie ook stap 17: er gaat iets mis.
2. De startwaarde moet zó zijn dat élke echte uitkomst beter is. Voor max start je dus op -inf, voor min op +inf.

Door naar stap 15: draai het zelf →.