Ga naar hoofdinhoud

9.18 Cheatsheet — Minimax

Snelle referentie. Klap open wat je nodig hebt.

Het complete tic-tac-toe project​

Alle 9 functies bij elkaar
import copy
import math


def initial_state():
    return [[None]*3 for _ in range(3)]


def player(bord):
    x_count = sum(rij.count("X") for rij in bord)
    o_count = sum(rij.count("O") for rij in bord)
    return "X" if x_count == o_count else "O"


def actions(bord):
    return {(i, j) for i in range(3) for j in range(3) if bord[i][j] is None}


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


def winner(bord):
    for rij in bord:
        if rij[0] == rij[1] == rij[2] and rij[0] is not None:
            return rij[0]
    for j in range(3):
        if bord[0][j] == bord[1][j] == bord[2][j] and bord[0][j] is not None:
            return bord[0][j]
    if bord[0][0] == bord[1][1] == bord[2][2] and bord[0][0] is not None:
        return bord[0][0]
    if bord[0][2] == bord[1][1] == bord[2][0] and bord[0][2] is not None:
        return bord[0][2]
    return None


def terminal(bord):
    if winner(bord) is not None:
        return True
    return all(cel is not None for rij in bord for cel in rij)


def utility(bord):
    w = winner(bord)
    if w == "X":
        return 1
    if w == "O":
        return -1
    return 0


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


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, beste_zet = score, zet
    else:
        beste_score = math.inf
        for zet in actions(bord):
            score = max_value(result(bord, zet))
            if score < beste_score:
                beste_score, beste_zet = score, zet
    return beste_zet

Per functie — wat doet hij?​

initial_state, player, actions
FunctieInputOutput
initial_state()—3×3 lijst van None
player(bord)bord"X" als X-beurt, anders "O"
actions(bord)bordset van (i, j) lege cellen
result, winner, terminal
FunctieInputOutput
result(bord, zet)bord + tuple (i, j)nieuw bord met zet toegepast
winner(bord)bord"X", "O" of None
terminal(bord)bordTrue als spel af is, anders False
utility, max_value, min_value, minimax
FunctieInputOutput
utility(bord)terminale bord1, -1 of 0
max_value(bord)bordhoogst-mogelijke utility (X-perspectief)
min_value(bord)bordlaagst-mogelijke utility (O-perspectief)
minimax(bord)niet-terminale bordoptimale zet (i, j)

Recursie-template​

Patroon voor max_value en min_value
def max_value(bord):
    if terminal(bord):
        return utility(bord)           # base case
    v = -math.inf                       # zoek hoogste
    for zet in actions(bord):
        v = max(v, min_value(result(bord, zet)))   # recursie alterneert
    return v

Drie cruciale elementen:

  1. Base case = if terminal(bord): return utility(bord).
  2. Initialiseer v op -inf (max) of +inf (min).
  3. Alternerend max_value ↔ min_value aanroepen.

Game-tree denkraam​

Hoe vertaal je een game-tree naar Python?
Game tree conceptPython
Knoopeen bord (3×3 lijst)
Aftakkingen vanuit een knoopactions(bord)
Kind-knoopresult(bord, zet)
Blad (terminal)terminal(bord) returns True
Score van een bladutility(bord)
MAX kiestmax(...) over kinderen
MIN kiestmin(...) over kinderen

Top-3 valkuilen​

Veelgemaakte fouten
  1. Bord muteren in result → gebruik copy.deepcopy.
  2. Base case vergeten → RecursionError. Check eerst of bord terminal is.
  3. max_value roept zichzelf aan in plaats van min_value → AI verliest. Wisselbeurten zijn cruciaal.

Volledig overzicht: stap 17: er gaat iets mis.

Bonus — alpha-beta pruning​

Sneller minimax voor grotere spellen

Voor tic-tac-toe is de basis-versie snel genoeg. Voor schaken is O(b^d) (b = aantal opties per beurt, d = aantal beurten) onbruikbaar.

Alpha-beta pruning snijdt takken weg die de uitkomst toch niet kunnen beïnvloeden. Het idee: tijdens recursie houd je een alpha (beste-score-voor-MAX-tot-nu) en beta (beste-score-voor-MIN-tot-nu) bij. Zodra beta <= alpha, weet je dat de tegenstander deze tak nooit kiest — sla hem over.

Resultaat: bij optimale ordening O(b^(d/2)) — kwadratisch sneller.

Niet vereist voor onze tic-tac-toe AI, maar wel het noemen waard.

Verder lezen​

Licentie en bronvermelding​

Deze track is een afgeleide bewerking van CS50 AI Project 0: Tic-Tac-Toe van Harvard University. Het origineel is gelicenseerd onder CC BY-NC-SA 4.0.

Wijzigingen ten opzichte van het origineel:

  • Volledig vertaald naar het Nederlands.
  • Opgeknipt in 18 PRIMM-stappen (concept → pen-en-papier → bouwstenen → tests → fouten → cheatsheet).
  • Conceptuele uitleg over game trees, MIN/MAX-spelers en recursie toegevoegd.
  • Per functie inline assertion-tests toegevoegd, ingebed in dezelfde PyRunner als de starter-code.
  • Aparte tutorialpagina over functies-in-functies (de Python-vaardigheid die nodig is om bouwstenen op elkaar te laten voortbouwen).
  • Geen wijzigingen aan de specificaties van de 8 functies — die zijn één-op-één overgenomen uit het CS50-project.

Conform de share-alike-eis wordt deze track onder dezelfde licentie verspreid: CC BY-NC-SA 4.0.

De rest van de Coderius Algoritmes-site staat onder CC BY-NC 4.0 — zie LICENSE.md in de repository voor details.