Concours de rentrée 2021 - Synchro-donjon !

[Pavel]

Par curiosité de voir comment l'algorithme A* contrôle les quatre héros en même temps, j'ai implémenté une version plus rapide de l'algorithme A* en C++ et je l'ai interfacé avec le code en Python. Ça reste quand même très lent (~10 secondes par plateau) mais j'aime regarder les héros bouger tout seuls. Le code se trouve dans ce dépôt.

[Lephe]

Ah mais tu as pris une heuristique correcte, c'est sûr que c'est lent. Honnêtement je suis pas surpris, avec les 10-100 millions d'états. Il "faut" pousser un peu pour accélérer la convergence, le plus simple étant de mettre des poids sur les coûts G/H en insistant sur le H. Dasn ce cas tu n'es pas correct dans le sens où tu n'a pas l'optimal, mais ça suffit. Et pour ton heuristique tu pourrais mettre la distance optimale comme ça pas de compromis

[ArtichautCosmique]

Bonsoir !
Merci pour ce concours et à ses organisateurs ! Je n'ai pas l'habitude de faire de l'algorithmique, du coup c'était super à faire !
Pour mon algo, j'ai d'abord repris l'IA "greedy", et remarqué que l'ordre pouvait changer pas mal au score, sauf que je ne savais pas du tout prévoir le coût de chaque ordre de joueur. J'ai juste copié la fonction play_board et viré les parties inutiles.
Ça m'a permit de faire des "pré simulations" où à la fin je savais le score maximal en fonction de l'ordre. Je pensais pouvoir prédire les graines avec cette fonction mais (mal)heureusement Lephe avait tout prévu xD
Sur ses conseils j'ai quand même gardé la fonction mais sans pouvoir prédire les pièges, il fallait la graine pour ça.
J'ai fait une fonction tour_wrapper qui va, sur une nouvelle partie, jouer les 8 ordres idéaux (l'intérêt du coup de pouvoir séparer la "vraie" fonction de tour).
C'est plus lent et sûrement moins opti que ce qu'ont pu faire Pavel et SlyVTT, mais j'ai pu atteindre les 60 points par plateau avec ça.
Ensuite j'avais vu passer des noms d'algo dans le thread du concours Alrys, notamment Dijkstra et A* (je les connaissais pas du tout), c'est une vidéo de SlyVTT qui m'a donné envie d'implémenter ça, donc merci
J'ai regardé des bouts de pseudo-code sur Wikipédia et d'autres sites dont je ne me souviens pas le nom, et essayé de mettre une sorte de Dijkstra en python (bon mon truc est super lent et pas optimisé certes x)). Là j'avais 70 points par plateau, et d'autres petits fix m'ont permis d'aller à 80.
J'ai fait un pavé déso déso ><"
Pour conclure, en plus des organisateurs merci à cell·eux qui ont participé, c'était encore mieux avec la concurrence ! (Concurrence un peu trop forte vers la fin )
Pour le lot, je veux bien le premier lot de goodies, la clé USB TI est juste trop cute.
Encore merci !

[Lephe]

Merci beaucoup ! Tu as bien mis la pression au début du concours avec tes 70, je pense que ça a servi d'objectif à battre pendant la majorité d'Octobre.

C'est à ton tour @Afyu. Toi aussi tu as été assez loin, jusqu'à apprendre et implémenter Dijkstra pour passer les 75, alors que je m'attendais surtout à recevoir des petites astuces empilées par-dessus calculer_chemin(). Quel lot te serait utile ?

• 1 lot Goodies n°2 : 1 recueil d'activités SNT Numworks (65 pages) + 1 clé USB simulateurs CASIO (8 Go) + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio
  
  
• 1 lot Goodies n°3 : 1 cahier «Boss des maths» Numworks (80 pages) + 1 clé USB simulateurs CASIO (8 Go) + 1 sac et stylo Casio + 1 pack de goodies TI-Planète Casio

[Afyu]

Bonsoir,

Je remercie beaucoup Lephe pour l'organisation de ce concours au sujet plutôt sympathique, relativement accessible mais qui laissait la place à de grandes améliorations en allant jusqu'à l'élaboration ou l'implémentation d'algorithmes vraiment compliqués et pointus. Ce concours m'a demandé de la réflexion et des efforts et m'a permis de me dépasser (un peu, beaucoup ?) avec l'implémentation d'un algorithme que je pensais être la manière d'appliquer l'algorithme de Dijkstra telle qu'enseignée en Term ES spé maths (lorsque cette filière existait encore). Je me suis inspiré de l'algorithme calculer_chemin présent dans le fichier ia3greed.py et de ce que j'ai lu sur cette page https://128mots.com/index.php/2021/03/1 ... ra-python/ mais en appliquant la méthode d'application manuelle de l'algorithme telle que décrite dans ce diaporama.

Ma meilleure participation envoyée commence par calculer la distance séparant chacun des 4 joueurs de sa sortie respective et ordonne ces joueurs par ordre croissant de distance, mais en intervertissant les deux premiers. Il semble en effet plus rentable de commencer par le joueur qui a la 2ème plus petite distance.
Ensuite, on cherche à déterminer le plus court chemin à parcourir pour attendre la sortie et on refait ce calcul à chaque changement de joueur ou à chaque fois qu'il y a un changement sur le plateau : lorsque l'activation d'un piège fait apparaître des pics ou des pièges (oui, pardon, c'est dommage mais j'ai oublié de faire ça lorsqu'un monstre est tué !).
Cette dernière participation fait 100 lignes exactement, sans tasser. Mes précédentes participations sont plus longues et moins propres, mais montrent les idées que j'ai eues et que j'ai essayé de mettre en place (avec plus ou moins de succès !).

Pour les optimisations que j'ai essayées, il y a, entre autres, et pas forcément dans l'ordre dans lequel je les ai essayées :

• Modifier l'ordre de sortie des joueurs
• Modifier l'ordre de test des 4 directions lors de la recherche du chemin de sortie pour chaque joueur, dans l'algorithme BFS donné
• Modifier la prise en compte ou non de la présence des pièges lorsqu'on attaque un monstre
• Réduire la recherche des monstres à la seule direction dans laquelle on s'apprête à avancer et non pas systématiquement dans les 4 directions possibles
• Modifier l'algorithme BFS donné pour qu'il prenne en compte également la présence des pièges ou des pics et pas uniquement la présence des murs
• Remplacer l'algorithme BFS donné par un "BFS avec pénalités" ou "Dijkstra exotique" ou "Dijkstra manuel Term ES spé maths" (appelez-le comme vous voulez )
• Modifier la pondération des différents obstacles présents sur le plateau (monstres, pics, pièges) dans l'algorithme de recherche de chemin

Je remercie Lephe pour ses retours assez rapides et toujours accompagnés de commentaires pertinents et d'encouragements !

Concernant le lot, j'aurais volontiers pris le lot Goodies n°1. Mais il a déjà été choisi, alors c'est avec grand plaisir que je ne prendrai que la satisfaction d'avoir participé à ce concours et d'avoir dépassé le score symbolique de 70 points et d'avoir même dépassé les 75 points (!) au prix d'efforts réguliers.
Je laisse donc mon lot aux participants suivants.

J'espère que ma réponse est complète. Je suis désolé pour le temps de réponse.

[Dubs]

Bonjour

Je me joins aux autres participants pour remercier Lephe d'avoir organisé ce concours.

Je n'ai pas eu/pris le temps d'améliorer mon second script et j'en suis navré .
Pour "rentrer" dans le concours, j'ai modifié légèrement le pathfind proposé pour trouver un chemin qui évite les murs ET les pics, pour les 4 joueurs.
Ensuite je déroule les 4 chemins trouvés pour tous les joueurs (le chemin de jaune est appliqué aux autres) pour ne prendre que le plus court qui ne fait pas passer un autre joueur par un pic.
C'est à peu près tout.

Je me suis ensuite focalisé sur le défi d'Alrys qui m'a phagocyté tout mon temps...
Ce défi est pourtant très intéressant, j'avais pas mal d'idées et de pistes d'améliorations.

Je regarderai les autres réponses à tête reposée.

Pour le lot : le "Goodies n°2" me tente bien (j'ai déjà la clef d'émulation casio)
1 recueil d'activités SNT Numworks (65 pages) + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio

Merci encore !

[Lephe]

Merci beaucoup. Cette épreuve m'a aussi fait très plaisir à concevoir, même si manifestement Critor est plus agile que moi pour faire des défis à la fois très abordables et captivants.

Afyu, je n'ai pas d'autre clé USB TI-83 PCE malheureusement, mais je peux trouver une batterie externe si c'est ça qui t'intéresse. Ce serait dommage que tu repartes sans lot !

Ta méthode est maline Dubs, en partant des IAs d'exemple le plus grand défaut est bien l'usage des pics, et tu as surveillé tous les joueurs. Tu es allé direct dans une direction efficace !

D'accord pour lot, merci. Il me faudra juste ton adresse par mail pour te l'envoyer.

[Afyu]

Afyu, je n'ai pas d'autre clé USB TI-83 PCE malheureusement, mais je peux trouver une batterie externe si c'est ça qui t'intéresse.

Haha, pas de chance, j'ai déjà cette batterie externe (gagnée au concours Casio de fin d'année en 2020) et c'est la clé USB TI-83 PCE qui m'intéressait beaucoup. Mais ne t'en fais pas, c'est vraiment pas grave.

Ce serait dommage que tu repartes sans lot !

Non, vraiment pas. J'ai déjà abusé de la générosité des concours de la rentrée sur TI-Planet et Planète Casio depuis 2019.
C'est vraiment avec plaisir que je laisse mon lot, en espérant qu'il plaise à Eragon, qui finit 6ème et n'espérait peut-être pas gagner quelque chose.

[Lephe]

Re-bonjour ! Les lots ne sont pas encore partis (je suis sous l'eau), mais ça ne saurait plus tarder maintenant, je serai damné s'ils ne sont pas tous dans ma boîte aux lettres Samedi. Désolé pour le contretemps !

[Lephe]

Les trois premiers colis (Pavel, SlyVTT, ArtichautCosmique) sont prêts à partir Lundi matin. Vous devriez être informés par mail/SMS du suivi.

Pavel, ton colis sera remis en main propre (c'était la seule option), les autres seront en boîte aux lettres.

Les deux autres colis (Dubs, Eragon) suivront Mardi