public class MiniMaxSansOpti {

    public static int[] tests = {5,11,17,42,100};

    private static int compteur;

    static long debut;

    public static void main(String[] args) {

        for(int n: tests) {
            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);
        }
    }

    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
     */
    public static int exploreMax(int allumette) {
        compteur++;
        if ((System.nanoTime()-debut)/1000000 > 100000 ){
            System.out.println("TimeOut au bout de 100 secondes");
            System.exit(-1);
        }
        int max = -1;
        for (int i=0;allumette>1&&i<3;i++){
            allumette--;
            int v=exploreMin(allumette);
            if (v > max){
                max = v;
            }

        }
        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
     */
    public static int exploreMin(int allumette){
        compteur++;
        int min = 1;
        for (int i=0;allumette>1&&i<3;i++){
            allumette--;
            int v=exploreMax(allumette);
            if (v<min){
                min = v;
            }
        }
        return min;
    }
}