11.S Corrigés des exercices
11.5.3 Le nombre de coups à gauche
191
La probabilité qu'un playout trouve la solution est la même que pour le problème
précédent : 2-n.
Pour un arbre de profondeur d, le nombre de feuilles qui ont un scores est (d). Pour
le sous arbre gauche ce nombre vaut (d= i). Pour le sous arbre droit ce nombre vaut (d - I ) .
La probabilité qu'un playout trouve le score s après un coup à gauche est donc
P1eftscore(s, d, 0) = ��a��( . La probabilité qu'un playout trouve le scores après un coup
' d
.
d
P
( d 0)
<;�_,)
a ro1te est one rightscore s, , = 2d-1 ·
La probabilité qu'un score s trouvé à gauche permette d'aller à gauche est donc
D
( d 0)
Priohtscore( s,d,O) + ..,s-l p
( · d 0) (J
·
t
t
r/eftmove S, ,
=
2
Lli=O rightscore i, ,
e premier erme es
du à un choix aléatoire en cas d'égalité de scores)
La probabilité de choisir le coup à gauche après un playout est donc Ptett(d, 0)
��=o(Pzeftscore(s, d, O) X Pzeftmove(s, d, O)).
On peut remarquer que la distribution des scores sous un noeud de l'arbre à hauteur
d est la même à une constante près. La probabilité de choisir un coup à gauche est donc
indépendante de la place du noeud dans l'arbre. La probabilité Ptett(d, 0) est donc valable
pour tous les noeuds de l'arbre de hauteur d.
On peut tenir un raisonnement similaire pour les niveaux plus élevés de recherche.
Soit Pteftscore(s, d, l) la probabilité qu' une recherche de niveau l commençant par un
coup à gauche trouve le scores à hauteur d. Soit Prightscore(s, d, l) la probabilité pour
le coup droit. La probabilité qu'un score trouvé à gauche permette de jouer le coup
h
t 1
n
( d l)
_
Prightscore (s,d,l) + ..,s-l p .
( · d l) L
gauc e es a ors rteftmove s, , -
2
Lli=O rightscore i, , . a probabilité qu'un coup gauche soit choisi est donc Pteft ( d, l) = ��=O ( Ptettscore ( s, d, l) x
Pteft move (s, d, l)).
La probabilité qu' une recherche de niveau l trouve le score s à hauteur d est alors
Pscore(s, d,l) = Pzett(d, l - 1) X Pscore(s - l, d - 1, l) + ( 1 - Pzett(d, l - 1)) X
Pscore(s, d - 1, l).
On a alors une formule de récurrence P1eftscore(s, d, l) = Pscore(s - 1, d - 1, l) et
Prightscore(s, d, l) = Pscore(s, d - 1, l).
Ces probabilités peuvent être calculées avec le programme suivant :
#include
#inclu de
#inclu de
const int MaxSize = 101;
const int MaxLevel = 4;