Planet Wars

Le site AI Challenge propose un concours de stratégies (désormais terminé) basé sur le jeu Planet Wars. Il s’agit d’un jeu dans lequel deux adversaires tentent de s’approprier un ensemble de planètes en envoyant des flottes (d’émissaires pacifiques) pour les conquérir (en parlementant plus ou moins ardemment).

La spécification du jeu est entièrement décrite sur cette page. Concrètement, le jeu se déroule en un certain nombre de tours, au cours desquels chaque adversaire reçoit la position de l’ensemble des planètes et des flottes en jeu, et décide des nouvelles flottes à expédier.

Techniquement, les intelligences artificielles reçoivent les données sur l’entrée standard, et envoient leurs ordres sur la sortie standard. Le site fournissait1 des starter packages contenant un programme Java qui, lui, permet d’organiser un plateau de jeu avec lequel les robots interagissent. Ainsi, la commande suivante organise une partie entre les robots RandomBot.jar et DualBot.jar sur la carte maps/map7.txt (avec 1s max par tour et 1500 tour de jeu maximum) :

java -jar tools/PlayGame.jar maps/map7.txt 1000 1500 log.txt "java -jar example_bots/RandomBot.jar" "java -jar example_bots/DualBot.jar" | java -jar tools/ShowGame.jar

Vous pouvez remplacer les parties entre guillemets par la commande nécessaire pour lancer votre propre robot par example "./mybot"

Réalisation

Sur l’ensemble du projet, il est demandé de réaliser au fur et à mesure les tâches suivantes :

  • Réaliser un robot jouant la partie sans rien faire, puis un robot jouant aléatoirement
  • Écrire une fonction permettant de calculer, pour une planète donnée, le nombre de troupes actuellement prévues pour attaquer dans N tours.

Ensuite, il s’agira de transformer le problème en un problème d’allocation de ressources. On pourra s’inspirer de problèmes comme celui du sac à dos pour concevoir des algorithmes d’allocation, et on utilisera des heuristiques pour décider des mouvements de troupes à réaliser. Enfin, on finira par :

  • Battre les intelligences artificielles fournies avec le code.

Remarque : ceci reste un projet de programmation, et même s’il sera en partie évalué sur l’efficacité des stratégies mises en place, la qualité des algorithmes et du code produit auront une place prépondérant

Remarques techniques

Envoyer des ordres

Pour une raison relativement technique, une fois un ordre passé (i.e., affichage sur la sortie standard), il faut aussi le flusher. Pour cela vous avez deux solutions :

  • Faire suivre tous vos appels à printf par fflush(stdout);
  • Ajouter au debut de votre programme : setvbuf(stdout, NULL, _IOLBF, 0);

Lire les informations

Lire des informations structurées est une tâche potentiellement complexe. Plus la grammaire sous jacente est complexe, plus cette tâche est ardue. Dans le cas present, la grammaire est simple et nous éviterons de sortir les machines de guerres (lex/yacc/bison/antlr/…).

Si l’on omet les commentaires, les informations envoyés par le moteur du jeu semblent très régulières et scanf pourrait être notre ami. En effet, scanf permet de scanner des données formatées sur l’entrée standard et de stocker les valeurs lues dans des variables locales après conversion. Cependant scanf n’est pas approprié dans ce cas, les instructions sont de deux formes incompatibles : les lignes commençant par P et celles commençant par F, et ces deux types de lignes n’ont pas ni le même nombre ni le même type d’arguments. De plus, scanf n’est que très peu robustes aux lectures erronées, typiquement en presence d’un humain qui n’aurait pas tapé une phrase attendue. En fait une grande partie du problème vient du fait qu’après un appel à scanf les données sont consommées (donc plus disponible). L’idée va être de séparer en deux le travail de scanf :

1) Acquérir les données: fgets lit une ligne (cf plus tard). 2) Extraire l’information: sscanf réalise le même travail que scanf mais sur une chaine de caractère en entré au lieu de lire depuis un fichier.

Lire une ligne est (en vrai) une opération plus complexe qu’il n’y parait. Cependant certaines fonctions semblent bien faire le travail, par exemple gets. D’après la documentation, il ne faut jamais utiliser gets. En effet cette fonction lit une ligne sans limite de taille et la stocke dans un tableau. Hors tout tableau a une taille, c’est donc la porte ouverte aux attaques dites de dépassement de tampon. La documentation nous conseille d’utiliser fgets, cette dernière prend une taille maximum en paramètre. Malheureusement cette fonction n'a pas exactement le même comportement, elle lit une ligne (de longueur max - 1) incluant le \n et la termine par le zéro terminal (d'ou le -1). Je vous laisse vous demander pourquoi cette fonction inclue, si possible, le \n` ? (Que ce passe-t-il si le tampon est plus court que la ligne à lire).

En bref: ne pas utiliser scanf, ni gets. Préférer fgets et sscanf.

SVN

Subversion est un outil relativement puissant nécessitant certaines explications. Pour cela nous avons écrit un petit Guide d’utilisation de svn (existe en PDF). Bien entendu vous en trouverez plein d’autres sur le net puisqu’il semble que vous commenciez par lire openclassroom avant les ressources que nous vous fournissons.

Dans tous les cas, à l’ENSEIRB malheureusement les configurations par défaut sont un peu foireuses. Il faudrait changer deux fichiers pour qu’ils contiennent.

# ~/.subversion/config`
[auth]
password-stores = gnome-keyring
# ~/.subversion/servers
[global]
store-passwords = yes
store-plaintext-passwords = no

Vous pouvez aussi bêtement copier/coller les quelques lignes suivante qui feront le job, voire plus.

export
URL=http://www.labri.fr/perso/renault/working/teaching/projets/files
&& \
   mkdir -p ~/.subversion && \
   wget -q $URL/config-subversion -O ~/.subversion/config && \
   wget -q $URL/servers-subversion -O ~/.subversion/servers && \
   unset URL && echo "Subversion config updated"

Fichiers fournis

Nous vous fournissons une archive tar gz contenant trois répertoires :

tools
Viewer et Player en Java
maps
Un ensemble de cartes
example_bots
Des robots plus ou moins intelligents jouant a planet-wars.

Modalités de rendu

Les modalités de rendu sont à la discrétion du chargé de TD (svn/forge/mail/copie dans un dossier/…). Néanmoins, chaque rendu devra contenir :

  • Seulement votre code source et Makefile.

Des points seront enlevés pour tout fichier exécutable ou objet et pour tous les fichiers que vous nous fournissons déjà.

Rapport

Un rapport court vous sera demandé. Il devra décrire à haut niveau (pas de paraphrase de code), vos choix techniques et algorithmiques ; vos réflexions autour du jeu, etc. Votre chargé de TD définira les modalités de celui-ci.


  1. Comme le site ne vous les fournit plus, vous les trouverez en fin de cette page.