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"
Sur l’ensemble du projet, il est demandé de réaliser au fur et à mesure les tâches suivantes :
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 :
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
Pour une raison relativement technique, une fois un ordre passé (i.e., affichage
sur la sortie standard), il faut aussi le flush
er. Pour cela vous avez deux
solutions :
printf
par fflush(stdout);
setvbuf(stdout, NULL, _IOLBF, 0);
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
, nigets
. Préférerfgets
etsscanf
.
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"
Nous vous fournissons une archive tar gz contenant trois répertoires :
tools
maps
example_bots
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 :
Makefile
.Des points seront enlevés pour tout fichier exécutable ou objet et pour tous les fichiers que vous nous fournissons déjà.
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.
Comme le site ne vous les fournit plus, vous les trouverez en fin de cette page. ↩