CrimsonDeus wrote:Hello tout le monde ! Tout d'abord un grand merci pour ce concours. Le problème est bien pensé et amusant, l'interface d'évaluation a la classe et l'organisation s'est bien déroulée. Ça a dû demander pas mal de boulot donc mes félicitations aux organisateurs.
D'après ce que je comprend j'ai le droit d'écrire un pavé donc je vais d'abord vous parler de mes IAs qui ont fait 4%, 90.5%, 90.8% et 93.7% puis brièvement des autres IAs qu'on aurait pu faire. Mais avant ça je pense que ce qui m'a le plus aidé pour gagner ce concours est de suivre un minimum de coding guidelines afin d'avoir du code stable, facilement debuggable et évolutif. J'ai cherché à éviter les effets de bords en évitant les variables globales. J'ai cherché à rendre le code flow clair à suivre en structurant avec des classes pythons et en limitant la longueur de mes fonctions. J'ai cherché à faire porter du sens à travers le nommage en choisissant des noms de variables plus ou moins clairs et concis selon leur scope. Cela m'a permis de rapidement développer mon IA et d'y ajouter mes nouvelles idées avec un minimum d'effort.
Pour commencer ma première participation était une IA troll pro Léviathan
En vrai c'est une IA modifiée de mon IA gagnante qui cherche à nourrir le plus possible le Léviathan. Elle va même jusqu'à éviter si possible la clé et surtout ne pas prendre la sortie si jamais elle a la clé. Son comportement est très proche de mon IA gagnante donc je ne vais pas développer plus mais elle a été autant optimisée que mon IA gagnante pour nourrir le Léviathan. Elle obtient un très joli score de 87% de mort par Léviathan.
L'IA que je considère gagnante de ce concours est mon IA à 90.5%. Pour chaque appel elle commence par récolter et déduire de l'information sur le labyrinthe puis elle cherche la prochaine action à faire selon qu'elle cherche la clé, qu'elle cherche la sortie ou cherche à aller à la sortie déjà connue.
La récolte d'informations se fait lorsqu'on explore une nouvelle corniche. On garde les informations sur une chauve-souris et sur la proximité avec la clé, le Léviathan ou un puits pour chaque corniche explorée. Puis on cherche à faire des déductions sur l'ensemble de l'information récoltée sur le labyrinthe. Par exemple, si une corniche explorée n'est pas à proximité d'un puits alors toutes ses voisines ne sont pas des puits Ensuite si une corniche à proximité d'un puits n'a plus qu'une seule voisine pour laquelle on n'est pas sûr d'avoir un puits et qu'aucune voisine est déjà un puits, alors cette voisine est un puits. Cela permet de détecter une partie des puits en explorant des corniches qui ne sont même pas toujours voisines du puits. Un autre exemple avec le Léviathan : si une corniche explorée est à proximité du Léviathan et qu'on a exploré toutes ses voisines, alors le Léviathan se trouve forcément dans les voisines des voisines que l'on connaît. On peut alors déduire que toutes les autres corniches n'ont pas le Léviathan. Un dernier exemple de déduction : si on a déterminé où se trouve la clé sans l'avoir encore récupéré, alors cette corniche n'est forcément pas un puits (et s'il y avait un puits de toute façon on aurait perdu mais le code de construction du labyrinthe empêche ce cas de figure).
Quand le Léviathan est détecté, on le tue avec la flèche si on l'a encore.
Selon que l'IA cherche à trouver la clé, aller à la clé, trouver la sortie ou aller à la sortie, le processus n'est pas le même mais les outils de raisonnement sont les mêmes. Le but est à chaque fois d'aller soit sur une corniche particulière comme celle avec la clé ou la sortie que je vais nommer corniches objectives, soit d'aller à une corniche inexplorée. On commence par chercher à aller sur les corniches objectives sûres en utilisant un chemin sûr c'est-à-dire sans chauve-souris. L'algorithme utilisé est itératif et en largeur ce qui permet d'avoir le plus court chemin sûr vers la corniche objective la plus proche. Si on ne trouve pas de chemin (ou qu'on n'a pas de corniches objectives parce qu'on cherche la sortie par exemple) alors on cherche à aller sur une corniche sûre inexplorée avec un chemin sûr. Déjà cette IA en répondant de manière aléatoire le reste du temps permet d'avoir un score au-dessus de 75%.
Lorsqu'on n'a pas de chemin sûr vers une corniche objective ou inexplorée, il faut choisir d'aller à la corniche la plus intéressante parmi les corniches accessibles. Pour cela on donne un score ou une probabilité de survie pour chaque corniche. Pour les corniches explorées sans chauve-souris le score est 1. Pour un puits le score est 0. Pour une corniche contenant possiblement le Léviathan, avec n le nombre de corniches avec possiblement le Léviathan, et m le nombre moyen de voisines et voisines de voisines d'une corniche, on prend le max entre 1 / nb et 1 / m.
J'ai fait un calcul plus compliqué pour la probabilité d'un puits. Voici la probabilité qu'une voisine soit un puits en fonction de la densité d des puits sans prendre en compte le reste des informations du labyrinthe. La probabilité d'avoir k puits avec n voisines est A(k,n)=(1-d)^(n-k)*d^k*Cb(k,n) avec Cb le coefficient binomial. S'il n'y a pas de puits identifié alors on cherche la probabilité d'avoir k puits sur n voisines sachant qu'on a au moins un puits : B(k,n)=A(k,n)/(1-A(0,n)). Ensuite la probabilité qu'une voisine soit un puits est C=Sum(k=1..n, B(k,n)) ce qui se simplifie en C=d/(1-(1-d)^n). S'il y a déjà un puits identifié alors la probabilité qu'une voisine soit un puits est simplement la densité d. Cela donne une formule assez sympa. Elle vérifie l'intuition que si par exemple on a deux voisines possiblement avec un puits alors la probabilité n'est pas 50% pour chaque voisine mais 50% + quelque chose pour prendre en compte le cas où on aurait non pas un puits mais deux puits.
Ensuite pour donner la probabilité d'un puits à une corniche, j'ai décidé de prendre la moyenne des probabilités que c'est un puits d'après ses voisines. La dernière étape d'optimisation de mon IA a montré que mon calcul n'était pas incroyable. Ce serait peut-être plus intéressant de calculer formellement la probabilité de puits en prenant en compte tout le labyrinthe exploré voir en incluant les probabilités d'avoir la clé vu qu'il ne peut pas y avoir de puits là où il y a la clé. Il y a peut-être un gentil prof de math pour m'éclairer.
On a maintenant une probabilité de survie pour chaque corniche et on sait qu'aucune corniche objective ou inexplorée sûre n'est accessible avec un chemin sûr. Pour l'ensemble des corniches objectives (non sûres du coup) accessibles avec un chemin sûr, on détermine celle avec la meilleure probabilité de survie. On fait de même avec les corniches inexplorées (non sûres également). Pour l'instant on choisit simplement de suivre la corniche avec la meilleure probabilité. Avec cela l'IA fait un score dans les 86% environ.
Au lieu d'explorer les corniches accessibles, on peut aussi tenter de voyager en chauve-souris pour espérer accéder à une corniche plus intéressante. Mais c'est assez difficile de déterminer quand c'est intéressant de le faire et ne donne pas forcément de gain significatif sur le score tel quel.
C'est un peu bête de mourir alors qu'on avait encore sa flèche. On détermine donc la corniche accessible inexplorée avec la meilleure probabilité de survie dans le cas où le Léviathan n'y serait pas. Si cette probabilité est supérieure aux autres candidats alors on tire la flèche vers cette corniche. Si elle tue le Léviathan on est très content. Sinon on sait au moins que cette corniche n'a pas le Léviathan. Cette optimisation permet d'atteindre un score d'environ 89%.
Lors de la prise de décision pour choisir entre aller vers une corniche non sûr ayant possiblement la clé ou une corniche non sûr inexplorée ou aller sur une corniche avec une chauve-souris par exemple, on utilise leurs probabilités de survie. On fait une pondération de ces probabilités avec des paramètres. Changer ces paramètres permet par exemple de privilégier une corniche non sûre avec la clé par rapport à une corniche non sûre inexplorée. On pondère aussi quelques éléments du calcul de probabilité de survie des corniches avec des paramètres notamment celui de la probabilité d'avoir un puits. L'objectif est maintenant de trouver un ensemble de paramètres qui optimise le score.
On utilise un simple algorithme génétique pour trouver le meilleur ensemble de paramètres. Pour cela il faut pouvoir calculer le score assez rapidement c'est-à-dire faire plein de simulations rapidement. J'ai donc modifié le code du déroulement de la partie pour le rendre thread safe afin de faire un grand ensemble de simulations de manière multithreader. Chez moi 100000 simulations prennent moins de 2min à tourner. J'ai ensuite lancé mon algo génétique pour trouver les meilleurs paramètres pendant toute une nuit. Il a probablement fait dans les 25 millions de simulations. En vrai l'algo génétique sature assez vite et continue de gagner que par la variation dans les mesures (qui est assez importante avec le générateur aléatoire de python). C'est ainsi que mon IA arrive au score de 90.5%.
Maintenant si vous êtes toujours là à me lire, mon IA à 90.8% est mon IA précédente tout en utilisant la prédiction de la prochaine corniche par une chauve-souris. Le "fix" du générateur aléatoire permet de déterminer trivialement la prochaine corniche par une chauve-souris en appelant tout simplement une seule fois rnd(). En quelques heures mon algo génétique n'a pas eu le temps de beaucoup tourner donc peut être que l'IA aurait pu atteindre 91%.
Vu cette exploitation, c'est pour cela que pour moi l'IA gagnante du concours est celle à 90.5%. J'ai d'ailleurs été très transparent dans toutes mes participations en expliquant toute tentative de contrôle ou d'exploitation des chauves-souris dans mes mails et en commentaire du code et en encourageant leur évaluation avec un tag invalide.
Lorsque Pavel a lancé son IA à 92.5%, j'ignorais s'il avait juste fait mieux ou s'il contrôlait les chauves souris. Mais 2% de plus c'est quand même beaucoup surtout que les derniers pourcentages sont les plus durs à avoir. J'ai donc envoyé en toute transparence dans mon mail une IA qui contrôle les chauves-souris. La fonction rnd() se fait craquer en 0.3s en moyenne chez moi. C'est dans la limite des 20s mais ça explique pourquoi, comme celle de Pavel, son évaluation prend du temps. C'était pas trivial de modifier mon IA gagnante pour utiliser au mieux les chauves-souris. D'ailleurs c'est une IA très flemmarde qui préfère faire un vol en chauve-souris que même se déplacer d'une corniche de plus sur un chemin sûr. C'est pourquoi cette IA a un trajet moyen de 24 alors que mon IA gagnante a un trajet moyen de 28. Après l'optimisation de mon algo génétique, cette IA atteint un score de 93.7%. Dans le cas où elle rate son contrôle de chauves-souris, elle fait autour de 50%. Au moins cette IA a forcé un fix du générateur aléatoire. J'ai juste peu apprécié qu'on mette en doute cette IA et non celle à 92.5% (au vu de l'écart de scores) et qu'on parle de suspicion de contrôle de chauves-souris alors que tout est explicitement dit dans mes mails. Mais finalement les organisateurs ont fait du très bon boulot en réagissant rapidement et en faisant une passe finale.
Toujours là à me lire ? Parlons brièvement des IAs qu'on aurait pu avoir. On aurait pu aller plus loin que le contrôle des chauves-souris. Les générateurs congruentiels linéaires peuvent non seulement être craqués facilement mais en plus on peut calculer toutes les valeurs précédemment générées ce qui représente une énorme faille de sécurité. On aurait donc pu créer une IA qui détermine toutes les valeurs utilisées pour créer le labyrinthe et ainsi déterminer tout le labyrinthe et cela avant même de faire un premier pas dedans. On aurait eu une IA avec un score de quasiment 100%. Le fix qui a été fait le dernier jour empêche le contrôle de chauves-souris mais n'empêche pas ce cas de figure. Évidemment cela casse le jeu parce qu'on remplace un joli problème d'IA par un petit problème de hacking contrairement au contrôle des chauves-souris.
Un autre problème du générateur aléatoire rnd() est que la seed prend qu'environ 64000 valeurs différentes. Cela signifie que sur 100000 simulations on repasse par les mêmes 64000 labyrinthes au lieu des milliards et plus labyrinthes différents. On aurait donc pu créer une IA qui apprend spécifiquement à bien se comporter sur ces 64000 labyrinthes (tout en étant peu performante sur les milliards et plus autres). Je pense donc qu'utiliser par exemple dans python une instance de la classe Random() du module random est préférable.
Une vraie idée d'amélioration est d'utiliser un algorithme d'apprentissage plus poussé qu'un simple algorithme génétique pour déterminer des meilleures probabilités de survie dans mon IA gagnante et/ou une meilleure prise de décision. Je pense à des algorithmes supervisés pour les probabilités de survie et des algos classiques de reinforcement learning pour une meilleure prise de décision (du DQN peut-être).
En espérant que ce pavé n'a pas été trop dur à lire, je souhaite encore remercier l'organisation et les participants pour ce chouette concours et vous souhaite de joyeuses fêtes.
by 
