# -*- coding: utf-8 -*-
# Created on Mon Dec 16 13:50:00 2024
# @author: mhebding
# TP6 - Theorie des jeux



## 1 - Modelisation du jeu

# 1.
def affiche_configuration(c):
    k, joueur = c
    pass

# ANNEXE 1 - EXEMPLE
# >>> C’est au joueur J0 de jouer, il y a 7 allumette(s) sur la table.

# 2.
def liste_coups_suivants(c):
    k, joueur = c
    pass



## 2 - Algorithme min-max avec heuristique

# 3.
def h(c):
    k, joueur = c
    pass
    
# 4.    
def minmax(c, h, p): # algorithme minmax avec heuristique
    k, joueur = c
    pass

# 5.1        
def XminimisantY(X, Y):
    pass

# 5.2
def XmaximisantY(X, Y):
    pass

# 5.3
def coup_suivant_par_minmax(c,h,p):
    k, joueur = c
    coups_suivants = liste_coups_suivants(c)
    pass

# 6.
def joue(n, h, p):
    c = (n, 0) # configuration initiale
    pass

# ANNEXE 2 - EXEMPLE
# >>> Vous êtes le joueur J0.
# >>> C’est au joueur J0 de jouer, il y a 8 allumette(s) sur la table.
# >>> Votre meilleur coup à jouer est de prendre 3 allumette(s).
# >>> Combien d’allumette(s) souhaitez-vous enlever ? 3
# >>> C’est au joueur J1 de jouer, il y a 5 allumette(s) sur la table.
# >>> Le joueur J1 enlève 1 allumette(s).
# >>> C’est au joueur J0 de jouer, il y a 4 allumette(s) sur la table.
# >>> Votre meilleur coup à jouer est de prendre 3 allumette(s).
# >>> Combien d’allumette(s) souhaitez-vous enlever ? 3
# >>> C’est au joueur J1 de jouer, il y a 1 allumette(s) sur la table.
# >>> Le joueur J1 enlève 1 allumette(s).
# >>> Le joueur J0 a gagné.

# 7.   
"""
L'ordinateur sera imbattable si p = n.
"""

# Cas où l'ordi gagne...
n = 21
p = n
#joue(n, h, p)

# A p=8, l'ordi peut perdre :)
p = 8
#joue(n, h, p)

# Remarque :
"""
Considérons la stratégie suivante (qui est bien positionnelle, même si nous ne l'exprimons pas ainsi),
consistant à prendre un nombre d'allumettes tel que la somme des allumettes prises par le joueur
précédent et le joueur actuel soit égale à 4.
Alors sur deux tours, le nombre d'allumettes décroît de 4 unités.
Ainsi si initialement n = 4k + 1, le joueur qui joue en second peut s'assurer que le premier joueur
a toujours face à lui un nombre d'allumettes égal à 1 modulo 4, et le premier joueur finit par devoir
tirer la dernière # allumette, perdant ainsi le jeu. Le second joueur a donc une stratégie gagnante.

A contrario si n <> 4k+1, le premier joueur peut prendre un nombre d'allumettes de sorte que le nombre
d'allumettes restantes soit égal à 1 modulo 4. C'est alors le second joueur qui se trouvera toujours
face à un nombre d'allumettes égal à 1 modulo 4, et qui finira par tirer la dernière allumette.
C'est maintenant le joueur qui commence qui a une stratégie gagnante.
"""



## 3 - Graphe du jeu et calcul des attracteurs

# 8.
def GA(n):
    d = dict()
    file = [(n, 0)]
    while len(file) > 0:
        c = file.pop(0)
        if c not in d:
            d[c] = pass
            for coup in d[c]:
                file.append(coup)
    return pass

#print(GA(4))

# ANNEXE 3 - EXEMPLE n = 4
# {(4,0):[(3,1),(2,1),(1,1)], (3,1):[(2,0),(1,0),(0,0)], (2,1):[(1,0),(0,0)], (1,1):[(0,0)], (2,0):[(1,1),(0,1)], (1,0):[(0,1)], (0,0):[], (0,1):[]}

# 9.
def attracteur(G,S0,W0):
    A = []
    tG = {t: [s for s in G.keys() if t in G[s]] for t in G.keys()} # dictionnaire du graphe transposé
    ind = {s: len(G[s]) for s in G.keys()} # dictionnaire des indices sortants du graphe G
    def parcours(t):
        """Fonction récursive qui augmente l'attracteur à partir du sommet t"""
        if t not in A:
            A.append(t)
            for s in tG[t]: # pour chaque prédécesseur s de t (on remonte le graphe)
                ind[s] -= 1 # on indique qu'on a visité ce sommet une fois depuis A
                if s in S0 or ind[s] == 0: # si s est contrôlé par J0 ou si tous les successeurs de s sont dans A
                    parcours(s)
    for t in W0:
        parcours(t)
    return A

# ANNEXE 4 - EXEMPLE
# >>> [(0,0),(1,1),(2,0),(3,0),(4,0),(5,1),(6,0),(8,0)] 

n = 8
G = GA(n)
S0 = [c for c in G.keys() if c[1] == 0] # liste des sommets contrôlés par le joueur J0
W0 = [(0, 0)] # liste des sommets finaux gagnants pour J0

pass # calculer et afficher les attracteurs pour G, S0, W0

# 10.
def strategie_gagnante(G,S0,W0):
    A = []
    tG = {t: [s for s in G.keys() if t in G[s]] for t in G.keys()} # dictionnaire du graphe transposé
    ind = {s: len(G[s]) for s in G.keys()} # dictionnaire des indices sortants du graphe G
    strategie = dict() # dictionnaire associant à tout sommet de J0 un successeur de position gagnante
    def parcours(t):
        """Fonction récursive qui augmente l'attracteur à partir du sommet t"""
        if t not in A:
            A.append(t)
            for s in tG[t]: # pour chaque prédécesseur s de t (on remonte le graphe)
                ind[s] -= 1 # on indique qu'on a visité ce sommet une fois depuis A
                if s in S0 or ind[s] == 0: # si s est contrôlé par J0 ou si tous les successeurs de s sont dans A
                    parcours(s)
                pass
    for t in W0:
        parcours(t)
    return pass

S1 = [c for c in G.keys() if c[1] == 1] # liste des sommets contrôlés par le joueur J1
W1 = [(0, 1)] # liste des sommets finaux gagnants pour J0

pass # afficher la strategie gagnante pour J0
pass # afficher la strategie gagnante pour J1

# ANNEXE 5 - EXEMPLE
# >>> (4, 0): (1, 1), (3, 0): (1, 1), (8, 0): (5, 1), (6, 0): (5, 1), (2, 0): (1, 1) # strategie gagnante J0
# >>> (4, 1): (1, 0), (3, 1): (1, 0), (7, 1): (5, 0), (6, 1): (5, 0), (2, 1): (1, 0) # strategie gagnante J1