95 lines
2.2 KiB
Java
95 lines
2.2 KiB
Java
|
|
public class MiniMaxOptiCarnet {
|
|
|
|
|
|
// J'aime bien les majuscules
|
|
public static boolean True = true;
|
|
public static boolean False = false;
|
|
|
|
/*
|
|
Variable donnant le nombre d'allumettes au départ du jeu (remplacée par un argument en ligne de commande)
|
|
*/
|
|
public static int[] tests = {5,11,17,42,100};
|
|
|
|
private static int[] J1;
|
|
private static int[] J2;
|
|
|
|
static long debut;
|
|
private static int compteur;
|
|
private static int limite;
|
|
|
|
public static void main(String[] args) {
|
|
limite = 0;
|
|
try {
|
|
for(int n: tests) {
|
|
J1 = new int[limite + 1];
|
|
J2 = new int[limite + 1];
|
|
compteur = 0;
|
|
debut = System.nanoTime();
|
|
compteur = 0;
|
|
System.out.print(n + " allumettes : ");
|
|
int s = Nim(n);
|
|
if (s == 1) {
|
|
System.out.print("Gagné ;");
|
|
} else {
|
|
System.out.print("Perdu ;");
|
|
}
|
|
long fin = System.nanoTime();
|
|
System.out.print(" Temps écoulé (ms) : "+((fin-debut)/1000000)+" ;");
|
|
System.out.println(" Compteur = " + compteur);
|
|
}
|
|
} catch (StackOverflowError e){
|
|
}
|
|
System.out.println(limite-1);
|
|
}
|
|
|
|
public static int Nim(int n){
|
|
return exploreMax(n);
|
|
}
|
|
|
|
/*
|
|
Vérifie les issues des coups jouables par le J1 et renvoie 1 si le J1 a une opportunité de gagner a coup sur
|
|
Vérifie si le coup a déjà été joué avant de continuer l'arbre, si il verifie l'arbre il ajoute au tableau
|
|
*/
|
|
public static int exploreMax(int allumette) {
|
|
compteur++;
|
|
if (J1[allumette] != 0){
|
|
return J1[allumette];
|
|
}
|
|
int n = allumette;
|
|
int max = -1;
|
|
for (int i=0;allumette>1&&i<3;i++){
|
|
allumette--;
|
|
int v=exploreMin(allumette);
|
|
if (v > max){
|
|
max = v;
|
|
}
|
|
}
|
|
J1[n] = max;
|
|
return max;
|
|
}
|
|
|
|
|
|
/*
|
|
Vérifie les issues possibles des coups du J2 et renvoie -1 si le J2 a une opportunité de gagner a coup sur
|
|
Vérifie si le coup a déjà été joué avant de continuer l'arbre, si il verifie l'arbre il ajoute au tableau
|
|
*/
|
|
public static int exploreMin(int allumette){
|
|
compteur++;
|
|
if (J2[allumette] != 0){
|
|
return J2[allumette];
|
|
}
|
|
int n = allumette;
|
|
int min = 1;
|
|
for (int i=0;allumette>1&&i<3;i++){
|
|
allumette--;
|
|
int v=exploreMax(allumette);
|
|
if (v < min){
|
|
min = v;
|
|
}
|
|
}
|
|
J2[n] = min;
|
|
return min;
|
|
}
|
|
|
|
} |