Algorithme du MiniMax

Elabor�e en 1928 par John Von Neumann, cette technique am�ne l'ordinateur � passer en revue toutes les possibilit�s pour un nombre limit� de coups et � leur assigner une valeur qui prenne en compte les b�n�fices pour le joueur et pour son adversaire. Le meilleur choix �tant alors celui qui maximise ses b�n�fices tout en minimisant ceux de son adversaire.

On consid�re un jeu se jouant � deux personnes, chaque joueur effectuant tour � tour un unique coup. On supposera qu'aucune partie ne comporte un nombre infini de coups, et qu'� chaque position, il existe un nombre fini de coups l�gaux. Alors, � chaque position p, il existe un nombre fini N(p) tel que toute partie commen�ant � partir de p ne comporte pas plus de N(p) coups.

Des exemples typiques de jeux entrant dans le cadre pr�c�dent sont les jeux des Echecs, d'Othello, etc..... Le but est de construire et d'�tudier des algorithmes qui, �tant donn� une position p, et un joueur, choisissent un coup ``valable'' pour ce joueur.

2) Mini Max.

L'algorithme Mini Max, d� � Von Neumann, est tr�s simple : on visite l'arbre de jeu pour faire remonter � la racine une valeur (appel�e "valeur du jeu") qui est calcul�e r�cursivement de la fa�on suivante :

• MiniMax(p)=f(p) si p est une position terminale
• MiniMax(p)=max(MiniMax(o1), ..., MiniMax(on)) si p est une position joueur avec fils o1, ..., on
• MiniMax(p)=min(MiniMax(j1), ..., MiniMax(jm)) si p est une position opposant avec fils j1, ..., jm

On peut v�rifier que MiniMax(p) est la meilleure valeur possible � partir de la position p, si l'opposant joue de fa�on optimale. Il est clair que pour appliquer l'algorithme MiniMax il suffit de disposer de :

• un type de donn�es position qui permet de repr�senter les �tats possibles du jeu (et une position initiale) ;
• une fonction pour �valuer les positions terminales ;
• une fonction qui sert � d�terminer si une position est une position joueur ou opposant ;
• une fonction qui prenne une position p et retourne la liste des positions accessibles par les coups disponibles � partir de p.

3) Tic-Tac-Toe.

Voici un application du MiniMax au jeu "Tic-Tac-Toe" (morpion sur un damier de 3*3) :

Des applications � d'autres jeux sont �videmment possibles. Par exemple :

• Jeu de Kono.
• Puissance 4.

LOEWENGUTH Pascal - http://lwh.free.fr -