De Minimax-algoritme implementeren voor AI in Python

Het Mini-max-algoritme heeft een rijke geschiedenis in AI en gaat terug tot de jaren 1920. Hoewel de term AI destijds niet voor computeralgoritmen werd gebruikt, gaf het onderliggende algoritme zeker al vroege inzichten in hoe machines optimale beslissingen kunnen nemen in tegengestelde scenario’s. Het algoritme werd voor het eerst geformaliseerd door John von Neumann in zijn paper uit 1928 “Zur Theorie der Gesellschaftsspiele” (Over de theorie van strategische spellen), die de basis legde voor de moderne speltheorie en besluitvormingsalgoritmen.

In 1997 versloeg IBM’s Deep Blue wereldkampioen schaken Garry Kasparov met geavanceerde varianten van Mini-max. Sindsdien is het algoritme de ruggengraat geweest voor meer verfijnde benaderingen zoals Monte Carlo Tree Search (MCTS) en reinforcement learning-systemen.

In dit artikel bouwen we geen nieuwe Deep Blue voor schaken, maar een veel eenvoudigere versie voor boter-kaas-en-eieren in Python. Onderweg krijg je een sterke intuïtie voor hoe het algoritme werkt en hoe je het toepast op complexere, realistische spellen.

Wat is het Minimax-algoritme?

Minimax is doorgaans een besluitvormingsalgoritme voor tweespelerspellen (zoals schaken, boter-kaas-en-eieren of dammen). Het stelt computers in staat meerdere zetten vooruit te plannen, ervan uitgaande dat je tegenstander altijd de best mogelijke zet doet. In deze sectie bekijken we een overzicht van het algoritme aan de hand van boter-kaas-en-eieren.

Overzicht van het Minimax-algoritme

In een echt potje boter-kaas-en-eieren probeer je bij elke beurt de best mogelijke zet te doen, terwijl je ervan uitgaat dat je tegenstander ook zijn beste spel speelt. Dat is precies wat het Minimax-algoritme doet — het helpt een computer de best mogelijke zet te maken door vooruit te denken over alle mogelijke zetten.

Het Minimax-algoritme dankt zijn naam aan de manier waarop het werkt:

• “Mini” staat voor de tegenstander die jouw score probeert te minimaliseren
• “Max” staat voor jou die je score probeert te maximaliseren

Als jij aan de beurt bent, wil je zetten doen die je de beste kans op winst geven (maximaliseren). Als je tegenstander aan de beurt is, ga je ervan uit dat die zetten doet die voor jou het slechtste resultaat opleveren (minimaliseren).

Het belang van Minimax in AI

Minimax is erg belangrijk in kunstmatige intelligentie om meerdere redenen:

1. Het helpt computers slimme beslissingen te nemen in tweespelerspellen
2. Het is de basis voor veel moderne spelende AI-systemen
3. Het leert computers vooruit te denken en zetten te plannen

Het leukste? Exact hetzelfde idee wordt in tal van echte toepassingen gebruikt:

• Tegenstanders in videogame-AI
• Strategiespellen zoals schaken en dammen
• Zelfs sommige tools voor zakelijke besluitvorming

Hoewel Minimax misschien ingewikkeld klinkt, leren we de computer in feite alleen te denken als een zorgvuldige speler die voor zijn beslissing zowel zijn eigen zetten als die van de tegenstander overweegt.

Het Minimax-algoritme begrijpen

Laten we uitleggen hoe Minimax werkt met een eenvoudig voorbeeld van boter-kaas-en-eieren. Stel: jij speelt als X en de computer is O.

Hoe de computer denkt

Als de computer aan de beurt is, volgt die deze stappen:

1. Kijkt naar alle mogelijke zetten die hij kan doen
2. Beeldt zich voor elke zet in wat jij daarna zou kunnen doen
3. Blijft vooruitdenken tot een eindpunt is bereikt (iemand wint of gelijkspel)
4. Kiest de zet die de grootste kans op winst geeft

Het spel scoren

De computer kan een eenvoudig scoresysteem gebruiken:

• +10 punten als de computer wint
• -10 punten als jij wint
• 0 punten bij een gelijkspel

Zie het als een boom van mogelijkheden:

• Bovenaan staat het huidige bord
• Elke tak is een mogelijke zet
• Onderaan staan alle mogelijke uitkomsten

Om de beurt

De computer schakelt tussen twee denkmodes:

1. Maximalisatiemodus (beurt van de computer):

• Zoekt naar zetten die de hoogste score opleveren
• Probeert te winnen of een gelijkspel af te dwingen

2. Minimalisatiemodus (beurt van de speler):

• Gaat ervan uit dat jij zetten doet die de laagste score opleveren
• Bereidt zich voor op jouw best mogelijke zetten

Een simpel voorbeeld

Stel, het is de beurt van de computer (X) in dit spel:

De computer zal:

1. Zien dat er 3 lege vakjes zijn om uit te kiezen
2. Voor elk leeg vakje alle mogelijke toekomstige zetten overwegen
3. De zet kiezen die tot de beste uitkomst leidt
4. In dit geval het middelste vakje onderaan kiezen om jouw winst te blokkeren

Door zo vooruit te denken speelt de computer elke keer een perfect potje boter-kaas-en-eieren!

Minimax-algoritme in pseudocode

Laten we stap voor stap uitschrijven hoe je het Minimax-algoritme schrijft. Geen zorgen als je nieuw bent met pseudocode — zie het als het in gewoon Engels uitschrijven van de stappen voordat we het in echte code omzetten!

Stap-voor-stap uitleg

De Minimax-functie heeft drie hoofdzaken nodig om te werken:

1. Het huidige speelbord
2. De diepte (hoeveel zetten vooruit we kijken)
3. Of het de beurt is van de maximaliserende speler (computer) of van de minimaliserende speler (mens)

Zo ziet de basispseudocode eruit:

function minimax(board, depth, isMaximizingPlayer):
   # First, check if the game is over
   if game is won:
       return +10 if computer wins, -10 if human wins
   if game is tied:
       return 0

   # If it's the computer's turn (maximizing)
   if isMaximizingPlayer:
       bestScore = -infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, false)
           undo the move
           bestScore = max(score, bestScore)
       return bestScore

   # If it's the human's turn (minimizing)
   else:
       bestScore = +infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, true)
           undo the move
           bestScore = min(score, bestScore)
       return bestScore

Hoewel de meeste pseudocodevoorbeelden in het Engels lezen en prima te begrijpen zijn, is het bovenstaande anders omdat het recursie gebruikt. Recursie is wanneer een functie zichzelf telkens weer aanroept om een groter probleem op te lossen. Zie het als in een spiegel kijken die een andere spiegel weerspiegelt — je ziet hetzelfde beeld vele malen herhaald, elke keer kleiner.

In ons Minimax-algoritme hebben we recursie nodig omdat we alle mogelijke toekomstige zetten in het spel willen bekijken. Elke keer dat de functie zichzelf aanroept, kijkt die naar de volgende mogelijke zet.

Dit helpt ons de beste zet te vinden door elke mogelijke manier waarop het spel kan verlopen te controleren, als een hele slimme speler die denkt: “Als ik dit doe, dan doen zij dat, en dan kan ik dit…” en zo verder tot het spel eindigt. Wil je meer leren over recursie, lees dan onze aparte tutorial over recursie.

Illustratief voorbeeld

Laten we zien hoe dit werkt in een eenvoudige spelsituatie:

1. Startpositie:

2. De computer denkt:

• “Als ik X in een leeg vakje zet…”
• “Wat zou de mens daarna doen?”
• “En wat kan ik daarna doen?”
• “Welke zet geeft mij de beste eindscore?”

3. Voor elk leeg vakje doet de computer:

• Doet een zet
• Controleert of het spel voorbij is
• Zo niet, beeldt zich de beste zet van de mens in
• Gaat door totdat er een einde is gevonden
• Kiest de zet met de hoogste score

Zie het als schaken — je denkt steeds: “Als ik hierheen ga, gaan zij daarheen, dan kan ik hierheen…” maar de computer kan ALLE mogelijke zetten tegelijk overwegen!

Het mooie aan dit algoritme is dat het altijd de best mogelijke zet vindt, ervan uitgaande dat beide spelers perfect spelen. Het is alsof je een glazen bol hebt die je alle mogelijke toekomsten van het spel laat zien!

Minimax voor boter-kaas-en-eieren stap voor stap implementeren

In deze sectie bouwen we een onverslaanbare boter-kaas-en-eieren-AI op basis van het Mini-max-algoritme in pure Python. We breken de implementatie op in eenvoudige stappen en leggen de intuïtie achter elke stap uit en hoe die in het grotere geheel van het spel past.

Stap 1: Een TicTacToe-klasse definiëren

Eerst definiëren we een klasse die alle benodigde logica en methoden bevat om een boter-kaas-en-eieren-spel met onze computer te spelen:

class TicTacToe:
   def __init__(self):
       # Initialize empty board (using ' ' for empty squares)
       self.board = [" " for _ in range(9)]
       self.human_player = "O"
       self.ai_player = "X"

   def print_board(self):
       """Print the current state of the board"""
       for i in range(0, 9, 3):
           print(f"{self.board[i]} | {self.board[i+1]} | {self.board[i+2]}")
           if i < 6:
               print("---------")

   def available_moves(self):
       """Returns list of available moves (indices of empty squares)"""
       return [i for i, spot in enumerate(self.board) if spot == " "]

Hierboven initialiseert de __init__-methode een nieuw speelbord als een lijst van 9 lege vakjes (weergegeven als spaties " "), met indexen 0-8 die de bordposities van links naar rechts, van boven naar beneden voorstellen. Hij stelt ook twee spelersymbolen in: "O" voor de menselijke speler en "X" voor de AI.

De print_board-methode biedt een manier om de huidige bordtoestand te visualiseren. Hij print het 3x3-raster met scheidingslijnen tussen de rijen en toont de zetten van elke speler op hun posities.

De available_moves-methode retourneert een lijst van alle geldige zetten die nog gedaan kunnen worden. Dit doet hij door te controleren welke posities op het bord nog leeg zijn (een spatie " ") en hun indexen terug te geven. Dit is cruciaal voor het minimax-algoritme om te weten welke zetten het kan overwegen.

Deze methoden vormen de basis waarop we onze AI-speler met het minimax-algoritme gaan bouwen.

Laten we ze snel testen:

>>> game = TicTacToe()
>>> game.print_board()
  |   | 
---------
  |   | 
---------
  |   |

>>> game.available_moves()
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Zoals verwacht hebben we nu een leeg bord en zijn alle zetten beschikbaar.

Stap 2: Methoden implementeren voor een zet doen en bordtoestanden controleren

Nu voegen we een methode toe om een zet te doen:

class TicTacToe:
   ...
  
   def make_move(self, position, player):
       """Make a move on the board"""
       if self.board[position] == " ":
           self.board[position] = player
           return True
       return False

We hebben de make_move-methode toegevoegd die:

• Een positie (0–8) en spelersymbool (“X” of “O”) als invoer neemt
• Controleert of de gekozen positie leeg is (“ ”)
• Als die leeg is, het symbool plaatst en True teruggeeft
• Als de positie al bezet is, False teruggeeft zonder wijzigingen

Laten we een paar zetten doen en de resterende zetten controleren:

>>> game = TicTacToe()

>>> game.make_move(0, "X")
>>> game.make_move(1, "O")

>>> game.print_board()
 X | O | 
-----------
   |   | 
-----------
   |   |

>>> game.available_moves()
[2, 3, 4, 5, 6, 7, 8]

Werkt goed. De volgende stap is een methode toevoegen om te controleren of het bord vol is:

class TicTacToe:
   ...

   def is_board_full(self):
       """Check if the board is full"""
       return " " not in self.board

is_board_full is een booleaanse methode die controleert of er nog lege vakjes op het bord zijn.

Vervolgens voegen we een methode toe om te controleren of een winnende staat is bereikt:

class TicTacToe:
   ...

   def check_winner(self):
       """Check if there's a winner. Returns winner symbol or None"""
       # Check rows
       for i in range(0, 9, 3):
           if self.board[i] == self.board[i + 1] == self.board[i + 2] != " ":
               return self.board[i]

       # Check columns
       for i in range(3):
           if self.board[i] == self.board[i + 3] == self.board[i + 6] != " ":
               return self.board[i]

       # Check diagonals
       if self.board[0] == self.board[4] == self.board[8] != " ":
           return self.board[0]
       if self.board[2] == self.board[4] == self.board[6] != " ":
           return self.board[2]

       return None

De check_winner-methode beoordeelt de huidige staat van het boter-kaas-en-eieren-bord om te bepalen of er een winnaar is. Hij controleert alle mogelijke winnende combinaties:

1. Rijen (3 mogelijkheden):

• Bovenste rij (indexen 0,1,2)
• Middelste rij (indexen 3,4,5)
• Onderste rij (indexen 6,7,8)

2. Kolommen (3 mogelijkheden):

• Linker kolom (indexen 0,3,6)
• Middelste kolom (indexen 1,4,7)
• Rechter kolom (indexen 2,5,8)

3. Diagonalen (2 mogelijkheden):

• Linksboven naar rechtsonder (indexen 0,4,8)
• Rechtsboven naar linksonder (indexen 2,4,6)

Voor elke combinatie controleert hij of alle drie de posities hetzelfde spelersymbool (X of O) bevatten en niet leeg zijn. Als een winnende combinatie is gevonden, retourneert hij het symbool van de winnende speler. Als er na alle controles geen winnaar is, retourneert hij None.

Laten we de functie testen in winnende en niet-winnende staten:

game = TicTacToe()

# Winning state
game.make_move(0, "X")
game.make_move(1, "X")
game.make_move(2, "X")

>>> game.print_board()
 X | X | X
-----------
   |   | 
-----------
   |   |

>>> game.check_winner()
'X'

game = TicTacToe()

# Non-winning state
game.make_move(0, "X")
game.make_move(1, "O")
game.make_move(2, "O")
game.make_move(3, "X")

>>> game.print_board()
 X | O | O
-----------
 X |   | 
-----------
   |   |

>>> game.check_winner() is None
True

Tot slot voegen we nog een booleaanse methode toe om aan te geven of het spel voorbij is of niet:

class TicTacToe:
   ...

   def game_over(self):
       """Check if the game is over"""
       return self.check_winner() is not None or self.is_board_full()

De methode retourneert True als er óf een winnaar is gevonden óf het bord vol is.

Op dit punt hebben we alle kernmechanieken van het spel gebouwd:

• Het bord is een lijst van 9 vakjes die leeg zijn geïnitialiseerd
• print_board() toont de huidige speltoestand visueel
• available_moves() geeft indexen van lege vakjes terug
• make_move() plaatst het symbool van een speler op het bord
• check_winner() bekijkt rijen, kolommen en diagonalen op een winst na elke zet
• is_board_full() bepaalt of er geen zetten meer over zijn
• game_over() combineert de winnaar- en vol-bord-controle

Deze methoden vormen de basis voor een speelbaar spel en handelen alle basisoperaties af zoals zetten doen en de speltoestand bepalen.

Nu komt het cruciale deel — de computer de “hersens” geven om met Minimax te spelen.

Stap 3: Minimax implementeren voor boter-kaas-en-eieren

Laten we nu het algoritme voor het spel implementeren in een nieuwe methode:

class TicTacToe:
   ...

   def minimax(self, depth, is_maximizing):
       """
       Minimax algorithm implementation
       Returns the best score possible for the current board state
       """
       # Base cases
       winner = self.check_winner()
       if winner == self.ai_player:
           return 1
       if winner == self.human_player:
           return -1
       if self.is_board_full():
           return 0

De functie neemt twee parameters aan:

• depth - Houdt bij hoe diep we in de recursie zitten. Dit kan worden gebruikt om de zoekdiepte te beperken voor zeer complexe spellen, maar voor boter-kaas-en-eieren is dat niet nodig.
• is_maximizing - Een booleaanse vlag die aangeeft of we momenteel zoeken naar de maximale score (beurt AI) of minimale score (beurt mens). Dit wisselt bij elke recursieve aanroep, omdat spelers om de beurt gaan.

In de functie beginnen we met de basisgevallen: Als het spel door de AI is gewonnen (winner == ai_player), retourneren we 1, want dat is de beste uitkomst voor de AI. Als de mens wint (winner == human_player), retourneren we -1, de slechtste uitkomst voor de AI. Als het bord vol is zonder winnaar, retourneren we 0 voor een gelijkspel.

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       best_score = float("-inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(depth + 1, False)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = max(score, best_score)
       return best_score

Als is_maximizing True is, simuleren we de beurt van de AI en willen we de zet vinden die tot de hoogst mogelijke score leidt. We beginnen met best_score op min oneindig zodat elke echte score beter is. Voor elke beschikbare zet doen we vervolgens:

1. Tijdelijk het symbool van de AI op het bord plaatsen
2. Recursief evalueren wat er zou gebeuren als we deze zet doen door minimax aan te roepen met is_maximizing=False (want daarna is de mens aan de beurt)
3. De tijdelijke zet ongedaan maken om de bordtoestand te herstellen
4. De hoogste score tot dan toe bijhouden met max()

Zo kunnen we elke mogelijke zet van de AI controleren. Voor elke zet bekijken we wat er daarna zou kunnen gebeuren, helemaal tot iemand wint of het gelijkspel is. Daarna werken we terug om te vinden welke eerste zet de AI de beste winstkans geeft.

Nu doen we het minimalisatiegedeelte voor de mens:

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       ...

   else:
       # if it is the minimizing player's turn (human), we want to minimize the score
       best_score = float("inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.human_player
           # Recursively call minimax with the next depth and the maximizing player
           score = self.minimax(depth + 1, True)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = min(score, best_score)
       return best_score

Als is_maximizing False is, simuleren we de beurt van de menselijke speler en willen we de zet vinden die tot de laagst mogelijke score leidt (omdat een hoge score betekent dat de AI wint). We beginnen met best_score als plus oneindig zodat elke echte score lager is. Voor elke beschikbare zet doen we:

1. Tijdelijk het symbool van de mens op het bord plaatsen
2. Recursief evalueren wat er zou gebeuren door minimax aan te roepen met is_maximizing=True (want daarna is de AI aan de beurt)
3. De tijdelijke zet ongedaan maken
4. De laagste score tot dan toe bijhouden met min()

Dit simuleert de menselijke speler die de beste zetten probeert te doen om te voorkomen dat de AI wint. De mens wil de score minimaliseren, omdat positieve scores AI-overwinningen vertegenwoordigen. Door af te wisselen tussen maximaliserende en minimaliserende beurten kan het algoritme de optimale zetvolgorde voor beide spelers bepalen.

Stap 4: De beste zet voor de AI vinden met Minimax

Nu het algoritme klaar is, hebben we nog een methode nodig die de minimax-methode gebruikt om na elke menselijke zet de beste zet voor de AI te bepalen:

class TicTacToe:
   ...

   def get_best_move(self):
       """Find the best move for AI using minimax"""
       best_score = float("-inf")
       best_move = None

       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(0, False)
           # Reset the move
           self.board[move] = " "

           # Update the best score
           if score > best_score:
               best_score = score
               best_move = move

       return best_move

De methode get_best_move is verantwoordelijk voor het bepalen van de optimale zet voor de AI-speler met behulp van het minimax-algoritme. Ze werkt als volgt:

1. Start met min oneindig als beste score en zonder gekozen zet

2. Voor elke beschikbare zet op het bord:

• Tijdelijk het symbool van de AI op die positie plaatsen
• Met minimax beoordelen hoe goed die zet is door de rest van het spel te simuleren
• De tijdelijke zet ongedaan maken
• Als deze zet tot een betere score leidt dan we eerder zagen, zowel de beste score als de beste zet bijwerken

3. Uiteindelijk de zet retourneren die tot de hoogste score leidde

Deze aanpak zorgt ervoor dat de AI de zet kiest die de beste winstkans geeft, ervan uitgaande dat de menselijke speler ook optimaal speelt. De methode overweegt alle mogelijke toekomstige speltoestanden en kiest het pad dat de kansen van de AI maximaliseert en de kansen van de mens minimaliseert.

Laten we het testen op een voorbeeldtoestand:

game = TicTacToe()

# Make a couple of moves
game.make_move(0, "X")
game.make_move(1, "O")

# Print the board

>>> game.print_board()
X | O | 
---------
  |   | 
---------
  |   |

>>> game.get_best_move()
3

# AI moves
>>> game.make_move(3, "X")

# I move
>>> game.make_move(4, "O")
>>> game.print_board()
X | O | 
---------
X | O | 
---------
  |   |

# Get the best move for AI
>>> game.get_best_move()
6

Zoals je ziet, vond de AI de winnende combinatie op basis van mijn zetten (het was een dummy-toestand, maar dit bewijst dat ons algoritme werkt).

Stap 5: Een gameloop implementeren

Nu we ons minimax-algoritme hebben geïmplementeerd en getest, maken we een gameloop waarmee we tegen de AI kunnen spelen.

class TicTacToe:

   ...

   def play_game(self):
       """Main game loop"""
       print("Welcome to Tic Tac Toe!")
       print("You are 'O' and the AI is 'X'")
       print("Enter positions (0-8) as shown below:")
       print("0 | 1 | 2")
       print("---------")
       print("3 | 4 | 5")
       print("---------")
       print("6 | 7 | 8")
       print("\n")

De methode play_game begint met een welkomstbericht en instructies voor de speler. Ze laat zien dat de menselijke speler ‘O’ gebruikt en de AI ‘X’. Vervolgens print ze een genummerd raster (0–8) om te tonen welk nummer bij welke positie op het bord hoort. Zo weet je precies welk nummer je moet invoeren voor je gewenste zet.

# ... the rest of the class
def play_game(self):
   ...

   # Randomly decide who goes first
   import random

   ai_turn = random.choice([True, False])

   while not self.game_over():
       self.print_board()

       if ai_turn:
           print("\nAI's turn...")
           move = self.get_best_move()
           self.make_move(move, self.ai_player)
       else:
           while True:
               try:
                   move = int(input("\nYour turn (0-8): "))
                   if 0 <= move <= 8 and self.make_move(move, self.human_player):
                       break
                   else:
                       print("Invalid move! Try again.")
               except ValueError:
                   print("Please enter a number between 0 and 8!")

       ai_turn = not ai_turn

Na de initiële instructies gaat het spel de hoofdloop in. Het spel beslist willekeurig wie er begint — de AI of de menselijke speler — met random.choice([True, False]). Dit zorgt voor eerlijkheid en onvoorspelbaarheid aan het begin van elk spel.

De hoofdgameloop gaat door tot game_over() True teruggeeft (iemand heeft gewonnen of het bord is vol). Tijdens elke beurt wordt de huidige bordtoestand getoond met print_board().

Als het de beurt van de AI is (ai_turn True is), dan:

1. Print een bericht dat de AI aan het denken is
2. Roept get_best_move() aan om met het minimax-algoritme de optimale zet te bepalen
3. Voert de zet uit door het symbool (‘X’) van de AI te plaatsen

Als het de beurt van de mens is (ai_turn False is), dan:

1. Gaat de code een lus in om geldige invoer van de speler te krijgen2. Vraagt een zetnummer tussen 0–83. Valideert dat de invoer:

• Een geldige integer is (met try/except)
• Binnen het geldige bereik 0–8 valt
• Naar een lege positie op het bord wijst

4. Blijft vragen tot er geldige invoer is. Voert de zet uit door het symbool (‘O’) van de speler te plaatsen

Na elke beurt wordt ai_turn omgeschakeld met not om tussen de spelers te wisselen. Dit creëert de afwisseling van het spel, waarbij elke speler steeds een beurt krijgt tot iemand wint of het in een gelijkspel eindigt.

De invoervalidatie zorgt ervoor dat het spel niet crasht door ongeldige invoer en geeft behulpzame foutmeldingen om de speler naar correcte zetten te leiden. Dit zorgt voor een robuuste en gebruiksvriendelijke spelervaring.

def play_game(self):
   ...
   # Game over
   self.print_board()
   winner = self.check_winner()
   if winner == self.ai_player:
       print("\nAI wins!")
   elif winner == self.human_player:
       print("\nCongratulations! You win!")
   else:
       print("\nIt's a tie!")

Als het spel eindigt, wordt de uiteindelijke bordtoestand weergegeven met print_board() en wordt de winnaar bepaald met check_winner(). Het spel kan op drie manieren eindigen:

1. AI wint — Als check_winner() het symbool van de AI (‘X’) retourneert, wat betekent dat de AI een winnende lijn heeft
2. Mens wint — Als check_winner() het symbool van de mens (‘O’) retourneert, wat betekent dat de speler een winnende lijn heeft
3. Gelijkspel — Als geen van beide spelers heeft gewonnen maar het bord vol is, dus er geen zetten meer mogelijk zijn

Het juiste bericht wordt getoond om de uitkomst van het spel aan te kondigen. Dit geeft de speler duidelijke feedback over hoe het spel is geëindigd.

Stap 6: Alles samenbrengen

Nu is het tijd om alle code die we tot nu toe hebben geschreven in een Python-script te zetten met de volgende if/main-clausule helemaal onderaan:

# Start the game
if __name__ == "__main__":
   game = TicTacToe()
   game.play_game()

Dit zorgt ervoor dat het spel start zodra je het script uitvoert met python script.py. Ben je de draad kwijtgeraakt tussen alle uitleg en codeblokken, dan vind je de volledige code voor het spel in deze GitHub gist.

Hier is een voorbeeldpotje dat ik speelde:

❯ python tic-tac-toe.py
Welcome to Tic Tac Toe!
You are 'O' and the AI is 'X'
Enter positions (0-8) as shown below:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8


  |   | 
---------
  |   | 
---------
  |   | 

Your turn (0-8): 4
  |   | 
---------
  | O | 
---------
  |   | 

AI's turn...
X |   | 
---------
  | O | 
---------
  |   | 

Your turn (0-8): 5
X |   | 
----------
  | O | O
----------
  |   | 

AI's turn...
X |   | 
---------
X | O | O
---------
  |   | 

Your turn (0-8): 6
X |   | 
---------
X | O | O
---------
O |   | 

AI's turn...
X |   | X
---------
X | O | O
---------
O |   | 

Your turn (0-8): 1
X | O | X
---------
X | O | O
---------
O |   | 

AI's turn...
X | O | X
---------
X | O | O
---------
O | X | 

Your turn (0-8): 8
X | O | X
---------
X | O | O
---------
O | X | O

It's a tie!

Onthoud: omdat boter-kaas-en-eieren een eenvoudig spel is, is er geen kans om de AI te verslaan. Het eindigt ofwel in een gelijkspel of je verliest!

Het Mini-max-algoritme formaliseren

Laten we nu de algemene definitie van het algoritme bekijken, los van het eenvoudige voorbeeld van boter-kaas-en-eieren.

Het Minimax-algoritme kan formeel worden gedefinieerd als een recursieve functie die posities in een nulsomspel evalueert. Laten we de formele componenten en eigenschappen uiteenzetten.

Wiskundige definitie

Voor een speltoestand s is de minimax-waarde V(s) gedefinieerd als:

V(s) =
   utility(s)                    if s is terminal
   max(V(s')) for all s' in S    if player = MAX
   min(V(s')) for all s' in S    if player = MIN

Waarbij:

• s’ de opvolgtoestanden van s voorstelt
• S de verzameling van alle legale zetten vanuit toestand s is
• utility(s) de evaluatiefunctie is voor terminale toestanden

Belangrijkste eigenschappen

1. Volmaakte informatie

• Alle spelers hebben volledige kennis van de speltoestand
• Geen verborgen informatie of toevalselementen
• Deterministische uitkomsten

2. Nulsomkarakter

• De winst van de één is exact het verlies van de ander
• De som van de utiliteiten van alle spelers is altijd nul
• Voor tweespelerspellen zijn utiliteiten doorgaans {-1, 0, 1}

3. Optimale speelwijze

• Gaat ervan uit dat beide spelers optimale beslissingen nemen
• Garandeert de best mogelijke uitkomst tegen perfect spel
• Leidt tot een Nash-evenwicht in termen van speltheorie

Complexiteitsanalyse

Tijdcomplexiteit: O(b^m)

• b = vertakkingsfactor (aantal legale zetten in elke toestand)
• m = maximale diepte van de spelboom

Ruimtecomplexiteit: O(bm)

• Vereist het opslaan van de speltoestand op elk niveau
• Kan worden geoptimaliseerd met iteratieve verdieping

Evaluatiefunctie

Voor niet-terminale toestanden moet de evaluatiefunctie f(s):

1. Correlatie hebben met de winstkans
2. Rekenkundig efficiënt zijn
3. Een consistente schaal behouden gedurende het spel

De formele definitie:

f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ

Waarbij:

• wᵢ gewichten zijn voor verschillende features
• xᵢ featurewaarden uit de speltoestand zijn
• n het aantal geëvalueerde features is

Optimaliteitsgarantie

Het Minimax-algoritme garandeert optimaal spel onder deze voorwaarden:

1. Volmaakte informatie
2. Deterministische uitkomsten
3. Volledige zoektocht tot terminale toestanden
4. Nauwkeurige evaluatie van terminale toestanden

Dit maakt het bijzonder geschikt voor spellen als schaken, boter-kaas-en-eieren en dammen, waar aan deze voorwaarden wordt voldaan.

Geavanceerde varianten en beperkingen

Hoewel Minimax geweldig is voor eenvoudige spellen zoals boter-kaas-en-eieren, heeft het problemen bij grotere spellen. Laten we kijken hoe we het sneller kunnen maken en waar het moeite mee heeft.

Minimax versnellen: Alpha-beta-pruning

Stel, je speelt schaken en denkt na over je zetten. Als je een winnende zet hebt gevonden, hoef je niet alle andere mogelijke zetten te controleren, toch? Alpha-beta-pruning werkt hetzelfde — het helpt de computer zetten over te slaan waarvan we al weten dat ze niet beter zullen zijn dan wat we hebben gevonden.

Denk er zo over:

• Je zoekt de goedkoopste chocoladereep
• Je hebt $1 te besteden
• Als je een reep van 50¢ vindt, kun je alle repen die meer dan $1 kosten overslaan
• Dat bespaart tijd!

Dieptelimieten: Niet té ver vooruitkijken

In grote spellen zoals schaken zijn er te veel mogelijke zetten om ze allemaal te controleren. Daarom voegen we een dieptelimiet toe:

1. Kijk slechts 4–5 zetten vooruit in plaats van tot het einde
2. Maak een goede gok over hoe goed de positie dan is
3. Kies de beste zet op basis van deze schattingen

Je kunt niet elke zet tot het einde plannen, maar wel een paar zetten vooruit!

Waar Minimax moeite mee heeft

Minimax is niet perfect. Dit zijn de grootste problemen:

1. Te veel keuzes

• Spellen zoals Go hebben veel te veel mogelijke zetten
• Zelfs snelle computers kunnen ze niet allemaal controleren
• Daarom hebben we andere methoden nodig voor echt complexe spellen

2. Tijdproblemen

• Hoe verder je vooruitkijkt, hoe langer het duurt
• In schaken kunnen computers niet elke mogelijke zet bekijken
• Ze moeten slim zijn in welke zetten ze controleren

3. Niet goed bij onzekere spellen

• Minimax werkt het best als je alles kunt zien
• Het is niet goed voor kaartspellen waarbij je de kaarten van anderen niet kent
• Het kan niet goed overweg met willekeurige gebeurtenissen (zoals dobbelstenen)

Moderne oplossingen

Tegenwoordig combineert game-AI Minimax vaak met andere slimme technieken:

1. Machine learning

• Computers kunnen leren door heel veel partijen te bekijken
• Dit helpt om betere inschattingen te maken van goede zetten
• Spellen zoals AlphaGo gebruiken dit om menselijke kampioenen te verslaan

2. Patroonherkenning

• In plaats van elke zet te controleren, zoeken naar patronen
• Net zoals menselijke spelers goede zetten herkennen
• Dit maakt de computer veel sneller

3. Geheugenbank

• Posities onthouden die eerder zijn gezien
• Geen tijd verspillen aan het twee keer uitrekenen van hetzelfde
• Als een spiekbriefje met goede zetten!

Het leukste? Deze verbeteringen helpen computers bijna net zo goed als mensen te spelen, en soms zelfs beter! Maar onthoud — zelfs met al deze slimme toevoegingen blijft Minimax de basis die alles laat werken.

Conclusie

In deze tutorial hebben we het Minimax-algoritme verkend van basisconcepten tot praktische implementatie. Dit is wat we hebben geleerd:

1. Kernconcepten

• Hoe Minimax computers helpt beslissingen te nemen in spellen
• Het verschil tussen minimaliserende en maximaliserende spelers
• Waarom het “minimax” heet en hoe het werkt

2. Implementatievaardigheden

• Een boter-kaas-en-eieren-spel from scratch bouwen
• Het Minimax-algoritme in Python schrijven
• Spel-logica testen en debuggen

3. Geavanceerde onderwerpen

• Het algoritme sneller maken met Alpha-Beta-pruning
• Omgaan met beperkingen in complexe spellen
• Moderne verbeteringen met machine learning

Wat nu?

Het Minimax-algoritme is slechts één stukje van de AI-puzzel. Als je enthousiast bent om meer te leren over AI en algoritmen, zijn dit mooie bronnen om je reis voort te zetten:

1. Verwante algoritmen

• A*-algoritme-tutorial — Leer over padvindingsalgoritmen
• Gids voor Gradient Boosting — Verken machinelearning-algoritmen

2. Toepassingen van machine learning

• Machine learning use cases — Zie toepassingen in de echte wereld

3. Complete leerpaden

• AI-toepassingen ontwikkelen — Bouw praktische AI-projecten
• AI Fundamentals — Beheers de basis van AI

Onthoud: of je nu een eenvoudig spel bouwt of een complex AI-systeem, inzicht in algoritmen zoals Minimax geeft je een sterke basis voor meer geavanceerde onderwerpen in kunstmatige intelligentie. Blijf oefenen, blijf leren en, vooral, blijf coderen!