Quoridor/project/Outils/arbre_alpha_beta.py

from random import randint
from random import shuffle

from Outils.Elagage import *
from Outils.Moteur_de_jeu import Distance
from Outils.Moteur_de_jeu.Distance import *



def obtenir_coup (num, plateau, fct_eval, H) :
    liste_coups = plateau.liste_coups_possibles()
    t = []
    for coup in liste_coups :
        if elagage(plateau, coup) :
            t.append ([coup, None ])
    alpha = -10**100
    beta = 10**100
    dist = distance_a_star(plateau)

    for k in range (len(t)) :
        plateau2 = plateau.copie()
  
        plateau2.executer_coup (t[k][0])
        t[k][1] = alphabeta (plateau2, num, alpha, beta, fct_eval,  1, H)
        alpha = max (alpha, t[k][1])

    maxi = t[0][1] 
    l = []
    for i in range(len(t)) :
        l.append(t[i][1])
        if t[i][1] >= maxi :
            maxi = t[i][1]

    liste_coups = []
    a = []
    for i in range(len(t)) :
        if t[i][1] == maxi :
            liste_coups.append(t[i][0])




        

        
    shuffle(liste_coups)
    coup = liste_coups[0]
    liste = plateau.liste_coups_possibles()

    for i in range(len(liste)) :
        if liste[i] == coup :
            return i




def alphabeta (plateau, num, alpha, beta, fct_eval, h, H) :

    if plateau.gagnant() !=-1 :
        return fct_eval (plateau, num )
    
    if h == H :
        return fct_eval (plateau, num )
    else :
        if h%2 == 1 :
            Val = 10**100
            liste_coups = plateau.liste_coups_possibles()
            t = []
            for coup in liste_coups :
                if elagage(plateau, coup) :
                    t.append (coup)

            for k in range (len(t)) :
                plateau2 = plateau.copie()
                plateau2.executer_coup (t[k])

                Val = min (Val, alphabeta (plateau2, num, alpha, beta, fct_eval, h+1, H))
                if alpha > Val :
                    return Val
                beta = min (beta, Val)
        else :
            Val = -10**100
            liste_coups = plateau.liste_coups_possibles()
            t = []
            for coup in liste_coups :
                if elagage(plateau, coup) :
                    t.append (coup)

            for k in range (len(t)) :
                plateau2 = plateau.copie()
                plateau2.executer_coup (t[k])

                Val = max (Val, alphabeta (plateau2, num, alpha, beta, fct_eval, h+1, H))
                if beta <= Val :
                    return Val
                alpha = max (alpha, Val)

    return Val