Sujet de 1997

Bonjour,
étant passionné de fouilles archéologiques, j'ai fait un tour dans les archives des finales précedentes.
Quelle ne fût pas ma surprise de constater un exemplaire des années 1997, que je conseille soit dit en passant. Mais, ô décéption, l'archive n'était pas complète, il manquait la pièce maitresse. Qui pourra me sortir de ce mauvais pas?

En clair, il manque malheuresement la Table des sorts du sujet de final 1997, Ba&bel Panic. Si un gentil orga pouvait le remettre en ligne (enfin, si vous l'avez toujours \^\^' ), ce serait très cool.

Merci beaucoup.

Oh mon 42, il y a des gens qui lisent les sujets de finale des années précédentes ! Pourquoi ne pas les refaire tant qu'on y est ?

Pendant l'été y'a un an et demi avec un pote on s'est fait le sujet de 2008 parce que je le trouvais sympa, et pour se faire un duel entre nous. :p

Qui a gagné ?

Moi. :p

Je doute qu'on est encore ça :-)
Ce qui est en ligne semble être tout ce que l'on a pour cette finale qui a eu lieu il y a 15 ans (tout même !)

ait* (Signé JJ, pour ne pas imiter ... Artifère, c'était toi qui avait signé JJ ?)

Vous aurez remarqué que le sujet de 1997 est en Comic Sans.

Fort à propos, vous proposez des entraînements pour résoudre les sujets de finale ?

Parce que le site ne semble en proposer aucun, et même France IOI ne va pas jusque là.

Or programmer une IA est horriblement difficile ( selon moi ) : si je suis de mesure de résoudre une bonne part des exercices je ne sais absolument pas comment procéder avec une IA.

C'est véritablement d'un autre niveau de difficulté.

Vous ne connaissez rien qui pourrait servir d'entraînement ?

J'étais toujours été surpris de voir des gens capables d'en programmer avec pour seul bagage apparent France IOI et Prologin.

Si tu es assez motivé pour passer beaucoup de temps sur ce genre de problème, Topcoder propose des marathons matchs, mais bon, les sujets sont souvent plus complexes et plus axés algorithmique, et la durée de ces marathons matchs est d'une semaine il me semble. Je n'en ai jamais fait (enfin, j'ai essayé de bidouiller un code rapide en quelques dizaines de minutes, mais rien de très constructif), donc je ne sais pas si ça entraîne bien pour Prologin.
http://community.topcoder.com/longcontest/?module=ViewActiveContests

Après, y'a un concours organisé par Google me semble-t-il, qui cette année était basé sur le développement d'une colonie de fourmis http://aichallenge.org/ , mais là tu dois partir de 0 (pas de fonction chemin, l'api est bien plus réduite, mais en même temps, tu as beaucoup plus de temps. Epsilon012 comptait y participer, je ne sais pas s'il a beaucoup travaillé dessus et fait une bonne soumission. Mais il est quand même mieux placé pour t'en parler, par rapport à quelqu'un qui s'est contenté d'un random et d'une recherche basique de profondeur 2 \^\^).

Je ne pense pas connaitre autre chose.

Mon but est de ne pas être démuni à la finale de 2013 (quel optimisme !) si jamais j'y parviens.

J'ai l'impression que ces sujets de finale s'éloignent de l'algorithmie pure puisqu'il faut programmer tout une IA ( chose que je n'ai jamais faite !).

Ouaip, tout à fait. Enfin, ça dépend, si tu veux faire une intelligence artificielle extrêmement sophistiquée, ce sera très algorithmique, mais "algorithmique floue" (je ne connais pas le terme exact) à base de réseau de neurones, et de trucs marrants comme ça.
Et même sans ça, le sujet de 2011 était très algorithmique, Pole Kirchner avait eu une très bonne place en implémentant un Djikstra modifié.
Essaie le second lien, c'est surement ce qui se rapproche le plus de ce qui peut t'intéresser, ou bien essaie de récupérer le serveur des autres finales ou d'en recréer un , ou même de te créer ton propre jeu, en essayant d'éviter de créer un jeu trop déséquilibré.

Et pour te rassurer, je n'avais jamais fait la moindre IA avant la finale de 2012, et je m'en suis pas trop mal sorti:
si tu n'as pas de grandes connaissances en intelligence artificielle, tu peux compenser cette lacune par une stratégie simple mais efficace.
Et si tu veux augmenter tes connaissances en intelligence artificielle, mieux vaut que quelqu'un passe par là pour te donner des conseils, parce que tout ce que je connais de ce domaine est très réduit et très peu utile pour la finale (soit trop complexe avec réseau de neurones, soit trop lent avec les algorithmes min max/alpha beta).

@alex3er :
« Pole Kirchner » heuu… daiphormassion de la part d'alex3er Comte. :p
C'était Arnaud je crois le Dijkstra modifié.
Sinon, pour aichallenge, bah j'avais pas trop le temps mais j'avais un super algo de pathfinding (pour les curieux, j'avais mélangé JPS et swamp, ça trouvait le chemin optimal plus rapidement que A*)… mais j'avais que ça.

@²lgorythme :
Le meilleur entraînement pour une finale, c'est une autre finale, sinon hormis ça, tu peux en effet t'essayer un peu sur aichallenge. Mais tu n'as pas besoin de te lancer dans l'intelligence artificielle, personnellement j'ai déjà eut des cours d'AI à la fac, je n'y ais rien appris d'utile pour la finale Prologin.

epsilon: Oui, c'est delfare (le nouvel orga, celui qui nous a parlé de la faille serveur qui permettait de gagner 1000000 de points par tour -- mais je ne me souviens plus si tu étais là). Bref, c'est le seul qui avait du courage à la bataille d'eau ! (à part ceux qui s'occupaient de debug le serveur, ce qui nécessitait sûrement encore plus de courage)

J'ai trouvé ce qu'était JPS (ça a l'air intéressant, d'ailleurs), mais swamp ... ?
EDIT: C'est bon !
Pour ceux qui voudraient en savoir plus et qui sont trp paresseux pour googler : https://harablog.wordpress.com/category/pathfinding/ et https://research.microsoft.com/apps/pubs/default.aspx?id=153668