Geipi Polytech — NSI 2022

Présentation de l'épreuve

Cette épreuve de Numérique et Sciences Informatiques fait partie du concours Geipi Polytech, édition 2022. Elle comporte 2 exercices indépendants : le premier porte sur la conception d'« intelligences artificielles » pour un jeu à deux joueurs, le second sur un algorithme de répartition équilibrée puis d'affectation par préférences.

Exercice 1 — Des IA pour un jeu à deux joueurs

Un club d'informatique organise un tournoi entre des « IA » programmées par ses membres, pour un jeu à deux joueurs où chaque partie se termine toujours par une victoire (jamais de match nul). Une « IA » est une fonction qui reçoit le numéro du joueur courant (1 ou 2) et la liste des états de jeu accessibles à l'issue de son prochain coup, et qui renvoie l'indice de l'état choisi dans cette liste. Si j désigne le numéro d'un joueur, 3 - j désigne celui de son adversaire.

On dispose d'une fonction coups_suivants(j, etat) qui renvoie la liste des états accessibles après que le joueur j ait joué un coup depuis l'état etat.

1. IA « gloutonne ». On dispose d'une fonction score(j, etat) qui renvoie un entier d'autant plus grand que le joueur j a de chances de gagner depuis l'état donné. L'IA gloutonne évalue le score de chacun des états accessibles, et choisit l'indice d'un état de score maximal ; en cas d'égalité entre plusieurs états, elle en choisit un au hasard parmi les meilleurs (on dispose pour cela d'une fonction alea(n), qui renvoie un entier aléatoire entre 0 et n-1 inclus). Compléter la fonction ci-dessous.

def gloutonne(j, coups):
    b = [0]                      # indices des etats de score maximal
    i = 1
    while i < len(coups):
        if ① > score(j, coups[b[0]]):
            b = ②
        elif ③ == score(j, coups[b[0]]):
            ④
        i = i + 1
    return coups[b[⑤]]

2. IA « probabiliste ». Une seconde IA, prudente, estime la probabilité de victoire du joueur j depuis un état donné, à l'aide d'une fonction proba(j, etat) déjà fournie. Plutôt que d'évaluer directement ses propres coups, prudente évalue les coups accessibles à l'adversaire au tour suivant, en supposant qu'il choisira celui qui maximise sa propre probabilité de victoire ; si cette probabilité pour l'adversaire vaut $p$, la probabilité de victoire du joueur j vaut alors $1-p$.

Voici un exemple, où les probabilités de victoire de l'adversaire depuis chacun des états accessibles sont indiquées :

Indiquer, pour les états A, B et C, la probabilité de victoire du joueur j estimée par prudente.

3. Compléter la fonction prudente ci-dessous, qui, en cas d'égalité, choisit le plus petit indice.

def prudente(j, coups):
    (b, p) = (0, 0.0)
    for i in range(0, len(coups)):
        a = coups_suivants(3 - j, coups[i])
        (ba, pa_max) = (0, 0.0)
        for k in range(0, len(a)):
            if proba(3 - j, a[①]) > pa_max:
                (②) = (k, proba(3 - j, a[k]))
        if 1 - pa_max > p:
            (b, p) = (i, 1 - pa_max)
    return coups[b]

4. Généralisation à un horizon de $k$ coups. L'idée de prudente se généralise : au lieu de s'arrêter après un seul coup de l'adversaire, on peut simuler l'échange de coups sur un horizon de nb coups, en alternant les joueurs à chaque appel récursif. La fonction prudente ci-dessus correspond au cas nb = 2. Compléter la fonction récursive proba_horizon ci-dessous, ainsi que l'IA avisee qui l'utilise avec un horizon de 3 coups.

def proba_horizon(j, etat, nb):
    a = coups_suivants(3 - j, etat)
    if nb <= 1 or len(a) == 0:
        return proba(j, ①)
    p_max = 0.0
    for i in range(0, len(a)):
        pa = proba_horizon(3 - j, a[②], ③)
        if pa > p_max:
            p_max = pa
    return ④
 
def avisee(j, coups):
    (b, p) = (0, 0.0)
    for i in range(0, len(coups)):
        pc = proba_horizon(j, coups[⑤], 3)
        if pc > p:
            (b, p) = (⑥)
    return coups[⑦]

Exercice 2 — Répartition équilibrée puis affectation par préférences

Un centre de vacances propose plusieurs ateliers (escalade, théâtre, robotique...) à un groupe d'adolescents. Chaque adolescent est identifié par une chaîne de caractères commençant par la lettre 'S' s'il est déjà inscrit à un stage l'année précédente (« senior »), ou par la lettre 'J' sinon (« junior »). L'objectif est double : d'abord retoucher les classements fournis par les animateurs pour chaque atelier de sorte qu'ils respectent une propriété de parité faible, puis affecter chaque adolescent à un atelier en tenant compte de ses préférences et de ces classements.

Propriété de parité faible. Un classement d'adolescents (liste ordonnée) respecte la parité faible si, à tout rang $k$, le nombre de juniors parmi les $k$ premières places ne dépasse jamais le nombre de seniors, sauf s'il ne reste plus aucun senior dans la suite du classement. L'ordre relatif des juniors entre eux, et celui des seniors entre eux, ne doivent jamais être modifiés.

1. Le classement C1 = ['J1', 'S4', 'S7', 'S2', 'S3', 'S6', 'S1', 'J2', 'S8', 'S5', 'J3'] ne respecte pas la parité faible (trop de seniors dans les 3 premières places, alors qu'il reste des juniors ensuite). Comment le retoucher pour qu'il la respecte, sans modifier l'ordre relatif des juniors entre eux ni celui des seniors entre eux ?

2. Compléter la fonction junior, qui renvoie True si la chaîne de caractères reçue en argument désigne un junior, False sinon.

def junior(ado):
    return ...

3. Compléter la fonction prochain_junior, qui renvoie l'indice du premier junior dans la liste ados à partir de l'indice i (ou len(ados) s'il n'y en a aucun).

def prochain_junior(ados, i):
    if i >= len(ados) or junior(ados[i]):
        return i
    return prochain_junior(ados, ...)

4. La fonction equilibrer ci-dessous retouche un classement pour respecter la parité faible : elle construit le classement final en retirant, à chaque étape, soit le junior le plus proche du début de la liste restante, soit le premier senior, selon une règle qui garantit qu'à tout moment, le nombre de juniors déjà placés reste au moins égal à la moitié du nombre de places déjà attribuées (arrondi), tant qu'il reste des juniors disponibles. Compléter le code.

def equilibrer(ados):
    ados = ados.copy()
    (classement, nb_juniors) = ([], 0)
    idx = prochain_junior(ados, 0)
    while ados:
        if junior(ados[0]):
            classement.append(ados.pop(0))
            nb_juniors = nb_juniors + 1
            idx = prochain_junior(ados, 0)
        elif nb_juniors < 0.5 * (① + 1) and idx < len(ados):
            classement.append(ados.pop(②))
            nb_juniors = nb_juniors + 1
            idx = prochain_junior(ados, ③)
        else:
            classement.append(ados.pop(0))
            idx = idx - 1
    return classement

Une fois les classements de tous les ateliers retouchés, le centre utilise un algorithme d'affectation par préférences avec quotas (variante de l'algorithme des mariages stables) pour tenir compte à la fois des vœux des adolescents et des classements des animateurs.

Structures de données : les préférences sont un dictionnaire {adolescent : liste d'ateliers par ordre de préférence} ; les classements sont un dictionnaire {atelier : liste d'adolescents classés par les animateurs} ; les quotas sont un dictionnaire {atelier : capacité maximale}.

L'algorithme, pour chaque adolescent non encore affecté (dans un ordre quelconque) :

1. l'affecter provisoirement à l'atelier qu'il préfère parmi ceux qu'il n'a pas encore essayés ;
2. si la capacité de cet atelier est dépassée d'une unité, éliminer l'adolescent le moins bien classé par l'animateur parmi les affectés provisoires ;
3. l'adolescent éliminé retire cet atelier de ses préférences, et recommence à l'étape 1 avec son prochain choix.

5. Écrire, en Python, une fonction inserer_selon_classement(ado, classement, affectes) qui insère ado dans la liste affectes (adolescents déjà affectés à un atelier donné) à la position qui respecte l'ordre du classement de cet atelier.

6. Écrire une fonction récursive affecter(ado, affect, prefs, classts, quotas) qui modifie le dictionnaire affect pour y intégrer ado, en suivant les étapes 1 à 3 décrites ci-dessus.