Jeu de parité

Le concept essentiel de l'algorithme SPM est la fonction de rang : on attribue à chaque sommet un vecteur de compteurs (mesure de progression), qui rassemble le nombre de fois que le joueur 1 peut forcer à visiter une priorité impaire avant qu'une priorité plus grande soit vue. Si la valeur est suffisamment petite, le sommet est déclaré comme gagnant pour le joueur 1. SPM calcule la mesure de progression en mettant à jour les valeurs d'un sommet à partir des valeurs de ses successeurs ; autrement dit en calculant un plus petit point fixe pour tous les sommets.

La notion de jeu de parité est étendue en rajoutant deux sous-ensembles de sommets disjoints : l'ensemble des sommets visités et l'ensemble des sommets évités.

L'algorithme RE introduit par Zielonka repose sur le paradigme diviser pour régner. Il utilise aussi le concept d'attracteur. Étant donné un sous-ensemble U de sommets, l'attracteur de U pour le joueur i est l'ensemble des sommets depuis lesquels le joueur i peut forcer à atteindre U. À chaque étape, l'algorithme supprime les sommets de priorité maximale p, ainsi que les sommets où le joueur i avec i = p mod 2 qui attire vers ces derniers. On obtient un jeu restant. Sur ce jeu restant, on appelle récursivement l'algorithme pour obtenir les deux ensembles gagnants W₀ et W₁ pour les joueurs 0 et 1 sur le jeu restant. Si le joueur i gagne sur le sous-jeu, alors il gagne aussi sur le jeu initial. Sinon, le joueur i ne gagne pas ce sous-jeu, i.e. W_1-i est non vide, l'algorithme calcule alors l'attracteur pour le joueur 1-i de W_1-i et on résout récursivement ce sous-jeu.

Formellement, soit ${\displaystyle G=(V,V_{0},V_{1},E,\Omega )}$ un jeu de parité où ${\displaystyle V_{0}}$ resp. ${\displaystyle V_{1}}$ sont les ensembles de sommets appartenant au joueur 0 resp. 1, ${\displaystyle V=V_{0}\cup V_{1}}$ est l'ensemble de tous les sommets, ${\displaystyle E\subseteq V\times V}$ est l'ensemble des transitions, et ${\displaystyle \Omega :V\rightarrow \mathbb {N} }$ la fonction qui donne la priorité à chaque sommet. Soit ${\displaystyle U\subseteq V}$ un ensemble de sommets et ${\displaystyle i=0,1}$ un joueur. Le i-attracteur de U est le plus petit ensemble de sommets ${\displaystyle Attr_{i}(U)}$ incluant U et tel que le joueur i peut forcer à visiter U depuis tout sommet de ${\displaystyle Attr_{i}(U)}$. L'ensemble ${\displaystyle Attr_{i}(U)}$ peut être calculer par itération car c'est un point fixe :

${\displaystyle {\begin{aligned}Attr_{i}(U)^{0}&:=U\\Attr_{i}(U)^{j+1}&:=Attr_{i}(U)^{j}\cup \{v\in V_{i}\mid \exists (v,w)\in E:w\in Attr_{i}(U)^{j}\}\cup \{v\in V_{1-i}\mid \forall (v,w)\in E:w\in Attr_{i}(U)^{j}\}\\Attr_{i}(U)&:=\bigcup _{j=0}^{\infty }Attr_{i}(U)^{j}\end{aligned}}}$

En d'autres mots, on commence avec l'ensemble initial U puis, on ajoute à chaque étape, tous les sommets du joueur i qui peuvent atteindre l'ensemble courant en une étape, et tous les sommets du joueur 1-i qui atteignent forcément l'ensemble courant quelle que soit la transition choisie par le joueur 1-i.

Voici un pseudo-code l'algorithme de Zielonka W₀, W₁) qui est une partition de l'ensemble des sommets avec W_i est l'ensemble des sommets depuis lesquels le joueur i gagne.

 fonction ${\displaystyle resoudre(G)}$
     p:= priorité maximale du jeu G
     si ${\displaystyle p=0}$
         retourner ${\displaystyle V,\{\}}$
     alors
         U:= ensemble des sommets de G de priorité p
         ${\displaystyle i:=p{\bmod {2}}}$
         ${\displaystyle A:=Attr_{i}(U)}$
         ${\displaystyle W_{0}',W_{1}':=resoudre(G\setminus A)}$
         si ${\displaystyle W_{i}'=V}$
              retourner ${\displaystyle V,\{\}}$
         ${\displaystyle B:=Attr_{1-i}(W_{1-i}')}$
         ${\displaystyle W_{0}'',W_{1}'':=resoudre(G\setminus B)}$
         retourner ${\displaystyle W_{i}'',(W_{1-i}''\cup B)}$