Centrale Informatique MPI 2024Sujet, corrigé et rapport du jury

Le jeu de go

I Introduction au jeu de go

I.A - Présentation du sujet

I.B - Présentation et règles du jeu de go

Figure 1 Un goban vide de dimension 9, un premier coup de Noir, une configuration du jeu à un moment intermédiaire, et une configuration à la fin de la partie dans laquelle chaque intersection est contrôlée par un des deux joueurs.

Figure 2 À gauche: la pierre A a une pierre sur chacune de ses 4 intersections voisines. La pierre B n'a pas de pierres sur ses 4 intersections voisines. La pierre C a une pierre sur une de ses deux intersections voisines. Au milieu : les pierres 1,2,3,4 et 5 forment un groupe de pierres noires, la pierre 6 ne fait pas partie de ce groupe, ni les pierres blanches 7 et 8 . Ce groupe a 7 libertés. La pierre 9 a 3 libertés. Le groupe de pierre 10, 11, 12 a une seule liberté, si Blanc joue en ( 7,7 ) alors il capture immédiatement ce groupe, et les pierres 10, 11, 12 sont retirées du plateau. L'intersection (3, 7) est contrôlée par noir. À droite : un exemple de goban de dimension 5 en fin de partie.

I.C - Généralités sur le jeu de go

II Implémentation du jeu de go

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

struct goban_s {
    int d;
    int* m;
};
typedef struct goban_s goban;

struct couple_int {
    int i;
    int j;
};
typedef struct couple_int position;

position pos(int i, int j) {
    position p = {.i = i, .j = j};
    return p;
}

int lire(goban g, position p) {
    return g.m[p.i * g.d + p.j];
}
void ecrire(goban g, position p, int couleur) {
    g.m[p.i * g.d + p.j] = couleur;
}

struct voisins_s {
    int nb;
    position t[4];
};
typedef struct voisins_s voisins;

voisins pos_voisins(goban g, position p) {
    int i = p.i;
    int j = p.j;
    voisins v;
    if (...) {v.t[k] = pos(i - 1, j); k = k + 1;}
    if (...) {v.t[k] = pos(i + 1, j); k = k + 1;}
    if (...) {v.t[k] = pos(i, j - 1); k = k + 1;}
    if (...) {v.t[k] = pos(i, j + 1); k = k + 1;}
    v.nb = k;
    return v;
}

int liberte(goban g, position p) {
    goban g1 = groupe(g, p);
    int cpt = 0;
    int couleur = lire(g, p);
    for (int i = 0; i < g.d; i = i + 1) {
        for (int j = 0; j < g.d; j = j + 1) {
            position p2 = pos(i, j);
            if (lire(g1, p2) == couleur) {
                voisins v = pos_voisins(g1, p2);
                for (int k = 0; k < v.nb; k = k + 1) {
                    if (lire(g, v.t[k]) == 0) {
                        cpt = cpt + 1;
                    }
                }
            }
        }
    }
    return cpt;
}

III Prédiction et évaluation d'un prochain coup

III.A - K plus proches voisins

III.B - Hachage de Zobrist

Figure 3 Gauche : l'étendue du zoom 1 (les 4 intersections avec un carré noir), et du zoom 2 (les 11 intersections avec des carrés blancs, et une intersection extérieure à la grille non représentée) sur la position (3, 1). La case (2, 1) est en position (− 1, 0) dans les zooms sur la position (3, 1).

struct observation_s {
    int n; //nombre d'observations du motif au total
    int v; //nombre de fois ou ce motif a ete choisi
};
typedef struct observation_s observation;

struct table_de_hachage_s {
    int nt;
    observation* t;
};
typedef struct table_de_hachage_s t_hachage;

void maj_coup(t_hachage table, uint64_t* tableau_hache, goban gN, goban gB, int zoom) {
    for (int i = 0; i < gN.d; i = i + 1) {
        for (int j = 0; j < gN.d; j = j + 1) {
            position p = pos(i, j);
            maj_n(table, tableau_hache, gN, p);
            maj_v(table, tableau_hache, gN, gB, p);
        }
    }
}
void maj_t_hache(uint64_t* tableau_hache, goban gN, goban gNs, int zoom) {
    for (int i = 0; i < gN.d; i = i + 1) {
        for (int j = 0; j < gN.d; j = j + 1) {
            position p = pos(i, j);
            maj_h(tableau_hache, gN, gNs, zoom, p);
        }
    }
}

void maj_n(t_hachage table, uint64_t* tableau_hache, goban gN, position p),
void maj_v(t_hachage table, uint64_t* tableau_hache, goban gN, goban gB, position p),
void maj_h(uint64_t* tableau_hache, goban gN, goban gNs, int zoom, position p),
pour que les fonctions maj_coup et maj_t_hache mettent correctement à jour la table de hachage et le tableau
des valeurs de hachage.
Une partie de go sera représentée par une structure de liste simplement chaînée, chaque coup étant représenté par le goban actuel, le joueur qui doit jouer, et un pointeur vers le reste de la partie. Nous supposerons que les parties commencent par le goban vide associé au joueur d'indice 1 (Noir).

struct partie_s {
    goban g;
    int joueur;
    struct partie_s* suivant;
};
typedef struct partie_s partie;

struct table_table_de_hachage {
    int nz;
    t_hachage* t;
};
typedef struct table_table_de_hachage tt_hachage;

IV Recherche arborescente de Monte-Carlo

type joueur = Noir | Blanc
type intersection = Libre | Pierre_noire | Pierre_blanche
type goban = intersection array array
type position = int * int

• liste_coup_prior : goban -> joueur -> (position * float) list: prend un goban et un joueur et renvoie une liste, pour toutes les positions jouables dans le goban pour le joueur, de couples (position, prior) où prior est un flottant entre 0 et 1 correspondant à une estimation de la probabilité de victoire de Noir lorsque le joueur joue en position position.
• strategie_defaut : goban -> joueur -> position: prend un goban et un joueur et renvoie une position où jouer, en suivant une stratégie par défaut définie a priori, et qui peut contenir une part d'aléatoire. Cette fonction renvoie l'exception Pas_de_coup_valide lorsque le plateau est complètement contrôlé et qu'il n'y a plus de coup valide.
• gagnant : goban -> joueur : prend un goban complètement contrôlé et renvoie le joueur gagnant.
• joue : goban -> position -> joueur -> goban: prend un goban, une position et un joueur et renvoie le goban obtenu après que le joueur a joué en cette position. Le goban en entrée n'est pas modifié.
  Q 24. Écrire une fonction de signature js : joueur -> joueur qui prend un joueur et renvoie le joueur suivant.

IV.A - Simulation de partie pour évaluer une configuration

IV.B - Valeur d'action

• n : le nombre de visites du nœud, entier mutable
• v: le nombre de visites du nœud ayant mené à une victoire de Noir, entier mutable
• prior : la probabilité a priori de victoire de Noir donnée par la fonction liste_coups_prior, flottant
• pos: la position du coup associé au nœud, position
• t : un verrou, de type t . Mutex, qui sera utilisé pour mettre en place des parcours et mises à jour concurrentes de l'arbre.
  Afin de stocker ces données, les nœuds de l'arbre seront étiquetés par le type enregistrement etiquette.

type etiquette =
    {mutable n:int; mutable v:int; prior:float; pos:position; t:Mutex.t}

1 type arbre = N of etiquette * arbre list

IV.C - Descente et remontée dans l'arbre

• une descente dans l'arbre partiel en choisissant à chaque nœud le fils de valeur d'action maximale pour le joueur associé, afin de sélectionner une feuille qui semble prometteuse;
• une simulation de partie depuis cette feuille comme implémentée en partie IV.A, donnant un joueur vainqueur ;
• une remontée qui met à jour le nombre d'observations et de victoires pour Noir dans chaque nœud rencontré, le long de la branche reliant la feuille explorée à la racine de l'arbre.
  Ces étapes pourront être exécutées en parallèles par plusieurs fils d'exécution. Il est donc nécessaire de faire attention à ce que deux fils ne rentrent pas en conflit d'écriture et de lecture pour un champ mutable d'une étiquette de l'arbre, ce qui justifie l'intérêt des verrous associés à chaque nœud.
  De plus, pour décourager deux fils d'exécution de suivre la même branche lors de la descente, lorsque l'enfant d'un nœud est sélectionné par un fil d'exécution, ce fil va modifier l'étiquette de cet enfant pour lui ajouter des défaites virtuelles, ce qui baissera sa valeur d'action et donc son attractivité du point de vue des autres fils. Nous ajouterons 5 défaites virtuelles à un nœud s'il est sélectionné, en prenant soin d'enlever ces défaites virtuelles lors de la remontée.
  Lors de la descente, nous empêcherons ainsi un fil d'exécution de commencer à traiter un nœud, (c'est-à-dire de chercher l'enfant de ce nœud de valeur d'action maximale) si un autre fil d'exécution est déjà en train de traiter ce nœud. Nous attendrons que le fil d'exécution en cours ait ajouté des défaites virtuelles à la branche qu'il a choisi de suivre avant de commencer le traitement.
  Q 30. Écrire la fonction descente_remontee_arbre : goban → joueur → arbre → joueur qui prend un goban, le joueur dont c'est le tour et un arbre de jeu, et qui réalise une descente, une simulation et une remontée de l'arbre. Cette fonction renverra le joueur gagnant, et lors de la remontée mettra à jour les champs mutables des nœuds rencontrés. Une attention particulière sera portée sur le fait que cette fonction puisse être exécutée par plusieurs fils d'exécution concurrents.

IV.D - Expansion de l'arbre

IV.E - Algorithme complet

Éléments du langage OCaml

Module Mutex
    Mutex.t: Le type des mutex.
    Mutex.create : unit $\rightarrow$ Mutex.t: Renvoie un nouveau mutex.
    Mutex.lock : Mutex.t -> unit: Verrouille le mutex donné. Un seul fil d'exécution peut verrouiller le
    mutex à un moment donné. Un fil d'exécution tentant de verrouiller un mutex déjà verrouillé attendra
    jusqu'à ce que l'autre fil d'exécution déverouille le mutex.
    Mutex.unlock : Mutex.t $\rightarrow$ unit : Déverouille le mutex donné. Les autres fils d'exécution en pause ten-
    tant de verouiller le mutex reprennent. Le mutex doit avoir été verrouillé par le fil d'exécution qui appelle
    Mutex.unlock.

Module List
    List.iter : ('a -> unit) -> 'a list -> unit:iter f [a1; ...; an] applique la fonction f tour à
    tour à [a1; ...; an]. Cet application est équivalente à $f a 1 ; f a 2 ; \ldots ; f$ an.
    List.map : ('a -> 'b) -> 'a list -> 'b list: map f [a1; ...; an] applique la fonction f à a1,
    $\ldots$, an, et construit la liste $[\mathrm{f} \mathrm{a1;} \mathrm{...;} \mathrm{f} \mathrm{an]} \mathrm{avec} \mathrm{les} \mathrm{résultats} \mathrm{renvoyés} \mathrm{par} \mathrm{f}$.

Type enregistrement
    type exemple = {mutable a : int; b int}: permet de définir un type enregistrement.
    let c = {a = 1; b = 3} permet de définir une variable du type exemple.
    c.a permet d'accéder au champ a de c.
    c.a<-2 permet de modifier le champ mutable a du type enregistrement c.

Fonction de conversion de type
    float_of_int : int -> float: convertit un int en float.
    int_of_float : float -> int: convertit un float en int.

V Complexité du problème de la stratégie gagnante au go

Go généralisé

Figure 5 La formule φ = (v_1 ∨ v_5 ∨ v_7) ∧ (v_2 ∨ v_3 ∨ v_4) ∧ (¬v_1 ∨ ¬v_2 ∨ ¬v_3) ∧ (¬v_4 ∨ ¬v_6 ∨ ¬v_7) représentée graphiquement sous forme planaire rectiligne. Il est à noter que sur une telle représentation graphique, certaines clauses peuvent en enjamber d'autres. Ici, la clause ( v_1 ∨ v_5 ∨ v_7 ) enjambe la clause ( v_2 ∨ v_3 ∨ v_4 ).

Figure 6 Un exemple de réserve de pierres blanches presque capturée par le joueur noir (a), ainsi que deux sections de tuyaux (b) et (c). Des représentations simplifiées sont données en bas. En (d) une configuration de 13 pierres blanches que Blanc va chercher à relier à sa réserve de pierres blanches pour les sécuriser.

Figure 7 Trois gadgets qui seront utilisés pour la réduction, ainsi que leurs représentations simplifiées associées.

Figure 8 Un circuit représentant le choix d'une valuation, modélisée par le fait de choisir de relier le tuyau du haut ou le tuyau du bas à la réserve pour chaque variable.

Figure 9 Un gadget permettant à Blanc de vérifier que le littéral de son choix est bien satisfait dans une clause, mais qui bloque le passage à d'autres clauses éventuelles comme C_i ou C_j qui peuvent être enjambées.