BUT3JeuR5.5

Jeu de Nim : MiniMax

Utilisation de deux fonctions récursives pour dire si le premier joueur peut gagner à coup sûr au jeu de Nim +1 = J1 peut Gagner à coup sur -1 = J1 peut perdre à coup sur

ExplorationMax -> Tour du joueur 1, vérifie si il a un coup permettant de gagner à coup sûr ExplorationMin -> Tour du joueur 2, vérifie si le joueur 2 perd à coup sûr

Optimisations faites : Si le joueur 1 possède un coup permettant de gagner à coup sûr, la fonction remontera directement pour finir la fonction.

Optimisation en utilisant le systeme de cahier (MiniMaxOptiCarnet.java)

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, étant à 9099 (sur ma machine). Cette limite est causée par la limite de récursivité de Java, causant une StackOverflowError.