Le mtd(f) : un algorithme multipasses

Une autre approche est possible ! En effet, puisque l'exploration de l'arbre avec une fenêtre nulle est si rapide, pourquoi ne pas faire la totalité de la recherche avec cette méthode ? Bien sûr, plusieurs recherches consécutives seront nécessaires pour trouver la valeur minimax de la racine, mais on espère gagner du temps au total.

Plusieurs algorithmes se sont développés autour de cette idée et le mtd(f) semble le meilleur.


l'algorithme Memory Test Driver (MTD(f))

int MTDF(depth, init_g)
{
int g = init_g , bêta;
int upperbound = +INFINITY;
int lowerbound = -INFINITY;
do {
if (g == lowerbound)
bêta = g + 1 ;
else
bêta = g;
g = AlphaBêtaWithMemory(depth, bêta - 1, bêta);
if (g < bêta)
upperbound = g
else
lowerbound = g;
}
while (lowerbound != upperbound);
return g ;
}



Plus la valeur init_g sera proche de la valeur minimax plus la recherche sera rapide. En générale, sans idée de la valeur minimax, init_g = 0.

Bien sûr, puisque la recherche doit être lancée plusieurs fois, il est judicieux de conserver pour chaque nœud les informations des précédentes recherches. C'est la technique connue sous le nom de table de transposition, que l'on implémente en général avec une table de hachage.