Comment fonctionne l'algorithme NegaScout?

Concernant l'élagage Alpha-Beta, NegaScout affirme qu'il peut accélérer le processus en définissant [Alpha, Beta] sur [Alpha, Alpha-1].

Je ne comprends pas tout le processus de NegaScout.

Comment ça marche? Quel est son mécanisme de récupération lorsque sa supposition a échoué?

Désolé pour la réponse tardive ( 4 ans !)

NegaScout est un algorithme très simple. Pour comprendre, nous devons réviser l' approfondissement itératif .

L'approfondissement itératif est une technique utilisée par un moteur d'échecs pour rechercher la profondeur i, puis i + 1, puis i + 2, etc. Ceci est un exemple de programmation dynamique. À chaque itération, nous avons notre meilleure estimation de ce que serait le meilleur coup. La plupart des moteurs d'échecs garderaient ce mouvement dans une table de hachage.

Imaginez que nous sommes maintenant à l'itération i + 1, et nous avons le meilleur coup de la dernière itération i. Maintenant, nous avons 5 nœuds à rechercher, devons-nous faire?

Si nous supposons que nous avons fait un travail raisonnablement bon lors de notre dernière itération, le meilleur mouvement de la dernière itération (que nous obtenons de la table de hachage) devrait également être le meilleur mouvement pour l'itération en cours.

Si notre hypothèse est correcte, nous devrions pouvoir gagner du temps en recherchant chaque mouvement autre que le meilleur mouvement (les quatre mouvements ne figurant pas dans la table de hachage) avec a null window. Une fenêtre nulle est quelque chose comme:

score := -pvs(child, depth-1, -α-1, -α, -color)

Remarque -α-1et -α. Ce sont les valeurs alpha et bêta que nous donnerons à la prochaine récursivité. Comme la largeur de la fenêtre n'est que de 1, la recherche échouera toujours:

• S'il échoue en dessous de α, le mouvement est pire que ce que nous avons déjà, nous pouvons donc l'ignorer
• S'il échoue au-dessus de β, le coup est trop bon pour être joué, on peut donc l'ignorer
• Sinon, nous devons faire une nouvelle recherche correctement

Bien sûr, nous rechercherons toujours le meilleur coup (celui que nous obtenons de la table de hachage) avec une fenêtre alpha et bêta appropriée. Nous devons le faire parce que nous devons connaître exactement la valeur du nœud, nous ne pouvons pas simplement l'ignorer.

Tout ce que j'ai dit est implémenté dans le pseudocode suivant. Le pseudocode spécifie child is not first childmais c'est un moyen de vérifier si le mouvement est également le meilleur mouvement de l'itération précédente. La table de hachage est l'implémentation la plus courante.

# Negasort is also termed Principal Variation Search - hence - pvs

function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α < score < β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # beta cut-off
        if α >= β
            break

    return α