const int nbLignes = 6;             // taille du plateau de jeu : lignes
const int nbColonnes = 7;           // taille du plateau de jeu : colonnes (26 max)              
const int nbAlignementGain = 4;     // combien de pions doit on aligner pour gagner 
const int profondeurAnalyse = 4;    // exploration de l'arbre des coups possibles

long tableDesPuissanceDe10[nbAlignementGain + 1];

enum {DEBUT, JOUEUR, AI, FIN } etat = DEBUT;

char emplacement[nbLignes][nbColonnes];

void raz() {
  for (int c = 0; c < nbColonnes; c++)
    for (int l = 0; l < nbLignes; l++)
      emplacement[l][c] = ' ';
}

void setup() {
  for (int i = 0; i < nbAlignementGain + 1; i++) tableDesPuissanceDe10[i] = (long) pow(10, i);
  randomSeed(analogRead(A0));
  Serial.begin(115200);
  Serial.println(" ~~~~~~~~ PUISSANCE 4 ~~~~~~~~");
  Serial.println("");
}

void loop() {
  switch (etat) {
    case DEBUT:
      raz();
      if (random(100) > 50) {
        afficher_puissance();
        Serial.println(F("Vous jouez en premier."));
        etat = JOUEUR;
      } else {
        Serial.print(F("Je commence → "));
        etat = AI;
      }
      break;

    case JOUEUR:
      { // Tour du joueur
        if (Serial.available() > 0) {
          char input = toupper(Serial.read());
          if (input >= 'A' && input < ('A' + nbColonnes)) {
            int colonne = input - 'A';
            int ligne;
            for (ligne = nbLignes - 1; ligne >= 0; ligne--) {
              if (emplacement[ligne][colonne] == ' ') {
                break;
              }
            }

            if (ligne >= 0) {
              emplacement[ligne][colonne] = 'X';
              afficher_puissance();

              if (verifier_victoire(ligne, colonne, 'X')) {
                Serial.println(F("Vous avez gagné !"));
                etat = FIN;
              } else {
                etat = AI;
              }
            } else {
              Serial.print(input);
              Serial.println(F(" → impossible, colonne pleine."));
            }
          } else {
            if (input != '\r' && input != '\n') {
              Serial.print(input);
              Serial.println(F(" → Colonne invalide."));
            }
          }
        }
        break;
      }

    case AI:
      { // Tour de l'IA

        Serial.print(F("\nJe réfléchis..."));
        int colonne = meilleurCoup();
        Serial.print(F(" → "));
        Serial.write('A' + colonne);
        Serial.println();

        int ligne;
        for (ligne = nbLignes - 1; ligne >= 0; ligne--) {
          if (emplacement[ligne][colonne] == ' ') {
            break;
          }
        }
        emplacement[ligne][colonne] = 'O';

        if (verifier_victoire(ligne, colonne, 'O')) {
          afficher_puissance();
          Serial.println(F("J'ai gagné !"));
          etat = FIN;
        } else {
          etat = JOUEUR;
          afficher_puissance();
          Serial.println(F("C'est à vous !"));
        }
        break;
      }

    case FIN:
      Serial.println(F("\n\n-----------------------------\nAllez, On refait une partie !\n\n"));
      etat = DEBUT;
      break;
  }


}


void afficher_puissance() {
  Serial.print("┌");
  for (int j = 0; j < nbColonnes - 1; j++) {
    Serial.write("───┬");
  }
  Serial.println("───┐");

  Serial.print("│ ");
  for (int j = 0; j < nbColonnes; j++) {
    Serial.write('A' + j);
    Serial.print(" │ ");
  }
  Serial.println();

  Serial.print("├");
  for (int j = 0; j < nbColonnes - 1; j++) {
    Serial.write("───┼");
  }
  Serial.println("───┤");

  for (int i = 0; i < nbLignes; i++) {
    Serial.print("│ ");
    for (int j = 0; j < nbColonnes; j++) {
      Serial.print(emplacement[i][j]);
      Serial.print(" │ ");
    }
    Serial.println();
  }

  Serial.print("└");
  for (int j = 0; j < nbColonnes - 1; j++) {
    Serial.write("───┴");
  }
  Serial.println("───┘");

  Serial.flush(); // on s'assure que tout est affiché

}

bool verifier_victoire(int ligne, int colonne, char symbol) {
  char joueurGagnant = symbol;
  int compte = 0;

  // Vérification horizontale
  for (int i = -nbAlignementGain + 1; i <= nbAlignementGain - 1; i++) {
    if (colonne + i >= 0 && colonne + i < nbColonnes && emplacement[ligne][colonne + i] == joueurGagnant) {
      compte++;
      if (compte >= nbAlignementGain) return true;
    } else {
      compte = 0;
    }
  }

  // Vérification verticale
  compte = 0;
  for (int i = -nbAlignementGain + 1; i <= nbAlignementGain - 1; i++) {
    if (ligne + i >= 0 && ligne + i < nbLignes && emplacement[ligne + i][colonne] == joueurGagnant) {
      compte++;
      if (compte >= nbAlignementGain) return true;
    } else {
      compte = 0;
    }
  }

  // Vérification diagonale (bas droite)
  compte = 0;
  for (int i = -3; i <= 3; i++) {
    if (ligne - i >= 0 && ligne - i < nbLignes && colonne + i >= 0 && colonne + i < nbColonnes && emplacement[ligne - i][colonne + i] == joueurGagnant) {
      compte++;
      if (compte >= nbAlignementGain) return true;
    } else {
      compte = 0;
    }
  }

  // Vérification diagonale (bas gauche)
  compte = 0;
  for (int i = -3; i <= 3; i++) {
    if (ligne - i >= 0 && ligne - i < nbLignes && colonne - i >= 0 && colonne - i < nbColonnes && emplacement[ligne - i][colonne - i] == joueurGagnant) {
      compte++;
      if (compte >= nbAlignementGain) return true;
    } else {
      compte = 0;
    }
  }

  return false;
}

int meilleurCoup() {
  int meilleurColonne = -1;
  long meilleurScore = -1000;

  for (int colonne = 0; colonne < nbColonnes; colonne++) {
    if (emplacement[0][colonne] == ' ') {
      int ligne;
      for (ligne = nbLignes - 1; ligne >= 0; ligne--) {
        if (emplacement[ligne][colonne] == ' ') {
          break;
        }
      }
      emplacement[ligne][colonne] = 'O';
      long score = minimax(profondeurAnalyse, false, -1000, 1000);
      emplacement[ligne][colonne] = ' ';

      if (score > meilleurScore) {
        meilleurScore = score;
        meilleurColonne = colonne;
      }
    }
  }

  return meilleurColonne;
}

long minimax(int profondeur, bool estMax, long alpha, long beta) {
  if (profondeur == 0 || verifier_match_nul()) {
    return evaluer();
  }

  if (estMax) {
    long meilleurScore = -1000;

    for (int colonne = 0; colonne < nbColonnes; colonne++) {
      if (emplacement[0][colonne] == ' ') {
        int ligne;
        for (ligne = nbLignes - 1; ligne >= 0; ligne--) {
          if (emplacement[ligne][colonne] == ' ') {
            break;
          }
        }
        emplacement[ligne][colonne] = 'O';
        long score = minimax(profondeur - 1, false, alpha, beta);
        emplacement[ligne][colonne] = ' ';

        meilleurScore = max(meilleurScore, score);
        alpha = max(alpha, meilleurScore);

        if (beta <= alpha) {
          break;
        }
      }
    }

    return meilleurScore;
  } else {
    long meilleurScore = 1000;

    for (int colonne = 0; colonne < nbColonnes; colonne++) {
      if (emplacement[0][colonne] == ' ') {
        int ligne;
        for (ligne = nbLignes - 1; ligne >= 0; ligne--) {
          if (emplacement[ligne][colonne] == ' ') {
            break;
          }
        }
        emplacement[ligne][colonne] = 'X';
        long score = minimax(profondeur - 1, true, alpha, beta);
        emplacement[ligne][colonne] = ' ';

        meilleurScore = min(meilleurScore, score);
        beta = min(beta, meilleurScore);

        if (beta <= alpha) {
          break;
        }
      }
    }

    return meilleurScore;
  }
}

long evaluer() {
  long score = 0;
  score += evaluer_lignes();
  score += evaluer_colonnes();
  score += evaluer_diagonales();
  return score;
}

long evaluer_lignes() {
  long score = 0;

  for (int ligne = 0; ligne < nbLignes; ligne++) {
    for (int colonne = 0; colonne <= nbColonnes - nbAlignementGain; colonne++) {
      int countO = 0;
      int countX = 0;
      for (int k = 0; k < nbAlignementGain; k++) {
        if (emplacement[ligne][colonne + k] == 'O') {
          countO++;
        } else if (emplacement[ligne][colonne + k] == 'X') {
          countX++;
        }
      }
      score += evaluer_case(countO, countX);
    }
  }

  return score;
}

long evaluer_colonnes() {
  long score = 0;

  for (int colonne = 0; colonne < nbColonnes; colonne++) {
    for (int ligne = 0; ligne <= nbLignes - nbAlignementGain; ligne++) {
      int countO = 0;
      int countX = 0;
      for (int k = 0; k < nbAlignementGain; k++) {
        if (emplacement[ligne + k][colonne] == 'O') {
          countO++;
        } else if (emplacement[ligne + k][colonne] == 'X') {
          countX++;
        }
      }
      score += evaluer_case(countO, countX);
    }
  }

  return score;
}

long evaluer_diagonales() {
  long score = 0;

  // Diagonales vers le bas à droite
  for (int ligne = 0; ligne <= nbLignes - nbAlignementGain; ligne++) {
    for (int colonne = 0; colonne <= nbColonnes - nbAlignementGain; colonne++) {
      int countO = 0;
      int countX = 0;
      for (int k = 0; k < nbAlignementGain; k++) {
        if (emplacement[ligne + k][colonne + k] == 'O') {
          countO++;
        } else if (emplacement[ligne + k][colonne + k] == 'X') {
          countX++;
        }
      }
      score += evaluer_case(countO, countX);
    }
  }

  // Diagonales vers le bas à gauche
  for (int ligne = 0; ligne <= nbLignes - nbAlignementGain; ligne++) {
    for (int colonne = nbAlignementGain - 1; colonne < nbColonnes; colonne++) {
      int countO = 0;
      int countX = 0;
      for (int k = 0; k < nbAlignementGain; k++) {
        if (emplacement[ligne + k][colonne - k] == 'O') {
          countO++;
        } else if (emplacement[ligne + k][colonne - k] == 'X') {
          countX++;
        }
      }
      score += evaluer_case(countO, countX);
    }
  }

  return score;
}

long evaluer_case(int countO, int countX) {
  if (countX == 0) {
    if (countO >= 1 && countO <= nbAlignementGain) return +tableDesPuissanceDe10[countO - 1];
  } else if (countO == 0) {
    if (countX >= 1 && countX <= nbAlignementGain) return -tableDesPuissanceDe10[countX - 1];
  }
  return 0;
}

bool verifier_match_nul() {
  for (int colonne = 0; colonne < nbColonnes; colonne++) {
    if (emplacement[0][colonne] == ' ') {
      return false;
    }
  }
  return true;
}