Available nodes

 Atomic Teddy 🧸 Investors1

La Sicile a été finalement envahie, et les ours ont vaincu l'armée du Grand-Duc. Se mêlant aux humains, ils se mêlent aux divers aspects de la société, reprenant à leur compte les divers métiers propres à la race humaine2. L'un des aspects qui les fascine est celui de l'économie de marché. Sur les places de marché de l'île, ils se mettent à jouer les magnats, les barons, les grands seigneurs, afin d'arrondir leur pécule personnel ventripotent. Dans leurs costumes impeccables, ils prospectent les villes à la recherche d'opportunités d'achat et de revente, dans un but finalement assez simple : du miel, rien que du miel. Leur appât du gain est certainement plus gourmand que cupide, et on admettra que leur compréhension de la mécanique économique reste un peu hasardeuse, ce qui donne l'objet de ce sujet, qui décrit ces ensembles d'échanges à la manière d'un jeu.

Dans la Sicile en question s'échangent donc un ensemble de ressources fixé de manière globale au début de la partie. Par exemple, pour une partie donnée, les ressources peuvent être le miel, les moteurs de hors-bord et les clés à molette. Une ressource est décrite par un identifiant et une chaîne de caractères. Pour que le jeu soit économiquement intéressant, il existe systématiquement une ressource nommée Honey. Chaque ressource a une valeur de référence, à savoir un nombre entier définissant sa valeur en équivalent-Honey. La valeur de référence du Honey est de 1. D'une manière générale, lorsqu'il s'agit de compter des ressources, les comptes sont faits en unités entières, et les ressources sont stockées dans un portefeuille. Naturellement, la valeur de référence d'un portefeuille est la somme des valeurs des ressources qu'il contient. Tous ces types de données sont spécifiés dans un fichier good.h  :

// An enumeration of the existing goods
enum good {
           HONEY,           // Always first
           MONKEY_WRENCH,
           OUTBOARD_MOTOR,
           MAX_GOOD,        // Always last
           ERROR_GOOD = -1, // Always -1
};

// A description of a good
const char* good__string(enum good g);
// The base value of a good (in equivalent-Honey)
unsigned int good__value(enum good g);

// A wallet containing different amounts of goods
struct wallet {
  unsigned int data[MAX_GOOD];
};

La Sicile dispose aussi d'un certain nombre de places d'échange, qui permettent de vendre ou d'acheter des ressources. Concrètement, dans une place d'échange, il est possible d'effectuer un ensemble de transactions. Une transaction se caractérise par un portefeuille de ressources achetées, et un portefeuille de ressources vendues. Les places d'échange et les transactions sont fixées pour une partie donnée. Initialement (dans ce sujet), il n'existe qu'une seule place d'échange fournie par une méthode starting_stockex(). Mais il va de soi que cette place d'échange peut proposer plusieurs transactions différentes.

Exemple : la place d'échange de Catane autorise 2 sortes de transactions : •  10 Honey et 1 Clé à Molette contre 1 Moteur de Hors-Bord.
•  et 1 Moteur de Hors-Bord contre 20 Honey.

Pour que le marché ne soit pas de dupes, une transaction qui propose une ressource à la vente ne peut acheter la même, et réciproquement. L'interface des places d'échange est spécifiée dans un fichier stockex.h  :
// The type representing stock exchanges
struct stockex;
// The type representing transactions
struct transac;

// The starting stock exchange
const struct stockex* starting_stockex();

// The name of the stock exchange
const char*           stockex__name(const struct stockex* s);

// Iterator on transactions : the first function returns the number
// `n` of available transactions, and the second accesses them with
// indices ranging between 0 and n-1.
size_t                stockex__num_transactions(const struct stockex* t);
const struct transac* stockex__transaction(const struct stockex* t, size_t num);
// The goods bought by the stock exchange
struct wallet         transac__in_wallet(const struct transac* s);
// The goods sold by the stock exchange
struct wallet         transac__out_wallet(const struct transac* s);

Chaque ours (aussi appelés dans la suite teddy) dispose d'un portefeuille de ressources personnel, contenant initialement simplement 1000 Honey, et se situe à la place d'échange par défaut fournie par starting_stockex(). A tout instant, il ne peut se trouver que dans une seule place d'échange3. A chaque tour de jeu, il sélectionne une transaction aléatoirement, décide d'un nombre positif N de fois où il réalise cette transaction (de manière à ce que ce nombre soit réalisable, cf. plus loin), soustrait N fois le vecteur de ressources achetées de son portefeuille, et ajoute N fois le vecteur de ressources vendues. Le temps passé à faire cette transaction est 1+log_2(N) unités de temps (1 pour une ressource, 2 pour 2 ressources, 3 pour 3 ou 4 ressources ...). Le code d'honneur des ours et des hommes d'affaires est très clair : il est interdit d'avoir un nombre négatif d'une quelconque ressource. Les échanges prennent un certain temps à se faire, mais les ordres d'achats sont considérés comme atomiques4. Si par hasard, le teddy ne pouvait pas réaliser la transaction choisie sans passer dans les négatifs, il passe son tour pendant une unité de temps.

Les ours jouent dans un ordre fixé par une file de priorité. La priorité est fixée par l'ours ayant dépensé le moins de temps jusqu'à présent. Si plusieurs ours ont la même priorité, l'un d'entre eux est choisi de manière non spécifiée (pour l'instant). Au bout d'un temps fixé, le vainqueur est celui dont la valeur de référence du portefeuille en Honey est la plus grande.

Sur les données : les données de jeu (ressources, places d'échange et transactions) doivent être codées dans les fichiers good.[ch] et stockex.[ch]. Le projet à réaliser doit forcément contenir ces 4 fichiers. Il est demandé à chaque équipe d'écrire une version personnelle de ces fichiers pour varier les règles du jeu. Le projet doit pouvoir continuer à fonctionner si on remplace ces 4 fichiers par une version différente respectant les même interfaces pour les fonctions.
Sur les 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.

 É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 4 fichiers src/good.[ch] et src/stockex.[ch]. Les deux .h sont fournis dans la première partie du sujet. Les deux .c devront respecter ces interfaces. Il est autorisé de modifier le contenu du type enum good. Les tests pourront utiliser (et devront passer avec) des versions différentes des .c et du type enum good que celles existant dans le dépôt.
  • 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 un ensemble complet de tours 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 -m pour indiquer le nombre de tours,
      • et un autre 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, 1000 turns, 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 -m 1000     # One optional parameter for the number of turns (here 1000)
    • 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.
  • 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.

Le programme doit mettre en place un système de jeu, pendant lesquels des teddies vont pouvoir agir les uns à la suite des autres pour échanger des ressources. Le programme se termine lorsqu'un nombre maximal de tours de jeu passé en paramètre est dépassé. Dans cette partie, il n'existe qu'une seule place d'échange. Le pseudo-algorithme de la boucle principale est le suivant :
queue = init_queue()
global_time = 0
While (global_time < max_party_time)
  active_teddy = queue.pop()
  global_time = active_teddy.time
  time_spent = active_teddy.play()
  queue.push(active_teddy, global_time + time_spent)
display_results()
Le projet suggère la décomposition des tâches suivante :
  • Manipuler des ressources et des transactions

    Implémenter les structures de données et les fonctions permettant de manipuler des valeurs de type
    good, stockex et transac. A terme, il est demandé de pouvoir fournir au moins deux versions différentes des biens et transactions possibles en jeu.
  • Implémenter une file de priorité

    Construire une structure de données pour une file de priorité nommée struct queue dans laquelle placer les joueurs de type struct teddy, et les sélectionner en prenant en priorité le joueur le plus rapide. La file doit pouvoir répondre aux opérations suivantes : ajouter un joueur dans la file avec une priorité égale au tour suivant auquel il peut jouer, donner le joueur pouvant jouer le plus tôt, et sortir de la file le joueur pouvant jouer le plus tôt. Pour les besoins du sujet, cette file de priorité devra se conformer à l'interface :
    struct queue  queue__new(); // create new empty queue
    void          queue__push(struct queue* h, int priority, struct teddy* t); // push teddy `t` into queue `h` with priority `priority`
    struct teddy* queue__top(struct queue* h);  // return the priority teddy in the queue `h`
    struct teddy* queue__pop(struct queue* h); // return and remove the priority teddy from the queue `h`
    
  • Mettre la boucle de jeu en place

    É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 teddies jouent de manière aléatoire, en sélectionnant une place d'échange disponible (la seule possible au départ), puis en essayant d'échanger des ressources sur cette place d'échange, en quantité aléatoire choisie dans la limite de leurs moyens.
  • Assurer le respect des règles

    Mettre en place les vérifications nécessaires par la boucle de jeu pour 1) empêcher les teddies de faire plusieurs transactions à un même tour dans leur fonction play, et 2) empêcher les teddies de dépenser des ressources dont ils ne disposent pas. Tout teddy sortant hors des clous est évincé de l'ensemble des joueurs, perd toutes ses ressources et ce faisant ne participe pas au classement final.
Le nombre de teddies maximal est de 20. Le nombre de ressources différentes est limité à 20. Le nombre de places d'échange est limité à 100. Le nombre de transactions maximal dans une place d'échange de de 100. La durée d'une partie est par défaut de 1000.

 Achievement 1 : Security Business / 🧷🧩🧧🧹🧶🧭🧸🧽 🧦🧹🧷🧭🧲🧩🧷🧷

Les ours apprenant bien vite de leurs homologues humains, ils se rendent bien vite compte qu'il y a avantage à chercher les meilleurs endroits où faire des affaires. Las, ceci reste bien monotone si tous les marchés sont accessibles immédiatement. Pour pallier ce problème, il est proposé d'améliorer le système des places d'échange5. La place d'échange de départ permet d'accéder à un certain nombre de transactions possibles. Mais effectuer des transactions permet maintenant d'accéder à de nouvelles places d'échange, qui en retour permettent de choisir de nouvelles transactions. Concrètement, on considère que les fonctions suivantes sont ajoutées au fichier stockex.h :
// The stock exchange where the transaction is done
const struct stockex* transac__stockex(const struct transac* s);
// The stock exchange reached after the transaction
const struct stockex* transac__next_stockex(const struct transac* s);

La fonction transac__next_stockex renvoie une place d'échange qui est accessible après avoir réalisé (au moins) une transaction sur la place d'échange initiale. Chaque transaction permet ainsi d'accéder à une place d'échange, mais plusieurs transactions peuvent permettre d'accéder à la même place d'échange. Dans tous les cas, la place d'échange atteignable grâce à une transaction reste la même au cours de la partie.

La boucle principale de jeu joue le rôle d'agent de contrôle et vérifie que les teddies ne font des transactions que depuis la place d'échange courante (et pas une autre obtenu précédemment qui les arrangerait mieux). De par leur curiosité, les teddies choisissent d'explorer le plus possible les places d'échange accessibles, afin d'avoir une bonne vision de l'ensemble du marché, et donc ils sélectionnent une transaction parmi celles permettant d'accéder à des places d'échange qu'ils n'ont jamais rencontré s'il en existe, et sinon en tirant au hasard.

 Achievement 2 : Strategy is Key / 🧷🧸🧶🧥🧸🧩🧫🧽 🧭🧷 🧯🧩🧽

Il est bien inconsidéré de croire que les ours se cantonnent à une compréhension de l'économie lacunaire. Les économistes humains ont d'ailleurs un peu trop tendance à se moquer du marché de l'ours6. Dans un univers dans lequel les places de marché offrent les biens à des prix différents, il ne faut pas être grand clerc pour se rendre compte qu'il est parfois plus malin de choisir les transactions au meileur rendement. Examinons dans cette partie une tactique d'optimisation des gains.

Ainsi, on propose que les teddies se comportent avec des stratégies positionnelles : à une place d'échange donnée, ils savent exactement quelle transaction réaliser. Pour simplifier, on considérera qu'ils ne font qu'une seule fois l'échange de la transaction en question. Implémenter de telles stratégies pour les teddies. Inventer une notion de stratégie positionnelle optimale par rapport à la fonction de gain et (plus difficile) implémenter une fonction recherchant une telle stratégie. On pourra autoriser quelques latitudes quant à l'exactitude de l'optimalité de la stratégie obtenue si elles sont justifié&es d'un point de vue algorithmique.

Accessoirement, on désire autoriser à ce que tous les ours ne disposent pas de la même stratégie. Trouver un moyen d'associer une stratégie à un ours, afin de faire jouer des ours "aléatoires" contre des ours "optimaux".

 Achievement 3 : Global Warning / 🧫🧰🧳🧦🧥🧰 🧻🧥🧶🧲🧭🧲🧫

Dans un petit monde insulaire, les ressources disponibles sont limitées, et les valeurs des ressources évoluent au cours de la partie. Chaque ressource (sauf le Honey) est associée à une quantité maximale en jeu. Il n'est plus possible de réaliser un échange si cela implique que l'ensemble des ressources possédées par les teddies dépasse les valeurs maximales autorisées. Toute requête d'achat alors qu'il reste moins de 10% des ressources disponibles fait augmenter la valeur de référence de la ressource de 1. Toute requête de vente alors qu'il reste plus de 90% des ressources disponibles fait baisser la valeur de référence de la ressource de 1, avec une valeur minimale de 2.

Pour réaliser cet achievement, les fonctions suivantes ajoutées au fichier good.h :

// The maximal amount of a good (returns UINT_MAX if g == Honey)
unsigned int good__total_amount(enum good g);
// Modifies the total amount of a good
void good__set_total_amount(enum good d, unsigned int v);
// Modifies the value of a good (supposes g != Honey, v >= 2)
void good__set_value(enum good g, unsigned int v);

Comme pour les autres parties, c'est à la boucle principale de jeu de contrôler les valeurs des différentes ressources et de les modifier au fur et à mesure de la partie.

 Achievement 4 : Concurrence is Bliss / 🧧🧳🧲🧧🧹🧶🧶🧩🧲🧧🧩 🧭🧷 🧦🧰🧭🧷🧷

Actuellement, l'ordre de jeu ne spécifie pas de règle de priorité pour deux ou plusieurs teddies ayant la même priorité. C'est injuste, surtout si l'on commence à modifier les valeurs des ressources. La règle suivante est proposée pour départager les teddies~: lorsque plusieurs teddies ont la même priorité sur la même place d'échange, l'un d'entre eux est sélectionné aléatoirement, et il vole une des ressources les plus chères à chacun de ses adversaires, en les remboursant avec une de ses ressources les moins chères.

De plus, il existe maintenant un teddy particulier nommé Swiper7 qui ne fait aucune transaction, peut accéder instantanément à toutes les places d'échange, et à chaque fois qu'il joue, est remplacé dans la file de priorité à la priorité du teddy suivant.

 Achievement 5 : Loopy Fingers / 🧰🧳🧳🧴🧽 🧪🧭🧲🧫🧩🧶🧷

Un nouveau type de stratégie est proposé pour les teddies, consistant à rechercher des suites de transactions qui soient positives. Une suite de transactions positive est telle que, à la fin de cette série de transactions, l'ensemble des ressources du porteur n'a fait qu'augmenter (strictement pour au moins l'une des ressources, le reste au sens large). L'idée étant que de telles boucles sont de bonnes stratégies de jeu.

Mettre en place un algorithme capable de détecter l'existence ou non d'une boucle positive dans l'ensemble des places de marché. Optionnellement, renvoyer la boucle de meilleur rendement.

L'utilisation de la bibliothèque lpsolve est autorisée pour construire un tel algorithme. Un exemple d'utilisation est accessible ici.

 Contact

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

1.Spéciale dédicace à un certain Atomic Hornet, le premier qui trouve ce qui signifie ce titre avant le dernier achievement gagne tout mon respect et 1 point sur sa note finale.
2.Si rien de cela ne vous inspire à aller lire du Dino Buzatti, le film est censé être à l'affiche au moment où ce projet débute.
3.A moins d'avoir le don d'ubiquité ou de tricher, mais il devrait y avoir quelqu'un qui vérifie l'application à la fois des règles du jeu et de la physique la plus élémentaire.
4.Je sens bien que vous êtes déçu, il y avait un certain potentiel narratif à considérer des ours jouant avec la physique de l'atome. Mais en fait, non, ce sujet reste d'une tristesse algorithmique très pacifiste, aucun animal ne devant être blessé au cours d'une partie.
5.Mille excuses pour une extension du sujet aussi prévisible, mais, je vous le promets, raisonnable en termes d'implémentation.
6.Le 'Bear market', en opposition au 'Bull market', est une expression dénotant un marché baissier, censément parce que les ours donnent des coups de patte vers le bas en attaquant. Mais allez donc demander à un taureau de grimper à un arbre.
7.Swiper, no swiping !