Negascout

Negascout és una variant de l'algoritme Minimax, és un algoritme que combina la relació matemàtica del Negamax i l'us de finestra nula.

També cridat "busca de la variant principal" este algoritme pot oferir rendiments inclús majors a la poda alfa-beta si els nodos es troben correctament ordenats.

De la mateixa manera que alfa-beta, negascout és un algoritme de busca direccional per a calcular el valor minimax d'un nodo en un arbre. La millora de l'algoritme negascout sobre l'algoritme alfa-beta és que el primer no examinarà un nodo que el segon podaria.

Este algoritme és útil sempre i quan els nodos estiguen ben ordenats ya que supon que el primer nodo explorat serà el millor, aixina podrà confirmar-ho en atres nodos usant la finestra nula. En cas de fallo, com el primer nodo no era el de màxim nivell, se seguirà buscant el millor nodo en l'arbre de la mateixa manera que en l'algoritme alfa-beta.

pseudocodigo:

int negascout(nodo, profunditat, α, β) {
    if (esTerminal(nodo) || profunditat==0)
        return valorHeuristico(nodo);
    b = β;  // la finestra inicial és (-β, -α)
    foreach nodoHijo
        a = -negascout (fill, profunditat-1, -b, -α);
        if (a>α) α = a;
        if (α>=β)
            return α; //Talle Beta
        if (α>=b)  //comprova si falle la finestra nula
           α = -negascout(fill, profunditat-1, -β, -α);  //Nova busca completa
           if (α>=β)
               return α; //Talle Beta    
        b = α+1; //Crea nuava finestra nula             
    return α;
}