Réalisation du projet
Nos recherches nous ont mené très rapidement vers l'algorithme mini-max.
Dans l'exemple du morpion, on peut voir que cette algorithme va vérifier chaque case et lui attribuer une valeurs qui est en fait le nombre de possibilité de victoire, l'algorithme va alors jouer la où ce chiffre est le plus grand tout en vérifiant les coups de l'adversaire et en l'empechant de gagner.
Ensuite nos recherches nous ont menés sur l'algorithme alpha-beta qui ets une version améliorer de minimax comme le montre l'exemple ci-dessous.
L'algorithme alpha-beta est une optimisation du MiniMax, qui «coupe» des sous arbres dès que leur valeur devient inintéressante aux fins du calcul de la valeur MiniMax du jeu.
Ensuite nous nous sommes lancés dans l'implémentation de minimax dans un puissance 4 pour rendre le programme intelligent et faire en sorte qu'il gagne à coup sur contre un débutant.
Voici le programme de base avec le puissance 4 où un joueur joue contre un ordinateur qui joue au hasard mais détecte tout de même si 3 pions sont alignés pour empêcher le joueur de gagner.
Télécharger la version 1 du puissance 4
Dans la version 2, le programme vérifie la présence de pions en dessous de l'endroit ou l'ordinateur veut jouer et effectue également à tour de rôle l'évaluation minimale et maximale pour renvoyer une position après avoir analyser une liste de possibilités. Dans cette version, cette liste n'est pas encore présente car la fonction qui la fait n'est pas encore crée.
Télécharger la version 2 du puissance 4
Dans la version 3, on trouve l'ajout de la fonction liste_possibilites() qui peut renvoyer différentes valeurs. Lors du premier coup de l'ordinateur, si c'est l'ordinateur qui joue en premier, elle renvoie la position avec le plus de coups possibles de la première ligne. Si c'est le joueur adverse qui commence, elle renvoie également la position avec le plus de coups possibles de la première ligne sans prendre en compte l'endroit où a joué l'adversaire avant, et en prenant la case au dessus de celle où à joué le joueur. A partir du moment où ce n'est plus le premier coup de l'ordinateur, la fonction va renvoyer la liste de possibilités de coups que la fonction mini_max() va analyser. Dans cette version, la liste créée ne prend en compte que les coups des lignes horizontales et des lignes verticales, le programme plante donc car la boucle while de la fonction ne s'arrête jamais.
