Ricerca e IA per i giochi: A* e minimax in Python

Il concetto in parole semplici

L'IA classica risolve i problemi cercando tra gli stati possibili. A* trova il percorso più economico sommando il costo già percorso a una stima del costo restante, e minimax sceglie le mosse nei giochi a due giocatori supponendo che l'avversario giochi bene.

Trova il percorso più breve su una griglia con la ricerca A* e scegli la mossa migliore in un gioco con minimax.

Idee chiave

A* trova il percorso migliore quando la stima (euristica) non sovrastima mai il costo reale.
Minimax esplora l'albero di gioco fino a una profondità fissa o fino alla fine della partita.
La potatura alfa-beta salta i rami che non possono cambiare la decisione.
Gli algoritmi genetici cercano in modo diverso: fanno evolvere una popolazione di soluzioni candidate.

Quando si usa?

Capire cosa succede dentro le reti neurali e le librerie di IA.
Imparare l'idea prima di implementarla nelle sfide corrispondenti.
Prepararti a corsi di machine learning, colloqui e progetti.

Guardalo in azione

Premi Avvia per guardare A* esplorare la griglia; fai clic sulle celle per aggiungere o togliere muri. Nell'albero di gioco, fai clic su una foglia per cambiarne il punteggio.

Codice di esempio

Esegui codice →

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

Output previsto

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

Come funziona

La coda di priorità espande sempre la cella con costo + stima minimo, dove la stima è la distanza di Manhattan dall'obiettivo, quindi A* raggiunge G in 5 passi aggirando i muri. minimax() prende il massimo nel nostro turno e il minimo in quello dell'avversario; la prima mossa garantisce 3, il migliore dei tre casi peggiori.

Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.

Esercizi pratici

Modifica gli input e verifica i casi limite prima di usare dataset più grandi.

Cambia gli input o i pesi e prevedi l'output prima di eseguire.
Stampa i valori intermedi per seguire ogni passo del calcolo.
Risolvi le sfide collegate qui sotto per implementare l'idea da solo.

Esegui nell’IDE Python →

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide