Quoridor/project/Outils/Arbre.py

"""
    MinMax consiste à calculer H coup d'avance, en considérant que l'adversaire joue au mieux.
"""
from random import randint
from Outils.Elagage import *



class Arbre() :     # Quentin 18/10/2016
    """
        Sert à construire l'arbre du minMax.

        Attributs :
        .plateau
        .hauteur : hauteur de l'arbre (Les feuilles ont une hauteur de 0)
        .num : joueur dont c'est le tour à cette position
    """
    def __init__(self, evaluer_position, plateau, num_racine, h, H) :
        """
            Sert à fabriquer l'arbre récursivement.

            evaluer_position : fonction d'évaluation
            plateau : clair
            num_racine : numéro du joueur dont c'est le tour dans la partie associée à la racine
            num_pere : numéro du père de l'arbre ici construit. Vaut None si l'arbre est la racine.
            h : accumulateur comptant le nombre d'appels récursifs
            H : hauteur désirée
        """

        self.hauteur = H - h
        self.num = plateau.tour



        # self.fils est la liste des fils correspondant aux nouveau plateaux obtenus après application des coups disponibles
        # C'est une liste de couples (Coup, Nombre, Arbre)
        self.fils = []

        # Liste des valeurs des fils :
        liste_valeurs = []

        if h < H and plateau.gagnant() == -1 :  #Si l'arbre ne correspond pas à une situation gagnante, il a des fils
            liste_coups = plateau.liste_coups_possibles()

            for coup in liste_coups :
                if elagage(plateau, coup) :
                    plateau_fils = plateau.copie()
                    plateau_fils.executer_coup(coup)
                
                # Chaque fils est associé au coup qui lui donne naissance et à la valeur de la position obtenue
                    arbre = Arbre(evaluer_position, plateau_fils, num_racine, h+1, H)
                    self.fils.append((coup, arbre))
                    liste_valeurs.append(arbre.valeur)




        # Calcul de la valeur :
        if liste_valeurs == [] :
            self.valeur = evaluer_position(plateau, num_racine)
        elif self.num == num_racine :
            self.valeur = max(liste_valeurs)
        else :
            self.valeur = min(liste_valeurs)




            

    def est_feuille(self) :
        """ Retourne True si le noeud est une feuille """
        return self.fils == []


    def liste_feuilles(self) :
        """ Retourne la liste des feuilles de l'arbre """
        if self.est_feuille() :
            return [self]
        else :  # Si l'arbre n'est pas une feuille, on appelle récursivement la fonction  sur ses fils et on concatène les listes de feuilles obtenues
            l = []
            for f in self.fils :
                l += f.liste_feuilles
            return l