Modifica lo pseudo codice di ridimensionamento da Minimax a Alpha-Beta: algoritmo, intelligenza artificiale, pseudocodice, scacchi, minimax

Sto imparando lo pseudo-codice Alpha-Beta e voglio scrivere un codice pseudo più semplice Potatura Alpha Beta.

Ho scritto lo pseudo codice per Minimax:

function minimax(node, depth)
if node is a terminal node or depth ==0
return the heuristic value of node
else
best = -99999
for child in node
best = max(best, -minimax(child, depth-1))
return best

Tuttavia, non so come modificarlo in potatura alfa-beta. Qualcuno può aiutarti?

risposte:

In Alpha-Beta, tieni traccia dei tuoi garantitipunteggio per una posizione. Puoi fermarti immediatamente se trovi una mossa che è migliore del punteggio che l'avversario ha già garantito nella sua posizione precedente (una mossa prima).

Tecnicamente, ogni squadra tiene traccia del suo punteggio inferiore (alfa) e si ha accesso al punteggio più basso dell'avversario (beta).

Il seguente pseudo-codice non è testato, ma ecco l'idea:

function alphabeta(node, depth, alpha, beta)
if node is a terminal node or depth ==0
return the heuristic value of node
else
best = -99999
for child in node
best = max(best, -alphabeta(child, depth-1, -beta, -alpha))
if best >= beta
return best
if best > alpha
alpha = best
return best

All'inizio della ricerca, puoi impostare alpha su -INFINITY e beta su + INFINITY. A rigor di termini, l'algoritmo di sketch non è alfa-beta ma negamax. Entrambi sono identici, quindi questo è solo un dettaglio di implementazione.

Nota che in Alpha-Beta, l'ordine di movimento è fondamentale. Se la maggior parte delle volte, inizi con la mossa migliore, o almeno una mossa molto buona, dovresti vedere un enorme miglioramento rispetto a Minimax.

Un'ottimizzazione aggiuntiva per iniziare con finestre alfa beta riservate (non -INFINITY e + INFINITY). Tuttavia, se la tua ipotesi si rivela sbagliata, devi riavviare la ricerca con una più aperta finestra di ricerca.