124
Rec herc he en meilleur d'abord pour les jeux à deux joueurs
PN-search choisit de développer la branche qui a le moindre coût.
FIGURE 6. 1 - Quelle feuille développer ?
Quelle est la feuille la plus intéressante à développer pour prouver la valeur 1 à la
racine de l ' arbre de la figure 6. 1 ?
Aux noeuds OU, pour prouver le noeud, il suffit qu' un seul des fils ait la valeur l. Le
nombre minimum de coups pour prouver le noeud OU est donc le minimum sur tous les
fils du nombre de coups qu' il faut pour prouver chacun des fils.
En revanche, pour prouver la valeur 0 à un noeud OU, il faut que tous les fils aient la
valeur O. Le nombre minimum de coups pour prouver la valeur 0 à un noeud OU (soit le
disproof number associé au noeud OU) est donc la somme des disproof numbers des fils.
De manière symétrique, aux noeuds ET, le proof number sera la somme des proof
numbers des fils (il faut que tous les fils soient à 1 pour que le noeud ET soit à 1), et le
disproof number sera le minimum des disproof numbers des fils (il suffit qu' un seul des
fils soit à 0 pour que le noeud ET soit à 0).
La remontée des valeurs de l ' arbre de la figure 6. 1 est donnée dans la figure 6.2.
Aux noeuds OU, on va choisir de développer le fils qui va permettre de prouver la
valeur du noeud OU le plus rapidement possible. On choisira donc le fils qui a le proof
number minimal. Or par construction, le proof number minimal des fils d' un noeud OU
est égal au proof number du noeud OU. On prendra donc le fils le plus à gauche qui a un
proof number égal à celui du noeud OU.
Aux noeuds ET, si on veut prouver le noeud ET, il faudra de toutes façons prouver
tous ses fils. En revanche, si on veut prouver la valeur 0, il suffira de prouver la valeur
0 pour un seul de ses fils. Le choix qui minimise la taille des arborescences est donc de
Rec herc he en meilleur d'abord pour les jeux à deux joueurs
PN-search choisit de développer la branche qui a le moindre coût.
FIGURE 6. 1 - Quelle feuille développer ?
Quelle est la feuille la plus intéressante à développer pour prouver la valeur 1 à la
racine de l ' arbre de la figure 6. 1 ?
Aux noeuds OU, pour prouver le noeud, il suffit qu' un seul des fils ait la valeur l. Le
nombre minimum de coups pour prouver le noeud OU est donc le minimum sur tous les
fils du nombre de coups qu' il faut pour prouver chacun des fils.
En revanche, pour prouver la valeur 0 à un noeud OU, il faut que tous les fils aient la
valeur O. Le nombre minimum de coups pour prouver la valeur 0 à un noeud OU (soit le
disproof number associé au noeud OU) est donc la somme des disproof numbers des fils.
De manière symétrique, aux noeuds ET, le proof number sera la somme des proof
numbers des fils (il faut que tous les fils soient à 1 pour que le noeud ET soit à 1), et le
disproof number sera le minimum des disproof numbers des fils (il suffit qu' un seul des
fils soit à 0 pour que le noeud ET soit à 0).
La remontée des valeurs de l ' arbre de la figure 6. 1 est donnée dans la figure 6.2.
Aux noeuds OU, on va choisir de développer le fils qui va permettre de prouver la
valeur du noeud OU le plus rapidement possible. On choisira donc le fils qui a le proof
number minimal. Or par construction, le proof number minimal des fils d' un noeud OU
est égal au proof number du noeud OU. On prendra donc le fils le plus à gauche qui a un
proof number égal à celui du noeud OU.
Aux noeuds ET, si on veut prouver le noeud ET, il faudra de toutes façons prouver
tous ses fils. En revanche, si on veut prouver la valeur 0, il suffira de prouver la valeur
0 pour un seul de ses fils. Le choix qui minimise la taille des arborescences est donc de