L'optimisation de MinMax du point
de vue de la rapidité serait une chose vraiment très interressante vue
le nombre de fois qu'elle est appelée, la solution proposé se nomme comme
tout le monde s'y attendait : Alpha-Beta.
Algorithme Alpha-Beta
1 - Solution
apportée par Alpha-Beta
Le but de cette procedure est d'éviter de calculer des branches inutilement.
Mais il est très dur d'expliquer Alpha-Beta sans exemple, c'est pour cela
que nous courons chercher l'exemple sur notre arbre de choix de type MinMax.

Maintenant observons la simplification
d'Alpha-Beta :

Explications : Le noeud
x peut couper la partie après la feuille de valeur 2. En effet, le noeud
y,père de x choisi Max (3) = 3 puis Max(3, Min(4,2,...)). Il est inutile
d'aller au-delà de la feuille de valeur 2 puisque Max(3,x) retourne une
valeur y 3 or x = Min(4,2,.. ) retourne une valeur .x 2.
2 - Definition d'Alpha-Beta
Alpha-Beta n'est ni plus ni moins qu'une simple vision optimisée de minmax.
Nous verrons plus-tard la preuve de son interet pas l'étude des statistiques
sur un jeu comme l'Othello.
En enlevant des branches, ne risquons nous pas de perdre le meilleur coup
au profit de la vitesse ?
Le procédé Alpha-Beta ne donne pas forcément les mêmes coups, mais souvent.
Si les coups donnés par les deux méthodes (MinMax et AlphaBeta) diffèrent,
ils ont néanmoins strictement la même valeur. Par conséquent rien n'est
perdu.
3 - Exemple d'application
Comme une longue explication vaut moins qu'un bon exemple, nous repassons
aux exemples abordés pour MinMax, et nous allons observer les différences.
Tout d'abord, nous travaillons sur l'Othello.
- Jeu complexe : Othello
Pour illustrer le rôle d'Alpha-Beta au sein de l'arbre de choix. Nous
allons simplement reprendre notre exemple d'arbre MinMax et le re-créer
avec Alpha-Beta. Tout en indiquant précisement les differences.
¤
Principe du travail sur les arbres générés
Par AlphaBeta, la rapidité pour trouver un coup à une profondeur N > N0
est de l'ordre de 30 % aux échecs. (N > N0, car le gain est insignifiant
pour des niveaux comme 1 ou 2...) Les graphiques ci-dessous montrent qu'il
n'en est pas ainsi pour Othello. Les gains sont nettement supérieurs,
jusqu'à +3000 % Mais le rapport est également lié à la fonction d'évaluation.
On se base ici non pas sur le temps, mais sur le nombre total de noeuds,
feuilles inclues, analysés par les algo de générations d'arbres de jeux.
Ce nombre total de noeuds est proportionnel à peu de chose près au temps.

On remarque que la tendance générale
du nombre de coups analysés par Min-Max augmente dans le premier tiers
suivant une loi gaussienne fortement prononcée. Ceci parce que le damier
est libre, et beaucoup de combinaisons sont permises. Dans les 2 tiers
suivants, la descente s'effectue également suivant la répartition de gauss,
mais de manière plus douce. Il va en effet que le nombre de combinaisons
de jeux diminue progressivement au fur et à mesure que l'on va atteindre
les bords.
En ce qui concerne la répartition du nombre de coups analysés par Alpha-Béta,
on peut conclure que dans le premier huitième et le dernier quart de la
partie, le nombre de coups reste très faible. La machine répond à ces
instants de manière quasi instantanée. Le reste de la courbe d' Alpha-Béta
varie presque aléatoirement.
¤ Comparaisons du gain de temps

A remarquer les points sortant
de la courbe de Min-Max lors du 22 ième et 32 ième coups, de quoi intriguer
plus d'un statisticien ! Il existe de temps à autre certaines configurations
de jeux, où le nombre de jeux qui doivent être analysés pour une profondeur
donnée sort du rang. Lors des tests, une configuration a largement attiré
notre attention : nous sommes en profondeur 4, et dépassons toujours avec
grande peine les 2500 noeuds pour Alpha-Beta. Subitement au 22 ième coups
Alpha-Béta explose avec 33374 noeuds analysés ! Au coup suivant on sera
à nouveau dans les normes. Min-Max analyse pour ce même coup, même joueur,
35645 noeuds. (voir le damier ci-après).

En profondeur 6 on a respectivement
pour les 2 algo 3.8 et 6.0 millions de damiers analysés pour finalement
jouer un coup évident en profondeur 2 : Noir doit jouer (5,8). Une évidence
apparaît : Alpha-Beta n'est encore pas la réincarnation de l'optimisation
à l'état pur...
4 - Conclusion sur MinMax/Alpha Beta
MinMax l'essentiel
Pour que ces algorithmes soient vraiment performants, il faut que la fonction
d'évalution soit le plus soigné possible, donc la solution n'est pas immédiate
pour des jeux plus complexes que le morpion. Il faut de nombreux testes
pour coéfficienter correctement les paramètres de cette fonction.
L'arbre de choix
Il faut bien être conscient qu'il n'est pas toujours utile de créer tout
l'arbre, ca ne sert à rien, il vaut mieux travailler la fonction d'évaluation
stratégique, afin qu'elle soit fiable. L'élagage d'un arbre peut permettre
de resortir le meillieur coup bien plus facilement sans gacher du temps
processeur.
|