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.