Wiki du LAMA (UMR 5127) - Contributions [fr]

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-25T10:45:37Z

Cfaucon : /* Définition */

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc un système qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|240px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|230px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

Nous utilisons toutes les étapes énoncés précédemment en faisant appel à des fonctions complémentaire pour récupérer les informations dont nous avons besoin.
Il nous suffit plus que de récupérer le résultat en faisant bien attention de prendre la première valeur du tuple.

=== Interface graphique ===
[[File:Figure7.png|thumb|300px|Interface graphique]]

Afin que les tests, que ce soit pour moi ou les personnes de mon entourage pour tester la qualité de mon puissance 4, soient plus agréables, nous avons mis en place un interface graphique.

Cette interface fait appel à la bibliothèque tkinter.
Tkinter est un module intégré à la bibliothèque standard de Python, permettant de créer des interfaces graphiques en créant:

*Des fenêtres,
*Des widgets (boutons, zones de texte, cases à cocher, …),
*Des évènements (clavier, souris, …).

Grace à celle-ci, nous avons pu créer un Canvas dans un fenêtre (fenêtre qui s'ouvrira lors de l'appel de la fonction de jeu) qui permettra au joueur de poser son pion à l'aide de bouton correspondant à des colonnes plutôt que sur la console python.
Dans son fonctionnement général après avoir créé la fenêtre ainsi que le Canvas, les boutons vont renvoyer la valeur de la colonne dans laquelle l'utilisateur souhaite jouer. Grace à cela il ne nous reste plus qu'a ajouter cette colonne dans une fonction permettant de poser le pion dans la colonne souhaité.

Dans la figure ci-dessus les pions roses sont ceux joués par l'utilisateur et ceux violets par l'ordinateur.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:50:43Z

Cfaucon : /* Interface graphique */

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|240px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|230px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

Nous utilisons toutes les étapes énoncés précédemment en faisant appel à des fonctions complémentaire pour récupérer les informations dont nous avons besoin.
Il nous suffit plus que de récupérer le résultat en faisant bien attention de prendre la première valeur du tuple.

=== Interface graphique ===
[[File:Figure7.png|thumb|300px|Interface graphique]]

Afin que les tests, que ce soit pour moi ou les personnes de mon entourage pour tester la qualité de mon puissance 4, soient plus agréables, nous avons mis en place un interface graphique.

Cette interface fait appel à la bibliothèque tkinter.
Tkinter est un module intégré à la bibliothèque standard de Python, permettant de créer des interfaces graphiques en créant:

*Des fenêtres,
*Des widgets (boutons, zones de texte, cases à cocher, …),
*Des évènements (clavier, souris, …).

Grace à celle-ci, nous avons pu créer un Canvas dans un fenêtre (fenêtre qui s'ouvrira lors de l'appel de la fonction de jeu) qui permettra au joueur de poser son pion à l'aide de bouton correspondant à des colonnes plutôt que sur la console python.
Dans son fonctionnement général après avoir créé la fenêtre ainsi que le Canvas, les boutons vont renvoyer la valeur de la colonne dans laquelle l'utilisateur souhaite jouer. Grace à cela il ne nous reste plus qu'a ajouter cette colonne dans une fonction permettant de poser le pion dans la colonne souhaité.

Dans la figure ci-dessus les pions roses sont ceux joués par l'utilisateur et ceux violets par l'ordinateur.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:49:45Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|240px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|230px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

Nous utilisons toutes les étapes énoncés précédemment en faisant appel à des fonctions complémentaire pour récupérer les informations dont nous avons besoin.
Il nous suffit plus que de récupérer le résultat en faisant bien attention de prendre la première valeur du tuple.

=== Interface graphique ===
[[File:Figure7.png|thumb|300px|Interface graphique]]

Afin que les tests, que ce soit pour moi ou les personnes de mon entourage pour tester la qualité de mon puissance 4, soient plus agréables, nous avons mis en place un interface graphique.

Cette interface fait appel à la bibliothèque tkinter.
Tkinter est un module intégré à la bibliothèque standard de Python, permettant de créer des interfaces graphiques en créant:

*Des fenêtres,
*Des widgets (boutons, zones de texte, cases à cocher, …),
*Des évènements (clavier, souris, …).

Grace à celle-ci, nous avons pu créer un Canvas dans un fenêtre (fenêtre qui s'ouvrira lors de l'appel de la fonction de jeu) qui permettra au joueur de poser son pion à l'aide de bouton correspondant à des colonnes plutôt que sur la console python.
Dans son fonctionnement général après avoir créé la fenêtre ainsi que le Canvas, les boutons vont renvoyer la valeur de la colonne dans laquelle l'utilisateur souhaite jouer. Grace à cela il ne nous reste plus qu'a ajouter cette colonne dans une fonction permettant de poser le pion dans la colonne souhaité.

Fichier:Figure7.png

2024-05-21T23:49:31Z

Cfaucon :

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:49:16Z

Cfaucon : /* Interface graphique */

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|240px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|230px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

Nous utilisons toutes les étapes énoncés précédemment en faisant appel à des fonctions complémentaire pour récupérer les informations dont nous avons besoin.
Il nous suffit plus que de récupérer le résultat en faisant bien attention de prendre la première valeur du tuple.

=== Interface graphique ===
[[File:figure7.png|thumb|300px|Interface graphique]]

Afin que les tests, que ce soit pour moi ou les personnes de mon entourage pour tester la qualité de mon puissance 4, soient plus agréables, nous avons mis en place un interface graphique.

Cette interface fait appel à la bibliothèque tkinter.
Tkinter est un module intégré à la bibliothèque standard de Python, permettant de créer des interfaces graphiques en créant:

*Des fenêtres,
*Des widgets (boutons, zones de texte, cases à cocher, …),
*Des évènements (clavier, souris, …).

Grace à celle-ci, nous avons pu créer un Canvas dans un fenêtre (fenêtre qui s'ouvrira lors de l'appel de la fonction de jeu) qui permettra au joueur de poser son pion à l'aide de bouton correspondant à des colonnes plutôt que sur la console python.
Dans son fonctionnement général après avoir créé la fenêtre ainsi que le Canvas, les boutons vont renvoyer la valeur de la colonne dans laquelle l'utilisateur souhaite jouer. Grace à cela il ne nous reste plus qu'a ajouter cette colonne dans une fonction permettant de poser le pion dans la colonne souhaité.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:48:43Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|240px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|230px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

Nous utilisons toutes les étapes énoncés précédemment en faisant appel à des fonctions complémentaire pour récupérer les informations dont nous avons besoin.
Il nous suffit plus que de récupérer le résultat en faisant bien attention de prendre la première valeur du tuple.

=== Interface graphique ===
[[File:figure1.png|thumb|300px|Interface graphique]]

Afin que les tests, que ce soit pour moi ou les personnes de mon entourage pour tester la qualité de mon puissance 4, soient plus agréables, nous avons mis en place un interface graphique.

Cette interface fait appel à la bibliothèque tkinter.
Tkinter est un module intégré à la bibliothèque standard de Python, permettant de créer des interfaces graphiques en créant:

*Des fenêtres,
*Des widgets (boutons, zones de texte, cases à cocher, …),
*Des évènements (clavier, souris, …).

Grace à celle-ci, nous avons pu créer un Canvas dans un fenêtre (fenêtre qui s'ouvrira lors de l'appel de la fonction de jeu) qui permettra au joueur de poser son pion à l'aide de bouton correspondant à des colonnes plutôt que sur la console python.
Dans son fonctionnement général après avoir créé la fenêtre ainsi que le Canvas, les boutons vont renvoyer la valeur de la colonne dans laquelle l'utilisateur souhaite jouer. Grace à cela il ne nous reste plus qu'a ajouter cette colonne dans une fonction permettant de poser le pion dans la colonne souhaité.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:48:04Z

Cfaucon : /* Interface graphique */

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|240px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|230px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

Nous utilisons toutes les étapes énoncés précédemment en faisant appel à des fonctions complémentaire pour récupérer les informations dont nous avons besoin.
Il nous suffit plus que de récupérer le résultat en faisant bien attention de prendre la première valeur du tuple.

=== Interface graphique ===
Afin que les tests, que ce soit pour moi ou les personnes de mon entourage pour tester la qualité de mon puissance 4, soient plus agréables, nous avons mis en place un interface graphique.

Cette interface fait appel à la bibliothèque tkinter.
Tkinter est un module intégré à la bibliothèque standard de Python, permettant de créer des interfaces graphiques en créant:

*Des fenêtres,
*Des widgets (boutons, zones de texte, cases à cocher, …),
*Des évènements (clavier, souris, …).

Grace à celle-ci, nous avons pu créer un Canvas dans un fenêtre (fenêtre qui s'ouvrira lors de l'appel de la fonction de jeu) qui permettra au joueur de poser son pion à l'aide de bouton correspondant à des colonnes plutôt que sur la console python.
Dans son fonctionnement général après avoir créé la fenêtre ainsi que le Canvas, les boutons vont renvoyer la valeur de la colonne dans laquelle l'utilisateur souhaite jouer. Grace à cela il ne nous reste plus qu'a ajouter cette colonne dans une fonction permettant de poser le pion dans la colonne souhaité.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:36:49Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|240px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|230px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

Nous utilisons toutes les étapes énoncés précédemment en faisant appel à des fonctions complémentaire pour récupérer les informations dont nous avons besoin.
Il nous suffit plus que de récupérer le résultat en faisant bien attention de prendre la première valeur du tuple.

=== Interface graphique ===

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:33:26Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|300px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|300px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

== Code et programmation ==
=== Minimax & Alpha Bêta ===

Avec toutes les informations fournies précédemment, nous avons donc pu coder une fonction minimax opérationnelle.
<pre>
def minimax_alpha_beta(plateau:list, profondeur:int, joueur_maximise:bool, alpha, beta):
colonnes_disponibles = colonnes_valides(plateau) #La fonction colonnes_valides renvoies sous forme de tableau les colonnes dans lesquelles il est possible de jouer
fin_jeu = est_finie(plateau)

if fin_jeu: #Vérification si le jeu est finie (victoire ou match nul), dans ce cas on a pas besoin de l'algorithme
if victoire(plateau, IA)[0]:
return (-1, float('inf'))
elif victoire(plateau, JOUEUR)[0]:
return (-1, -float('inf'))
else:
return (-1, 0) #8484
if profondeur == 0: #Si nous sommes a la profondeur 0, nous faisons appel à l'heuristique
return (-1, H(plateau, IA)) #8484

if joueur_maximise: #Nous entrons dans le cas où c'est au tour de l'ordinateur de jouer car c'est le joueur qui maximise
colonne_choisie =colonnes_disponibles[0]
valeur_max = -float('inf') #On initialise la valeur maximale puis nous créons l'arbre de jeu en visualisant toutes les possibilité de coups.

for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = IA
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1] #Tant que profondeur != 0 nous continuons d'appeler la fonction
if nouvelle_valeur > valeur_max:
valeur_max = nouvelle_valeur
colonne_choisie = col
if valeur_max > beta: #Nous faisons appel à alpha bêta en utilisant la règle vu au dessus
return (colonne_choisie, valeur_max)
alpha = max(alpha ,valeur_max)
return (colonne_choisie, valeur_max)

else: #Nous faisons de même pour le joueur c'est a dire celui qui minimise
valeur_min = float('inf')
colonne_choisie = colonnes_disponibles[0]
for col in colonnes_disponibles:
ligne_vide = prochain_ligne_vide(plateau, col)
plateau_copie = copy.deepcopy(plateau)
plateau_copie[ligne_vide][col] = JOUEUR
nouvelle_valeur = minimax_alpha_beta(plateau_copie, profondeur - 1, False, alpha, beta)[1]
if nouvelle_valeur < valeur_min:
valeur_min = nouvelle_valeur
colonne_choisie = col
if valeur_min < alpha:
return (colonne_choisie, valeur_min)
beta = min(beta, valeur_min)
return (colonne_choisie, valeur_min)

</pre>

=== Interface graphique ===

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:18:01Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|200px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|300px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|300px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:17:35Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|250px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|300px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|300px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:17:07Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|300px|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|300px|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|300px|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|300px|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|300px|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|300px|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:13:34Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|right|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|right|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|right|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
* Exemple 1
[[File:figure5.png|thumb|right|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

* Exemple 2
[[File:figure6.png|thumb|right|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:12:58Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
[[File:figure2.png|thumb|right|heuristique]]
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
[[File:figure3.png|thumb|right|Minimax]]
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|right|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
==== Exemple 1 ====
[[File:figure5.png|thumb|right|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

==== Exemple 2 ====
[[File:figure6.png|thumb|right|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Fichier:Figure6.png

2024-05-21T23:11:58Z

Cfaucon :

Fichier:Figure5.png

2024-05-21T23:11:11Z

Cfaucon :

Fichier:Figure4.png

2024-05-21T23:09:44Z

Cfaucon :

Fichier:Figure3.png

2024-05-21T23:07:47Z

Cfaucon :

Fichier:Figure2.png

2024-05-21T23:06:06Z

Cfaucon :

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:05:43Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
[[File:figure1.png|thumb|Arbre de jeu]]
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

[[File:figure2.png|thumb|right|heuristique]]

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

[[File:figure3.png|thumb|right|Minimax]]

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|right|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
==== Exemple 1 ====
[[File:figure5.png|thumb|right|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

==== Exemple 2 ====
[[File:figure6.png|thumb|right|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:05:26Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

[[File:figure1.png|thumb|Arbre de jeu]]

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

[[File:figure2.png|thumb|right|heuristique]]

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

[[File:figure3.png|thumb|right|Minimax]]

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|right|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
==== Exemple 1 ====
[[File:figure5.png|thumb|right|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

==== Exemple 2 ====
[[File:figure6.png|thumb|right|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T23:04:57Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

[[File:figure1.png|thumb|right|Arbre de jeu]]

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

[[File:figure2.png|thumb|right|heuristique]]

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

[[File:figure3.png|thumb|right|Minimax]]

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:figure4.png|thumb|right|Exemple Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
==== Exemple 1 ====
[[File:figure5.png|thumb|right|Exemple1 alpha bêta]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

==== Exemple 2 ====
[[File:figure6.png|thumb|right|Exemple2 alpha bêta]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Fichier:Figure1.png

2024-05-21T23:02:27Z

Cfaucon :

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T22:52:19Z

Cfaucon :

Tuteur: Valentin Gledel

Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

[[File:Example.jpg|alt=Exemple d'image|thumb|right|300px|Ceci est une légende]]

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

[[File:Heuristique_puissance4.png|alt=Heuristique Puissance 4|thumb|center|Exemple d'heuristique pour le Puissance 4]]

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
==== Exemple 1 ====
[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

==== Exemple 2 ====
[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.

Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

2024-05-21T22:51:52Z

Cfaucon : Page créée avec « Tuteur: Valentin Gledel Etudiante: Chloe Faucon == Introduction == Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc... »

Tuteur: Valentin Gledel
Etudiante: Chloe Faucon

== Introduction ==
Le Puissance 4 est un jeu créé en 1974 dont les règles sont très simples. Sur un plateau de 7 colonnes et 6 lignes, deux joueurs s'affrontent afin d'aligner 4 de leurs pions. Il y a 2 façons de finir le jeu : soit par un match nul lorsque le plateau est rempli sans aucun alignement réalisé, soit en ayant réalisé un alignement vertical, horizontal ou diagonal. Le but de ce projet est donc de pouvoir coder une IA pour pouvoir jouer contre. Cette IA sera codée à l’aide des fonctions minimax et alpha bêta, mais pour cela, il faut connaître des notions essentielles qui sont : l’arbre des jeux et les heuristiques.

== Arbre de jeu ==
=== Définition ===
Un arbre de jeu représente l’ensemble des coups successifs menant à toutes les positions possibles dans le plateau. C’est donc une structure qui permet de représenter toutes les positions possibles d'un jeu. Elle représente également les mouvements qui peuvent être effectués à partir de chaque position. On part d’une position initiale pour explorer toutes les autres possibles.

=== Structure ===
Un arbre de jeu est construit de la manière suivante :
* La racine : La racine de l'arbre représente l'état initial / la position de départ du jeu, où aucune décision n'a encore été prise. C’est le début du jeu.
* Les branches de l’arbre : Les branches entre les nœuds représentent les mouvements possibles d'une position à une autre, faisant passer le jeu d’un état A à un état B.
* Les nœuds : Chaque nœud de l'arbre représente une position/un coup possible du jeu à un certain moment. Les nœuds sont uniques et dépendent les uns des autres.
* Les feuilles : Les nœuds de l'arbre qui n'ont pas d'autres nœuds enfants (nœuds reliés par une branche à un nœud suivant) sont appelés des feuilles. Ils représentent les positions finales du jeu.

[[File:Example.jpg|alt=Exemple d'image|thumb|right|300px|Ceci est une légende]]

=== Profondeur ===
La profondeur permet de savoir jusqu'où l'arbre va s'étendre. Il s'agit de la distance entre la racine et les feuilles. Il faut prendre en compte que la racine de l'arbre est de profondeur 0. La profondeur de l'arbre permet de représenter le nombre de coups joués dans le jeu à partir de la position de départ. Plus l'arbre est profond, plus il explore de coups possibles, meilleur sera le résultat final.

=== But ===
L'étude et l'utilisation d'un arbre de jeu permettent de visualiser et d'analyser les différentes stratégies et leurs résultats en considérant toutes les actions possibles à chaque étape du jeu, d'analyser et de déterminer les meilleures stratégies et enfin de prédire les mouvements futurs des adversaires pour pouvoir anticiper les résultats.

== 3) Heuristique ==
=== Définition ===
Une heuristique est une fonction d'évaluation utilisée pour estimer la valeur ou la qualité d'une position dans un jeu. Dans l'étude de l'arbre, cette fonction sera uniquement utilisée au niveau des feuilles. Cette fonction peut permettre de savoir qui des 2 joueurs est en train de gagner.

=== Exemple ===
Dans le jeu des échecs, une heuristique simple pourrait être celle prenant en compte le nombre de pions présents dans le plateau. S'il y a plus de pions blancs présents sur le plateau, le résultat sera positif ou négatif (dépendant des caractéristiques des joueurs) et inversement pour les pions noirs.
Dans le cadre du Puissance 4, une heuristique efficace est celle renvoyant toutes les possibilités d'alignement d'un pion en fonction de sa position. Nous comprenons mieux ce concept à l'aide de la figure 2, où le résultat renvoyé par l'heuristique sera 4 car le pion peut effectuer 2 alignements horizontaux, 1 en vertical et un autre en diagonal.

[[File:Heuristique_puissance4.png|alt=Heuristique Puissance 4|thumb|center|Exemple d'heuristique pour le Puissance 4]]

== 4) Minimax ==
=== Contexte ===
Minimax avec l'élagage Alpha Bêta est connu comme étant le premier algorithme à avoir battu le champion du monde d'échecs Garry Kasparov le 11 mai 1997. Ce jour marque l'histoire pour l'avancée de l'intelligence artificielle. On doit cet algorithme ainsi qu'un théorème lié, à John Von Neumann. L'algorithme Minimax permet donc de jouer/résoudre des jeux de stratégie en évaluant les positions de jeu et en choisissant les actions de manière à maximiser le gain tout en minimisant les pertes possibles. Pour cela, il utilise des notions fondamentales telles que les arbres comme vu précédemment ou encore la récursivité.

=== Étapes de fonctionnement ===
*Étape n°1 : La réalisation et exploitation de l'arbre de jeu:
Au moment précis du jeu, l'algorithme va explorer toutes les possibilités de coups et positions à l'aide de l'arbre et d'une profondeur mise en paramètre au préalable.

*Étape n°2 : Utilisation de l'heuristique :
Après avoir construit tout l'arbre, il est maintenant temps de faire appel à l'heuristique au niveau des feuilles afin de faire remonter la valeur correspondant au coup optimal pour le joueur.

*Étape n°3 : Caractérisation des joueurs :
Nous avons donc 2 joueurs : Un joueur max, il s'agit du joueur qui va chercher à maximiser son score ainsi qu'un joueur min qui va lui chercher à minimiser son score. Dans l'arbre, chacun des joueurs représentera alternativement une ligne de l'arbre. Les nœuds de ces lignes seront des nœuds max (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur maximisant, ou alors des nœuds min (récupérant la valeur la plus grande de ses enfants) s'il s'agit de la ligne du joueur minimisant.

[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

*Étape n° 4 : La remontée des valeurs :
Pour chaque nœud, la valeur est calculée en fonction des valeurs de ses nœuds enfants. Si c'est le tour du joueur MAX (celui qui cherche à maximiser son score, l’ordinateur dans le cadre de Minimax), le nœud parent prendra la valeur maximale de ses enfants. Si c'est le tour du joueur MIN (celui qui cherche à minimiser le score de l'adversaire), le nœud parent prendra la valeur minimale de ses enfants. Une fois que la valeur est remontée jusqu'à la racine de l'arbre, le joueur choisit le coup correspondant à la branche avec la valeur maximale si c'est son tour, ou la valeur minimale si c'est le tour de l'adversaire. Il s’agit du meilleur coup à jouer dans la position actuelle selon l'algorithme Minimax. Dans le cadre du Puissance 4, nous obtiendrons la meilleure colonne dans laquelle il faut jouer.

=== Exemple ===
[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

Dans cet arbre de profondeur 3 très simple car l’algorithme Minimax n’a calculé que 14 coups, nous avons bien calculé les valeurs des feuilles à l’aide d’une heuristique. Après cela, le joueur maximisant a fait remonter les plus grandes valeurs parmi ses nœuds enfants (ici nous avons bien 4,6,-5,11). Ensuite, nous passons au tour du joueur minimisant et on réitère les mêmes actions. On prend les valeurs minimales entre les nœuds frères du nœud parent. Nous faisons ces actions jusqu’à remonter à l’origine. A l’origine ne remonte donc plus qu’une seule valeur : celle liée au meilleur coup. Il ne nous reste plus qu’à récupérer le nœud lié à la valeur présente à l’origine de l’arbre. On fait remonter les valeurs pour qu’à la fin il ne reste qu’une valeur liée à un nœud : la meilleure.

En conclusion:
L'algorithme Minimax permet ainsi de déterminer le meilleur mouvement pour l’ordinateur, en prenant en compte les réponses optimales du joueur. Cela garantit que chaque décision prise maximise les gains potentiels de Max tout en minimisant les pertes potentielles dues aux mouvements adverses.

=== Désavantages ===
Minimax est un algorithme qui fonctionne très bien cependant son efficacité est liée à la valeur de la profondeur. Plus la profondeur est grande, meilleur sera le résultat. Cependant, à partir d’une certaine profondeur, l’algorithme devient de plus en plus lent ce qui ne rend pas l’expérience de jeu agréable. Pour des problèmes concrets, le nombre de coups peut être très élevé, ce qui augmente grandement le temps de calcul. On peut passer pour le Puissance 4 d'environ une seconde en profondeur 3 à 30 secondes en profondeur 7. Et il s’agit du temps pour un coup. Il nous faut donc trouver une solution pour réduire les temps de coups. Cette solution est l’élagage Alpha Bêta.

== Elagage Alpha Bêta ==
==== Définition ====
L’élagage Alpha bêta consiste à supprimer des branches de l’arbre. En faisant cela, nous réduisons le nombre de nœuds qui ne servent pas, c’est-à-dire qui ne changent en rien le résultat final si celles-ci sont explorées ou non. Ce fonctionnement permettra donc de réduire considérablement le temps de calcul de Minimax puisque nous réduisons le nombre de nœuds. Pour ce faire, nous allons exploiter l'arbre des possibles pendant la remontée.

====Alpha et Bêta ====
Nous allons introduire des bornes Alpha et Bêta qui vont être transmises de père en fils et modifiées en fonction des évaluations qui sont faites.
Alpha : Représente le score maximum pour le joueur maximisant. Sa valeur ne peut qu’augmenter. De ce fait, il est initialisé à -∞. Il est mis à jour lors de l’étude d’un nœud MAX.
Bêta : Représente le score minimum pour le joueur minimisant. Sa valeur peut que baisser et est donc initialisé à +∞. Il sera mis à jour lors de l’étude d’un nœud MIN.

=== Fonctionnement de l’élagage ===
À chaque nœud Max, l'algorithme cherche le score maximal parmi les enfants du nœud. Si ce score est supérieur ou égal à bêta, la branche est élaguée.

À chaque nœud Min, l'algorithme cherche le score minimal parmi les enfants du nœud. Si ce score est inférieur ou égal à alpha, la branche est élaguée car Max.

Pour résumer : Si la valeur d'un nœud Min est inférieure ou égale à alpha, l'algorithme arrête d'explorer ce nœud. Si la valeur d'un nœud Max devient supérieure ou égale à bêta, l'algorithme arrête d'explorer ce nœud. Voici donc la règle : si Alpha est supérieur ou égal à Bêta, alors on peut élaguer la branche.

=== Exemple ===
==== Exemple 1 ====
[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

Nous étudions tout d’abord le premier nœud en remontant la valeur maximale des 2 feuilles qui lui sont fils. Il s’agit d’un nœud MAX, donc Alpha prend comme valeur 8. Nous remontons cette valeur à son père qui est un nœud MIN, donc Bêta prend la valeur 8.
Étudions maintenant le frère du nœud MAX. La première feuille donne une valeur de 9. La valeur du nœud MAX sera donc 9. Nous mettons à jour Alpha à 9. Cependant on constate que alpha (9) supérieur à Bêta (8), donc nous pouvons élaguer la branche.

==== Exemple 2 ====
[[File:Arbre_minimax.png|alt=Arbre Minimax|thumb|center|Exemple d'arbre pour l'algorithme Minimax]]

Faisons pareil pour cet arbre qui est la suite de l’arbre plus haut, c’est pour cela que nous avons déjà la valeur d’Alpha à 8 qui est la valeur actuelle de la racine de l’arbre. Par le même procédé que celui vu précédemment, nous étudions les premières feuilles, nous faisons remonter cette valeur jusqu’au nœud fils de la racine. Cela nous permet d’obtenir un premier Bêta à 2 et Alpha à 8. Nous constatons pour le nœud MIN qu’Alpha est supérieur à Bêta, nous pouvons donc élaguer.

=== Conclusion ===
L'élagage Alpha Bêta est une technique qui permet de réduire le nombre de nœuds explorés dans l'arbre de jeu en éliminant les branches qui ne contribuent pas à la décision finale, tout en garantissant que la même décision soit prise que si l'arbre complet avait été exploré. Cela permet de réduire significativement le temps nécessaire pour prendre une décision dans des jeux complexes.