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 -