Suche und Spiele-KI: A* und Minimax in Python

Das Konzept in einfachen Worten

Klassische KI löst Probleme, indem sie mögliche Zustände durchsucht. A* findet den günstigsten Weg, indem es die bisherigen Kosten und eine Schätzung der Restkosten addiert, und Minimax wählt Züge in Zwei-Personen-Spielen unter der Annahme, dass der Gegner gut spielt.

Finde mit der A*-Suche den kürzesten Weg auf einem Gitter und wähle mit Minimax den besten Zug in einem Spiel.

Die wichtigsten Ideen

A* findet den besten Weg, wenn die Schätzung (Heuristik) die echten Kosten nie überschätzt.
Minimax durchsucht den Spielbaum bis zu einer festen Tiefe oder bis zum Spielende.
Alpha-Beta-Pruning überspringt Zweige, die die Entscheidung nicht ändern können.
Genetische Algorithmen suchen anders: Sie entwickeln eine Population von Kandidatenlösungen weiter.

Wann wird dieser Ansatz verwendet?

Verstehen, was in neuronalen Netzen und KI-Bibliotheken passiert.
Die Idee lernen, bevor du sie in den passenden Challenges umsetzt.
Dich auf Kurse zu maschinellem Lernen, Vorstellungsgespräche und Projekte vorbereiten.

Selbst ausprobieren

Klicke auf Start, um A* beim Erkunden des Gitters zuzusehen; klicke auf Felder, um Wände zu setzen oder zu entfernen. Im Spielbaum änderst du per Klick auf ein Blatt dessen Wert.

Beispielcode

Code ausführen →

main.py

import heapq

# A* finds the cheapest path using cost so far + a guess of the cost left.
grid = ["S..#",
        ".#..",
        "...G"]
start, goal = (0, 0), (2, 3)
guess = lambda r, c: abs(r - goal[0]) + abs(c - goal[1])   # Manhattan distance

frontier = [(guess(*start), 0, start, [start])]
seen = set()
while frontier:
    _, cost, (r, c), path = heapq.heappop(frontier)
    if (r, c) == goal:
        print("path:", path, "cost:", cost)
        break
    if (r, c) in seen:
        continue
    seen.add((r, c))
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 4 and grid[nr][nc] != "#":
            heapq.heappush(frontier, (cost + 1 + guess(nr, nc), cost + 1, (nr, nc), path + [(nr, nc)]))

# Minimax: the maximizer assumes the opponent always picks the worst for it.
def minimax(node, maximizing):
    if isinstance(node, int):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

tree = [[3, 5], [2, 9], [0, 7]]   # our move, then the opponent's reply
print("best guaranteed score:", minimax(tree, True))

Erwartete Ausgabe

path: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] cost: 5
best guaranteed score: 3

So funktioniert es

Die Prioritätswarteschlange erweitert immer das Feld mit den kleinsten Kosten + Schätzung, wobei die Schätzung die Manhattan-Distanz zum Ziel ist; so erreicht A* das G in 5 Schritten um die Wände herum. minimax() nimmt in unserem Zug das Maximum und im Zug des Gegners das Minimum; der erste Zug garantiert 3, das Beste der drei schlechtesten Fälle.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungsaufgaben

Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.

Ändere Eingaben oder Gewichte und sage die Ausgabe vor dem Ausführen voraus.
Gib die Zwischenwerte aus, um jeden Rechenschritt zu verfolgen.
Löse die verlinkten Challenges unten, um die Idee selbst umzusetzen.

In der Python-IDE ausführen →

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges