Projet Puissance 4 - Illustration de l'algorithme minimax

Le jeu

Explication de l’intelligence artificielle

L'intelligence artificielle utilisée utilise l'algorithme minimax, c'est le vieux algorithme qui a permis de battre l'homme aux échecs (mais pas au go), l'algorithme utilise la puissance de calcul de l'ordinateur pour examiner toutes les possibilités dans les n prochains coups, sa complexité est exponentielle en n.

Dans la première colonne on trouve toutes les tentatives possibles du joueur , dans la ligne qui suit on trouve alors toutes les possibilités suivantes du deuxième joueur, on considère que les joueurs feront maximiser ou minimiser ses scores. Ainsi le coup joué si on examine deux coups à l'avance sera la colonne car alors le deuxième joueur ne pourra avoir un score plus favorable que

Prenons l'exemple d'un jeu imaginaire où les joueurs ont le choix de jouer 0 ou 1, voici un arbre qui résume toutes les possibilités trois coups à l'avance.

Plus les points sont élevés plus le jeu est favorable au J1, on voit que si le J1 joue 0 puis le J2 joue 1 et enfin le J1 rejoue 0 alors on arrive à la situation la plus favorable au joueur 1 (avec 5 points) seulement le J2 s'il joue un minimum bien ne va pas jouer 1 au deuxième tour mais 0 et le J1 ne peut donc pas espérer faire mieux que -2. J1 doit jouer 1 car il est sur d'avoir au moins 1 point même si J2 joue au mieux.

On crée une classe Jeu qui va conserver la position (par exemple à l'aide d'un tableau deux dimensions) et le joueur qui doit jouer. Sans programmation objet on peut conserver ses choses en utilisant des variables.

Méthodes nécessaires

1. Une méthode score() qui évalue le jeu, plus le score est élevé et plus le joueur 1, par exemple dans le jeu on examine chaque possibilité de réalisation d'un alignement victorieux, si il y a juste un jeton du joueur 1 on gagne 1 point, si il y juste deux jetons on gagne 2 points et si il y a en a 3 on gagne 5 points. Les points sont négatifs si les jetons sont pour le joueur 2. Si on trouve une victoire du joueur 1 on retourne inf (ou un grand nombre), si le joueur 2 gagne on retourne - inf.
2. Une méthode donne_coup() qui donne tous les coups possibles par exemple sous forme d'un tableau par exemple, [3,4,6] signifie que l'on peut joueur à la colonne 3 4 et 6 (en commençant à 0).
3. Une méthode joue_coup(coup) qui joue un coup.
4. Une méthode annule_coup(coup) qui annule le coup joué.
5. Une méthode qui vérifie la victoire d'un joueur.
6. Une méthode qui vérifie le match nul.

Algorithme

Optimisation

L’algorithme minimax étant exponentielle (ici en 7ⁿ)il faut se contenter d'un faible nombres de coups de prévision on peut faire un peu mieux (tout en restant exponentielle mais avec un nombre inférieur à 7) en remarquant qu'il n'est pas nécessaire de calculer forcément toutes les combinaisons par exemple si pour un coup donné (par exemple il joue à la colonne 4) le joueur 1 a un score de 10 au mieux et si pour un autre coup (par exemple la colonne 3) on trouve directement que le joueur 2 peut faire un score de 7 en jouant à la colonne 1 alors il ne sert à rien d'examiner les autres coups du joueur 2 (il fera au mieux moins que 7 et le joueur 1 restera sur son coup de la colonne 4).

Vidéo

Du code à compléter.