Retour en haut

» Présentation de l'algorithme MinMax

Dans cette partie, nous allons nous intéresser à une méthode utilisée dans le cadre des jeux de plateaux dans lesquels deux joueurs s’affrontent à tour de rôle, notamment le morpion, Puissance 4 ou bien d’autres encore.
Nous avons choisi de conclure notre TPE par l’étude de l’algorithme MinMax, un des plus simples qui soit dans l’intelligence artificielle. A partir de son étude, nous avons réalisé un morpion à l’aide du langage PHP, très utilisé dans la conception de sites web.

Présentation de l’algorithme MinMax

La théorie

Conçu en 1928 par Von Neumann, le principe de base de l’algorithme consiste à dire que l’adversaire de l’ordinateur jouera à chaque fois le meilleur coup possible. L’intelligence artificielle jouera donc le coup qui contrera ce meilleur coup. Pour ce faire, il faut réaliser l’arbre de jeu.

Prenons l’exemple de cet état de jeu :



A partir de cet état, l’arbre nous permet de représenter toutes les évolutions possibles du jeu. On l’arrête lorsque la partie s’arrête, c'est-à-dire soit le joueur a gagné, l’IA a gagné ou il y a égalité.

Une fois que nous avons dressé l’arbre du jeu, on attribue différentes à l’état final du jeu suivant le résultat :
- 1000 si l’IA a gagné
- 0 s’il y a égalité
- -1000 si le joueur a gagné

On appelle l’ordinateur le joueur maximisant et le joueur réel le joueur minimisant.

Remarque : ces valeurs sont arbitraires. On aurait pu mettre n’importe quelle autre valeur, le but étant de donner une valeur forte à une victoire de l’IA, une valeur faible pour une défaite et une valeur intermédiaire pour un résultat nul.




Les applications

Comme précisé précédemment, cet algorithme étant relativement simple, il est majoritairement utilisé dans le cadre de jeux où deux joueurs s’affrontent à tour de rôle, tels le célèbre morpion, Puissance 4 ou encore Othello.

Les limites de cet algorithme

S’il fonctionne bien sur des jeux relativement simples, il est en revanche bien trop lent pour des jeux plus complexes comme les dames ou pire, les échecs.

En effet, il effectue une exploration complète de l'arbre de recherche jusqu'à un niveau donné, alors qu'une exploration partielle de l'arbre est généralement suffisante : lors de l'exploration, il n'est pas nécessaire d'examiner les sous-arbres qui conduisent à des configurations dont la valeur ne contribuera sûrement pas au calcul du gain à la racine de l'arbre.

L’élagage Alpha/Bêta permet de réaliser ceci. Ainsi, il permet d'optimiser efficacement et de manière sûre l'algorithme MinMax.
Il est très utilisé dans le cas des jeux à 2 joueurs, comme par exemple les échecs ou le go.

Mise en place

Algorithme en français

Nous écrivons tout d’abord l’algorithme en pseudo-code, c'est-à-dire que nous ne l’écrivons pas dans un langage particulier pour le moment, mais nous le simplifions au maximum afin qu’il soit compréhensible.



Dans le cadre de ce jeu de morpion, on compte le nombre de séries de pions alignées par chaque joueur pour distinguer quel est le meilleur choix à faire entre deux victoires ou deux égalités par exemple : ainsi, le poids pour renvoyé pour un plateau contenant deux séries de deux pions pour le joueur aura un poids moindre par rapport à celui n'en contenant qu'une.

Algorithme en PHP

Ceci fait, nous pouvons le traduire en PHP. Il faut également rajouter tout le nécessaire pour afficher le morpion, lancer la fonction d'intelligence artificielle au bon moment, établir plusieurs niveaux de difficulté suivant la profondeur explorée...

Voici le code finalement utilisé:



Vous pouvez tester le résultat ci-dessous.



Il est également téléchargeable au complet en cliquant ici.