Available nodes

 Tilings

Ce sujet est construit sur l'idée de réaliser des pavages du plan, à l'aide d'objets simples nommés des tuiles de Wang. Il s'agit de tuiles carrées divisées en quatre triangles. Chaque triangle est associé à un côté du carré, et coloré d'une couleur particulière. Le dessin suivant permet de rapidement se faire une idée de la forme d'une tuile, ainsi que du fait que les couleurs des triangles ne sont pas forcément toutes distinctes1 :
La réalisation de ces pavages va se faire sous la forme d'un jeu à plusieurs joueurs, se jouant sur un plateau carré, dans lequel chaque joueur place à son tour une tuile de manière à 1) que l'ensemble des tuiles reste connexe et 2) que les bords de deux tuiles attenantes soient de même couleur. Les couleurs autorisées sont spécifiées dans le fichier color.h suivant  :
#ifndef _COLOR_H_
#define _COLOR_H_

struct color; // Anonymous struct for colors

// A string giving the color name
const char* color_name(const struct color* t);
// An ANSI-colored string describing the color
const char* color_cstring(const struct color* t);
// Return a color from its name, or NULL
// The relation between `name` and `struct color*` is bijective.
struct color* color_from_name(const char* name);

#endif // _COLOR_H_
Les tuiles sont arrangées dans des jeux de tuiles ou decks, qui sont simplement la donnée d'un ensemble de paires (tuile × quantité), chaque paire signifiant la présence d'une tuile répétée un certain nombre de fois dans le jeu. La description des tuiles est fixée dans le fichier tile.h  :
#ifndef _TILE_H_
#define _TILE_H_

#include "color.h"

enum direction { NORTH, SOUTH, EAST, WEST,
  MAX_DIRECTION, ERROR_DIRECTION = -1 };

struct tile; // Anonymous struct for tiles

#define MAX_DECK_SIZE 100
struct deck_pair {
  const struct tile* t; // a pointer to a tile
  unsigned int n;       // a number of occurrences of this tile
};

struct deck {
  struct deck_pair cards[MAX_DECK_SIZE]; // an array of struct deck_pair
  unsigned int size;                     // the number of struct deck_pair in `cards`
};

// A tile that is empty
const struct tile* empty_tile();
// A predicate telling if the tile is empty
int tile_is_empty(const struct tile* t);
// A comparator between tiles
int tile_equals(const struct tile* t1, const struct tile* t2);
// Accessors to the color of the edges
struct color* tile_edge(const struct tile* t, enum direction d);

// A function that fills a deck with tiles
// The contents of the deck `d` after the call must always be the same.
void deck_init(struct deck* d);

#endif // _TILE_H_
La fonction deck_init prend en paramètre un deck initialement vide, et le remplit avec un ensemble de tuiles particulier. Le projet est prévu pour pouvoir fournir différentes implémentations des fichiers color.[ch] et tile.[ch] afin de varier les parties possibles avec des couleurs différentes, des tuiles différentes, et des decks différents. Pour fixer les idées, voici un exemple de deck possible contenant 12 tuiles :
{ { , 4}, { , 2}, { , 2}, { , 2}, { , 2} }

Les règles du jeu sont particulièrement simples. Le jeu de tuiles est mélangé aléatoirement, et distribué équitablement aux joueurs. Chaque joueur fait une pile de l'ensemble de ses tuiles, et les joue une par une. Le premier joueur pose sa tuile aléatoirement sur le plateau, et ensuite, à chaque tour de jeu, chaque joueur dans l'ordre pose une tuile sur le plateau respectant les conditions de contiguïté et de connexité. Si un joueur ne peut pas poser de tuile à son tour, il remet sa tuile en dessous de sa pile et passe son tour. Si aucun joueur ne peut jouer, ou si un des joueurs a joué sa dernière tuile, la partie se termine. Par défaut, le joueur ayant posé le plus de tuiles gagne la partie.

Pour simplifier l'écriture de code, il est décidé que chaque fois qu'un joueur est placé devant un choix, il prend une décision aléatoire uniforme parmi l'ensemble des choix possibles. Le projet ne s'intéresse pas à l'écriture de stratégies pour les joueurs.

À propos des achievements : ce sujet de projet est construit sur la notion d'achievement. Un achievement est un ensemble de fonctionnalités à développer pour le projet. Les achievements doivent être réalisés dans l'ordre, et de manière cumulative. Ils seront débloqués à chaque fois qu'au moins une équipe de projet aura rempli les conditions de l'achievement précédent. La version de base correspond à l'achievement initial. L'évaluation du projet est basée en partie sur le nombre d'achievements réalisés. La version de base n'est pas forcément représentative du travail nécessaire pour atteindre la moyenne.

 Écriture du code

Le code écrit est censé respecter les standards de codage suivant :
  • Le code devra être organisé en répertoires de la manière suivante :
    latest/
            Makefile
            src/
            tst/
    achiev0/
            Makefile
            src/
            tst/
    achiev1/
    ...
    
    Le répertoire latest correspond au dernier achievement réalisé. Les autres répertoires achiev? sont des copies du code validant l'achievement en question. La version de base est considérée comme l'achievement 0.
  • Le code devra contenir (entre autres) 4 fichiers src/color.[ch] et src/tile.[ch]. Les deux .h sont fournis dans la première partie du sujet et ne doivent pas être modifiés. Les deux .c restent à écrire et devront respecter ces interfaces. Les tests devront passer avec des versions différentes de ces fichiers .c (et donc des types struct color et struct tile). En particulier, les tests automatiques fourniront une implémentation particulière avec lesquels le code devra continuer à compiler et s'exécuter correctement.
  • Chaque répertoire du projet (latest et achiev?) doit contenir un fichier Makefile permettant de le compiler et comportant au moins les règles ci-après.
    • Une règle principale permettant de compiler un exécutable appelé project, qui exécutera une partie entière de jeu comme spécifié ci-après, en prenant comme paramètres optionnels :
      • un paramètre optionnel -n pour indiquer le nombre de joueurs,
      • un paramètre optionnel -b pour indiquer la taille du plateau,
      • un paramètre optionnel -s pour initialiser le générateur aléatoire.
      Les exemples suivants donnent des idées sur les possibilités d'utilisation :
      ./project             # No parameters, 2 players, board 10x10, random initialization of the RNG
      ./project -n 5 -s 156 # One optional parameter for the number of players (here 5)
                            #     and an optional parameter to initialize the RNG (here 156)
      ./project -b 25       # One optional parameter for the size of the board (here 25x25)
    • Une règle test lançant l'ensemble des tests pour le dernier achievement réalisé. Chaque achievement est censé posséder ses propres tests dans un exécutable différent.
  • Chaque répertoire doit contenir un fichier source s'inspirant de ce fichier , qui (dans cet exemple, il reste à compléter) prend en paramètre une graine aléatoire à l'aide de l'option '-s'.
Un code qui ne compile pas est un code sans intérêt, et un code qui n'intéresse pas le responsable des projets est un code qui ne valide pas les projets.

 Base version

Pour valider la version de base du projet, il est demandé de produire un exécutable avec les caractéristiques décrites dans ce paragraphe.
Il n'y a aucun lien entre le fait de "valider la version de base" et celui de "valider le projet". Le fait de "valider la version de base" est simplement le premier pas vers la réalisation des achievements.
Le programme doit mettre en place un système de jeu, pendant lesquels des joueurs vont pouvoir placer des tuiles les uns à la suite des autres. Le programme se termine lorsque toutes les tuiles ont été jouées, ou que tous les joueurs ont passé leur tour. Le pseudo-algorithme de la boucle principale est le suivant :
d = deck_init();           b = board_init();
players = players_init();  n = players.length();
split_deck(d, players);
While the n last turns have not all been skipped
  active_player = get_next_player(players);
  t = active_player.cards.top();
  p = list_authorized_places(b, t);
  if (!p.is_empty())
    place_tile(b, select_position(p));
    active_player.cards.pop()
display_results()
Le projet suggère la décomposition des tâches suivante :
  • Créer des tuiles et des jeux de tuiles

    Implémenter les structures de données et les fonctions permettant de manipuler des valeurs de type color, tile et deck. A terme, il est demandé de pouvoir fournir au moins deux versions différentes des couleurs, tuiles et jeu de tuiles disponibles en jeu. Les couleurs et tuiles utilisées peuvent évidemment différer des exemples fournis ci-dessus.
  • Créer une structure de file pour gérer les jeux des joueurs

    Une telle file devrait pouvoir accepter d'insérer des éléments à l'intérieur (push), de récupérer un pointeur vers l'élément en tête de pile (top) ainsi que de retirer des éléments si la file n'est pas vide (pop), tout cela en respectant l'ordre d'insertion. Aussi, il faudra pouvoir mélanger, et distribuer un jeu de tuiles à un ensemble de joueurs. Même si c'est envisageable, le sujet n'impose pas de gérer la liste des joueurs avec une file2.
  • Mettre en place la boucle de jeu

    Écrire le code nécessaire pour pouvoir faire jouer une partie à un ensemble de joueurs, et afficher le joueur gagnant à la fin de la partie. Les joueurs font des choix aléatoires, en sélectionnant un emplacement autorisé aléatoirement parmi la liste des positions jouables. Le premier joueur peut jouer sur n'importe quelle case libre.
  • Assurer le respect des règles

    Mettre en place les vérifications nécessaires par la boucle de jeu pour 1) assurer que l'ensemble des tuiles en jeu reste connexe au cours de la partie et 2) vérifier que deux tuiles adjacentes partagent la même couleur sur leur jonction. Tout joueur sortant hors des clous est évincé de l'ensemble des joueurs actifs, ses tuiles restent en jeu, mais son score en fin de partie est nul.
Le nombre de joueurs maximal est de 20. Le nombre de couleurs différentes est compris entre 2 et 20. Le nombre de tuiles possibles dans un deck, et aussi dans la main d'un joueur, est de 200. La taille maximale du plateau est de 50x50.

 Achievement 1 : Patterns

Dans cette extension, les tuiles ont désormais un propriétaire, qui correspond au joueur ayant posé la tuile. Les règles du jeu définissent aussi un ensemble de motifs, rapportant chacun un certain nombre de points. Par exemple, le motif suivant représente une tuile rouge avec 4 tuiles voisines accolées, représentant un score de 34 points :
Motif : 
Score :  34
Chaque motif possède une tuile centrale, qui est utilisée pour déterminer le propriétaire du motif. Le nombre maximal de motifs pour une partie est de 20. La taille d'un motif est définie comme la distance maximale (de Chebyshev) d'une tuile du motif à la tuile centrale. La taille maximale d'un motif est de 2.

Le calcul du score final est modifié par rapport à la version de base, et correspond pour chaque joueur à la somme des scores des motifs dont il est propriétaire. Plusieurs motifs peuvent se recouvrir, tant qu'ils ont des tuiles centrales différentes.

 Achievement 2 : Connections

Dans cette extension, on propose une façon supplémentaire de marquer des points. Les couleurs des tuiles définissent des zones connexes du plan recouvrant un certain nombre de tuiles. Deux triangles de même couleur sont considérés comme connexes s'ils partagent une arête commune, ou un sommet commun qui est centre d'une tuile. Dans l'exemple suivant, considérant que les zones noires représentent des couleurs autres que la couleur rouge, la zone rouge recouvre 9 tuiles différentes :
Le score associé à une zone connexe est défini comme le carré du nombre de tuiles couvertes. Le propriétaire d'une zone connexe est défini comme le joueur étant le propriétaire d'un maximum de tuiles de cette zone. S'il y a plusieurs joueurs se partageant ce maximum, ils se partagent le score de la zone équitablement, en arrondissant à l'entier inférieur.

 Achievement 3 : Influence

Dans cette extension, on propose de modifier la façon dont les joueurs deviennent propriétaires des tuiles.

Chaque tuile possède un niveau (entier) de propriété par joueur. Le joueur qui joue une nouvelle tuile dispose d'un niveau de propriété de 100 sur cette tuile, tandis que celui des autres joueurs est nul. Mais un joueur qui pose une tuile adjacente à cette même tuile (dans les huit directions) après qu'elle ait été placée peut remonter son niveau de propriété. Le premier joueur à poser une tuile adjacente remonte son niveau de 90, le suivant de 80, et ainsi de suite pour les 8 voisins possibles. A chaque tour, les niveaux de propriété de tous les joueurs baissent de 1, sans jamais passer en dessous de 0. Le (ou les) propriétaires d'une tuile sont ceux dont le niveau de propriété sur cette tuile est maximal.

Un joueur supplémentaire nommé "The King" apparaît dans la liste des joueurs. Il ne dispose pas de jeu de tuiles, et ne pose jamais de tuiles. A son tour de jeu, il sélectionne aléatoirement un emplacement sur le plateau de jeu, saute dessus, et s'il tombe sur une tuile, réduit le niveau d'influence des propriétaires de toutes les tuiles atteignables de manière connexe sur la même ligne et la même colonne. Pour une tuile atteinte, le niveau d'influence du ou des propriétaires (et uniquement eux) est réduit de 50, les niveaux d'influence des autres joueurs ne sont pas modifiés.

Il peut donc toujours y avoir plusieurs propriétaires pour une tuile donnée. Si tous les joueurs ont un niveau de propriété nul sur la tuile, ils sont tous propriétaires. Les propriétaires d'une zone connexe sont ceux pour lesquels la somme de leurs niveaux de propriété sur les tuiles de la zone est maximal.

 Achievement 4 : Symmetries and Loops and Adjacencies

Dans cette extension, on propose que les tuiles puissent être utilisées à symétrie près. Il est alors possible d'appliquer aux tuiles des rotations à 90°, 180° ou 270°. Les compatibilités de couleurs entre tuiles ne sont pas modifiées, simplement, on permet d'utiliser une tuile donnée dans 4 configurations possibles3.

En parallèle, la notion d'adjacence entre emplacements du plateau est modifiée. Certains emplacements du plateau ne permettent pas de placer de tuiles, mais acceptent n'importe quelle tuile à côté. Certains emplacements du plateau voient leurs bords être associés à un autre emplacement du plateau. Cas d'application pratique : rendre le plateau torique et créer (en théorie, si la fin de partie recouvre l'ensemble du plateau) des pavages périodiques.

Enfin, les tuiles définissent maintenant elles-même leurs relations d'adjacence. Ainsi, sur une tuile donnée, deux triangles d'une même couleur partageant une arête peuvent ne pas être considérés comme adjacents. Réciproquement, deux triangles d'une même couleur se touchant uniquement sur un sommet peuvent être considérés comme adjacents. Par exemple, on pourrait considérer une tuile de la forme suivante :

dans laquelle les sommets nord et sud ne sont pas connectés, tandis que les sommets est et ouest le sont.
Ces trois extensions peuvent être gérées en parallèle ou en série, mais elles partagent toutes les trois une forme d'évolution du code. Laquelle ?

 Achievement 5 : Blocs

A chaque tour de jeu, le joueur peut désormais tirer une suite de tuiles accolées, et placées sur le terrain. Pour faire simple, il joue seul sur son plateau, prépare une "méta-tuile" composée de plusieurs tuiles accolées, et ensuite place cette "méta-tuile" sur le plateau. Il s'arrête de tirer des tuiles dès qu'aucun accolement n'est possible ou que la "méta-tuile" n'est plus plaçable sur le plan de jeu, ou que l'on a atteint un nombre maximum de 3 tuiles pour la "méta-tuile". Les accolements sont calculés de manière aléatoire, et les symétries s'appliquent au bloc entier.

 Contact

Pour toute information complémentaire, contacter : David RENAULT disponible aux séances d'encadrement le mardi et le vendredi.

1.Pour les personnes intéressées, par le sujet, le chapitre 1 de l'EJCIM 2017 (École de Jeunes Chercheurs en Informatique et Mathématique) donne un panorama des problèmes actuels, et la vidéo de Veritasium suivante sur Youtube fait de même avec un point de vue plus général.
2.Quoique la réalisation d'une implémentation d'une structure de données file qui évite de dupliquer le code entre les joueurs et les tuiles sera considérée comme un bonus.
3.Les plus aventureux des codeurs peuvent considérer à la fois les rotations et les symétries des tuiles, ce qui autorise 8 transformations possibles par tuile. Les plus combinatoristes peuvent argumenter sur le fait qu'on pourrait autoriser des symétries non continues. Ils peuvent le faire (je veux dire, argumenter).