Ce fichier repertorie et explique les code qui se trouve dans ce fichier.
MiniMax_versionBase
Ce code est la version de base vu en cours du jeu de Nim. Il fonctionne et donne bien -1 en resultat.
Tableau d'états visité
| n (allumettes) | Nombre de nœuds explorés |
|---|---|
| 5 | 46 |
| 7 | 157 |
| 13 | 6 094 |
| 19 | 235 957 |
| 31 | 353 693 521 |
MiniMax_versionprofondeur
Ce code est une version optimisé de la version vu en cours du jeu de Nim. Celui-ci a un autre paramètre qui est profoncdeur qui limite les calcul et donne une approximation. Il fonctionne et donne bien 0 en resultat si la profonceur est inférieur à 6 et si elle est de 6 ou plus elle donne bien -1 car 6 est la profondeur maximal de l'abre du jeu de Nim.
Tableau d'états visité
| Nombre d’allumettes | Profondeur max | Nombre de nœuds (états) |
|---|---|---|
| 5 | 6 | 46 |
| 7 | 8 | 157 |
| 13 | 14 | 6 094 |
| 19 | 20 | 235 957 |
| 31 | 32 | 353 693 521 |
MiniMax_versionarret
Ce code est une version optimisé de la version vu en cours du jeu de Nim. Celui-ci a une autre condition d'arret qui limite les calcul qui est donné par un chemin où il y a une victiore ou une défaite. Il fonctionne et donne bien -1 en resultat si le nombre d'allumettes est de 5 et si elle est de 4, elle donne bien 1.
Tableau d'états visité
| Nombre d’allumettes | Nœuds visités |
|---|---|
| 5 | 36 |
| 7 | 74 |
| 13 | 1 828 |
| 19 | 25 610 |
| 31 | 8 784 458 |
MiniMax_versionMemoisation
Ce code est une version optimisé de la version vu en cours du jeu de Nim. Celui-ci garde en mémoire avec un tableau pour le min et le max pour éviter de recalculer des sous-arbres déjà vu précédemment. Il fonctionne avec les tests effectué.
Tableau d'états visité
| Nombre d’allumettes | Nœuds distincts (états) visités |
|---|---|
| 5 | 25 |
| 7 | 37 |
| 13 | 73 |
| 19 | 109 |
| 31 | 181 |
MiniMax_version_AlphaBeta
Ce code est une version optimisé de la version vu en cours du jeu de Nim. Celui-ci permet de coupé des partie de l'arbre de jeux, donc de visité moins de noeuds. Il fonctionne avec les tests effectué.
Tableau d'états visité
| Nombre d’allumettes | Nœuds visités |
|---|---|
| 5 | 41 |
| 7 | 107 |
| 13 | 2 244 |
| 19 | 31 898 |
| 31 | 9 523 124 |
Différence de noeud visité entre MiniMax_version_AlphaBeta et MiniMax_versionBase
La différence entre le nombre de noeuds visité car alpha_beta ne regarde pas tous les sous-arbres, contrairement à la version de base, cela se voit surtout avec une grande longueur de l'arbre de jeux.
Nombre d'états visités dans chaque version
| Version | Paramètres initiaux | États explorés |
|---|---|---|
| MiniMax_versionBase | nbr_allumettes = 5 |
46 |
| MiniMax_versionarret | nbr_allumettes = 5 |
36 |
| MiniMax_versionprofondeur | nbr_allumettes = 5, profondeur=6 |
46 |
| MiniMax_versionMemoisation | nbr_allumettes = 5 |
25 |
| MiniMax_version_AlphaBeta | nbr_allumettes = 5 |
41 |