Negascout

Da Wikipedia, l'enciclopedia libera.

Il NegaScout o Ricerca a variazione principale è un algoritmo minimax 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 alcune decadi dopo l'invenzione della potatura alfa-beta; dimostrò la correttezza di questo algoritmo nel suo libro, citato sotto nei riferimenti.

Funzionamento[modifica | modifica wikitesto]

L'algoritmo NegaScout è essenzialmente un miglioramento della normale potatura alfa-beta (vedi): esso assume che il nodo attualmente esaminato sia già il migliore, cioè che sia contenuto nella variazione principale, dopodiché procede a verificare se questa assunzione è vera esplorando gli altri nodi dell'albero con la cosiddetta finestra di esplorazione (una finestra nulla, con alfa e beta uguali fra loro, il che accelera molto la ricerca). Se l'assunzione si rivela sbagliata, la ricerca continua come una normale ricerca alfa-beta. Quindi NegaScout darà prestazioni tanto migliori quanto più spesso la sua assunzione di partenza risulterà vera, 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]