2.4 KiB
Rapport Jeu de Nim
Membres du groupe : Axel Pietrois et Simon Saye Babu
Avancement
La version de base de Minimax a été implémentée pour rappel voici son fonctionnement :
Le joueur1 va faire un exploreMax de ces coups possible, pour chaque coup, si celui ci n'est pas final la fonction exploreMin est lancé sur celui ci. Ensuite exploreMax sur les choix de n+1 ainsi de suite, jusqu'a que l'un des joueur tombe sur un coups final ce qui garantie la victoire/la perte de coup.
Dans exploreMax, si il y a une possibilité de perdre dans une branche elle vaudra -1 si elle est obligatoirement victorieuse elle vaudra 1 et inversement pour exploreMin.
exploreMin represente le meilleur choix du joueur2 (qui est le pire choix pour joueur1 d'ou exploreMIN).
Version avec carnet
Cette optimisation utilise le système de carnet demandé afin de vérifier qu'une seule fois chaque situation. Ainsi, l'algorithme vérifie a chaque fois exactement n*6-17 noeuds, n étant le nombre d'allumettes au démarrage du jeu. Le carnet existe sous la forme de deux tableaux d'entiers, un par joueur. Chaque joueur à n-1 situations car le Joueur 1 ne peut pas se retrouver avec n-1 allumette et le Joueur 2 ne peut pas avoir n allumettes La limite du nombre d'allumettes est de 33736 (testé grace au bloc try/catch lançant en batch). Cependant lorsque le programme est lancé avec une valeur simple, la limite est beaucoup plus basse.
Test et comparaison
Version non optimisée
5 allumettes : Perdu ; Temps écoulé (ms) : 3 ; Compteur = 15 11 allumettes : Gagné ; Temps écoulé (ms) : 0 ; Compteur = 600 17 allumettes : Perdu ; Temps écoulé (ms) : 0 ; Compteur = 23249 42 allumettes : TimeOut au bout de 100 secondes
Version optimisée
5 allumettes : Perdu ; Temps écoulé (ms) : 4 ; Compteur = 15 11 allumettes : Gagné ; Temps écoulé (ms) : 0 ; Compteur = 228 17 allumettes : Perdu ; Temps écoulé (ms) : 0 ; Compteur = 5601 42 allumettes : Gagné ; Temps écoulé (ms) : 7089 ; Compteur = 659108914 100 allumettes : TimeOut au bout de 100 secondes
Version avec carnet
5 allumettes : Perdu ; Temps écoulé (ms) : 3 ; Compteur = 13 11 allumettes : Gagné ; Temps écoulé (ms) : 0 ; Compteur = 49 17 allumettes : Perdu ; Temps écoulé (ms) : 0 ; Compteur = 85 42 allumettes : Gagné ; Temps écoulé (ms) : 0 ; Compteur = 235 100 allumettes : Gagné ; Temps écoulé (ms) : 0 ; Compteur = 583
Graphique
