Calcul des valeurs de Grundy pour des jeux octaux

Étudiant : Mathieu BRUNOT

Tuteur : Valenti Gledel

Jeu de Impartiaux

Description

Un jeu impartial est un jeu à 2 joueurs où les joueurs jouent à tour de rôle et leurs mouvements possibles ne dépendent pas du joueur qui joue, il n'y a donc pas de hasard ni d'égalité dans une partie.

Le perdant étant celui qui ne peut plus jouer, aussi appelé version normale.

En voici des exemples:

• Jeu de Cram
  Les joueurs mettent des dominos sur une grille. Le joueur qui met le dernier domino gagne.
  
• Jeu de Nim
  Il se joue avec un ou plusieurs tas d'objets exemple des allumettes.
  Chacun des joueurs joue à tour de rôle en choisissant un tas et en retirant autant d’allumettes que souhaité dans le tas, pour que son adversaire n’ait plus la possibilité de jouer, c’est ainsi que le jeu prend fin.
  
• Jeu des bâtonnets Fort Boyard
  Ce jeu consiste à n’avoir que le droit de retirer de 1 à 3 bâtonnets à chaque tour. Hormis la différence est que le joueur perdant est celui qui prend le dernier bâtonnet. Cette condition de victoire est appelé version misère.
  

Stratégie Gagnante

En effet, l’ensemble des jeux impartiaux sont résolubles à l’aide d’outils théorique afin de connaitre l'action à faire pour être le joueur en position gagnante.

Prenons le jeu de Fort Boyard mais cette fois-ci en version normale. Dans celui-ci la stratégie gagnante est de laisser un tas à l'adversaire qui serait un multiple de quatre.

• Pour le trouver il suffit de regarder les positions perdantes dans chaque cas:
  1. Si le nombre de bâtonnets est n=1, le joueur courant gagne car il peut enlever le dernier jeton et laisser l'adversaire avec un tas vide.
  2. Si n=2, le joueur courant gagne car il peut retirer les derniers bâtonnets.
  3. Si n=3, le joueur courant gagne car il peut retirer les derniers bâtonnets.
  4. Si n=4, le joueur courant perd car il va forcément laisser son adversaire dans une position gagnante.
  5. Plus généralement, toute position où $n\equiv 1,2,ou3{\pmod {4}}$est une position gagnante, et toute position où $n\equiv 0{\pmod {4}}$ est une position perdante.

Ainsi on pourrait se demander la stratégie gagnant d'autres jeux tel que le jeu de Nim ou le jeu de Cram

Valeurs de Grundy

Théorème de Sprague-Grundy

Le théorème de Sprague-Grundy nous permet de trouver la stratégie gagnante d’un jeu impartial fini en version normale (le perdant est le joueur ne pouvant plus jouer).

La valeur de Grundy ou d’un tas se calcule récursivement par ses règles :

- Un tas vide a pour valeur de Grundy 0.
- Le nombre Grundy d’une position non nulle est le plus petit entier positif ou nul qui n’est pas dans la liste des valeurs de Grundy des positions que l’on peut atteindre à partir de notre position.

Une position perdante d’un jeu celle qui donne une valeur de Grundy de 0.

Calcul des valeurs pour le jeu de Nim

Cas à 1 tas

La valeur de Grundy du jeu de Nim classique d’un tas de taille n (un entier) est celle du nombre de bâtonnets dans ce tas.

On l’explique car toutes les tailles de tas strictement inférieures à n sont atteignables à partir de celui-ci. Alors le minimum exclu(mex) des valeurs atteignables est n.

On appelle ce nombre précis dans le cas du jeu de Nim, un nimber.

Donc par exemple dans un tas de taille 9 du jeu Nim, on aurait une valeur de Grundy de 9, ceci est simple à comprendre.

Cas à plusieurs tas

Dans le cas de plusieurs tas, la valeur de Grundy de tous les jeux est le XOR de toutes les valeurs de Grundy de chaque tas.

Par exemple :

Voici un jeu de Nim composé de trois tas de bâtonnets:

Ce jeu a pour valeur de Grundy : $17\oplus 6\oplus 24\Leftrightarrow 10001\oplus 00110\oplus 11000\Leftrightarrow 15$

Application

Mettons à l’œuvre nos connaissances afin de gagner une partie dans le jeu de Nim de l'exemple précédent.

Imaginons que nous soyons les premiers joueurs à jouer.

Nous nous trouvons dans une position gagnante car la valeur de Grundy du Jeu est de $15\neq 0$.

Pour pouvoir ramener celui-ci à une valeur de 0 pour que notre adversaire soit dans une position perdante, il nous suffit de changer un tas où la valeur de grundy de celui-ci possède un bit à 1 au même indice que le bit à 1 avec le plus grand exposant de 2 de la valeur de Grundy du jeu.

Dans notre cas le premier bit à 1 de 15 est celui qui est au 3eme exposant de 2. Le nombre qu’on doit changer est 24. Pour savoir à quelle valeur on doit le baisser il suffit de faire le XOR de 24 et de la valeur de Grundy du jeu qui est 15. On obtient $24\oplus 15=23$.

• On a choisi de retirer 1 bâton au tas de 24 pour avoir une valeur de Grundy totale de 0.
• L'adversaire est dans une position perdante, quoiqu’il fasse il ne peut pas passer en position gagnante.
• Il nous reste plus qu'à continuer ainsi pour s'assurer de gagner.

Jeux Octaux

Les jeux octaux sont aussi des jeux impartiaux, assez proches du jeu de Nim. Ils se jouent aussi avec des tas d’objet. Leurs caractéristiques sont que les coups autorisés sont définis à l’aide d’un système numérique de 0 à 7 d’où le nom jeu octal.

Règles

Les règles d'un jeu octal précisent les actions possibles lorsqu'un joueur retire n objets d'un tas donné, et sont encodées par une suite de chiffres entre 0 et 7 (d'où le nom jeu octal) :

Notation 0.k₁ k₂ k₃ k₄ …

où chaque chiffre k_n indique en combien de tas le joueur doit scinder le tas dans lequel il a retiré n objets. Le chiffre k_n est la somme de :

• $2^{0}$ si le joueur peut laisser 0 tas, 0 sinon;
• $2^{1}$ si le joueur peut laisser 1 tas, 0 sinon;
• $2^{2}$ si le joueur peut laisser 2 tas, 0 sinon

Par exemple, si k_n=0, les joueurs n'ont pas le droit de retirer n objets d'un tas. Si k_n=3, on retrouve la règle classique du jeu de Nim, à savoir que le joueur peut retirer n objets d'un tas de taille supérieure ou égale n.

Représentation en jeu octal

Comme vous l'avez compris il y a une infinité de jeux octaux.

On retrouve les jeux qu'on a introduit dans ces catégories. Jeu de Fort Boyard = 0.333
Jeu de Fort Cram = 0.07

Néanmoins, le jeu de Nim n'est pas un jeu octal. Dans Nim, les mouvements sont extrêmement flexibles : un joueur peut retirer n'importe quel nombre d'objets d'une pile choisie. Cette flexibilité n'est pas présente dans les jeux octaux, où les mouvements sont prédéfinis. Un jeu "octal" qui pourrait représenter le jeu de Nim serait 0.333... un sauf que ce n'est pas un jeu octal.

Valeurs de Grundy pour les jeux octaux

Méthode

Périodicité

def est_periode(p:int,s:int,tab_grundy:list,n:int)->bool:
    """ test la périodicité"""
    res = True
    m = n-(p+s)
    for i in range(m):
        if s+p+i == len(tab_grundy):
            res = False
            break
        if tab_grundy[s+i] != tab_grundy[s+p+i]:
            res = False
            break
    return res

def test_periodicite(n:int,k:int,tab:list)->list:
    """ renvoie un tableau si on trouve la période sinon renvoie None"""
    for p in range(1,n+1):#periode
        s = n-p
        if est_periode(p,s,tab,n*2+k):
            return (s,p,tab[s:s+p])
    return None

def periodicite(nbr_octal:str)->list:
    """ renvoie la période , taille de la période, taille de la prépériode d'un tableau avec les valeurs de grundy d'un jeu"""
    taille_test = 30000
    tab_test = tab_val_grundy(taille_test, nbr_octal)[1:taille_test] #tableau où chercher la périodicité
    k = len(nbr_octal)
    for n in range(k+2,len(tab_test)+1,2):
        res = test_periodicite(n,k,tab_test)
        if res != None:
            return res 
    return "Periode non trouvé pour .{}".format(nbr_octal)

Méthode rare/fréquentes

Masque

def trie_dico_en_tab_croissant(dico:dict)->list:
    """ renvoie un tableau de tableau trié par ordre croissant 
    selon les valeurs des clefs"""
    res = []
    dico_copy = dico.copy()
    while dico_copy != {}:
        clef_min = min(dico_copy, key=dico_copy.get)#cherche la clef avec la val minimale
        res += [[clef_min,dico_copy[clef_min]]]
        dico_copy.pop(clef_min)
    return res
        
def cherche_id_gap_rare_freq(tab_frequences:list, nbr_echantillon:int)->int:
    """ renvoie l'id du dernier element rare
    d'un tableau trie de frequence de valeur """
    freq = 0.1 * nbr_echantillon #frequence choisi pour determiner les valeurs rares
    for i in range(len(tab_frequences)):
        if tab_frequences[i] > freq:
            id_gap = i-1
            break
    return id_gap

def cherche_rare_commun(tab_grundy:list)->list:
    """ cherche les valeures rare d'un tableau en regardant leurs nombre d'apparitions
    à partir d'un dico qui a pour clef le nombre et pour valeur son nombre d'apparition"""
    nombre_ele = len(tab_grundy)
    dico_frequence = {}
    for ele in tab_grundy:
        dico_frequence[ele] = dico_frequence.get(ele,0) + 1 #creer le dico de toutes les valeurs en clef et en valeurs leurs fréquences
    
    tab_trie = trie_dico_en_tab_croissant(dico_frequence)
    print(tab_trie)
    tab_clef = [tab[0] for tab in tab_trie]
    tab_frequences = [tab[1] for tab in tab_trie]
    id_gap = cherche_id_gap_rare_freq(tab_frequences,nombre_ele)
    
    rare = {0}
    commun = set()
    
    for i in range(len(tab_clef)):
        if i <= id_gap:
            rare.add(tab_clef[i])
        else:
            if tab_clef[i] != 0:
                commun.add(tab_clef[i])
            
    
    res = [rare,commun]
    return res

def indice_des_bits_a_un(masque:str)->list:
    """ renvoie un tableau contenant les indices des bits à 1"""
    res = []
    for i in range(len(masque)):
        if masque[i] == '1':
            res.append(i)
    return res

def est_rare(ele_bin:str,ind_1_du_masque:list)->bool:
    """ verfie si le nombre est rare"""
    cpt_1 = 0
    for ind in ind_1_du_masque:
        if ele_bin[ind] == '1':#verifie que l'element à l'indice ind est bien 1 à l'indice des 1 sur le masque
            cpt_1 += 1
    return cpt_1 % 2 == 0

def rares_dans_masque(masque:str,val_max:int)->set:
    """Donne toutes les valeurs rares d'un masque dans un set"""
    res = set()
    n_bit = len(masque)
    ind_des_1 = indice_des_bits_a_un(masque)
    for nbr in range(val_max+1):
        nbr_bin = mets_nombre_en_bin_sur_x_bits(nbr,n_bit)
        if est_rare(nbr_bin,ind_des_1):
            res.add(nbr)
    
    return res

def cherche_masque_pour_un_tab_grundy(tab_grundy:list)->str:
    """ va chercher un masque de n bit qui convient le mieux pour le tableau de grundy donné"""
    tab_grundy = tab_grundy[1:] #enlève la première valeur qui est 0
    val_max = max(tab_grundy)
    taille_bit = len(bin(val_max)[2:])
    masques_possibles = 2**taille_bit
    tab_rare_commun= cherche_rare_commun(tab_grundy)
    set_rare_cherche = tab_rare_commun[0]
    set_frequent = tab_rare_commun[1]
    res = 0
    
    print("\nset_rare : {}".format(set_rare_cherche))
    print("set_frequent : {}\n".format(set_frequent))
    
    for i in range(1,masques_possibles):
        masque = mets_nombre_en_bin_sur_x_bits(i,taille_bit)
        set_rare_masque = rares_dans_masque(masque,val_max)
        
        contient_rare = set_rare_cherche.issubset(set_rare_masque)
        inter = set_frequent.intersection(set_rare_masque)
        ne_contient_pas_frequent = inter == set() 
        if contient_rare and ne_contient_pas_frequent: #verifie si les rares cherchés sont biens dans le masque et qu'il ne contient pas de valeurs frequentes
            res = masque
            break
    return f"\nle masque qui convient est {res}"

Code

def liste_des_id_des_rares_dans_tab(tab_grundy:list, listes_rares:set):
    """ renvoie un tableau de tous les id des valeurs rares dans le tableau """
    res = []
    for i in range(1,len(tab_grundy)):
        if tab_grundy[i] in listes_rares:
            res + [i]
    return res

def liste_des_separations_tas_en_2_pour_avoir_val_commune(taille_tab:int, dn:int, liste_rares:set)->list:
    """ renvoie tous les couples de possibilités d'une separation en deux d'un tas
    contenant uniquement une valeur rare"""
    res = []
    somme_des_taille_couple = taille_tab - dn
    
    for val1_rare in liste_rares:
        val2 = somme_des_taille_couple-val1_rare
        if not val2 in liste_rares: #verifie que la valeur ne soit pas rares
            couple = (val1_rare,val2) #crée le couple sous forme de tuple
        res += [couple]
    
    return res

def set_des_valeurs_grundy_atteignables_rares(jeu_actions:list, tab_grundy:list, instant_i:int, liste_rares:set):
    """ renvoie un set des valeurs atteignables avec des couples contenant des valeurs rares"""
    res = set()
    for actions in jeu_actions:
        les_actions_possibles = liste_action_possibles(instant_i, actions[0], actions[1])
        if les_actions_possibles[0] == True:
            res.add(0)
            
        if les_actions_possibles[1] == True:
            res.add(tab_grundy[instant_i - actions[1]])           
                
        if les_actions_possibles[2] == True:
            global liste_separations_possibles_rares_commun
            liste_separations_possibles_rares_commun = liste_des_separations_tas_en_2_pour_avoir_val_commune(instant_i, actions[1], liste_rares)
            for couple in liste_separations_possibles_rares_commun:
                res.add(tab_grundy[couple[0]] ^ tab_grundy[couple[1]])
    return res

def tab_val_grundy_methode_masque(taille_tab_souhaite:int, nbr_octal:str, masque:str)->list:
    taille_tab_inital = 10000
    assert taille_tab_souhaite > taille_tab_inital, f"La taille de tableau recherché doit dépasser {taille_tab_inital}"
    tab_grundy = tab_val_grundy(taille_tab_inital, nbr_octal)
    jeu_actions = tab_kn_dn(nbr_octal)
    listes_rares = rares_dans_masque(masque,max(tab_grundy)) #un set contant toutes les valeurs rares du masque
    liste_id_rares = liste_des_id_des_rares_dans_tab(tab_grundy, listes_rares)

    for taille in range(taille_tab_inital+1, taille_tab_souhaite+1):#Trouver les valeurs suivantes avec la méthode du masque
        set_valeurs_atteignables = set_des_valeurs_grundy_atteignables_rares(jeu_actions, tab_grundy, taille, liste_id_rares) 
        mex = calc_mex(set_valeurs_atteignables)
        if not mex in listes_rares:#si le mex est commun alors
            tab_grundy += [mex]
        
        else: #on va rajouter des valeurs jusqu'à avoir un mex commun sinon on continue jusqu'au bout
            for actions in jeu_actions:
                les_actions_possibles = liste_action_possibles(taille, actions[0], actions[1])
                if les_actions_possibles[2] == True:
                    somme_des_taille_couple = taille - actions[1]
                    for i in range(1, (somme_des_taille_couple//2)+1):
                        val1 = i
                        val2 = somme_des_taille_couple-i
                        if all(val1 not in couple for (couple) in liste_separations_possibles_rares_commun):#verifie que la valeur n'a pas déjà été testé
                            set_valeurs_atteignables.add(tab_grundy[val1] ^ tab_grundy[val2])
                            mex = calc_mex(set_valeurs_atteignables)
                            if not mex in listes_rares:
                                break
                if not mex in listes_rares:
                    break
            tab_grundy += [mex]
            
    return tab_grundy