Espérance de gain d'une situation

Soit S une situation de jeu et J le joueur ayant le trait dans cette situation.

On peut associer à S une variable aléatoire G à trois valeurs: 1, 0 ou -1.

G vaut 1 (respectivement 0, -1) si le jeu se termine par une victoire de J (respectivement partie nulle, défaite de J).

Avec cette modélisation, l'espérance de G est donc un nombre situé entre -1 et 1. Plus précisément

  E(G)= -1 × P(G=-1) + 0 × P(G=0) + 1 × P(G=1) = P(G=1) - P(G=-1)

L'espérance de gain est donc la différence entre la probabilité de victoire de J et la probabilité de défaite de J.

Pour ne pas trop alourdir les notations, nous définirons l'espérance de gain de la situation S, notée E(S) comme l'espérance de gain de G.

Si S n'est pas une feuille de l'arbre de jeu, elle possède M fils:

Dans les situations F₁,F₁, ..., F_M, le trait est à l'adversaire de J.

Supposons que J connaisse les espérances de gain E(F₁), E(F₁), ..., E(F_M).

Dans ce cas, il choisira de jouer le coup donnant une espérance de gain minimale à son adversaire. Soit F_K, un des fils réalisant l'espérance de gain minimale. Soit v_K, la probabilité de victoire de l'adversaire dans cette situation et soit d_K, sa probabilité de défaite. On a

E(F_K) = v_K - d_K

Mais dans cette même situation F_K, la probabilité de victoire de J est d_K et sa probabilité de défaite est v_K. Son espérance de gain est donc

d_K - v_K = -E(F_K)

On en déduit que si J choisit bien le coup donnant une espérance de gain minimale à son adversaire, alors son espérance de gain dans la situation S est l'opposée du minimum des espérances de F₁,F₁, ..., F_M:

E(S) = - Min ( E(F₁), E(F₂), ..., E(F_M) )

En développant un arbre de jeu tronqué d'une situation, nous pouvons donc calculer récursivement son espérance de gain à condition que les espérances de gain des feuilles de l'arbre soient connues.

La figure suivante illustre ceci pour un arbre de profondeur 2. Le ou les meilleurs coups à jouer son indiqués en vert.

Si nous pouvions connaitre l'espérance de gain des feuilles nous aurions donc un moyen de trouver le meilleur coup à jouer dans n'importe quelle situation.

Malheureusement, le calcul théorique de l'espérance de gain d'une situation de jeu est un problème extrèmement complexe (pour ne pas dire impossible à résoudre !).

Valeur d'une situation

Pour contourner cette difficulté, nous allons associer une valeur numérique à une situation quelconque de l'arbre de jeu en supposant que l'espérance de gain dépende d'une manière optimale de cette valeur (nous verrons plus loin comment).

Commencons par définir la valeur d'une feuille de l'arbre. Dans un arbre de jeu tronqué, il y a deux catégories de feuilles: celles qui représentent des situations de fin de partie. Ce sont les feuilles terminales. Les autres résultent de la troncature de l'arbre de jeu. Elles représentent les situations où la partie n'est pas finie et telles que la profondeur maximale de recherche a été atteinte.

Pour une feuille terminale, il y a deux possibilités :

• Elle représente la victoire d'un des deux joueurs. Dans ce cas, c'est forcément le joueur qui a le trait qui a perdu. Nous associons la valeur -V_max à ce type de situation où V_max est un nombre positif.
• Elle représente une situation de partie nulle: nous associons la valeur 0 à ce type de situation.

Pour une feuille non terminale, on fera un calcul. Le résultat de ce calcul est la valeur heuristique de la situation. On s'arrange pour qu'elle soit toujours strictement comprise entre -V_max et V_max. Nous la noterons V_H.

La manière de calculer cette valeur heuristique est totalement dépendante du type de jeu. Il n'est donc pas possible ici d'en donner une définition générale. Pour vous donner une idée, nous donnerons plus loin deux exemples d'heuristiques: un exemple pour le jeu d'échec, puis un exemple pour le super morpion.

Voyons à présent comment définir la valeur d'un noeud interne. Un noeud interne possède M fils.

La valeur de la situation S, noté V(S) est définie par:

V(S) = - Min ( V(F₁), V(F₂), ..., V(F_M) )

où V(F₁), V(F₂), ..., V(F_M) sont les valeurs respectives des situations F₁, F₂, ..., F_M.

Notez que si la valeur d'un des fils est -Vmax, alors celle de S sera Vmax. Cela représente la situation où J possède un coup gagnant (le coup menant à ce fils). Sa victoire est donc certaine.

Cette manière de définir la valeur d'une situation à partir de ses fils conduit à l'algorithme connu sous le nom de Négamax qui est lui même une variante de l'algorithme du Minimax de Von Neumann.

Pour comprendre l'origine du nom Négamax, il faut voir que l'opposé du minimum d'un ensemble de nombre est égale au maximum des opposés de ces nombres. Donc, on aurait très bien pu définir V(S) par:

V(S) = Max ( -V(F₁), -V(F₂), ..., -V(F_M) )

Une remarque importante: lorsque toutes les feuilles de l'arbre de jeu tronqué sont terminales et de valeur non nulles (donc Vmax ou -Vmax), Négamax peut prédire avec certitude la défaite ou la victoire du joueur ayant le trait.

La valeur zéro ne donne pas d'information certaine, car on ne peut pas distinguer un zéro provenant d'une valeur heuristique nulle d'un zéro provenant d'une situation de partie nulle.

Optimalité de l'algorithme Negamax

Avec cette définition de la valeur d'une situation, on peut montrer que si la valeur heuristique d'une situation vérifie les hypothèses suivantes :

alors choisir le coup conduisant à une situation de valeur minimale pour l'adversaire revient exactement au même que choisir le coup conduisant à une espérance de gain minimale pour l'adversaire.

En voici, la preuve:

Soit S un noeud interne de l'arbre de jeu et ses fils F₁,F₁, ..., F_M.

Il s'agit de démontrer que l'espérance de gain d'un fils de valeur minimale est forcément minimale.

Soit F_K un tel fils. On a

V(F_K) = Min ( V(F₁), V(F₂), ..., V(F_M) )

Il faut montrer que cela implique

E(F_K) = Min ( E(F₁), E(F₂), ..., E(F_M) )

La preuve est basée sur l'existence d'une fonction φ qui associe une espérance à toute valeur d'une situation de jeu.

Soit H l'ensemble des valeurs heuristiques de toutes les situations de jeu possibles. Nous pouvons définir φ sur H ∪ {-Vmax; Vmax} à valeurs dans [-1;1] de la manière suivante:

Notez que d'après la manière dont nous avons définit l'espérance de gain d'une situation φ(v) est forcément dans l'intervalle [-1;1].

Nous allons à présent montrer que la fonction φ, vérifie les propriétés suivantes:

Preuve que φ(0)=0

D'après l'hypothèse (H4), il existe une situation de jeu S₀ telle que V_H(S₀)=0. On a donc V_H(S₀) = - V_H(S₀).

D'après l'hypothèse (H3), cela implique E(S₀) = - E(S₀) et donc E(S₀)=0. Donc, d'après la définition de φ, φ(0)=0.

Preuve que φ est croissante

Soit v₁, v₂ deux éléments de H ∪ {-Vmax; Vmax} tels que v₁ ≤ v₂. Montrons que l'on a nécessairement φ(v₁) ≤ φ(v₂).

Ici, nous allons distinguer quatre cas:

1. v₁=-Vmax et v₂=Vmax
   Par définition φ(-Vmax)=-1 et φ(Vmax)=1. On a donc bien
   φ(v₁) ≤ φ(v₂).
2. v₁=-Vmax et v₂ ∈ H
   Comme φ(-Vmax)=-1 et φ(v₂) ∈ [-1;1], on a forcément φ(v₁) ≤ φ(v₂).
3. v₁ ∈ H et v₂=Vmax
   Comme φ(v₁) ∈ [-1;1] et φ(Vmax)=1 et , on a forcément φ(v₁) ≤ φ(v₂).
4. v₁ ∈ H et v₂ ∈ H
   Dans ce cas, il existe une situation de jeu S₁ telle que V_H(S₁)= v₁
   et une situation de jeu S₂ telle que V_H(S₂)= v₂.
   Donc par la définition de la fonction φ on a
   
   φ(v₁) = E(S₁) et φ(v₂) = E(S₂).
   
   Donc v₁ ≤ v₂ équivaut à V_H(S₁) ≤ V_H(S₂)
   Mais d'après l'hypothèse (H1), ceci implique E(S₁) ≤ E(S₂)
   et par conséquent φ(v₁) ≤ φ(v₂)

Preuve que φ est impaire

Soit v₁ et v₂ deux éléments de H ∪ {-Vmax; Vmax}, tels que v₁ = -v₂. Montrons que φ(v₁) = -φ(v₂).

On a trois possibilités:

1. v₁=-Vmax et v₂=Vmax
   Par définition, φ(v₁)=-1 et φ(v₂)=1. On a donc bien φ(v₁) = -φ(v₂)
2. v₂=-Vmax et v₁=Vmax
   Par définition, φ(v₂)=-1 et φ(v₁)=1. On a donc bien φ(v₁) = -φ(v₂)
3. v₁ ∈ H et v₂ ∈ H
   Dans ce cas, il existe une situation de jeu S₁ telle que V_H(S₁)= v₁
   et une situation de jeu S₂ telle que V_H(S₂)= v₂.
   Donc v₁ = -v₂ équivaut à V_H(S₁)= - V_H(S₂). D'après (H3), cela implique
   E(S₁) = - E(S₂) et par conséquent φ(v₁) = -φ(v₂)

Preuve de la propriété P4

Il s'agit de montrer que φ(V(S))=E(S) , pour toute situation de jeu S d'un arbre de jeu.

Nous allons démontrer cette propriété par récurrence.

Initialisation: montrons que la la propriété est vraie lorsque S est une feuille de l'arbre de jeu.

Si la feuille est terminale sa valeur est -Vmax ou 0. Sinon, c'est une valeur de H différente de 0 et de -Vmax. La valeur Vmax, n'est pas possible.

Nous distinguons ici trois cas:

1. V(S)=-Vmax: d'après la définition de la valeur d'une situation, cela signifie que le joueur ayant le trait a perdu. On a donc E(S)=-1, qui est bien égal à φ(V(S)).

2. V(S)=0:

   • Si S est terminale, on a une situation de partie nulle et dans ce cas E(S)=0. On a donc bien φ(V(S)) = E(S).
   • Si S n'est pas terminale, on a V_H(S)=0. On a donc V_H(S)= -V_H(S) D'après l'hypothèse (H3), cela implique E(S)=-E(S) et par conséquent E(S)=0. Donc φ(V(S)) = E(S).

3. V(S) ∈ H et V(S)≠0: dans ce cas, V(S)=V_H(S) et par définition de φ, φ(V(S)) = E(S).

A présent, montrons que si P4 est vraie pour toute situation dont l'arbre de jeu est de profondeur inférieure où égale à N, alors elle est nécessairement vraie pour toute situation dont l'arbre de jeu est de profondeur inférieure où égale à N+1.

Soit S, une situation dont l'arbre de jeu est de profondeur N+1 (N ≥ 0). S possède M fils dont les arbres de jeu sont de profondeur inférieure ou égale à N.

Par définition de la valeur d'une situation:

V(S) = -Min ( V(F₁), V(F₂), ..., V(F_M) )

Par hypothèse de récurrence φ(V(F_i)) = E(F_i) pour i = 1,2,...,M.

D'autre part, E(S) = -Min ( E(F₁), E(F₂), ..., E(F_M) ) et donc
E(S) = -Min ( φ(V(F₁)), φ(V(F₂)), ..., φ(V(F_M)) ).

Mais comme φ est croissante

Min ( φ(V(F₁)), φ(V(F₂)), ..., φ(V(F_M)) ) = φ(Min(V(F₁),V(F₂),..., V(F_M)))

Donc

E(S)= -φ(Min(V(F₁),V(F₂),..., V(F_M)))

Comme φ est impaire

E(S)=
-φ(Min(V(F₁),V(F₂),..., V(F_M))) = φ(-Min(V(F₁),V(F₂),..., V(F_M)))
= φ(V(S))

Revenons à présent à notre objectif initial, qui était de prouver l'implication

Nous partons de

V(F_K)=Min(V(F₁), V(F₂), ..., V(F_M))

En appliquant φ à chaque coté de l'égalité

φ(V(F_K))= φ(Min(V(F₁), V(F₂), ..., V(F_M)))

D'après la propriété (P4):

E(F_K)= φ(Min(V(F₁), V(F₂), ..., V(F_M)))

Mais comme φ est croissante :

E(F_K)= Min(φ(V(F₁)), φ(V(F₂)), ..., φ(V(F_M)))

et en appliquant encore une fois la propriété (P4):

E(F_K)=Min(E(F₁), E(F₂), ..., E(F_M))

Exemples d'heuristiques

Exemple 1: Heuristique pour le jeu d'échec

Une manière assez rudimentaire d'évaluer une situation de jeu aux échecs est de baser le calcul sur la valeur des pièces de chaque joueur. Une autre manière plus élaborée, serait d'intégrer la position des pièces dans le calcul. Mais le critère positionnel est plus délicat à évaluer. Notre objectif étant simplement de faire ressortir quelques principes à travers un exemple, nous nous contenterons ici du critère matériel (la valeur des pièces).

Les valeurs officiellement acceptées des pièces sont les suivantes: la dame vaut 9 points, la tour 5 points, le fou et le cavalier 3 points et le pion 1 point. Le roi n'est pas pris en compte dans le calcul, car il est toujours présent.

On pourrait calculer la valeur heuristique d'une situation en soustrayant le nombre de points de A du nombre de points de J. Cela nous donnerait, le calcul suivant:

où :

• D_J (respectivement D_A) est le nombre de dames de J (respectivement de A)
• T_J (respectivement T_A) est le nombre de tours de J (respectivement de A)
• F_J (respectivement F_A) est le nombre de fous de J (respectivement de A)
• C_J (respectivement C_A) est le nombre de cavaliers de J (respectivement de A)
• P_J (respectivement P_A) est le nombre de pions de J (respectivement de A)

Il nous faut ensuite choisir une valeur pour V_max de telle manière que -V_max < V_H < V_max.

Il suffit de trouver un majorant très grossier de la valeur heuristique. Il faut tenir compte ici de la règle de transformation du pion. Lorsqu'un pion atteint la dernière ligne, il peut être transformé en une autre pièce (au choix dame, tour, fou ou cavalier). J peut donc théoriquement posséder au maximum 9 dames, 10 tours, 10 fous, 10 cavaliers et 8 pions. Dans la réalité, il est impossible de réaliser tout ces maximum simultanément, mais peu importe, puisque nous cherchons simplement un majorant. D'autre part A aura au minimum 0 points, s'il ne lui reste que le roi.

Cela nous donne:

On peut donc prendre par exemple V_max = 200. Une situation de jeu de valeur 200 représentera dans ce cas la situation de mat de A ou autrement dit, la victoire de J. Inversement, Une situation de jeu de valeur -200 représentera la situation de mat de J ou autrement dit, la victoire de A.

---

Exemple 2: Heuristique pour le super morpion

Au super morpion, on peut définir la valeur heuristique d'une situation à partir de la présence de deux types de motifs permettant potentiellement de réaliser un alignement de trois symboles identiques (croix ou rond). Les motifs de type 1 permettent de réaliser un alignement de trois symboles en un coup et ceux de type 2, en deux coups.

Voici, les douze motifs de type 1 pour les ronds. Si les ronds jouent la case vide, ils gagnent un alignement:

Motifs de type 1

et voici les douze motifs de type 2 pour les ronds. Si les ronds jouent les deux cases vides, ils gagnent un alignement:

Motifs de type 2

Les motifs de type 1 sont beaucoup plus dangereux que ceux de type 2. Il faut donc leur donner un poids plus important dans le calcul de l'heuristique. Il faut également tenir compte du nombre d'alignements déjà réalisé, par chaque joueur.

Voici une manière de tenir compte de tout cela dans le calcul de V_H

où :

• A3_J (respectivement A3_A) est le nombre d'alignements déjà réalisés par J (respectivement A).
• M1_J (respectivement M1_A) est le nombre de motifs de type 1 de J (respectivement de A).
• M2_J (respectivement M2_A) est le nombre de motifs de type 2 de J (respectivement de A).
• K₂ est un majorant de M2_J - M2_A. Cela nous assure que la somme du nombre de motifs de type 1 et d'alignements réalisés est prioritaire sur le nombre de motifs de type 2. Le nombre de motifs de type 2, n'intervient que pour départager les situations dans lesquelles la différence (A3_J+M1_J) - (A3_A+M1_A) est nulle.

Comme dans le cas du jeu d'échec, pour définir la valeur de V_max, on s'arrange pour que -V_max < V_H < V_max, Ici on pourra prendre

où K₁ est un majorant de (A3_J+M1_J) - (A3_A+M1_A).