Ga naar hoofdinhoud

Bouwsteen 9 — minimax(bord)

Hier bouw je op verder

Leerdoel: je schrijft de functie die alle vorige bouwstenen gebruikt om de beste zet terug te geven, direct in je lokale tictactoe.py.

Bij draai het zelf heb je je negen functies in één lokaal bestand gezet, of in de verzamel-PyRunner. Nu de tiende.

Wat doet deze functie?​

minimax(bord) geeft de beste zet terug voor de speler die nu aan zet is: niet het getal, dat doen max_value en min_value, maar de tuple (i, j). Is X aan zet, dan kies je de zet met de hoogste min_value(result(bord, zet)); is O aan zet, de zet met de laagste max_value(result(bord, zet)). Kruislings, want na een zet van X is O aan zet, dus je rekent met min_value. Voor O andersom.

Het patroon​

beste_zet = None
beste_score = -math.inf      # of +math.inf voor O

voor elke zet in actions(bord):
    score = min_value(result(bord, zet))    # of max_value voor O
    als score beter is dan beste_score:
        beste_score = score
        beste_zet = zet

return beste_zet

Dezelfde lus als in max_value, alleen onthoud je nu ook welke zet de beste was.

Speciaal geval​

Is het bord terminal, dan is er geen zet meer mogelijk en geef je None terug.

Specificatie​

  • Input: een bord (mag terminal zijn).
  • Output: een tuple (i, j) met de beste zet, óf None als het bord terminal is.

Voorspel​

Wat moet minimax teruggeven op deze positie? X is aan zet.

bord = [["X","O","O"], ["O","X","X"], [None, None, None]]
Antwoord

(2, 2): dat maakt de diagonaal X X X vol, directe winst.

De twee andere zetten winnen niet. Na (2, 0) of (2, 1) blokkeert O op (2, 2) en eindigt het in remise. Van de drie zetten heeft er dus precies één de waarde 1, en die geeft minimax terug.

Bouw zelf in tictactoe.py​

Open je lokale tictactoe.py (gemaakt bij draai het zelf). Plak deze starter onderaan, ná je negen functies:

def minimax(bord):
    if terminal(bord):
        return None

    # Vul aan:
    # 1. bepaal wie aan zet is met player(bord)
    # 2. loop over actions(bord); voor elke zet, bereken de score
    #    (min_value als X aan zet, max_value als O aan zet)
    # 3. onthoud de zet met de beste score
    # 4. return die zet
    return None
Tip

Het patroon is bijna hetzelfde als in max_value en min_value, met één verschil: je onthoudt welke zet het beste getal opleverde, niet alleen het getal. Je houdt dus twee variabelen bij, beste_score en beste_zet, en per speler een if: voor X vergelijk je met > en begin je op -math.inf, voor O met < en math.inf.

Vergeet je beste_zet bij te werken? Dan geeft minimax None terug.

Antwoord
def minimax(bord):
    if terminal(bord):
        return None

    beste_zet = None
    if player(bord) == "X":
        beste_score = -math.inf
        for zet in actions(bord):
            score = min_value(result(bord, zet))
            if score > beste_score:
                beste_score = score
                beste_zet = zet
    else:
        beste_score = math.inf
        for zet in actions(bord):
            score = max_value(result(bord, zet))
            if score < beste_score:
                beste_score = score
                beste_zet = zet
    return beste_zet

Het is max_value met een geheugen: dezelfde lus, alleen onthoud je naast de beste score ook bij welke zet die hoorde.

Test je minimax in tictactoe.py​

Plak deze tests onderaan je lokale bestand (na minimax):

# === Tests ===

# Terminal -> None
vol = [["X","O","X"],["X","O","O"],["O","X","X"]]
assert minimax(vol) is None, "Terminal bord -> None"

# X kan direct winnen op (2,2); de andere twee zetten geven hoogstens remise
bord = [["X","O","O"], ["O","X","X"], [None, None, None]]
zet = minimax(bord)
assert zet == (2, 2), f"Verwacht (2,2), kreeg {zet}"

# O moet X-winst blokkeren
# X heeft (0,0) en (1,1) -> dreigt op (2,2). O is aan zet.
bord = [["X", None, "O"], [None, "X", None], [None, None, None]]
zet = minimax(bord)
assert zet == (2, 2), f"O moet blokkeren op (2,2), kreeg {zet}"

print("Alle tests gehaald ✓")

In de terminal:

python tictactoe.py

Verwachte output: Alle tests gehaald ✓.

De AI-vs-AI demo​

Werkt het? Plak dan dit blok onderaan, na de tests:

def print_bord(bord):
    for rij in bord:
        cellen = []
        for c in rij:
            if c:
                cellen.append(c)
            else:
                cellen.append(".")
        print(" | ".join(cellen))
    print()


# AI vs AI
bord = initial_state()
print("\nStart:")
print_bord(bord)

while not terminal(bord):
    zet = minimax(bord)
    print(f"{player(bord)} speelt {zet}")
    bord = result(bord, zet)
    print_bord(bord)

w = winner(bord)
if w:
    print(f"Winnaar: {w}")
else:
    print("Remise — exact zoals voorspeld!")

Run opnieuw:

python tictactoe.py

Je AI speelt nu tegen zichzelf, en dat eindigt altijd in remise: zo zit tic-tac-toe in elkaar bij optimaal spel.

Op je laptop is dit een paar seconden, niet 30. Dat is het verschil tussen Python in de browser en Python op je eigen computer.

Bonus — CS50's runner.py met clickable GUI​

CS50 levert bij dit project een tweede bestand, runner.py, dat een venster opent waarin jij tegen je eigen AI speelt. Het gebruikt het tictactoe.py dat jij net hebt gebouwd. Zo werkt het:

  1. Download het project-zip via cs50.harvard.edu/ai/projects/0/tictactoe/ — daar staat runner.py in (Engelse versie van wat jij in het Nederlands hebt gebouwd).
  2. Vervang het bijgeleverde lege tictactoe.py door jouw versie. Zet bovenaan, onder de imports, drie regels die runner.py verwacht: 
    X = "X"
    O = "O"
    EMPTY = None
    Het CS50-project spreekt jouw bestand aan met die drie namen; jouw functies gebruiken de waardes zelf, dus verder verandert er niets.
  3. Installeer eenmalig pygame: 
    python -m pip install pygame
  4. Draai: 
    python runner.py

Er opent een venster. Je klikt op een vakje en je AI antwoordt: boter-kaas-en-eieren tegen een tegenstander die nooit blundert.

Geen lokale Python? Noodoplossing met PyRunner​

Open dit alleen als je echt niet lokaal kan draaien

Vervang de lege minimax op de aangegeven plek door je eigen versie, inclusief de regel def. De andere negen functies staan al klaar: ze draaien mee, en je leest ze onder de editor via "Toon de code die al klaarstaat". Onder minimax staan dezelfde tests als hierboven. Halen die het, dan speelt de AI tegen zichzelf. Let op: die demo kan in de browser zo'n 30 seconden duren — minimax rekent honderdduizenden posities door.

Python
Code-omgeving wordt voorbereid…

Je hebt nu een werkende AI op je eigen laptop, in een Python-bestand dat je kunt kopiëren, mailen of verder uitbouwen: tien kleine functies die elkaar aanroepen, elk apart getest.

Door naar veelgemaakte fouten →.