2025-Mines-Info-Mpi2-Corrigé

Le jeu de Shannon

Préliminaires

L’épreuve est composée d’un problème unique, comportant 33 questions.

Dans ce problème, nous nous intéressons au jeu de Shannon, qui est un jeu de stratégie dans lequel l’un des joueurs doit parvenir à établir une certaine connexion en posant des pièces de jeu, tandis que son opposant doit l’en empêcher en essayant de le bloquer.

Le problème est divisé en trois sections. Dans la première section (page 1), nous introduisons les règles du jeu et une étude de tournois. Dans la deuxième section (page 5), nous analysons les stratégies de jeu conduisant l’un des joueurs à la victoire.

Dans la troisième section (page 7), nous étudions la construction de deux arbres couvrants disjoints dans un graphe, ce qui est un prérequis de l’une des stratégies d’un joueur, vue dans la deuxième section.

Dans tout l’énoncé, un même identificateur écrit dans deux polices de caractères différentes désigne la même entité, mais du point de vue mathématique pour la police en italique (par exemple n) et du point de vue informatique pour celle en romain avec espacement fixe (par exemple n).

Travail attendu

Pour répondre à une question, il est permis de réutiliser le résultat d’une question précédente, même sans avoir réussi à établir ce résultat.

Selon les consignes, il faudra coder des fonctions à l’aide du langage de programmation C exclusivement, en reprenant le prototype de fonction fourni par le sujet, ou en pseudo-code (c.-à-d. dans une syntaxe souple mais conforme aux possibilités offertes par le langage C).

Inclure les entêtes tels que , , etc., n’est pas demandé. Quand l’énoncé demande de coder une fonction, sauf indication explicite, il n’est pas nécessaire de justifier que celle-ci est correcte ou de tester que des préconditions sont satisfaites.

Le barème tient compte de la clarté et de la concision des programmes : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrira le rôle.

1 Le jeu de Shannon

1.1 Implémentation du jeu en langage C

Un graphe non orienté et connexe G = (V, E) est fixé, ainsi que deux sommets particuliers : le sommet s et le sommet t. La lettre n désigne le nombre de sommets. Définition : Le jeu de Shannon sur le graphe G est un jeu qui se joue entre deux joueurs, Positus et Minus, qui agissent à tour de rôle.

Chaque coup consiste à marquer une arête qui n’a pas été marquée précédemment. Dans ce jeu, Positus remporte la victoire s’il parvient à marquer un ensemble d’arêtes dans lequel les sommets s et t sont reliés par un chemin (appelé aussi une chaîne d’arêtes).

Minus gagne le jeu si toutes les arêtes ont été marquées sans que Positus ne soit parvenu à relier les sommets s et t.

En pratique, Positus « verrouille » des arêtes tandis que Minus « supprime » des arêtes encore jouables. Indication C : Dans l’ensemble du sujet, les sommets du graphe G = (V, E) sont numérotés entre {0} et {n-1}, {S=\{0,1,2,\ldots,n-1\}}.

Par convention, les sommets {s} et {t} correspondent aux sommets de numéros {0} et {1}. Les arêtes des graphes sont de la forme {\{u,v\}} et donc {E} est un sous-ensemble de {\mathcal P_2(S)=\{X\subseteq S:|X|=2\}}. Nous notons {M\subseteq E} l’ensemble des arêtes marquées.

Nous introduisons les déclarations suivantes.

Le type link_t permet de représenter des maillons de listes simplement chaînées. Le graphe {(V,E\setminus M)} est représenté par un tableau de listes d’adjacences. Le type game_t permet de représenter un jeu de Shannon en cours de déroulement.

Dans les enregistrements de ce type, — le champ n désigne le nombre de sommets, — le champ nm désigne le nombre d’arêtes non marquées, — le champ adj_arr renvoie à un tableau de pointeurs où, pour tout entier u compris entre {0} et {n-1}, le pointeur adj_array[u] désigne le premier maillon d’une liste simplement chaînée contenant tous les voisins du sommet u dans le graphe {(V,E\setminus M)}, — le champ cmps renvoie à un tableau permettant de représenter les sommets reliés entre eux par des arêtes marquées par Positus selon une convention détaillée aux questions 6 et 7.

Une variable globale gm est utilisée dans tout le sujet pour désigner le jeu en cours. On notera que les arêtes marquées au cours du jeu sont perdues et ne figurent plus dans la variable gm.

Nous rappelons que la structure « unir & trouver » (ou, en anglais, union find) permet de représenter les classes d’équivalence d’une relation d’équivalence pour un ensemble E.

On choisit d’implémenter cette structure à l’aide d’un tableau associatif A, de taille n pour un ensemble E de cardinal n dont les éléments sont numérotés de {0} à {n-1}.

Le tableau rend compte d’une forêt où chaque arbre est orienté des feuilles vers la racine et représente une classe d’équivalence.

Pour un élément de numéro u, A[u] vaut u s’il s’agit de la racine, que l’on appellera identifiant de la classe, ou A[u] vaut le numéro de son parent dans l’arbre dans tout autre cas.

Nous appelons {M^+\subseteq E} l’ensemble des arêtes marquées par le joueur Positus. Nous notons {\sim_P} la relation d’équivalence dans laquelle deux sommets u et v sont en relation si et seulement s’il existe une chaîne entre u et v formée d’arêtes de {M^+}.

Les classes d’équivalence sont ainsi les composantes connexes du graphe (V, {M^+}). Nous utilisons le champ cmps de la variable gm afin de stocker cette relation d’équivalence selon une structure « unir & trouver ».

1.2 Étude de tournois en langage SQL

Un tournoi de jeux de Shannon est une compétition dans laquelle s’affrontent exactement deux joueurs (A et B) au cours de plusieurs matchs. Le vainqueur d’un tournoi est le joueur qui a gagné le plus grand nombre de matchs.

Le rôle de chaque joueur (Positus ou Minus) peut changer entre chaque match.

On dispose d’une base de donnée SQL composée de trois tables (les clés primaires sont soulignées) — Joueurs(JoueurID, NomJ) — Tournois(TournoiID, NomT, JoueurAID, JoueurBID) — Matchs(MatchID, TournoiID, RoleJoueurA, VainqueurID) dont voici certains extraits :

Par exemple, le tournoi du 12 décembre a opposé Alice et Bob, il s’est joué en 3 matchs.

Alice, qui a gagné deux des trois matchs, a été victorieuse.

2 Stratégies de jeu

2.1 Stratégies gagnantes

2.2 Une stratégie pour Positus

Définition : Selon la terminologie usuelle, nous appelons arbre couvrant tout sous-ensemble de {n-1} arêtes {T\subseteq E} ne contenant pas de cycle.

Il est rappelé les faits suivants : — le graphe (V, T ) est connexe ; — tout ajout d’une arête {e\in E\setminus T}, à un arbre couvrant {T}, crée un unique cycle noté C(T, e) ; — si T est un arbre couvrant, alors, pour tout couple de sommets u et v de V , il existe un unique chemin simple reliant u et v avec des arêtes de T .

Indication C : Nous représentons tout arbre couvrant par un tableau T de taille n tel que T[0] vaut 0 et, pour tout autre sommet u, T[u] vaut le parent du sommet u dans l’arbre enraciné en 0. Pour représenter un arc, nous déclarons :

Dans ce qui suit, nous supposons que Minus joue en premier.

Définition : Pour tout ensemble de sommets {U\subseteq V} qui contient les sommets {s} et {t}, nous notons {G_U} le graphe induit par {U}, c’est-à-dire le sous-graphe {(U,E_U)} où, {E_U=\{\{u,v\}\in E:u,v\in U\}.}Pour tout entier naturel {k}, nous notons {M_k^+\subseteq E} l’ensemble des {k} arêtes marquées par Positus, après que {k} coups ont été joués par Positus.

De même, nous notons {M_k^-\subseteq E} l’ensemble des {k} arêtes marquées par Minus après que {k} coups ont étés joués par Minus. Enfin, nous appelons {(\maltese_k)} l’assertion suivante :

{(\maltese_k)} Après que {2k} coups ont été joués par Minus et Positus, il existe un ensemble de sommets {U} contenant les sommets {s} et {t} ainsi que deux arbres couvrant le graphe induit {G_U}, que l’on note {T_k\subseteq E_U} et {T_k^{\prime}\subseteq E_U}, tels que l’on a {T_k\cap T_k^{\prime}=M_k^+} et {(T_k\cup T_k^{\prime})\cap M_k^-=\varnothing}.

3 Arbres couvrants disjoints

Dans toute cette section, nous supposons que la paire {\{s,t\}} n’appartient pas à l’ensemble des arêtes E. Nous notons {\widehat G} le graphe obtenu à partir de G en ajoutant une arête supplémentaire entre les sommets s et t. Nous appelons {\widehat E} l’ensemble d’arêtes {E\cup\{s,t\}}.

3.1 Une condition suffisante pour {(\maltese_0)}

Soient {T\subseteq\widehat E} et {T^{\prime}\subseteq\widehat E} deux arbres couvrants de {\widehat G} et {\alpha_0} une arrête n’appartenant pas à {T\cup T^{\prime}}. Notons {L_0=\{\alpha_0\}}. Notons {L_1\subseteq\widehat E} l’unique cycle {C(T,\alpha_0)} présent dans l’ensemble {T\cup\{\alpha_0\}}.

Définition : Pour tout couple d’arbres couvrants, {T\subseteq\widehat E} et {T^{\prime}\subseteq\widehat E}, notons {\delta(T,T^{\prime})} le cardinal de l’intersection {T\cap T^{\prime}}. Deux arbres couvrants {T_0} et {T_0^{\prime}} sont éloignés si le couple {(T_0,T_0^{\prime})} atteint le minimum global de la fonction {\delta} parmi tous les couples d’arbres couvrants de {\widehat G}.

Définition : Une arête {\alpha\in\widehat E} est principale s’il existe un couple d’arbres couvrants {T} et {T^{\prime}} éloignés, tel que l’arête {\alpha} n’appartient pas à {T\cup T^{\prime}}.

Si {L_1} ne contient aucune arête de {T\cap T^{\prime}}, nous appelons {L_2\subseteq\widehat E} la réunion des cycles {\bigcup_{\alpha\in L_1}C(T^{\prime},\alpha)} qui se créent lorsque l’on ajoute à {T^{\prime}} l’une des arêtes de {L_1}.

Plus généralement, nous construisons par récurrence la suite croissante {(L_k)_{k\in\mathbb N}\subseteq\widehat E} d’ensembles d’arêtes où

— pour tout entier {k\ge1}, si l’ensemble {L_{2k}} ne contient aucune arête de {T\cap T^{\prime}}, alors on pose {L_{2k+1}=\bigcup_{\alpha\in L_{2k}}C(T,\alpha),}— pour tout entier {k\ge0}, si l’ensemble {L_{2k+1}} ne contient aucune arête de {T\cap T^{\prime}}, alors on pose {L_{2k+2}=\bigcup_{\alpha\in L_{2k+1}}C(T^{\prime},\alpha).}

3.2 Recherche des arêtes principales

Soit {T} et {T^{\prime}} un couple d’arbres couvrants éloignés. On pose {P=\bigcup_{\alpha_0\in E\setminus(T\cup T^{\prime})}\Lambda(\alpha_0).}On appelle {U} l’ensemble des arêtes incidentes à {P}. On appelle {n_U} le cardinal de {U}, {m_P} le cardinal de {P}, et {c=|E\setminus(T\cup T^{\prime})|} le nombre d’arêtes hors de {T} et {T^{\prime}}.

On note {\kappa} le nombre de composantes connexes de {(U,P)}.

Soit {\widetilde T} et {\widetilde T^{\prime}} un autre couple d’arbres couvrants éloignés. Notons {\widetilde c_1} le cardinal de {(E\setminus(\widetilde T\cup\widetilde T^{\prime}))\cap P}.