Negascout

Il NegaScout o Ricerca a variazione principale è un algoritmo negamax che in alcuni casi può essere più veloce della potatura alfa-beta. Come quest'ultima, il Negascout è un algoritmo per la ricerca del nodo di valore minimo in un dato albero; è dominante sull'algoritmo alfa-beta, cioè non visiterà mai un nodo che l'alfa-beta avrebbe potato, però questa caratteristica esige un accurato ordinamento dell'albero da esaminare per essere vantaggiosa, per cui la sua adozione deve essere decisa valutando la struttura del programma e le caratteristiche del problema da affrontare.

Il NegaScout è stato inventato da Alexander Reinefeld alcuni decenni dopo l'invenzione della potatura alfa-beta; dimostrò la correttezza di questo algoritmo nel suo libro, citato sotto nei riferimenti.

Funzionamento

L'algoritmo NegaScout è essenzialmente un miglioramento della normale potatura alfa-beta: esso assume che il nodo attualmente esaminato sia già il migliore, cioè che sia contenuto nella variazione principale, dopodiché procede a verificare se questo assunto è vero esplorando gli altri nodi dell'albero con la cosiddetta finestra di esplorazione (una finestra nulla, con alfa e beta uguali fra loro, ciò che accelera notevolmente la ricerca). Se l'assunto si rivela erroneo, la ricerca continua come una normale ricerca alfa-beta. Quindi NegaScout darà prestazioni tanto migliori quanto più spesso il suo assunto di partenza risulterà vero, come nel caso di un albero già almeno parzialmente ordinato; viceversa se l'albero sarà disordinato il vantaggio di ricerca svanirà, perché anche se visiterà meno nodi, dovrà visitare molti di questi più volte.

Nei motori di scacchi per computer, l'adozione dell'algoritmo NegaScout porta un incremento medio delle prestazioni di circa il 10% grazie al fatto che la ricerca procede per raffinazioni successive e che quindi l'albero delle mosse possibili è, tranne che in apertura di partita, sempre parzialmente ordinato.

Alternative

Un altro algoritmo di ricerca, l'MTD(f), è teoricamente superiore al NegaScout, tuttavia il suo utilizzo pone alcuni problemi pratici (in particolare usa moltissimo la tabella di trasposizione), per cui i programmi di scacchi continuano a usare algoritmi NegaScout.

Pseudocodice

funzione negascout(nodo, profondità, α, β)
    se (nodo è un nodo terminale) o (profondità = 0)
        restituisci (valore euristico del nodo)
    b := β
    per ogni figlio del nodo
        v := -negascout(figlio, profondità-1, -b, -α)
        se (α < v < β) e (non è il primo figlio)
            v := -negascout(figlio, profondità-1, -β, -v)   (* cerca ancora *)
        α := max(α, v)
        if α ≥ β
            restituisci α                                   (* pota *)
        b := α + 1                                          (* imposta una nuova finestra nulla *)
    restituisci α

Bibliografia

• A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), ISBN 3540507426
• Explanation of PVS/NegaScout, su brucemo.com.

Voci correlate

• Minimax
• Negamax
• Teoria dei giochi
• Scacchi