23 lines
1.4 KiB
Markdown
23 lines
1.4 KiB
Markdown
# 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.
|
|
|
|
|