# ###############################################
# Puissance 4 avec Turtle
# Version 2
# IA Minimax avec Élagage Alpha-Bêta
# Compatible Python 3.2.5+
# Juin 2026
# nsi.gecif.net
# ###############################################

"""Amélioration de la Version 1 :

Il est tout à fait possible de rendre l'ordinateur nettement plus fort et agressif. Pour cela, nous allons implémenter trois optimisations majeures sans ralentir le jeu :

L'élagage Alpha-Bêta (Alpha-Beta Pruning) : C'est l'amélioration indispensable du Minimax. Elle permet de "couper" des branches entières de l'arbre de décision dès que l'IA sait qu'un coup est moins bon qu'un autre déjà calculé. Cela permet de pousser la profondeur de recherche à 6 ou 7 coups d'avance au lieu de 4, dans le même laps de temps.

L'ordonnancement des coups (Move Ordering) : L'élagage Alpha-Bêta est maximal si l'IA examine les colonnes centrales en premier. En effet, au Puissance 4, le centre offre beaucoup plus de possibilités d'alignements.

Une heuristique plus fine : Augmenter le poids des alignements de 3 pions pour que l'IA cherche activement à créer des pièges (comme des attaques doubles).

Le Code Amélioré (Minimax + Alpha-Bêta)

Voici la version 1 optimisée. La profondeur (PROFONDEUR_MAX) a été montée à 6. L'IA va désormais analyser plusieurs dizaines de milliers de combinaisons par seconde pour bloquer vos moindres pièges.

Pourquoi cette version 2 est beaucoup plus forte :

L'effet couperet d'Alpha-Bêta : Imaginez que l'ordinateur étudie une colonne et s'aperçoive que vous pouvez le battre au coup suivant. Il s'arrête immédiatement d'étudier les sous-variantes de cette colonne (le paramètre beta <= alpha coupe la recherche). Cela économise parfois jusqu'à 80 % des calculs inutiles !

Priorité à l'axe central ([3, 2, 4, 1, 5, 0, 6]) : En testant d'abord la colonne du milieu (la 3), l'IA trouve très vite des scores très hauts ou très bas. Les coupes Alpha-Bêta se déclenchent donc beaucoup plus tôt sur les colonnes extérieures.

Profondeur accrue : À 6 coups d'avance, l'IA est capable de voir si le fait de poser un pion va vous donner l'opportunité de construire un piège imparable au coup d'après.

Bonne chance pour cette nouvelle partie !"""

import turtle
import random

LIGNES = 6
COLONNES = 7
TAILLE = 60

grille = [[0 for j in range(COLONNES)] for i in range(LIGNES)]

joueur = 1      # humain (Rouge)
ordinateur = 2  # IA (Jaune)

# Grâce à Alpha-Bêta, on peut monter à 6 (voire 7) coups d'avance de manière fluide
PROFONDEUR_MAX = 6

fenetre = turtle.Screen()
fenetre.title("Puissance 4 - IA Expert (Alpha-Bêta) - nsi.gecif.net")

dessin = turtle.Turtle()
dessin.hideturtle()
dessin.speed(0)

message = turtle.Turtle()
message.hideturtle()
message.penup()
message.goto(0, -230)

jeu_termine = False


def dessiner_grille():
    dessin.clear()
    for ligne in range(LIGNES):
        for colonne in range(COLONNES):
            x = colonne * TAILLE - 210
            y = ligne * TAILLE - 180
            dessin.penup()
            dessin.goto(x, y)

            if grille[ligne][colonne] == 0:
                couleur = "white"
            elif grille[ligne][colonne] == 1:
                couleur = "red"
            else:
                couleur = "yellow"

            dessin.fillcolor(couleur)
            dessin.begin_fill()
            for _ in range(4):
                dessin.pendown()
                dessin.forward(TAILLE)
                dessin.left(90)
            dessin.end_fill()
    fenetre.update()


def jouer(colonne, pion):
    for ligne in range(LIGNES):
        if grille[ligne][colonne] == 0:
            grille[ligne][colonne] = pion
            return True
    return False


def annuler_coup(colonne):
    for ligne in reversed(range(LIGNES)):
        if grille[ligne][colonne] != 0:
            grille[ligne][colonne] = 0
            break


def colonne_valide(colonne):
    return grille[LIGNES - 1][colonne] == 0


def victoire(pion):
    # Horizontal
    for l in range(LIGNES):
        for c in range(COLONNES - 3):
            if (grille[l][c] == pion and grille[l][c+1] == pion and
                grille[l][c+2] == pion and grille[l][c+3] == pion):
                return True
    # Vertical
    for l in range(LIGNES - 3):
        for c in range(COLONNES):
            if (grille[l][c] == pion and grille[l+1][c] == pion and
                grille[l+2][c] == pion and grille[l+3][c] == pion):
                return True
    # Diagonale montante
    for l in range(LIGNES - 3):
        for c in range(COLONNES - 3):
            if (grille[l][c] == pion and grille[l+1][c+1] == pion and
                grille[l+2][c+2] == pion and grille[l+3][c+3] == pion):
                return True
    # Diagonale descendante
    for l in range(3, LIGNES):
        for c in range(COLONNES - 3):
            if (grille[l][c] == pion and grille[l-1][c+1] == pion and
                grille[l-2][c+2] == pion and grille[l-3][c+3] == pion):
                return True
    return False


def grille_pleine():
    for c in range(COLONNES):
        if colonne_valide(c):
            return False
    return True


# =======================================================
#   IA OPTIMISÉE : COUPS ORDONNÉS, HEURISTIQUE & ALPHA-BÊTA
# =======================================================

def evaluer_fenetre(fenetre_4_pions):
    score = 0
    nb_ia = fenetre_4_pions.count(ordinateur)
    nb_joueur = fenetre_4_pions.count(joueur)
    nb_vide = fenetre_4_pions.count(0)

    if nb_ia == 4:
        score += 10000
    elif nb_ia == 3 and nb_vide == 1:
        score += 100  # IA agressive : cherche à faire des menaces de 3 pions
    elif nb_ia == 2 and nb_vide == 2:
        score += 10

    if nb_joueur == 3 and nb_vide == 1:
        score -= 200  # Contre-attaque obligatoire (Bloquer le joueur)
    elif nb_joueur == 2 and nb_vide == 2:
        score -= 20

    return score


def evaluer_grille():
    score_total = 0

    # Valorisation forte du centre
    colonne_centre = [grille[l][3] for l in range(LIGNES)]
    score_total += colonne_centre.count(ordinateur) * 6

    # Horizontale
    for l in range(LIGNES):
        ligne_complete = grille[l]
        for c in range(COLONNES - 3):
            score_total += evaluer_fenetre(ligne_complete[c:c+4])

    # Verticale
    for c in range(COLONNES):
        colonne_complete = [grille[l][c] for l in range(LIGNES)]
        for l in range(LIGNES - 3):
            score_total += evaluer_fenetre(colonne_complete[l:l+4])

    # Diagonales
    for l in range(LIGNES - 3):
        for c in range(COLONNES - 3):
            score_total += evaluer_fenetre([grille[l+i][c+i] for i in range(4)])
            score_total += evaluer_fenetre([grille[l+3-i][c+i] for i in range(4)])

    return score_total


def obtenir_coups_ordonnes():
    """Trie les colonnes pour analyser le centre en premier (optimise Alpha-Bêta)."""
    ordre_ideal = [3, 2, 4, 1, 5, 0, 6]
    return [c for c in ordre_ideal if colonne_valide(c)]


def minimax_alphabeta(profondeur, alpha, beta, maximisation):
    """Minimax optimisé par l'élagage Alpha-Bêta."""
    est_terminal = victoire(joueur) or victoire(ordinateur) or grille_pleine()

    if profondeur == 0 or est_terminal:
        if est_terminal:
            if victoire(ordinateur):
                return 1000000 + profondeur
            elif victoire(joueur):
                return -1000000 - profondeur
            else:
                return 0
        return evaluer_grille()

    coups_possibles = obtenir_coups_ordonnes()

    if maximisation:
        valeur_max = float('-inf')
        for c in coups_possibles:
            jouer(c, ordinateur)
            score = minimax_alphabeta(profondeur - 1, alpha, beta, False)
            annuler_coup(c)
            valeur_max = max(valeur_max, score)
            alpha = max(alpha, score)
            if beta <= alpha:
                break  # Élagage Bêta : inutile de chercher plus loin dans cette branche
        return valeur_max
    else:
        valeur_min = float('inf')
        for c in coups_possibles:
            jouer(c, joueur)
            score = minimax_alphabeta(profondeur - 1, alpha, beta, True)
            annuler_coup(c)
            valeur_min = min(valeur_min, score)
            beta = min(beta, score)
            if beta <= alpha:
                break  # Élagage Alpha
        return valeur_min


def coup_ordinateur():
    meilleur_score = float('-inf')
    meilleures_colonnes = []

    coups_possibles = obtenir_coups_ordonnes()

    # Premier coup de la partie toujours au centre
    if len(coups_possibles) == COLONNES and grille[0][3] == 0:
        jouer(3, ordinateur)
        return

    # Valeurs de départ pour Alpha et Bêta
    alpha = float('-inf')
    beta = float('inf')

    for c in coups_possibles:
        jouer(c, ordinateur)
        score_coup = minimax_alphabeta(PROFONDEUR_MAX - 1, alpha, beta, False)
        annuler_coup(c)

        if score_coup > meilleur_score:
            meilleur_score = score_coup
            meilleures_colonnes = [c]
        elif score_coup == meilleur_score:
            meilleures_colonnes.append(c)

    if meilleures_colonnes:
        jouer(random.choice(meilleures_colonnes), ordinateur)

# =======================================================


def afficher(texte):
    message.clear()
    message.write(texte, align="center", font=("Arial", 16, "normal"))


def clic(x, y):
    global jeu_termine

    if jeu_termine:
        return

    colonne = int((x + 210) // TAILLE)

    if colonne < 0 or colonne >= COLONNES or not colonne_valide(colonne):
        return

    # --- TOUR DU JOUEUR ---
    jouer(colonne, joueur)
    dessiner_grille()

    if victoire(joueur):
        afficher("Vous avez gagné !")
        jeu_termine = True
        return
    if grille_pleine():
        afficher("Match nul.")
        jeu_termine = True
        return

    fenetre.onclick(None)  # Bloque le clic pendant la réflexion
    afficher("L'ordinateur calcule (Alpha-Bêta)...")

    # --- TOUR DE L'ORDINATEUR ---
    coup_ordinateur()
    dessiner_grille()

    if victoire(ordinateur):
        afficher("L'ordinateur a gagné.")
        jeu_termine = True
        return
    if grille_pleine():
        afficher("Match nul.")
        jeu_termine = True
        return

    afficher("À votre tour ! Cliquez dans une colonne")
    fenetre.onclick(clic)


fenetre.setup(500, 500)
fenetre.tracer(0)
dessiner_grille()
afficher("Cliquez dans une colonne")
fenetre.onclick(clic)
fenetre.mainloop()