Er gaat iets mis — vier valkuilen

Leerdoel: je herkent de vier valkuilen bij het bouwen van een minimax-AI, en je weet bij elk symptoom waar je moet kijken.

Bord muteren in result

Geen foutmelding, wel een onverklaarbaar verkeerd antwoord. Minimax probeert zetten en gaat ervan uit dat het origineel niet mee verandert; doet het dat wel, dan raakt het hele algoritme van slag.

Oorzaak: zonder copy.deepcopy werkt Python met referenties. Een wijziging in nieuw_bord is ook zichtbaar in bord:

# FOUT
def result(bord, zet):
    nieuw = bord            # ← nieuw is GEEN kopie, het is hetzelfde object
    i, j = zet
    nieuw[i][j] = player(bord)
    return nieuw

Ook bord.copy() of list(bord) is niet genoeg: die maken alleen de buitenste lijst nieuw, de rijen daaronder blijven gedeeld.

Oplossing: gebruik copy.deepcopy(bord) voor een echte, diepe kopie:

# GOED
def result(bord, zet):
    nieuw = copy.deepcopy(bord)
    i, j = zet
    nieuw[i][j] = player(bord)
    return nieuw

result vergeten in de recursie

Foutmelding: RecursionError: maximum recursion depth exceeded. De browser hangt soms een paar seconden voordat hij komt.

Oorzaak: een recursieve aanroep moet een kleiner probleem krijgen. Geef je hetzelfde bord door in plaats van het bord na de zet, dan roept de functie zichzelf eindeloos aan op precies dezelfde positie:

# FOUT — hetzelfde bord gaat de recursie in
def max_value(bord):
    if terminal(bord):
        return utility(bord)
    v = -math.inf
    for zet in actions(bord):
        v = max(v, min_value(bord))            # ← zet wordt nergens gebruikt
    return v

Oplossing: de recursie krijgt altijd result(bord, zet), het bord met één cel meer gevuld. Na hoogstens negen stappen is het bord vol en stopt het vanzelf:

# GOED
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

Base case vergeten in max_value of min_value

Geen foutmelding, wel een AI die gewonnen borden niet ziet en waardes van inf of -inf teruggeeft. Geen RecursionError: het bord raakt na negen zetten vol, dus de recursie stopt wel, alleen op de verkeerde plek.

Oorzaak: zonder base case speelt de functie door op een bord waar al drie op een rij staat. Pas op een vol bord is actions(bord) leeg; dan draait de lus niet, blijft v op -math.inf staan en is dát wat er terugkomt:

# FOUT — geen base case
def max_value(bord):
    v = -math.inf
    for zet in actions(bord):
        v = max(v, min_value(result(bord, zet)))
    return v

Oplossing: check eerst of het bord terminal is. Zo ja, geef de utility terug (1, -1 of 0). Dat is de bodem van de recursie, en de enige plek waar een echt getal de boom in komt:

# GOED
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

Idem in min_value, en minimax zelf begint met if terminal(bord): return None.

Min en max omdraaien per laag

Geen foutmelding, wel een AI die verliest of zwak speelt.

Oorzaak: max_value roept per ongeluk max_value aan (zichzelf) in plaats van min_value. Of je verwart wie maximaliseert (X) en wie minimaliseert (O).

# FOUT — max_value roept max_value aan in plaats van min_value
def max_value(bord):
    if terminal(bord):
        return utility(bord)
    v = -math.inf
    for zet in actions(bord):
        v = max(v, max_value(result(bord, zet)))   # ← moet min_value zijn
    return v

Oplossing: onthoud het ritme van de beurten. max_value zoekt de beste keuze van X; de volgende beurt is van O, dus daar hoort min_value(result(...)). Andersom geldt hetzelfde.

# GOED
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)))    # ← afwisselend
    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)))    # ← afwisselend
    return v

Vuistregel: in max_value komt het woord min voor, en in min_value het woord max. Staat het andersom, dan klopt het niet.

Door naar cheatsheet →.

Doe je de route machine learning? Dan ben je nu klaar voor Tic-Tac-Toe van CS50, en daarna ga je door naar de buren van een vakje.