6.4 Df-pn
127
6.4 Df-pn
Df-pn (Depth first proof number) [64) est une amélioration de PN* qui fait une recherche en profondeur d'abord en utilisant des seuils aussi bien pour les PN que pour les
DN. Il utilise moins de mémoire que PN-search. À chaque noeud on a deux variables :
- n.phi = PN(n) si n est un noeud OU, DN(n) si n est un noeud ET
- n.delta = DN(n) si n est un noeud OU, PN(n) si n est un noeud ET
Les seuils utilisés par Df-pn sont propres aux noeuds comme dans la recherche récursive en meilleur d'abord [55). La fonction récursive MID [64, 49) explore ses fils tant que
les PN et DN ne dépassent pas leurs seuils et tant que le noeud n'est pas prouvé. Comme
les mêmes noeuds sont redéveloppés de nombreuses fois, la table de transposition est très
importante pour Df-pn. Elle stocke les PN et les DN du noeud en plus des informations
classiques, lorsqu'une position n'est pas dans la table son PN et son DN sont intialisés à
l.
int dfpn (node root ) {
root . phi = Infini te ;
mot . delta = Infinite ;
MID (root );
}
if ( ro o t . d e lt a == 1 n f i n i t e )
return 1;
el se
return 0;
void MID (no de n) {
TT. look (n, phi , delta );
if (n. phi

Il seuil dép assé
}
n. phi = phi ;
n. delta = delta ;
return ;
if (fin (n)) {
}
if (gagne ( n)) {
n.phi = O;
}
n. delta = Inifinite ;
return ;
else {
}
n. phi = Infinite ;
n. delta = O;
return ;