Lernpfad
Implementieren des Minimax-Algorithmus für KI in Python
Der Mini-Max-Algorithmus hat eine lange Geschichte in der KI, die bis in die 1920er Jahre zurückreicht. Obwohl der Begriff KI zu dieser Zeit noch nicht für Computeralgorithmen verwendet wurde, lieferte der grundlegende Algorithmus sicherlich einige der ersten Erkenntnisse darüber, wie Maschinen in gegnerischen Szenarien optimale Entscheidungen treffen können. Der Algorithmus wurde erstmals von John von Neumann in seiner Schrift "Zur Theorie der Gesellschaftsspiele" von 1928 formalisiert, die den Grundstein für die moderne Spieltheorie und Entscheidungsalgorithmen legte.
1997 besiegte Deep Blue von IBM den Schachweltmeister Garry Kasparov mit der fortgeschrittenen Variante von Mini-max. Seitdem ist der Algorithmus das Rückgrat für anspruchsvollere Ansätze wie Monte Carlo Tree Search (MCTS) und Verstärkungslernen Systeme.
In diesem Artikel werden wir nicht das berühmte Deep Blue für Schach nachbauen, sondern eine viel einfachere Version für Tic-Tac-Toe in Python. Auf dem Weg dorthin wirst du ein gutes Gespür dafür bekommen, wie der Algorithmus funktioniert und wie du ihn auf komplexere Spiele in der realen Welt anwenden kannst.
Was ist der Minimax-Algorithmus?
Minimax ist normalerweise ein Entscheidungsalgorithmus für Spiele mit zwei Spielern (wie Schach, Tic-Tac-Toe oder Dame). Sie erlaubt es Computern, mehrere Züge zu planen, während sie davon ausgehen, dass dein Gegner immer seinen bestmöglichen Zug machen wird. In diesem Abschnitt werden wir uns einen Überblick über den Algorithmus am Beispiel von Tic-Tac-Toe verschaffen.
Überblick über den Minimax-Algorithmus
Bei einem echten Tic-Tac-Toe versuchst du jedes Mal, wenn du an der Reihe bist, den bestmöglichen Zug zu machen, während du davon ausgehst, dass dein Gegner ebenfalls sein Bestes geben wird. Genau das macht der Minimax-Algorithmus - er hilft dem Computer, den bestmöglichen Zug zu machen, indem er über alle möglichen Züge nachdenkt.
Der Minimax-Algorithmus hat seinen Namen von seiner Funktionsweise:
- "Mini" steht für den Gegner, der versucht, deinen Punktestand zu minimieren.
- "Max" bedeutet, dass du versuchst, deine Punktzahl zu maximieren.
Wenn du an der Reihe bist, willst du Züge machen, die dir die besten Gewinnchancen bieten (Maximierung). Wenn dein Gegner an der Reihe ist, gehst du davon aus, dass er Züge machen wird, die dir das schlechteste Ergebnis bringen (Minimierung).
Die Bedeutung von Minimax in der KI
Minimax ist in der künstlichen Intelligenz aus mehreren Gründen sehr wichtig:
- Es hilft Computern, in Spielen mit zwei Spielern kluge Entscheidungen zu treffen
- Sie ist die Grundlage für viele moderne KI-Systeme in Spielen
- Es lehrt Computer, vorauszudenken und Züge zu planen
Das Coolste daran? Die gleiche Idee wird in vielen realen Anwendungen genutzt:
- KI-Gegner in Videospielen
- Strategiespiele wie Schach und Dame
- Sogar einige Entscheidungshilfen für Unternehmen
Minimax hört sich vielleicht kompliziert an, aber eigentlich geht es nur darum, dem Computer beizubringen, wie ein umsichtiger Spieler zu denken, der sowohl seine Züge als auch die seines Gegners bedenkt, bevor er eine Entscheidung trifft.
Den Minimax-Algorithmus verstehen
Lass uns die Funktionsweise von Minimax anhand eines einfachen Tic-Tac-Toe-Beispiels erläutern. Stell dir vor, du spielst als X, und der Computer ist O.
Wie der Computer denkt
Wenn der Computer an der Reihe ist, folgt er diesen Schritten:
- Schau dir alle möglichen Bewegungen an, die es machen kann
- Für jeden Zug stellt es sich vor, was du als nächstes tun könntest
- Es denkt so lange weiter, bis es einen Endpunkt erreicht (z.B. einen Sieg oder ein Unentschieden)
- Sie wählt den Zug, der ihr die besten Chancen auf den Sieg gibt
Das Spiel punkten
Der Computer kann ein einfaches Punktesystem verwenden:
- +10 Punkte, wenn der Computer gewinnt
- -10 Punkte, wenn du gewinnst
- 0 Punkte bei unentschiedenem Ausgang
Stell dir das wie einen Baum der Möglichkeiten vor:
- Oben ist der aktuelle Spielplan
- Jeder Zweig ist ein möglicher Zug
- Ganz unten stehen alle möglichen Ergebnisse
Abwechselnd
Der Computer wechselt zwischen zwei Denkmodi:
1. Maximierungsmodus (der Computer ist dran):
- Sucht nach Zügen, die die höchste Punktzahl erhalten
- Versucht zu gewinnen oder ein Unentschieden zu erzwingen
2. Minimierungsmodus (der Spieler ist am Zug):
- Geht davon aus, dass du Züge machst, die die niedrigste Punktzahl bringen
- Bereitet dich auf deine bestmöglichen Züge vor
Ein einfaches Beispiel
Nehmen wir an, der Computer (X) ist in diesem Spiel an der Reihe:
Der Computer wird:
- Siehst du, dass es 3 leere Stellen gibt, aus denen du wählen kannst?
- Für jeden leeren Platz stellt es sich alle möglichen zukünftigen Züge vor
- Wählt den Zug, der zu seinem besten Ergebnis führt
- In diesem Fall sollte er die untere mittlere Ecke auswählen, um deinen Sieg zu blockieren
Diese Art des Vorausdenkens hilft dem Computer, jedes Mal eine perfekte Partie Tic-Tac-Toe zu spielen!
Minimax-Algorithmus Pseudocode
Wir erklären dir Schritt für Schritt, wie du den Minimax-Algorithmus schreibst. Mach dir keine Sorgen, wenn du Pseudocode nicht kennst - betrachte es als eine Art, die Schritte in einfachem Englisch aufzuschreiben, bevor wir sie in echten Code umwandeln!
Schritt-für-Schritt-Erklärung
Die Minimax-Funktion braucht drei Dinge, um zu funktionieren:
- Der aktuelle Spielplan
- Die Tiefe (wie viele Züge voraus wir schauen)
- Ob der maximierende Spieler (Computer) oder der minimierende Spieler (Mensch) am Zug ist
So sieht der grundlegende Pseudocode aus:
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
Während sich die meisten Pseudocode-Beispiele auf Englisch lesen und vollkommen verständlich sind, ist das obige Beispiel anders, da es eine Rekursion verwendet. Rekursion ist, wenn eine Funktion sich selbst immer wieder aufruft, um ein größeres Problem zu lösen. Stell dir vor, du schaust in einen Spiegel, der einen anderen Spiegel reflektiert - du siehst das gleiche Bild viele Male wiederholt und jedes Mal kleiner.
In unserem Minimax-Algorithmus brauchen wir eine Rekursion, weil wir versuchen, alle möglichen zukünftigen Züge im Spiel zu betrachten. Jedes Mal, wenn die Funktion sich selbst aufruft, schaut sie sich den nächsten möglichen Zug an.
Das hilft uns, den besten Zug herauszufinden, indem wir alle möglichen Spielverläufe prüfen, wie ein wirklich kluger Spieler, der denkt: "Wenn ich dies tue, dann könnten sie das tun, dann könnte ich das tun..." und so weiter, bis das Spiel endet. Um mehr über Rekursion zu erfahren, kannst du unser separates Rekursionstutorial lesen.
Anschauliches Beispiel
Schauen wir uns an, wie das in einer einfachen Spielsituation funktioniert:
1. Startposition:
2. Der Computer denkt:
- "Wenn ich X an eine beliebige freie Stelle setze..."
- "Was würde der Mensch als Nächstes tun?"
- "Und was könnte ich danach tun?"
- "Welcher Zug bringt mir die beste Endnote?"
3. Für jede freie Stelle wird der Computer:
- Macht einen Zug
- Prüft, ob das Spiel vorbei ist
- Wenn nicht vorbei, stellt euch den besten Zug des Menschen vor
- Geht immer weiter, bis es ein Ende findet
- Wählt den Zug mit der höchsten Punktzahl
Stell dir das wie beim Schach vor - du denkst immer: "Wenn ich hier ziehe, werden sie dort ziehen, dann kann ich hier ziehen...", aber der Computer kann über ALLE möglichen Züge gleichzeitig nachdenken!
Das Tolle an diesem Algorithmus ist, dass er immer den bestmöglichen Zug findet, vorausgesetzt, beide Spieler spielen perfekt. Es ist, als hätte man eine Kristallkugel, die einem alle möglichen Zukünfte des Spiels zeigt!
Minimax für Tic-Tac-Toe Schritt für Schritt implementieren
In diesem Abschnitt bauen wir eine unschlagbare Tic-Tac-Toe-KI mit dem Mini-max-Algorithmus in reinem Python. Wir werden die Umsetzung in einfache Schritte unterteilen und die Intuition hinter jedem einzelnen Schritt erklären und wie er in das Gesamtbild des Spiels passt.
Schritt 1: Definieren einer TicTacToe-Klasse
Zuerst definieren wir eine Klasse, die alle notwendigen Logiken und Methoden enthält, die wir brauchen, um ein Tic-Tac-Toe-Spiel mit unseren Computern zu spielen:
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 == " "]
Die Methode __init__
initialisiert ein neues Spielbrett als eine Liste von 9 leeren Feldern (dargestellt durch die Felder " "), wobei die Indizes 0-8 die Brettpositionen von links nach rechts und von oben nach unten darstellen. Außerdem werden zwei Spielersymbole eingerichtet - "O" für den menschlichen Spieler und "X" für die KI.
Die Methode print_board
bietet eine Möglichkeit, den aktuellen Zustand des Boards zu visualisieren. Er druckt das 3x3-Gitter mit Trennlinien zwischen den Zeilen aus, die die Züge der einzelnen Spieler an ihren jeweiligen Positionen zeigen.
Die Methodeavailable_moves
liefert eine Liste aller gültigen Züge, die noch gemacht werden können. Dazu prüft sie, welche Positionen auf dem Spielbrett noch leer sind (ein Leerzeichen " " enthalten) und gibt ihre Indizes zurück. Dies ist wichtig, damit der Minimax-Algorithmus weiß, welche Züge er berücksichtigen kann.
Diese Methoden bilden die Grundlage, auf der wir aufbauen, um unseren KI-Spieler mit dem Minimax-Algorithmus zu erstellen.
Lass sie uns schnell testen:
>>> game = TicTacToe()
>>> game.print_board()
| |
---------
| |
---------
| |
>>> game.available_moves()
[0, 1, 2, 3, 4, 5, 6, 7, 8]
Wie erwartet, haben wir im Moment ein leeres Brett und alle Züge sind verfügbar.
Schritt 2: Implementierung von Methoden zur Durchführung eines Zuges und zur Überprüfung des Brettstatus
Jetzt fügen wir eine Methode hinzu, um einen Zug zu machen:
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
Wir haben die Methode make_move
hinzugefügt, die:
- Nimmt eine Position (0-8) und ein Spielersymbol ("X" oder "O") als Eingabe
- Prüft, ob die ausgewählte Position leer ist (" ")
- Wenn leer, platziert er das Symbol des Spielers und gibt True zurück.
- Wenn die Position bereits besetzt ist, wird False zurückgegeben, ohne dass eine Änderung vorgenommen wird.
Lass uns ein paar Züge machen und die restlichen Züge überprüfen:
>>> 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]
Gut arbeiten. Der nächste Schritt ist das Hinzufügen einer Methode zur Überprüfung, ob das Board voll ist:
class TicTacToe:
...
def is_board_full(self):
"""Check if the board is full"""
return " " not in self.board
is_board_full
ist eine boolesche Methode, die überprüft, ob es noch leere Felder auf dem Spielbrett gibt.
Als Nächstes fügen wir eine Methode hinzu, um zu prüfen, ob ein Gewinnzustand erreicht wurde:
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
Die Methode check_winner
wertet den aktuellen Zustand des Tic-Tac-Toe-Bretts aus, um festzustellen, ob es einen Gewinner gibt. Sie prüft alle möglichen Gewinnkombinationen:
1. Reihen (3 Möglichkeiten):
- Oberste Reihe (Indizes 0,1,2)
- Mittlere Reihe (Indizes 3,4,5)
- Untere Reihe (Indizes 6,7,8)
2. Spalten (3 Möglichkeiten):
- Linke Spalte (Indizes 0,3,6)
- Mittlere Spalte (Indizes 1,4,7)
- Rechte Spalte (Indizes 2,5,8)
3. Diagonalen (2 Möglichkeiten):
- Von oben links nach unten rechts (Indizes 0,4,8)
- Von oben rechts nach unten links (Indizes 2,4,6)
Bei jeder Kombination wird geprüft, ob alle drei Positionen das gleiche Spielersymbol (X oder O) enthalten und keine leeren Felder sind. Wenn eine Gewinnkombination gefunden wird, gibt sie das Symbol des Gewinners zurück. Wenn nach der Überprüfung aller Möglichkeiten kein Gewinner gefunden wird, wird None zurückgegeben.
Lass uns die Funktion in Gewinner- und Nicht-Gewinner-Staaten testen:
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
Schließlich fügen wir eine weitere boolesche Methode hinzu, um festzulegen, ob das Spiel vorbei ist oder nicht:
class TicTacToe:
...
def game_over(self):
"""Check if the game is over"""
return self.check_winner() is not None or self.is_board_full()
Die Methode gibt True zurück, wenn entweder der Gewinner gefunden wurde oder das Brett voll ist.
An diesem Punkt haben wir alle grundlegenden Spielmechanismen entwickelt:
- Das Brett wird als eine Liste von 9 Feldern dargestellt, die leer initialisiert werden
print_board()
zeigt den aktuellen Spielstatus visuell anavailable_moves()
gibt die Indizes der leeren Quadrate zurückmake_move()
platziert das Symbol eines Spielers auf dem Spielbrettcheck_winner()
prüft Zeilen, Spalten und Diagonalen auf einen Gewinn in jedem Zugis_board_full()
bestimmt, ob keine Züge übrig bleibengame_over()
Kombiniert Gewinnerprüfung und Volltafelprüfung
Diese Methoden bilden die Grundlage, um ein spielbares Spiel zu erstellen, indem sie alle grundlegenden Vorgänge wie das Ausführen von Zügen und die Bestimmung des Spielzustands behandeln.
Jetzt kommt der entscheidende Teil - dem Computer das "Gehirn" zu geben, um das Spiel mit Minimax zu spielen.
Schritt 3: Minimax für Tic-Tac-Toe implementieren
Nun wollen wir den Algorithmus für das Spiel in einer neuen Methode implementieren:
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
Die Funktion benötigt zwei Parameter:
depth
- Verfolgt, wie viele Ebenen wir in der Rekursion sind. Dies kann verwendet werden, um die Suchtiefe bei sehr komplexen Spielen zu begrenzen, aber für Tic-Tac-Toe brauchen wir das nicht.is_maximizing
- Ein boolesches Flag, das angibt, ob wir gerade nach der maximalen Punktzahl (KI-Zug) oder der minimalen Punktzahl (Menschenzug) suchen. Dies geschieht abwechselnd mit jedem rekursiven Aufruf, während die Spieler/innen sich abwechseln.
Im Hauptteil der Funktion beginnen wir mit der Definition der Basisfälle: Wenn das Spiel von der KI gewonnen wird (winner == ai_player
), geben wir 1 zurück, da dies das bestmögliche Ergebnis für die KI ist. Wenn der Mensch gewinnt (winner == human_player
), geben wir -1 zurück, da dies das schlechteste Ergebnis für die KI ist. Wenn das Spielbrett voll ist und es keinen Gewinner gibt, geben wir 0 für ein Unentschieden zurück.
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
Wenn is_maximizing
wahr ist, simulieren wir den Zug der KI und wollen den Zug finden, der zur höchstmöglichen Punktzahl führt. Wir beginnen damit, best_score auf negative Unendlichkeit zu setzen, damit jede echte Punktzahl besser ist. Dann werden wir für jeden verfügbaren Zug:
- Platziere das Symbol der KI vorübergehend auf dem Spielbrett
- Berechne rekursiv, was passieren würde, wenn wir diesen Zug machen würden, indem du Minimax mit
is_maximizing=False
aufrufst (da der Mensch als nächstes an der Reihe wäre) - Den temporären Zug rückgängig machen, um den Zustand des Brettes wiederherzustellen
- Behalte den Überblick über die höchste Punktzahl, die wir bisher erreicht haben, indem du
max()
So können wir jeden möglichen Zug der KI überprüfen. Bei jedem Zug schauen wir uns an, was als nächstes passieren könnte, bis jemand gewinnt oder das Spiel unentschieden ist. Dann arbeiten wir rückwärts, um herauszufinden, welcher erste Zug der KI die beste Chance auf den Sieg gibt.
Jetzt wollen wir den menschlichen Teil minimieren:
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
Wenn is_maximizing
falsch ist, simulieren wir den Zug des menschlichen Spielers und wollen den Zug finden, der zu einer möglichst niedrigen Punktzahl führt (denn eine hohe Punktzahl bedeutet, dass die KI gewinnt). Wir beginnen mit best_score
als positiver Unendlichkeit, so dass jede reale Punktzahl niedriger sein wird. Für jeden verfügbaren Spielzug, wir:
- Platziere das Symbol des Menschen vorübergehend auf der Tafel
- Berechne rekursiv, was passieren würde, wenn du Minimax mit
is_maximizing=True
aufrufst (da die KI als nächstes an der Reihe wäre). - Den temporären Zug rückgängig machen, um den Zustand des Brettes wiederherzustellen
- Verfolge die niedrigste Punktzahl, die wir mit
min()
Dies simuliert, dass der menschliche Spieler versucht, die besten Züge zu machen, um zu verhindern, dass die KI gewinnt. Der Mensch möchte die Punktzahl so gering wie möglich halten, da positive Punktzahlen Siege der KI bedeuten. Durch den Wechsel zwischen maximierenden und minimierenden Zügen kann der Algorithmus die optimale Zugfolge für beide Spieler bestimmen.
Schritt 4: Mit Minimax den besten Zug für KI finden
Jetzt, da wir den Algorithmus fertig haben, brauchen wir eine weitere Methode, die die minimax
Methode verwendet, um den besten Zug für die KI nach jedem menschlichen Zug zu bestimmen:
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
Die Methode get_best_move ist dafür zuständig, den optimalen Zug für den KI-Spieler mithilfe des Minimax-Algorithmus zu bestimmen. Das funktioniert so:
1. Beginnend mit negativer Unendlichkeit als bester Punktzahl und keinem ausgewählten Zug
2. Für jeden verfügbaren Zug auf dem Spielbrett:
- Vorübergehende Platzierung des KI-Symbols an dieser Position
- Mit Minimax bewerten, wie gut dieser Zug ist, indem du den Rest des Spiels simulierst
- Rückgängigmachen des vorübergehenden Umzugs
- Wenn dieser Zug zu einer besseren Punktzahl führt als das, was wir zuvor gesehen haben, aktualisieren wir sowohl die beste Punktzahl als auch den besten Zug
3. Zum Schluss den Zug zurückgeben, der zur höchsten Punktzahl geführt hat
Dieser Ansatz stellt sicher, dass die KI den Zug wählt, der ihr die besten Gewinnchancen bietet, vorausgesetzt, der menschliche Spieler spielt auch optimal. Die Methode berücksichtigt alle möglichen zukünftigen Spielzustände und wählt den Weg, der die Chancen der KI maximiert und die Gewinnchancen des Menschen minimiert.
Testen wir es an einem Beispielspielstand:
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
Wie du sehen kannst, hat die KI die Gewinnkombination anhand meiner Züge gefunden (es war ein Dummy-Zustand, aber das beweist, dass unser Algorithmus funktioniert).
Schritt 5: Eine Spielschleife implementieren
Nachdem wir nun unseren Minimax-Algorithmus implementiert und getestet haben, wollen wir eine Spielschleife erstellen, mit der wir gegen die KI spielen können.
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")
Die play_game-Methode beginnt damit, dass eine Willkommensnachricht und Anweisungen für den Spieler angezeigt werden. Es zeigt, dass der menschliche Spieler das "O" und die KI das "X" benutzt. Es druckt dann ein nummeriertes Raster (0-8) aus, um dem Spieler zu zeigen, welche Zahl welcher Position auf dem Spielbrett entspricht. So wissen die Spieler/innen genau, welche Zahl sie für ihren gewünschten Zug eingeben müssen.
# ... 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
Nachdem die ersten Anweisungen angezeigt wurden, beginnt das Spiel mit seiner Hauptschleife. Das Spiel entscheidet nach dem Zufallsprinzip, wer den Anfang macht - entweder die KI oder der menschliche Spieler - mit random.choice([True, False])
. Das schafft ein Element der Fairness und Unvorhersehbarkeit zu Beginn jedes Spiels.
Die Hauptspielschleife wird fortgesetzt, bis game_over()
True zurückgibt (entweder hat jemand gewonnen oder das Brett ist voll). Während jeder Runde wird der aktuelle Zustand des Spielbretts mit print_board()
angezeigt.
Wenn die KI am Zug ist (ai_turn
ist True), wird das Programm:
- Druckt eine Nachricht, die anzeigt, dass die KI denkt
- Ruft
get_best_move()
auf, um den optimalen Zug mit dem Minimax-Algorithmus zu bestimmen - Führt den Zug aus, indem er das KI-Symbol ("X") an der gewählten Position platziert
Wenn der Mensch an der Reihe ist (ai_turn
ist falsch), wird das Programm:
1. Startet eine Schleife, um gültige Eingaben vom Spieler zu erhalten2. Fordert zur Eingabe einer Zugnummer zwischen 0-8 auf3. Überprüft die Eingabe ist:
- Eine gültige Ganzzahl (mit try/except)
- Innerhalb des gültigen Bereichs 0-8
- Zeigt auf eine leere Position auf dem Spielbrett
4. Fragt so lange, bis eine gültige Eingabe eingegangen ist. Führt den Zug aus, indem er das Spielersymbol ("O") an der gewählten Position platziert
Nach jeder Runde wird ai_turn
mit not
umgedreht, um zwischen den Spielern zu wechseln. So entsteht das Hin und Her des Spiels, bei dem jeder Spieler abwechselnd spielt, bis jemand gewinnt oder das Spiel unentschieden endet.
Die Eingabevalidierung stellt sicher, dass das Spiel nicht durch ungültige Benutzereingaben abstürzt und gibt hilfreiche Fehlermeldungen aus, um den Spieler zur Eingabe der richtigen Züge anzuleiten. So entsteht ein robustes und benutzerfreundliches Spielerlebnis.
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!")
Wenn das Spiel endet, wird der endgültige Zustand des Brettes mit print_board()
angezeigt und der Gewinner wird mit check_winner()
ermittelt. Das Spiel kann auf drei Arten enden:
- KI gewinnt - Wenn
check_winner()
das KI-Symbol ("X") zurückgibt, zeigt dies an, dass die KI eine Gewinnlinie erreicht hat. - Der Mensch gewinnt - Wenn
check_winner()
das Symbol des Menschen ("O") zurückgibt, bedeutet das, dass der Spieler eine Gewinnlinie erzielt hat. - Unentschieden - Wenn keiner der beiden Spieler gewonnen hat, das Brett aber voll ist, also keine weiteren Züge möglich sind
Die entsprechende Meldung wird angezeigt, um das Spielergebnis zu verkünden. So erhält der Spieler/die Spielerin eine klare Rückmeldung darüber, wie das Spiel endete.
Schritt 6: Alles zusammenfügen
Jetzt ist es an der Zeit, den gesamten Code, den wir bisher geschrieben haben, in ein Python-Skript mit folgendem Inhalt zu packen if/main Klausel ganz am Ende:
# Start the game
if __name__ == "__main__":
game = TicTacToe()
game.play_game()
So kann das Spiel starten, sobald du das Skript mit python script.py ausführst. Wenn du dich zwischen all den Erklärungen und Codeblöcken verlaufen hast, findest du den vollständigen Code für das Spiel in diesem GitHub-Gist.
Hier ist ein Beispielspiel, das ich gespielt habe:
❯ 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!
Denk daran, dass Tic-Tac-Toe ein einfaches Spiel ist und es keine Chance gibt, die KI zu schlagen. Entweder es gibt ein Unentschieden oder du verlierst!
Formalisierung des Mini-Max-Algorithmus
Jetzt wollen wir die allgemeine Definition von Algorithmus über das einfache Tic-Tac-Toe-Beispiel hinaus betrachten.
Der Minimax-Algorithmus kann formal als eine rekursive Funktion definiert werden, die Positionen in einem Nullsummenspiel auswertet. Schauen wir uns seine formalen Bestandteile und Eigenschaften an.
Mathematische Definition
Für einen Spielzustand s
ist der Minimax-Wert V(s)
definiert 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
Wo:
- s' repräsentiert Nachfolgezustände von s
- S ist die Menge aller legalen Züge vom Zustand s
- Nutzen(s) ist die Bewertungsfunktion für Endzustände
Wichtige Eigenschaften
1. Perfekte Informationen
- Alle Spieler haben vollständige Kenntnis über den Spielstand
- Keine versteckten Informationen oder Zufallselemente
- Deterministische Ergebnisse
2. Nullsummenspiel
- Der Gewinn des einen Spielers entspricht genau dem Verlust des anderen Spielers
- Die Summe der Nutzwerte für alle Spieler ist immer null
- Bei Spielen mit zwei Spielern sind die Nützlichkeiten typischerweise {-1, 0, 1}
3. Optimales Spiel
- Angenommen, beide Spieler treffen optimale Entscheidungen
- Garantiert das bestmögliche Ergebnis bei perfektem Spiel
- Führt zu einem Nash-Gleichgewicht im Sinne der Spieltheorie
Komplexitätsanalyse
Zeitliche Komplexität: O(b^m)
- b = Verzweigungsfaktor (Anzahl der erlaubten Züge in jedem Zustand)
- m = maximale Tiefe des Spielbaums
Raumkomplexität: O(bm)
- Erfordert die Speicherung des Spielstatus auf jeder Ebene
- Kann mit iterativer Vertiefung optimiert werden
Bewertungsfunktion
Für nicht-terminale Zustände sollte die Bewertungsfunktion f(s):
- Korrelieren mit der Gewinnwahrscheinlichkeit
- rechnerisch effizient sein
- Konsistente Skalierung im gesamten Spiel beibehalten
Die formale Definition:
f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ
Wo:
- wᵢ sind Gewichte für verschiedene Merkmale
- xᵢ sind Merkmalswerte aus dem Spielzustand
- n ist die Anzahl der zu bewertenden Merkmale
Optimalitätsgarantie
Der Minimax-Algorithmus garantiert unter diesen Bedingungen ein optimales Spiel:
- Perfekte Informationen
- Deterministische Ergebnisse
- Vollständige Suche nach Endzuständen
- Genaue Bewertung des Endzustands
Das macht es besonders geeignet für Spiele wie Schach, Tic-Tac-Toe und Dame, bei denen diese Bedingungen erfüllt sind.
Erweiterte Variationen und Beschränkungen
Während Minimax für einfache Spiele wie Tic-Tac-Toe gut geeignet ist, hat es bei größeren Spielen einige Probleme. Schauen wir uns an, wie wir es besser machen können und wo es hapert.
Minimax schneller machen: Alpha-Beta-Beschneidung
Stell dir vor, du spielst Schach und denkst über deine Züge nach. Wenn du einen Gewinnzug gefunden hast, brauchst du nicht alle anderen möglichen Züge zu prüfen, richtig? Alpha-Beta Pruning funktioniert auf die gleiche Weise - es hilft dem Computer, Züge zu überspringen, von denen wir bereits wissen, dass sie nicht besser sind als die, die wir gefunden haben.
Stell dir das folgendermaßen vor:
- Du bist auf der Suche nach dem billigsten Schokoriegel
- Du hast $1 zum Ausgeben
- Wenn du einen Schokoriegel für 50¢ findest, kannst du dir alle Schokoriegel, die mehr als 1 $ kosten, sparen.
- So sparst du Zeit!
Tiefenbegrenzungen: Nicht zu weit vorausschauen
In großen Spielen wie Schach gibt es zu viele mögliche Züge, um sie alle zu prüfen. Wir fügen also eine Tiefenbegrenzung hinzu:
- Schaue nur 4-5 Züge voraus, statt bis zum Ende
- Schätze ein, wie gut die Position zu diesem Zeitpunkt ist
- Wähle den besten Zug basierend auf diesen Vermutungen
Du kannst nicht jeden Zug bis zum Ende des Spiels planen, aber du kannst ein paar Züge vorausplanen!
Wo Minimax zu kämpfen hat
Minimax ist nicht perfekt. Hier sind seine Hauptprobleme:
1. Zu viele Auswahlmöglichkeiten
- Spiele wie Go haben viel zu viele mögliche Züge
- Selbst schnelle Computer können sie nicht alle prüfen
- Deshalb brauchen wir für wirklich komplexe Spiele andere Methoden
2. Zeitprobleme
- Je mehr Züge du vorausschaust, desto länger dauert es
- Beim Schach können Computer nicht jeden möglichen Zug berücksichtigen.
- Sie müssen sich gut überlegen, welche Züge sie überprüfen wollen
3. Nicht gut für unsichere Spiele
- Minimax funktioniert am besten, wenn du alles sehen kannst
- Es ist nicht gut für Kartenspiele, bei denen du nicht weißt, welche Karten die anderen haben
- Es kann nicht gut mit zufälligen Ereignissen umgehen (wie Würfelwürfe)
Moderne Lösungen
Die heutige Spiel-KI kombiniert Minimax oft mit anderen coolen Techniken:
1. Maschinelles Lernen
- Computer können lernen, indem sie viele Spiele anschauen
- Das hilft ihnen, gute Spielzüge besser zu erraten
- Spiele wie
AlphaGo
nutzen dies, um menschliche Champions zu schlagen
2. Mustererkennung
- Anstatt jede Bewegung zu überprüfen, suche nach Mustern
- Genau wie menschliche Spieler gute Spielzüge erkennen
- Das macht den Computer viel schneller
3. Speicherbank
- Erinnere dich an Positionen, die du schon einmal gesehen hast
- Verschwende keine Zeit damit, dieselbe Sache zweimal zu berechnen
- Als hätte man einen Spickzettel mit guten Moves!
Das Coolste daran? Dank dieser Verbesserungen können Computer Spiele fast genauso gut spielen wie Menschen - und manchmal sogar besser! Aber vergiss nicht, dass Minimax auch mit all diesen ausgefallenen Ergänzungen immer noch die Grundlage ist, auf der alles funktioniert.
Fazit
In diesem Tutorium haben wir den Minimax-Algorithmus von seinen grundlegenden Konzepten bis hin zur praktischen Umsetzung erforscht. Hier ist, was wir gelernt haben:
1. Kernkonzepte
- Wie Minimax Computern hilft, Entscheidungen in Spielen zu treffen
- Der Unterschied zwischen minimierenden und maximierenden Spielern
- Warum es "Minimax" genannt wird und wie es funktioniert
2. Fähigkeiten zur Umsetzung
- Ein Tic-Tac-Toe-Spiel von Grund auf bauen
- Den Minimax-Algorithmus in Python schreiben
- Testen und Debuggen der Spiellogik
3. Fortgeschrittene Themen
- Den Algorithmus mit Alpha-Beta Pruning schneller machen
- Umgang mit Einschränkungen in komplexen Spielen
- Moderne Verbesserungen durch maschinelles Lernen
Was kommt als Nächstes?
Der Minimax-Algorithmus ist nur ein Teil des KI-Puzzles. Wenn du mehr über KI und Algorithmen erfahren möchtest, findest du hier einige gute Ressourcen, um deine Reise fortzusetzen:
1. Verwandte Algorithmen
- A* Algorithmus Tutorial- Lerne über Pfadfindungsalgorithmen
- Leitfaden für Gradient Boosting- Algorithmen für maschinelles Lernen erkunden
2. Anwendungen des maschinellen Lernens
- Anwendungsfälle für maschinelles Lernen- Anwendungen aus der Praxis sehen
3. Vollständige Lernpfade
- Entwicklung von KI-Anwendungen- Baue praktische KI-Projekte
- KI-Grundlagen- Beherrsche die Grundlagen der KI
Egal, ob du ein einfaches Spiel oder ein komplexes KI-System entwickelst, das Verständnis von Algorithmen wie Minimax bietet dir eine solide Grundlage für fortgeschrittenere Themen der künstlichen Intelligenz. Übe weiter, lerne weiter und, was am wichtigsten ist, programmiere weiter!
Minimax Algorithmus FAQs
Wie schwierig ist es, den Minimax-Algorithmus zu verstehen und umzusetzen?
Der Minimax-Algorithmus ist relativ einfach zu verstehen, besonders wenn er für einfache Spiele wie Tic-Tac-Toe eingesetzt wird. Auch wenn das Konzept der Rekursion für Anfänger eine Herausforderung sein mag, ist das Grundprinzip, zwischen maximierenden und minimierenden Zügen abzuwechseln, intuitiv. In diesem Tutorial wird die Implementierung in überschaubare Schritte unterteilt, sodass sie auch für Programmierer mit grundlegenden Python-Kenntnissen zugänglich ist.
Kann ich diesen Algorithmus auch für andere Spiele als Tic-Tac-Toe verwenden?
Ja, der Minimax-Algorithmus kann für viele Nullsummenspiele für zwei Spieler mit perfekter Information angepasst werden, z. B. Schach, Dame oder Vier-Gewinnt. Für komplexere Spiele musst du jedoch zusätzliche Optimierungen wie Alpha-Beta-Beschneidung und Tiefenbegrenzung implementieren, da die Anzahl der möglichen Züge exponentiell ansteigt.
Wie schafft es die KI, bei Tic-Tac-Toe nie zu verlieren?
Der Minimax-Algorithmus simuliert alle möglichen zukünftigen Spielzustände und wählt Züge, die zum bestmöglichen Ergebnis führen. Bei einem einfachen Spiel wie Tic-Tac-Toe gibt es relativ wenige mögliche Züge, so dass die KI in jeder Situation den optimalen Zug berechnen kann. Da Tic-Tac-Toe ein "gelöstes Spiel" ist, führt das perfekte Spiel beider Seiten immer zu einem Unentschieden, weshalb die KI nie verlieren kann.
Welche Vorkenntnisse brauche ich, um diesem Tutorial zu folgen?
Du solltest über grundlegende Python-Programmierkenntnisse verfügen:
Verstehen von Funktionen und Klassen
Vertrautheit mit Listen und grundlegenden Datenstrukturen
Grundlegender Kontrollfluss (if-Anweisungen, Schleifen)
Kenntnisse über Rekursion sind hilfreich, aber nicht erforderlich, da das Konzept im Tutorial erklärt wird.
Warum ist dieser Algorithmus wichtig für die KI-Entwicklung?
Der Minimax-Algorithmus ist grundlegend für das Verständnis der Spieltheorie und der Entscheidungsfindung in der KI. Es werden wichtige Konzepte wie rekursive Baumsuche, kontradiktorisches Denken und optimale Entscheidungsfindung unter perfekten Informationen vorgestellt. Diese Prinzipien bilden die Grundlage für fortschrittlichere KI-Algorithmen, die in modernen Anwendungen eingesetzt werden, von Spielen bis hin zu strategischer Planung und Entscheidungsunterstützungssystemen.

Ich bin ein Data Science Content Creator mit über 2 Jahren Erfahrung und einem der größten Follower auf Medium. Ich schreibe gerne ausführliche Artikel über KI und ML mit einem etwas sarkastischen Stil, denn man muss etwas tun, damit sie nicht so langweilig sind. Ich habe mehr als 130 Artikel verfasst und einen DataCamp-Kurs gemacht, ein weiterer ist in Vorbereitung. Meine Inhalte wurden von über 5 Millionen Augenpaaren gesehen, von denen 20.000 zu Followern auf Medium und LinkedIn wurden.
Top KI-Kurse
Kurs
Explainable Artificial Intelligence (XAI) Concepts
Kurs
Distributed AI Model Training in Python
Der Blog
Top 30 Generative KI Interview Fragen und Antworten für 2024

Hesam Sheikh Hassani
15 Min.
Der Blog
Die 32 besten AWS-Interview-Fragen und Antworten für 2024

Der Blog
Lehrer/innen und Schüler/innen erhalten das Premium DataCamp kostenlos für ihre gesamte akademische Laufbahn
Der Blog
Q2 2023 DataCamp Donates Digest
Der Blog
Die 20 besten Snowflake-Interview-Fragen für alle Niveaus

Nisha Arya Ahmed
20 Min.
Der Blog