Cheatsheet — Minimax

Snelle referentie. Klap open wat je nodig hebt.

Het complete tic-tac-toe project

Alle tien functies bij elkaar

import copy
import math


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


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


def actions(bord):
    mogelijk = set()
    for i in range(3):
        for j in range(3):
            if bord[i][j] is None:
                mogelijk.add((i, j))
    return mogelijk


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
    for rij in bord:
        for cel in rij:
            if cel is None:
                return False
    return True


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 = 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

Per functie — wat doet hij?

initial_state, player, actions

Functie	Input	Output
initial_state()	—	3×3 lijst van None
player(bord)	bord	"X" als X-beurt, anders "O"
actions(bord)	bord	set van (i, j) lege cellen

result, winner, terminal

Functie	Input	Output
result(bord, zet)	bord + tuple (i, j)	nieuw bord met zet toegepast
winner(bord)	bord	"X", "O" of None
terminal(bord)	bord	True als spel af is, anders False

utility, max_value, min_value, minimax

Functie	Input	Output
utility(bord)	terminale bord	1, -1 of 0
max_value(bord)	bord	hoogst-mogelijke utility (X-perspectief)
min_value(bord)	bord	laagst-mogelijke utility (O-perspectief)
minimax(bord)	niet-terminale bord	optimale 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 dingen die erin moeten zitten: de base case if terminal(bord): return utility(bord), een startwaarde -inf voor max en +inf voor min, en de afwisseling waarin max_value steeds min_value aanroept en andersom.

Game-tree denkraam

Hoe vertaal je een game-tree naar Python?

Game tree concept	Python
Knoop	een bord (3×3 lijst)
Aftakkingen vanuit een knoop	actions(bord)
Kind-knoop	result(bord, zet)
Blad (terminal)	terminal(bord) returns True
Score van een blad	utility(bord)
MAX kiest	max(...) over kinderen
MIN kiest	min(...) over kinderen

Valkuilen

Veelgemaakte fouten

1. Bord muteren in result: gebruik copy.deepcopy.
2. result vergeten in de recursie: RecursionError. De recursie krijgt altijd result(bord, zet), nooit bord zelf.
3. Base case vergeten in max_value of min_value: waardes van inf en -inf, en gewonnen borden blijven ongezien. Check eerst of het bord terminal is.
4. max_value roept zichzelf aan in plaats van min_value: de AI verliest. De beurten moeten wisselen.

Volledig overzicht: 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 veranderen. Tijdens de recursie houd je een alpha (de beste score voor MAX tot nu toe) en een beta (de beste score voor MIN tot nu toe) bij. Zodra beta <= alpha weet je dat de tegenstander deze tak nooit kiest, en sla je hem over. Bij een gunstige volgorde van de zetten wordt het O(b^(d/2)), kwadratisch sneller. Voor onze tic-tac-toe-AI niet nodig, maar wel goed om te kennen.

Verder lezen

• het idee: nog een keer door het concept.
• met pen en papier: de boom met de hand, voor wie het algoritme nog niet ziet.
• helpers: max_value en min_value.
• draai het zelf: je negen functies in één lokaal tictactoe.py, of in een verzamel-PyRunner als noodoplossing.
• minimax: de AI zelf, in je lokale bestand, en daarna speelt hij tegen zichzelf.
• Big O notatie: waarom minimax bij grotere spellen onhoudbaar wordt zonder optimalisaties.
• Waar minimax echt is gebruikt: Deep Blue, Chinook, Stockfish.

Licentie en bronvermelding

Dit hoofdstuk 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 met 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 dit hoofdstuk onder dezelfde licentie verspreid: CC BY-NC-SA 4.0.

De rest van de Coderius Algoritmes-site staat onder CC BY-NC 4.0.