#import "@preview/fletcher:0.4.2" as fletcher: node, edge
#import "/templates/base_formatting.typ": project, heading_1, heading_2, commented_text
#import "/templates/algo.typ": algo, i, d, comment, shell


#show: project.with(
  title: "Jeu de Dames",
  subtitle: "Implémentation et résolution avec différents algorithmes",
  authors: (
    (name: "Steendly", 
    email: "<EMAIL>"),
  ),
  abstract: [
    Le code source de ce projet est disponible sur : \
    #link("https://github.com/Steendly/Jeu-Dames/") \
  ]
)



#heading_1("Introduction")
Ce projet est réalisé dans le cadre d'un projet de fin d'année en NSI en terminal. Son but est d'implémenter le jeu de Dames dans sa #link("https://en.wikipedia.org/wiki/Brazilian_draughts")[variante Brésilienne] avec des agents (aussi appelés "bots") jouant de manière autonome en utilisant plusieurs algorithmes, le tout en Python. L'objectif principal est avant tout de les réimplémenter de zéro, mettant ainsi l'accent sur l'algorithmique. Pour cela, la réalisation de ce projet divisé en deux grandes parties.

La première partie est la création du moteur de jeu. Il suit les règles officielles du jeu de Dames qui sont les suivantes :

« Le jeu se joue à deux joueurs sur un plateau 8x8, chaque joueur dispose de 12 pièces. À chaque tour, vous devez vous déplacer vers une case vide, si vous pouvez capturer une pièce, vous devez effectuer ce mouvement.

Un mouvement fonctionne comme suivant :
- Vous avancez une pièce en diagonale vers une case vide. Vous ne pouvez pas déplacer une pièce en diagonale vers l'arrière tant qu'elle n'est pas promue roi. Si vous pouvez capturer une pièce, vous devez effectuer ce mouvement.

Un saut fonctionne comme suivant :
- Si une pièce adverse se trouve sur une case en diagonale à côté d'une de vos pièces et que l'espace au-delà est vide, alors vous devez sauter par-dessus la pièce adverse, la capturer et atterrir dans l'espace au-delà.
- Si un autre saut est disponible après avoir effectué un saut, vous devez alors sauter à nouveau et capturer la pièce suivante. Vous devez continuer à sauter jusqu'à ce qu'il n'y ait plus de sauts disponibles.
- Une pièce capturée est retirée du plateau.
- Si plusieurs pièces peuvent sauter, vous pouvez choisir la pièce sur laquelle vous souhaitez sauter.

Un couronnement fonctionne comme suivant :
- Lorsqu'une de vos pièces atteint le côté opposé du plateau, elle est couronnée et promue Roi.
- Un roi peut se déplacer en diagonale d'avant en arrière, il ne peut se déplacer que d'une case à la fois.
- Un Roi peut aussi sauter en avant et en arrière, il doit effectuer le saut disponible »

Cependant, dans cette version toutes les règles ne sont pas encore implémentées. Seul le mouvement d'une case vers une autre et la simple prise d'un pion adverse sont fonctionnelles. Les autres règles telles que le couronnement, l'obligation de capturer une pièce pouvant l'être ou encore la capture de plusieurs pions adverses à la suite ne le sont pas.


La deuxième partie est l'implémentation d'un système de joueurs et d'agents autonomes. Il s'agit de la partie principale. Le système de joueur désigne l'ensemble des classes qui permettront à un joueur humain ou non de jouer. Les agents désignent quant à eux les différentes classes jouant de manière autonomes. Pour le moment, trois d'entre eux sont mis en place :
- RandomBot : un agent renvoyant un coup aléatoire à jouer
- MinMaxBot : un agent utilisant l'algorithme MinMax
- Albator : un agent utilisant l'algorithme MinMax et l'élagage alpha-beta

De plus, ces deux parties ont une conception orientée objet afin d'avoir une plus grande modularité, particulièrement au niveau des agents, qui suit cette structure générale :
#shell(```sh
└── code
    └── src
        ├── game_engine
        │    ├── board.py
        │    ├── game.py
        │    └── gui.py
        ├── main.py
        ├── players
        │    ├── bots
        │    │    ├── algorithms
        │    │    │    ├── alpha_beta.py
        │    │    │    └── minmax.py
        │    │    ├── bot.py
        │    │    └── training.py
        │    └── player.py
        └── utils.py
```)
- code/ : Dossier contenant le code et tout ce qui lui est relatif.
- src/ : Dossier contenant (principalement) tout le code en Python.
- game_engine/ : Module du gestion moteur de jeu.
- players/ : Module de gestion des joueurs (humains et bots).
- utils.py : Contiendra toutes les fonctions utilitaires.

Les outils utilisés sont/seront les suivants :
- Langage de programmation : Python 3 (≥ 3.10)
- Environnement de développement : Linux
- Gestionnaire de version : Git (hébergé sur Github)

Le plan de ce rapport suit ces deux grandes parties. Nous aborderons dans un premier temps l'implémentation du moteur de jeu pour finir sur le système de joueurs et d'agents.

#commented_text[
  Ce projet n'est pas finalisé de même que ce rapport. Certaines sources ne sont pas créditées, mais le seront prochainement. Merci de votre compréhension.
]



#heading_1("Première partie", subtitle: "Moteur de jeu")
#heading_2("Introduction")
Le moteur de jeu est le pilier fondamental de tout logiciel de jeu. Dans cette première phase de notre projet, nous avons élaboré un moteur de jeu pour permettre à la fois aux joueurs humains et aux agents autonomes de participer au jeu de dames. Ce rapport vise à expliciter l'importance de chaque fonctionnalité implémentée dans ce moteur de jeu, ainsi que les valeurs d'entrées et de sorties associées à chacun des composants.

#commented_text[
  Le moteur de jeu n'ayant pas été finalisé, cette partie du rapport n'est pour l'instant pas rédigée.
]


#heading_1("Deuxième partie", subtitle: "Système de joueurs et agents")
#heading_2("Généralités")
La deuxième partie concerne le système de joueurs et l'implémentation des agents.

Le système de joueur désigne l'ensemble des classes permettant à un joueur humain ou non de jouer. Il s'agira des classes de plus "bas niveau" qui interagiront avec le moteur de jeu. Elles viendront en quelque sorte se greffer par-dessus. Les agents désignent quant à eux les classes implémentées jouant de manière autonomes. Ils jouent un coup en suivant un algorithme donné. Plusieurs agents sont implémentés :
- RandomBot : un agent renvoyant un coup aléatoire à jouer
- MinMaxBot : un agent utilisant l'algorithme MinMax
- Albator : un agent utilisant l'algorithme MinMax et l'élagage alpha-beta

Le développement des agents MinMaxBot et Albator sont le cœur de cette partie. Il s'agit d'implémenter plusieurs algorithmes en utilisant le moins de modules externes possibles :
- #link("https://fr.wikipedia.org/wiki/Algorithme_minimax")[MinMax]: en théorie des jeux, c'est un algorithme visant à évaluer les différents coups possibles à jouer pour choisir le meilleur en supposant que le joueur adverse choisira le pire coup pour nous au prochain tour. Cela peut être modélisé via un arbre de décision à plusieurs nœuds.  Il est utilisé dans des jeux à deux joueurs, comme dans notre cas les Dames ou encore les échecs.
- #link("https://fr.wikipedia.org/wiki/%C3%89lagage_alpha-b%C3%AAta")[Élagage alpha-bêta] : en théorie des jeux et en intelligence artificielle, c'est un algorithme permettant de réduire le nombre de nœuds a évaluer par l'algorithme MinMax dans son arbre de décision.

Tout le code correspondant sera regroupé dans le fichier nommé "players". Voici sa structure :
#shell(```sh
    ├── players
    │    ├── bots
    │    │    ├── algorithms
    │    │    │    ├── alpha_beta.py
    │    │    │    └── minmax.py
    │    │    └── bot.py
    │    └── player.py
```)
- players/ : Module de gestion des joueurs (humains et bots).
- player.py : Implémentation de(s) classe(s) pour les joueurs humains.
  - bots/ : Sous module de gestion des bots.
    - bot.py : Fichier regroupant les classes principales de tous les futurs bots
    - algorithms/ : Sous module de gestion des algorithmes pour les bots
      - alpha_beta.py : Implémentation de l'élagage alpha-bêta
      - minmax.py : Implémentation de l'algorithme MinMax

La suite de cette partie est divisée en trois autres sous-parties :
- Le système de joueurs
- L'agent RandomBot
- L'agent MinMaxBot
- L'agent Albator


#heading_2("Le système de joueurs")
Le système de joueurs permet à n'importe quel joueur humain ou agent de jouer. Elle est en réalité assez minimaliste. Voici son diagramme « UML » simplifié :
#figure(
  block(
    image("/annexes/player_system_diagram.png", width: 100%), 
    stroke: 0.5pt,
    inset: 1em
  ),
  caption: "Diagramme UML simplifié du système de joueurs"
)

La classe BasePlayer est au cœur de ce système. Elle modélise un joueur quelconque avec quelques attributs de bases. Les classes HumanPlayer, RandomBot, MinMaxBot et Albator sont ses enfants et modélisent les joueurs suivants :
- HumanPlayer : un joueur humain qui entre ses coups via l'entrée standard
- RandomBot : l'agent qui joue un coup aléatoire parmi les coups possible à jouer
- MinMaxBot : l'agent qui joue en utilisant l'algorithme MinMax
- Albator : l'agent qui joue en utilisant l'algorithme MinMax et l'élagage alpha-beta

Tous les joueurs (donc la classe BasePlayer) possèdent comme attributs :
- nom (string) : le nom du joueur
- plateau (Board) : le plateau de jeu sur lequel joue le joueur
- valeur_pion(int) : la valeur du jouer, 1 pour les blancs et -1 pour les noirs

Et comme méthode :
- joue() :  fonction renvoyant le coup joué par le joueur

Ils sont construits en suivant ce principe : un coup est constitué de deux cases, la case d'origine et la case de destination. Prenons un exemple pour comprendre et considérons le coup du joueur blanc entouré en blanc :
#grid(columns: 2, rows: 20em, column-gutter: 1em,
  figure(
      block(
        image("/annexes/board_1.png"), 
        stroke: 3pt
      ),
      caption: "Exemple coup sur plateau de jeu"
    ),
  align(horizon)[
    #text()[
      La case d'origine (entouré en rouge) a pour coordonnées (5, 2), et la case de destination (4, 3) avec en x le numéro de la colonne et en y le numéro de la ligne.
    ]
  ]
)

\ La méthode "joue()" renvoie alors dans des couples les coordonnées de la case d'origine et de la case de destination : (x_origine, y_origine), (x_destination, y_destination).

Quant à l'exécution d'une partie, le système de joueur se comporte de la manière suivante :
- GameEngine appelle les méthodes "set_jeu(…)" des joueurs pour mettre à jour le joueur qu'ils sont et la plateau sur lequel ils vont jouer
- GameEngine appelle ensuite à tour de rôle jusqu'a la fin de la partie les méthodes "joue()" des joueurs et applique leur coup sur le plateau s'il est valide


#heading_2("L'agent RandomBot")
L'agent RandomBot est très simpliste : il se contente de retourner un coup au hasard parmi la liste des coups possibles sur le plateau. Ses chances, de remporter une partie sont donc très variables bien que très faible face à un quelconque joueur avec un minium de stratégie. Ses performances sont évidemment catastrophiques. Dans la prochaine version, il serait intéressant de mesurer sa probabilité de remporter une partie face à l'agent MinMaxBot et Albator.

Pour retourner un coup aléatoire, c'est-à-dire un couple (case_origine, case_destination) il choisit dans un premier temps une case d'origine aléatoire dans la liste des coups possible et ensuite une case de destination dans la liste des cases de destination de cette case d'origine.

Pour rappel, voici un exemple de la liste des coups possible accessible via la méthode get_coups_possible(joueur=…) de la classe Board pour ce plateau de jeu :
#grid(columns: 2, rows: 20em, column-gutter: 1em,
  figure(
      block(
        image("/annexes/board_2.png", width: 100%), 
        stroke: 3pt
      ),
      caption: "Exemple plateau de jeu"
    ),
  shell(```sh
{
  joueur_blanc :
  {
    (5, 0): [(4, 1)], 
    (5, 2): [(4, 1), (4, 3)], 
    (5, 4): [(4, 3), (4, 5)], 
    (5, 6): [(4, 5), (4, 7)]
  },
  joueur_noir :
  {
    (2, 1): [(3, 0), (3, 2)], 
    (2, 3): [(3, 2), (3, 4)], 
    (2, 5): [(3, 4), (3, 6)], 
    (2, 7): [(3, 6)] 
  }
}
```, adaptive: true),
)


#heading_2("L'agent MinMaxBot")
L'agent MinMaxBot implémente l'algorithme MinMax. Avant de rentrer dans le vif du sujet, voyons ce qu'est l'algorithme MinMax :

MinMax est un algorithme s'appliquant aux jeux à deux joueurs, à somme nulle et à informations complète. Un jeu à deux joueurs est simplement un jeu ou deux entités s'affrontent. Un jeu à somme nulle est un jeu où la somme des gains et des pertes de tous les joueurs est égale à 0. Cela signifie donc que le gain d'un joueur constitue obligatoirement une perte pour l'autre. Par exemple, dans une partie de morpion, si on définit la valeur de la grille à 1 si on gagne, -1 si on perd et 0 s'il y a égalité, ce jeu est à somme nulle (1 - 1 + 0 = 0). Les gains d'un joueur sont exactement l'opposé de ceux de l'autre joueur. Un jeu à informations complète, quant à lieu, est un jeu ou toutes les données sur la partie en cours sont entièrement accessible à tous les joueurs. Chaque joueur connaît précisément : ses possibilités d'action, les possibilités d'action de son adversaire et les gains résultants de ces actions. Par exemple, les échecs sont un jeu à informations complètes, car tous les joueurs peuvent savoir où se trouvent toutes les pièces. Au contraire, la bataille navale n'est pas un jeu à information complète, car un joueur ne sait pas où se trouvent les bateaux de son adversaire sur la grille.

L'algorithme MinMax, dû à #link("https://en.wikipedia.org/wiki/John_von_Neumann")[<NAME>ann], consiste à passer en revue toutes les possibilités pour un nombre limité de coups ou non, et à leur assigner une valeur qui prend en compte ses bénéfices et ceux de son adversaire. Le meilleur choix est alors celui qui minimise ses pertes tout en supposant que son adversaire cherche au contraire à maximiser nos pertes, d'où l'appellation MinMax.

Ceci peut être modélisé par un arbre de jeu constitué de nœuds joueur et opposant. Les nœuds s'alternent, de telle sorte qu'un nœud joueur a comme enfant un nœuds opposant, et inversement, que l'on obtient à partir des différents coups disponibles. Si un nœud n'a pas de enfant, c'est un nœud terminal, dit une "feuille". D'une certaine façon, cet arbre contient tous les coups possibles que l'on peut jouer à partir d'une position initiale. Si on a la possibilité d'explorer tout l'arbre, on peut déterminer s'il existe une stratégie gagnante pour un joueur. Si l'arbre est trop important on se contente normalement d'explorer le sous-arbre obtenu en tronquant l'arbre de jeu à une certaine profondeur, et en évaluant les nœuds tronqués à l'aide d'une fonction d'évaluation (fonction heuristique).

Voici un arbre de jeu associé à l'algorithme MinMax :
#figure(
  block(
    image("/annexes/diag_1.png", width: 100%), 
    stroke: 0.5pt,
    inset: 1em
  ),
  caption: "Arbre de jeu MinMax"
)

Cet arbre est composé de :
- D'un nœud racine représentant la configuration de jeu à analyser.
- De nœuds enfants qui représentent chacun une configuration du jeu atteignable depuis le nœud racine.
- De branches qui symbolisent les coups possibles dans une configuration données.
- De feuilles qui représentent chacune une configuration finale du jeu.

A chaque feuille (état/configuration finale du jeu) est associée une valeur :
- Positive (généralement) en cas de victoire.
- 0 en cas d'égalité.
- Négative (généralement) en cas de défaite.

Voici un exemple :
#figure(
  block(
    image("/annexes/diag_2.png", width: 100%), 
    stroke: 0.5pt,
    inset: 1em
  ),
  caption: "Exemple arbre de jeu MinMax"
)

Les nœuds C sont des feuilles et correspondent au joueur cherchant à minimiser ses pertes, le "minimizing player" appelé précédemment le "joueur". Leurs valeurs sont calculées par une fonction d'évaluation. Les nœuds B quant à eux, correspondent au joueur cherchant à maximiser les pertes de son adversaire, le "maximizing player", nommé avant l' "opposant".

Le "minimizing player" dans les sous-arbres contenant les nœuds C1 à C3 et C4 à C9 va choisir leur plus petite valeur et la faire remonter au nœud parent, respectivement B1 et B2.

Ensuite, le "maximizing player" va choisir la plus grande valeur entre ces deux nœuds et la faire remonter au nœud parent étant A1, le nœud racine.

Ainsi, il est possible de donner une valeur à un coup/un état/une position du jeu.

En pratique, explorer tous les sous-arbres d'un état du jeu prendrait dans le cas du jeu de Dames trop de temps. En conséquence, une fonction d'évaluation sera appliquée sur des positions non terminales. On considérera que plus la fonction d'évaluation est appliquée loin de la racine, meilleur est le résultat du calcul. C'est-à-dire qu'en examinant plus de coups successifs, nous supposons obtenir une meilleure approximation de la valeur théorique donc un meilleur choix de coup.

Comme dit précédemment, l'algorithme MinMax est très simple (d'un point de vue théorique) : on parcourt l'arbre du jeu jusqu'à un certain nœud (une certaine profondeur) ou jusqu'aux feuilles pour faire remonter à la racine la meilleur valeur du coup à jouer. Ceci de manière récursive.

Voici une implémentation en pseudo-code de cet algorithme avec une profondeur limitée :
#algo(
  title: "minmax",
  parameters: ("node", "depth", "maximizingPlayer",)
)[
  if $"depth" = 0$ or $"node is a terminal node"$:#i\
    return the heuristic value of node#d\
  if $"maximizingPlayer"$:#i\
    $"value" <- "−∞"$\
    for each child of node:#i\
      $"value" <- "max(value, minimax(child, depth - 1, FALSE))"$#d#d\
  else:#i\
    $"value" <- "+∞"$\
    for each child of node:#i\
      $"value" <- "min(value, minimax(child, depth - 1, TRUE))"$#d#d\
  return value
]

Revenons à notre agent MinMaxBot. L'implémentation de l'algorithme MinMax est en réalité gérée par la classe MinMax. Elle à comme attributs :
  - plateau (Board) : Le plateau de jeu à évaluer
  - joueur_actuel (int) : Le joueur qui doit actuellement jouer sur ce plateau
  - profondeur (int) : La hauteur du graphe des coups testés (le nombre de coups successifs à tester)

Et comme méthodes :
  - evaluate_node() : Retourne la valeur heuristique du plateau actuel (fonction d'évaluation)
  - #text("_")evaluate(...) : Retourne récursivement la valeur d'un plateau en suivant l'algorithme MinMax
  - evaluate() : Initialise l'appel de #text("_")evaluate et retourne sa valeur

La méthode evaluate_node() est la fonction d'évaluation. Elle a pour responsabilité d'évaluer l'état du plateau. Les performances de l'agent dépende grandement d'elle. Actuellement, elle se contente de faire la différence entre le nombre de pions blancs et le nombre de pions noirs. L'implémentation de sa futur nouvelle version est discuté deux chapitres plus bas. Dans cette situation, le joueur blanc cherché alors à maximiser sa valeur tandis que le joueur noir cherché à la minimiser.

La méthode #text("_")evaluate(…) quant à elle implémente l'algorithme MinMax de façon récursive en suivant son implémentation en pseudo-code vu ci-dessus.

Et enfin, la méthode evaluate() initialise simplement l'appel de la fonction #text("_")evaluate(...). Si l'attribut joueur_actuel vaut 1, alors #text("_")evaluate(…) est appelé avec le paramètre maximizing_joueur à True, et sinon à False. 

L'agent MinMaxBot fait donc appel à la classe MinMax pour calculer les valeurs de chaque coup possible sur le plateau. Voici le pseudo-code de sa méthode joue() :
#algo(
  title: "joue",
  parameters: ("plateau", "profondeur", "joueur_actuel",)
)[
  valeurs_coups $<-$ {}\
  for each coup in liste_coups_possible:#i\
    plateau.joue(case_origine=coup[0], case_destination=coup[1])\
    valeurs_coups[coup] $<-$ MinMax(plateau=plateau, profondeur=profondeur, joueur_actuel=joueur_actuel).evaluate()\
    plateau.joue(case_origine=coup[1], case_destination=coup[0])#d\
  if joueur_actuel is white:#i\
    return max(valeurs_coups)#d\
  else:#i\
    return min(valeurs_coups)  
]

Regardons un exemple d'extrait d'exécution de l'algorithme MinMax avec les paramètres depth à 3, un plateau de taille 4 et maximizing_player à True. Ceci correspond à un début de partie avec l'agent MinMax en tant que joueur blanc :
#figure(
  block(
    image("/annexes/minmax_1.png"), 
    stroke: 0.5pt,
    inset: 1em
  ),
  caption: "Exemple d'exécution MinMax"
)


#heading_2("L'agent Albator")
L'élagage alpha-bêta est un algorithme permettant de réduire le nombre de nœuds évalué par l'algorithme MinMax. Cela permet d'évaluer un arbre de jeu plus rapidement. Il élague ces branches qui n'ont pas besoin d'être recherchées, car il existe déjà un meilleur coup disponible. Dit autrement, l'élagage alpha-bêta permet de ne pas évaluer les nœuds enfants dont on peut penser, si la fonction d'évaluation est assez correcte, que leur valeur sera inférieur à celle du nœud parent déjà évalué. Il est important de comprendre qu'une fonction d'évaluation parfaite (comme par exemple au jeu des allumettes) ne demanderait pas de parcourir un arbre de jeu pour déterminer la valeur d'un coup. C'est justement parce qu'aucune fonction d'évaluation parfaite n'existe au jeu de Dames que l'emploi de l'algorithme MinMax et de l'élagage alpha-bêta est pertinent.

L'élagage alpha-bêta ajoute deux paramètre à l'algorithme MinMax :
  - Alpha : La meilleure valeur que le "maximizing_player" peut actuellement garantir à cette profondeur ou au-dessus.
  - Bêta : la meilleure valeur que le "minimizing_player" peut actuellement garantir à cette profondeur ou au-dessus.

Voici la fonction MinMax avec l'élagage alpha-bêta implémenté en pseudo-code :
#algo(
  title: "alphabeta",
  parameters: ("node", "depth", "maximizingPlayer", "alpha", "beta",)
)[
  if depth = 0 or node is a terminal node:#i\
    return the heuristic value of node#d\
  if maximizingPlayer:#i\
    best_value $<-$ −∞\
    for each child of node:#i\
      value $<-$ alphabeta(child, depth - 1, FALSE, alpha, beta)\
      best_value = max(best_value, value)\
      alpha = max(alpha, best_value)\
      if beta <= alpha:#i\
        break#d#d\
    return best_value#d\
  else:#i\
    best_value $<-$ +∞\
    for each child of node:#i\
      value $<-$ alphabeta(child, depth - 1, TRUE, alpha, beta)\
      best_value = min(best_value, value)\
      alpha = min(alpha, best_value)\
      if beta <= alpha:#i\
        break#d#d\
    return best_value#d\
]

Voici un exemple :
#figure(
  block(
    image("/annexes/alphabeta_1.png"), 
    stroke: 0.5pt,
    inset: 1em
  ),
  caption: "Exemple AlphaBeta n°1"
)

  - L'appel initial commence par A. La valeur d'alpha est ici -∞ et la valeur de beta est +∞. Ces valeurs sont transmises aux nœuds suivants de l'arborescence. En A, le "maximizing_player" doit choisir max de B et C, donc A appelle B en premier.
  - En B dit, le "minimizing_player" doit choisir min de D et E et appelle donc D en premier.
  - En D, il regarde son enfant à gauche qui est un nœud feuille. Ce nœud renvoie une valeur de 3. Maintenant, la valeur de alpha en D est max( -∞, 3) qui est 3. 
  - Pour décider s'il vaut la peine de regarder son nœud droit ou non, il vérifie la condition beta <= alpha. C'est faux puisque beta = +∞ et alpha = 3. Il continue donc la recherche. 
  - D regarde maintenant son nœud enfant droit qui renvoie une valeur de 5. À D, alpha = max(3, 5) qui est 5. Maintenant, la valeur du node D est 5.
  - D renvoie une valeur de 5 à B. À B, beta = min(+∞, 5) qui est 5. Le "minimizing_player" est garanti maintenant une valeur de 5 ou moins. B appelle E pour voir s'il peut obtenir une valeur inférieure à 5.
  - En E, les valeurs d'alpha et de bêta ne sont pas -∞ et +∞ mais plutôt -∞ et 5 respectivement, car la valeur de bêta a été modifiée en B. C'est ce que B a transmis à E.
  - Maintenant E regarde son enfant à gauche qui vaut 6. À E, alpha = max(-∞, 6) qui est 6. Ici la condition devient vraie. beta vaut 5 et alpha vaut 6. Donc beta <= alpha est vrai. Par conséquent, il s'arrête et E renvoie 6 à B.
  - Notez que la valeur de l'enfant à droite de E n'a pas d'importance. Cela aurait pu être +∞ ou -∞, cela n'aurait toujours pas d'importance. Nous n'avons même jamais eu à le regarder car le "minimizing_player" était garanti d'une valeur de 5 ou moins. Ainsi, dès que le "maximizing_player" a valut 6, le "minimizing_player" ne viendrait jamais de cette façon car il peut obtenir un 5 sur le côté gauche de B. De cette façon, nous n'avons pas à regarder ce 9 et donc à gagner du temps de calcul.
  - E renvoie une valeur de 6 à B. À B, beta = min(5, 6) qui est 5. La valeur du node B est également 5.

Jusqu'à présent, voici à quoi ressemble notre arbre de jeu. Le 9 est barré car il n'a jamais été calculé :
#figure(
  block(
    image("/annexes/alphabeta_2.png"), 
    stroke: 0.5pt,
    inset: 1em
  ),
  caption: "Exemple AlphaBeta n°2"
)

  - B renvoie 5 à A. À A, alpha = max(-∞, 5) qui est 5. Maintenant, le "maximizing_player" est garanti d'avoir une valeur de 5 ou plus. A appelle maintenant C pour voir s'il peut obtenir une valeur supérieure à 5.
  - À C, alpha = 5 et beta = +∞. C appelle F .
  - À F , alpha = 5 et beta = +∞. F regarde son nœud enfant à gauche qui est un 1. alpha = max(5, 1) qui est toujours 5. 
  - F regarde son nœud enfant à droite qui est un 2. La meilleure valeur de ce nœud est donc 2. Alpha reste toujours 5.
  - F renvoie une valeur de 2 à C. À C , bêta = min(+∞, 2). La condition beta <= alpha devient vraie quand beta = 2 et alpha = 5. Donc la recherche s'arrête et n'a même pas besoin de calculer tout le sous-arbre de G.
  - L' "intuition" derrière cette rupture est qu'en C, le "minimizing_player" était garanti d'avoir une valeur de 2 ou moins. Mais le "maximizing_player" était déjà assuré d'avoir une valeur de 5 s'il choisissait B. Alors pourquoi le "maximizing_player" choisirait-il jamais C et obtiendrait-il une valeur inférieure à 2 ? Encore une fois, vous pouvez voir que peu importaient ces 2 dernières valeurs. Nous avons également économisé beaucoup de calculs en sautant tout un sous-arbre.
  - C renvoie maintenant une valeur de 2 à A. Par conséquent, la meilleure valeur en A est max(5, 2) qui est un 5.
  - Par conséquent, la valeur optimale que le "maximizing_player" peut obtenir est 5.

Voici à quoi ressemble notre arbre de jeu final. Comme vous pouvez le voir, G a été barré car il n'a jamais été calculé :
#figure(
  block(
    image("/annexes/alphabeta_3.png"), 
    stroke: 0.5pt,
    inset: 1em
  ),
  caption: "Exemple AlphaBeta n°3"
)


#heading_2("Fonction d'évaluation")
Nous avons vu précédemment que les algorithmes MinMax et l'élagage AlphaBeta avaient besoin de connaître la valeur d'un état du plateau. Si le nombre de coups possible est assez réduit, il est possible d'explorer tout l'arbre de jeu jusqu'aux feuilles pour savoir si un coup mène à une victoire, une égalité ou une défaite. Cependant, dans notre cas le nombre de possibilités est trop élevé, il n'est pas possible d'atteindre les feuilles dans un temps raisonnable. Seul une partie de l'arbre de jeu est explorée et les valeurs de ces derniers nœuds sont calculé à l'aide d'une fonction d'évaluation (aussi appelée fonction heuristique).

Une fonction d'évaluation est un algorithme qui fournit rapidement (en temps polynomial) une solution, pas nécessairement optimale, pour un problème d'optimisation. C'est le contraire d'un algorithme exact qui trouve une solution optimale pour un problème donné. En effet, le jeu de Dames dans sa variante Brésilienne n'a jamais encore été résolu au contraire de sa #link("https://citeseerx.ist.psu.edu/pdf/208122e877a967222093afa80f0f4c318f3ae63e")[variante Américaine] qui possède un algorithme de résolution exact.

Cette fonction sera la différence de la combinaison linéaire des différents paramètres de chaque joueurs suivants :
  + Le nombre de pions
  + Le nombre de pions protégé (non prenable par l'adversaire)
  + Le nombre de pions déplaçable
  + La distance cumulée des pions à la ligne de promotion (ligne la plus haute)
  + Le nombre de cases occupés sur sa ligne de promotion (ligne la plus basse)
  + Nombre de pions défensifs (ceux situés dans les deux rangées les plus basses)
  + Nombre de pions attaquants (ceux situés dans les deux rangées les plus hautes)
  + Nombre de pions positionnés au centre (sur les deux lignes centrales)

Le résultat de cette fonction est un nombre entier. Voici sa forme :
#algo(line-numbers: false)[
(a#sub[1] · param#sub[1] + ... + a#sub[j] · param#sub[j])#sub[joueur_blanc] - (a#sub[1] · param#sub[1] + ... + a#sub[j] · param#sub[j])#sub[joueur_noir]
]
Les paramètres param#sub[1], ..., param#sub[j] sont choisi parmi les paramètres ci-dessus, et nous utiliserons un algorithme génétique pour générer les coefficients a#sub[1], ..., a#sub[j].

Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle et l'appliquent à une population de solutions potentielles au problème donné. La solution est approchée par « bonds » successifs. Chaque bond correspond à une génération.

Pour trouver la meilleur configuration des coefficients ci-dessus, des bots utilisant l'algorithme MinMax et l'élagage AlphaBeta s'affronteront les uns contre les autres à tour de rôle.

Les 50% des meilleurs de chaque génération (ceux ayant le plus de manches gagnées) seront conservés, et se reproduiront entre eux de la façon suivante avec en plus une chance de 15% de muter aléatoirement de 20% (qu'un coefficient augmente ou diminue de 20%) :
#figure(
  block(
    image("/annexes/genetic_reproduction.png", width: 70%), 
    stroke: 0.5pt,
    inset: 1em,
    width: 100%
  ),
  caption: "Genetic reproduction"
)

La fonction d'évaluation est implémentée dans le module "src/players/bots/algorithms/heuristic.py" dans la classe Heuristic et la gestion de l'évolution génétique dans la classe Train dans le fichier "src/players/bots/training.py".

Il n'a pas été possible de faire de tests statistiques à cause du temps pris pour calculer ne serait-ce rien qu'une génération et de contrainte matériel. En effet, une partie sur un plateau de 8x8 dure environ 150 secondes. Calculer une génération de 8 bots prendrait alors environ 2h20...


#heading_2("Conclusion", break_ordering: true)
Ce projet aura été un défi tout au long de l'année. L'implémentation d'algorithmes tels que MinMax ou l'évolution génétique auront été très intéressants. Ils sont une belle introduction à la résolution de jeux par les machines.

Cette version du rapport à été rédigé avec #link("https://typst.app/")[Typst], une alternative à Latex en Rust. Pour suivre l'évolution, référez-vous au repo Git.



#heading_2("Annexes et bibliographie", break_ordering: true)
Pour parvenir à implémenter ces algorithmes nous avons plusieurs ressources à notre disposition (liste non-exhaustive) :
  - #link("https://en.wikipedia.org/wiki/Minimax", text("Wikipédia_Minimax_[en]"))
  - #link("https://fr.wikipedia.org/wiki/Algorithme_minimax", text("Wikipédia_MinMax_[fr]"))
  - #link("https://fr.wikipedia.org/wiki/Théorème_du_minimax_de_von_Neumann", text("Wikipédia_Théorème_MiniMax_von_Neumann"))
  - #link("https://www.youtube.com/watch?v=SLgZhpDsrfc", text("Minimax: How Computers Play Games"))
  - #link("https://www.youtube.com/watch?v=l-hh51ncgDI", text("Algorithms Explained - minimax and alpha-beta pruning"))
  - #link("https://www.youtube.com/watch?v=zp3VMe0Jpf8", text("Minimax with Alpha Beta Pruning"))
  - #link("https://www.youtube.com/watch?v=STjW3eH0Cik", text("MIT - Minimax, and Alpha-Beta"))
  - #link("https://www.enseignement.polytechnique.fr/profs/informatique/Jean-Christophe.Filliatre/14-15/MAN_Caml/td6/index.html", text("Polytechnique - Jeux sans hasard et modules"))
  - #link("https://www.di.ens.fr/~granboul/enseignement/mmfai/algo2003-2004/tp5/", text("ENS - Les algorithmes MiniMax et alpha-beta"))
  - #link("https://lucidar.me/fr/algorithmic/files/ANA_CM5__-_Algorithme_MinMax.pdf", text("Lucidarme - Algorithme MinMax"))
  - #link("https://sifflez.org/misc/tronbot/index.html", text("University of Waterloo - Tron bot"))
  - #link("https://stacklima.com/algorithme-minimax-en-theorie-des-jeux-ensemble-4-elagage-alpha-beta/", text("Stacklima (geekforgeek traduction) - Elagage Alpha-Beta"))
  - #link("https://fr.wikipedia.org/wiki/Élagage_alpha-bêta#Améliorations_possibles", text("Wikipédia_Elagage_Alpha-Beta_[fr]"))
  - #link("https://en.wikipedia.org/wiki/Alpha-beta_pruning", text("Wikipédia_Alpha-beta_pruning_[en]"))
  - #link("https://pages.mini.pw.edu.pl/~mandziukj/PRACE/es_init.pdf", text("Evolutionary-based heuristic generators for checkers and give-away checkers"))
  - #link("https://papersdb.cs.ualberta.ca/%7Epapersdb/uploaded_files/590/paper_ijcai05checkers.pdf", text("Solving Checkers"))
  - #link("https://en.wikipedia.org/wiki/Genetic_algorithm", text("Wikipedia_Genetic_algorithm_[en]"))
  - ...
