4.5 La réduction aux coups prometteurs
69
si toutes les recherches lambda d'ordre strictement inférieur à n qui le suivent échouent.
L'algorithme pour la recherche >. est le suivant :
Algorithm 2 Recherche >.
lambda (joueur, ordre)
if position gagnée ou gagnante en un coup de joueur then
return true
end if
if ordre = 0 then
return false
end if
for tous les coup légaux de joueur do
menace Vérifiée +-- false
jouer le coup
if lambda (joueur, ordre - 1) then
menace Vérifiée +-- true
for tous les coup légaux de l'adversaire de joueur do
jouer le coup
if not lambda (joueur, ordre) then
menace Vérifiée +-- false
end if
retirer le coup
end for
end if
retirer le coup
if menace Vérifiée then
return true
end if
end for
return false
On peut remarquer qu 'on passe de la recherche >. à la recherche de menaces directes
en remplaçant ordre par ordre - 1 dans l'appel récursif.
Exercice : Implémenter la recherche >. au Phutball.
4.5 La réduction aux coups prometteurs
Au Phutball les coups gagnants sont très souvent des coups qui étendent le chemin
possible de la balle vers son but ou des coups qui déplacent la balle. Si on restreint à ces
coups la recherche de coups gagnants dans les menaces, on réduit énormément le facteur
de branchement sans pour autant omettre beaucoup de menaces.
On peut de plus observer que les coups d'ordre zéro (les coups immédiatement ga-