Sujet 2010 et stratégies
Je m'occupe de la finale depuis des années, et c'est la première fois que je suis aussi ravi des résultats. Tous les points du sujet et toutes les subtilités ont été utilisés par des candidats. Des stratégies très différentes ont été élaborées - certaines sont originales et je n'y avais même pas pensé :) - et pourtant tout reste équilibré. Du coup, même dans les 10 premiers, on trouve des approches qui n'ont rien à voir. Voici un résumé de ce que j'ai vu.
Commençons par la technique de la "méga-combo". Ça consiste à avancer un chat le plus possible chez l'ennemi, près du perroquet adverse. Il se fait alors frapper. On le relève avec une potion, on le déguise en singe et on utilise banzaï pour qu'il puisse attaquer aussitôt en lançant une banane. Si l'adversaire ne s'y était pas préparé, il a perdu au 4e tour. :)
Certains ont basé leur stratégie uniquement sur cette combo. On garde les 3 cartes de côté, on crée des chats qui foncent sur l'ennemi. Avec un peu de chance, il y en a qui réussira à la placer.
Les stratégies à base de rush de chats semblaient assez populaires. On profite de la rapidité du chat pour contrôler rapidement le terrain et menacer l'ennemi. Certains complétaient leur armée avec quelques singes en défense, voire parfois un kangourou.
La carte pacifisme était assez peu jouée. Pourtant, je la trouve intéressante vers le 4e tour pour déployer son armée plus rapidement, ce qui était utile si on veut rusher ou juste contrôler le territoire. Si dans un tour on ne fait pas d'attaque, ou si la seule attaque que l'on fait est avec un banzaï, le pacifisme se révélait utile. On a souvent envie de jouer plus de 3 unités en un tour.
Certains ont aussi essayé "l'invasion pacifique". Il s'agit d'avancer 4 chats chez l'ennemi en même temps. À moins que l'adversaire sache jouer efficacement avec le banzaï, il y a généralement un chat ou deux qui passent. C'est une technique assez délicate à mettre en œuvre, mais ça peut être efficace.
Il y a aussi la stratégie appelée "La meilleure attaque, c'est la défense". Ça consiste à garder toutes ses unités en défense et à abattre toute unité qui se rapproche. C'est une technique un peu lâche, mais qui peut marcher. Pour gagner, on compte sur le temps et le terrain qui se rétrécit (les unités sont alors forcées de se rapprocher).
Il y avait donc des champions très offensifs, type rush ; et des champions très défensifs. Certains faisaient un peu les deux, avec un groupe en attaque et un groupe en défense. Il y a aussi un candidat qui essayait d'envoyer un chat pour bloquer la case de renforts de l'ennemi. Mais l'histoire ne dit pas si ça marchait vraiment.
Si les chats ont été souvent utilisés en masse, ce n'est pas le cas chez tout le monde. Il y a (au moins) un candidat qui n'a utilisé que des kangourous. C'est assez explosif, il faut prendre un certain nombre de précautions et se méfier des explosions en chaîne, mais c'est efficace contre beaucoup de champions.
Sans aller jusqu'à cet extrême, avoir quelques kangourous peut faire mal dans les rangs adverses. Un kangourou peut être déguisé en chat pour se jeter chez l'ennemi, qui hésitera à deux fois avant de le faire exploser. Ça peut être redoutable si l'adversaire n'est pas préparé à ce type d'attaque.
Dans les cas critiques, notre perroquet se retrouver parfois seul face à un ennemi. Dans ces cas-là, on a vu des "perroquets-ninjas". Certains se transformaient en chat pour fuir à toute vitesse ; d'autres se déguisaient pour mettre l'adversaire à terre.
Sur les 10 premiers, j'ai compté 4 champions en Python, 1 en Caml, 2 en C, 2 en C++, 1 Java.
Comme d'habitude, si vous avez des remarques, critiques, insultes sur le sujet, je serai ravi de les entendre. Si vous avez utilisé des stratégies que je ne mentionne pas dans ce message, n'hésitez pas à l'indiquer.
Enfin, n'oubliez pas de relire le sujet et cherchez les références, citations et plagiats dans le texte. C'est votre jeu post-finale. :)
- Vous devez vous identifier ou créer un compte pour écrire des commentaires
Suivez-nous !
Les partenaires grâce à qui Prologin peut exister :
Python will rule the world!
Ah, le « méga-combo », on me l'a expliqué, mais ensuite, j'ai plus pensé au Jeu qu'à lui :/
donc je l'ai pas pris en compte, et j'me fais exploser en match 1 contre 1 contre Jill-Jênn !
« La meilleure attaque, c'est la défense », c'est moi, ou presque, j'attaque un peu, et ma défense est foireuse /o\
« Dans ces cas-là, on a vu des "perroquets-ninjas". Certains se transformaient en chat pour fuir à toute vitesse ; d'autres se déguisaient pour mettre l'adversaire à terre. », c'est moi aussi ! En théorie...
Oh, tien, ce serait cool une vraie GUI, au fait.
Python powaa!
Voici ma stratégie:
Tour 1: Deplacer perroquet + créer kangoo
Tour 2: déplacer kangoo vers l'ennemi + créer singe
Tour 3: utiliser déguisement pour le kangoo pour le déguiser en chat, avancer de 5cases vers ennemi. + création Dun 2ème singe.
ÉDIT: Jai remarqué que pas mal de défenses tuaient mon kangoo avec leurs chats, sans vérifier, de ce fais leur (et parfois leurS) chat explosaient avec!
Note: au début de chaque tour, je vérifie si mon Kangoo est KO, si oui, j'utilise potion. Je vérifie aussi si qqchose est dans la portée des singes dans le but de défendre le perroquet.
Après, création Dun chat qui se déplace autour du perroquet pour le protéger + avancée du kangoo pour avoir perroquet dans sa zone est BOOM.
Il y avait un plus un truc style:
if ( (tour_actuel+1)%5==0 ) #si tour suivant = rétrécissement map
alors je déplace les unités
Voici les principales caractéristiques
In web I trust.
Sekler> Ouais, vive les Kangourous \o/
J'aime l'idée de ne pas avoir à se prendre la tête pour se placer a cote de l'ennemi pour l'attaquer ^^
In web I trust.
la strategie du 4 chats etait beaucoup plus subtile :
il falait utiliser pacifisme pour avoir 4 chats chez l'ennemi
OU relever un chat et en avancer 3 autres en utilisant pacifisme + potion
ensuite, l'ennemi avait du mal a tuer 4 chats en un seul tour (en general, c'est dur d'en tuer 4, meme avec banzai, des singes et des kangourous ne suffisent pas souvent) , et il se faisait tuer par un des chats.
@Sekler: ET ça t'as permis de finir cbème cette stratégie? (en tout cas sur le papier elle rend bien ;-) )
34eme.
En fait, ma défense avait un problème, je n'ai pas eu le temps de le résoudre:
un chat hors de porté de mes singes mais à 5 cases de mon perroquet, pouvais m'avoir. je n'ai pas eu le temps de bien faire le comprtement du chat en fait :/
In web I trust.
On a vu une stratégie dans les 10 premiers qui n'utilisait aucun Kangourou aussi.
Certains on pensé à développer une stratégie de relève de KO. (Et ne pas prendre tout le temps le premier)
Je n'ai pas eu beaucoup de temps à consacrer à la recherche de stratégie, y a eu beaucoup de choses à faire pour préparer et aider... mais j'essayerai d'y penser un peu.
La stratégie défense totale, je crois que c'est la mienne et je termine 10ème...
Tous les chats en défense sans exception et on ne laisse rien passé!!(sauf les meilleurs :( )
"La meilleur attaque c'est la défense"
Je connais quelqu'un (jaloyan) qui profite des segfault de l'adversaire pour gagner.
D'ailleurs je me demande si mon programme ne fait pas la même chose...
En effet, c'était ma stratégie de base, avant que je décide de la changer. (et dire que si j'avais trouvé le combo avec les 3 cartes, j'aurais surement gagné 10 places)
Ma stratégie de base (qui m'aurait valu la première place à coup sûr) consistait a envoyé mon perroquet attaquer le perroquet adverse. C'était un peu copié sur mc100s, inventeur de la stratégie. Il se nomme Triton le perroquet fou.
En lisant tout ça, j'ai trop envie d'être déjà à la prochaine finale. Ma stratégie était trop bidon, ça m'apprendra à ne pas assez réflechir avant de coder.
Pareil, sauf que j'aurais pas l'occasion de refaire xD finale. Ca m'apprendra à venir en touriste sans réflexion préalable sur comment faire une IA ou coder tout plein de règle de jeu :p
Moi j'dis, Progolin à 21 ans or gtfo.
Je suis pour aussi (même si je n'ai que 16 ans).
je dis non, car sinon on va se taper JJ et thomas une année de plus.
T'façon JJ vous le reverrez en tant qu'orga moi j'dis, comme ça il pourra jouer à Tetrinet plus que cette fois ci.
jaloyan : « En effet, c'était ma stratégie de base, avant que je décide de la changer. (et dire que si j'avais trouvé le combo avec les 3 cartes, j'aurais surement gagné 10 places) »
→ Ou pas.
TLN : « T'façon JJ vous le reverrez en tant qu'orga moi j'dis, comme ça il pourra jouer à Tetrinet plus que cette fois ci. »
→ En fait, si on fait le compte, il y a 3-4 candidats qui m'ont demandé si je serais orga l'année prochaine et 2 orgas qui m'ont dit : « Ah, ouf, on ne le reverra plus. » Ça tombe bien, pour ces deux orgas je me suis dit la même chose :) Mais bon, ouais, je ferai au moins un sujet d'épreuve régionale.
Président Prologin 2012
moi, c'était la technique de rush avec uniquement des chats avec une influence entre les unités pour qu'elles s'espacent le plus possible lors de l'attaque (mieux vaut être le moins proche de l'ennemi possible à par du perroquet et également espacer mes propres unités car si ça passe pas d'un coté, peut-être que ça passe de l'autre). méga-combo ou banzai ou coup normal pour tuer l'adversaire
je n'attaquais que pour tuer l'adversaire ou protéger mon perroquet (quand il est a portée d'un ennemi) mais pas de sentinelle, juste un code pour le bouger si il est en danger.
pacifisme était utilisé dès qu'un mouvement sans attaque sur le tour était nécessaire quand j'ai atteint la limite
et ça m'a permis d'être 3ème :-)
j'avais tenté le bouclier pendant l'après midi mais j'ai observé que je n'avais pas assez de temps pour le former et je l'ai donc abandonné (c'est d'ailleurs pour ça que je n'avais pas de code à soumettre pour le match)
sinon, une remarque : ça aurait été utile d'avoir un identifiant unique pour chaque unité pour le cas ou on veut faire une correspondance entre une classe qui contient des données et un personnage.
mon idée de départ était de faire une classe unité et de faire ensuite des héritage Sentinelle, Attaquant,... qui définissaient leur comportement (c'est comme ça que j'avais fait sur le sujet ou on contrôlait les globules blanc dans le corps humain). j'avais perdu beaucoup de temps à coder une liste de pointeurs, à surcharger les fonctions de déplacement et à vérifier à partir des positions pour garder les mêmes pointeurs entre les différents tours.
et un autre truc qui pourrait être utile : une fonction qui permet d'afficher du texte au dessus des cases dans l'interface graphique, ce serait vraiment plus simple pour débugger son code (ça permettrait notamment de visualiser si l'entité nous appartient ou appartient à l'ennemi, de numéroter les cases, d'afficher l'influence mapping calculé,...)
Oulala, je comprends pourquoi tu as fini 3e !
EDIT : Je ne parle pas de la stratégie globale, mais de tous les détails et du pavé (pioché dans le README ?) fourni.
En vrai y'avait bien un id dans chaque unité, je l'ai pas vu non plus et j'ai eu du mal aussi à tenir les pointeurs (enfin références, ici) à jour, mais ça se faisait. C'était clairement plus facile d'utiliser les ids effectivement.
En tout cas je suis bien content de pas être le seul à avoir tenté l'idée des influence maps (sauf que j'ai pas pu l'implémenter correctement), et surtout de voir que c'est efficace !
T'en as entendu parler où ? J'ai lu cette technique dans "AI Game Programming Wisdom", mais j'en ai pas trop entendu parler ailleurs, d'où ma question.
L'id faisait bien partis de la structure, un unit.id me renvoyait un nombre entre 0 et 9. ( je l'ai vu en faisant un print unit avec python --> tous les attributs s'affichaient.)
Pas mal ton ebook ^^
Moi j'ai essayé de faire un mix entre défense et attaque mais j'aurais du me focaliser uniquement sur l'un des deux car on perd trop de temps à mettre en place à la fois les unités , mais aussi pour choisir si le tour sera attaque ou défense , sachant qu'en général ca paralyse pas mal la suite car sa bloque ou le respawn ou bien le rush en cours.
Bref, comme TLN j'aurais pas l'occasion de m'y reprendre donc tampix X).
Pourquoi vous faites pas la version 20 - 25 ans ?
En plus tous le monde serais majeur du coup tous les interdits serais levé ! On pourrais boire ! xD
... Je sors
"Pourquoi vous faites pas la version 20 - 25 ans ?"
Ça demande beaucoup de temps et d'argent. On ne peut pas tout faire.
`"Pourquoi vous faites pas la version 20 - 25 ans ?"
Ça demande beaucoup de temps et d'argent. On ne peut pas tout faire.`
Ouais certes ^^".
A ce propos y'aurait pas d'autre concours similaire pour notre tranche d'âge ?
Hum. Les IOI ? J'sais pas à quels âges on peut y participer. Mais c'est bien plus académique.
« En tout cas je suis bien content de pas être le seul à avoir tenté l'idée des influence maps (sauf que j'ai pas pu l'implémenter correctement), et surtout de voir que c'est efficace ! »
Ce que j'ai appelé zones de contrôle ? Genre les cases où tu peux tuer sur la map ? J'en ai fait et je m'en suis servi, mais pas avec une stratégie très astucieuse. :þ
Les IOI sont réservées aux mineurs.
Non les ioi c'est encore pire (du moins si c'est comme les oim), vous devez être au maximum en terminale pour participer.
Sinon y a toujours l'ACM ou le Google Code Jam (dont les qualifications commencent bientôt). C'est pour les grands mais c'est plus du style "épreuve machine de demi-finale". Donc en gros ça n'a rien à voir avec la finale de Prologin. Je ne pense pas qu'il y ait d'autres événement aussi intéressant que la finale Prologin pour les grands en tout cas.
Il ya le concours Wingineer :D ... avec un programmation en ... NetLogo !!
Jviens de voir le google jam (et je viens de m'inscrire car l'épreuve de séléction commence vendredi à 23h00 UTC).
Par contre le systéme de submit est completement différent du votre.
On développe le truc en local, quand on a fini on clic sur un lien qui lance le téléchargement d'un fichier d'entrée et un timer se déclanche. On a 2 ou 4 minute selon l'exo pour soumettre la sortie de notre algo. (D'après ce que j'ai compris des explications en anglais ^^").
Le timer c'est le genre de truc qui doit être trop stressant je sens XD
Erf, je peux pas faire le Google Jam cette année, on n'a pas le droit de le faire en même temps que le Summer of Code ><
Après on peut toujours tenter de motiver les orgas pour un défi de l'été \o/ (Et les participants aussi, parce que la dernière fois...)
L'été dernier je travaillais donc c'était pas évidant.
Par contre cette été je vais glander donc jpourrais m'y donner à coeur joie X)
Le google Jam à l'air sympa en tous cas.
Le seul hic c'est les sujets uniquement en anglais. J'ai pas trop de mal à les comprendre mais déjà qu'un sujet de prologin en francais j'arrive pas à valider parce que je fais pas attention à une contrainte alors la... XD
Ilod t'a photo sur facebook est vraiment immonde...
*ta *alléchante
Ilod, moi perso' j'ai un stage de recherche qui m'empêche de faire le summer of code. Et puis t'façon j'ai moyen envie de passer mon été à faire du développement xD
En revanche le google code jam ça m'intéresse un peu plus. Bon le coup du timer je trouve que ça change de la façon dont on submit sur Prologin, mais finalement c'est toujours un peu pareil. Et puis shaolan si tu n'aimes pas les énoncés en anglais n'essaie pas non plus les pb d'ACM :p
Pour ma part en tout cas je trouve souvent les sujets d'ACM plus clairs que les sujets de demi-finale Prologin, au niveau de ce qu'on a le droit de faire ou pas. Après les entrées sont parfois plus tordues, mais ça c'est un autre pb.
« En tout cas je suis bien content de pas être le seul à avoir tenté l'idée des influence maps (sauf que j'ai pas pu l'implémenter correctement), et surtout de voir que c'est efficace !
T'en as entendu parler où ? »
dans un des game programming gem
j'avais implémenté ça sur le défi de l'été sur le corps humain et ça fonctionnait parfaitement (comme les cibles étaient très nombreuses et avec des intérêts différents (tuer les bactéries est moins important que tuer un virus), on pouvait diffuser l'influence plus loin que juste la case et donc une case au centre de 3 cibles gagnait plus d'importance que la case d'une entité isolée, de plus, je rajoutait une importance au temps depuis que j'ai pas visité une case, et comme on avait un brouillard de guerre, un petit mélange de l'influence map avec les influences map des tours précédents permettait de garder une évolution temporelle (trace d'une entité qui vient de disparaitre du champs de vision)
TLN -> Ouais mais au final ca reste correct même en anglais, jsuis en train de faire les exo du qualification round de 2009 et ca derange pas plus que ça au final ^^
Par contre si j'ai bien compris c'est la finale qui a lieu a Berlin hein ? xD
Le Google Code Jam je l'aurais bien fait, mais il tombe mal. Je serai pas là tout le samedi.
Par contre si j'ai bien compris c'est la finale qui a lieu a Berlin hein ? xD
Il me semblait que c'était à Dublin, mais il faudrait que je vérifie.
C'est faisable en python le GCJ ? Ou il y a des langages imposés?
C'est faisable de regarder la FAQ ? :p
http://code.google.com/codejam/faq.html
Can I use an obscure or exotic coding language?
Absolutely!
Donc tu peux utiliser du Caml ou du PHP ;)
Le principe étant d'uploader des fichiers out, et ton code pour la vérification (si besoin est), tu peux tout avoir.
Cool! Thx, mais sur iphone j'avais un peu la flemme de faire une recherche...
Jvais le faire , si j'ai bien compris, pour les qualifs ca a l'air simple (l'annee derniere il suffisait de resoudre le premier exercice qui etait un exo sur les chaines de caracteres simplisimme). Apres ya les autres tours... ( 3) puis la finale.... Je pense pouvoir me qualifier mais pour le premier tour je vais me faire eliminer, ca me semble chaud...
Sinon, j'ai pas trop pige, tout les tours se font depuis chez nous aussi? Jtrouve ca bizarre, on peut tricher facilement, et ce serait con que ce soit un bon tricheur qui fasse partie des 25 premiers pour la finale....
Edit: Perso, jle ferais en C (deja qu'avec les langages que je "connais" je galere... jvais pas m'amuser à le faire en je ne sais quel langage... (qui veut le faire en malboge??? ^^ Ou en ook))
En gros :
1 - Qualification Round : ce soir à 1h du mat. 3 exos d'algo sont proposés et il vous suffit d'en reussir un seul complètement (qui passe les contraintes de temps small input et large input) pour être qualifié pour la prochaine manche.
2 - Round 1 : Tous les qualifiés sont repartis en trois groupe, et chaque groupe s'affronte sur des exos d'algo durant le week end du 22 mai. Pour chaque groupe, les 1000 meilleurs sont qualifiés pour le round 2 (soit 3000 personnes).
3 - Round 2 : Une epreuve pour les 3000 retenus de la manche précedente, seule les 500 premiers sont qualifié.
4 - Round 3 : A partir de la vous êtes dans les 500 premiers et vous gagnez un t-shirt Google Code Jam, cette fois-ci y'en a que 25 qui seront qualifié pour la finale
5 - Final Round : Les 25 meilleurs s'affrontent à Dublin , tout est financé par Google pour le voyage et vous avez la garantie de remporter au moins 100$ si vous vous classez entre 25 et 4 ème. Les 3 premiers de cette finale remporte entre 1000$ et 5000$.
Voila pour les explications ^^
Il me semble que si l'on fail sur le premier groupe dans le Round 1, on peut recommencer dans le deuxième groupe, puis dans le troisième. A confirmer cela dit.
C'était le cas l'an dernier. L'année d'avant c'était un seul essai pour le round 1, et 1/3 des gens à chaque date.
Sinon, comment ca se deroule en fait les differentes phases en ligne ? Parce que pour le practice, la soumission est assez etonnante car il fallait telecharger un fichier input, et renvoyer l'output de notre programme. Je m'attendais plutot à la soumission d'un fichier dans le langage qu'on souhaitait utiliser (j'ai d'ailleurs galere un bon moment en envoyant un fichier .c pour un exo tout con, à chaque fois le site me disait " Erreur, votre output ne commence pas par Case #1:" alors que sur ideone ca marchait nickel...).
Est ce pareil lors des differentes phases? (si c'est le cas c'est un peu moche...)
Bah d'un autre côté ça te permet de coder en Brainfuck si tu veux :p