Concours de rentrée 2021 - Synchro-donjon !

[Lephe]

Quelques nouvelles participations ces derniers jours, avec la montée fulgurant de SlyVTT qui dépasse tout le monde de loin avec 85.7341 points/plateau. Mais par quel moyen me demande-t-on ?! https://tiplanet.org/concours_synchrod2 ... &invalid=1

[Lephe]

Il reste 3 jours (aujourd'hui compris !) pour participer. Comme il y a des participations encore anciennes, il suffirait de soumettre ia3greed.py pour attraper un lot... et il serait dommage de ne pas en profiter, les goodies bien que modestes sont dignes d'intérêt.

Les deux premiers scores à battre sont de 53.4195 et 61.0491, ce qui est tout à fait accessible : https://tiplanet.org/concours_synchrod2 ... &invalid=1

Étonnamment, personne n'a codé l'approche que j'attendais quand j'ai conçu l'épreuve. J'ai ajouté (symboliquement) mon score au tableau ; il a fallu que je reprenne mon IA plusieurs fois pour rester compétitif, bravo.

[SlyVTT]

Étonnamment, personne n'a codé l'approche que j'attendais quand j'ai conçu l'épreuve. J'ai ajouté (symboliquement) mon score au tableau ; il a fallu que je reprenne mon IA plusieurs fois pour rester compétitif, bravo.

Bravo Lephe'

On voit qui est le chef
Je vais essayer de te battre, mais pas gagné, car en plus pas beaucoup de temps là ...
Curieux de savoir ce que tu nous as concocté, certainement moins "brutal" que mon code

Ciao

Sly

[Lephe]

Ha ha bravo à toi surtout, tu as poussé le problème très loin. Prépare tes explications parce que j'en demanderai pour l'article de résultats !

[Lephe]

Le concours est maintenant fini ! Merci beaucoup à tous les participants à la fois sur Alrys et sur Synchro-Donjon, vous avez vraiment gratté ces problèmes jusqu'au fond (Alrys encore plus !) et ça fait plaisir de voir qu'ils vous ont plu.

Les scores de Synchro-Donjon sont finaux et l'anonymat est levé : https://tiplanet.org/concours_synchrod2 ... &invalid=1

Les scripts seront disponibles dans la journée pour que vous puissiez voir comment chacun a procédé. En plus de ça, je voudrais avoir en quelques lignes (ou plus ) une description de vos solutions/approches histoire de pouvoir tout compiler dans l'article de résultats. Synchro-Donjon cache de l'algorithmique très sympa que vous avez largement pu expérimenter et je ne vois pas de meilleure conclusion que de rassembler toutes les bonnes idées.

C'est parti pour la sélection des lots. @Pavel, qu'est-ce que tu nous prends ?

• 1 lot Graph 90+E : 1 calculatrice Graph 90+E + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio
  
  
• 1 lot Graph 35+E II : 1 calculatrice Graph 35+E II + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio
  
  
• 1 lot Goodies n°1 : 1 clé USB TI-83 Premium CE (4 Go) + 1 batterie externe CASIO (2200 mAh) + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio
  
  
• 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

[Pavel]

@Pavel, qu'est-ce que tu nous prends ?

Merci pour ce défi. Je me suis beaucoup amusé à jouer avec l'algorithme A* en Python.

Je voudrais prendre le lot Graph 35+E II.

[Pavel]

En plus de ça, je voudrais avoir en quelques lignes (ou plus ) une description de vos solutions/approches histoire de pouvoir tout compiler dans l'article de résultats.

Comme j'ai appris à utiliser l'algorithme A* dans le défi d'Alrys, je me suis dit qu'il pourrait être intéressant d'appliquer cet algorithme à un problème en 4 dimensions pour trouver simultanément un chemin optimal pour les quatre héros. Malheureusement, mon implémentation de cette solution en Python était super lente et j'ai dû passer à un problème en 2 dimensions et ne contrôler que deux héros en même temps.

Ensuite, j'ai dû faire quelques mises à jour de mon script pour rentrer dans la limite de 15 minutes et corriger quelques bugs. Les deux principales optimisations ont été de trouver une heuristique qui fonctionne bien et d'optimiser la fonction qui calcule le coût des déplacements.

Mon script compare les coûts des deux séquences de héros:

• Jaune et Bleu puis Rouge et Vert
• Rouge et Vert puis Jaune et Bleu

et puis il choisit la séquence la moins coûteuse des deux

Voici les liens vers les articles qui m'ont beaucoup aidé à apprendre comment implémenter et utiliser l'algorithme A*:
https://www.redblobgames.com/pathfinding/a-star/
https://theory.stanford.edu/~amitp/GameProgramming/

[Lephe]

Merci ! À ton tour, @SlyVTT. Qu'est-ce qui pourrait te faire plaisir pour récompenser les efforts à générer automatiquement les stratégies de sortie ?

• 1 lot Graph 90+E : 1 calculatrice Graph 90+E + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio
  
  
• 1 lot Goodies n°1 : 1 clé USB TI-83 Premium CE (4 Go) + 1 batterie externe CASIO (2200 mAh) + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio
  
  
• 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

[SlyVTT]

Salut Lephe,

tout d'abord, je voulais vraiment remercier les organisateurs car j'ai vraiment apprécié ces deux concours.

Synchro-Donjon était un vrai challenge pour moi car il y a 3 semaines encore, je n'avais jamais touché Python. J'ai donc écris mes premières lignes pour Synchro Donjon.

Mon algo repose sur 2 concepts simples :
- notre principale ressource est le temps disponible associé à la connaissance de la configuration du tableau de jeu
- il vaut toujours mieux réfléchir à la solution la plus pertinente à l'instant t donné

Pour commencer, j'ai donc codé des fonctions de métriques, me permettant de sortir pour l'ensembles des tableaux des stats (score +/- écart type, cout de déplacement +/- écart type et dommage +/- écart type) afin de voir où se situaient les gains potentiels, très vite il apparait que ce sont les dommages qui priment.

A partir de là, j'ai créé un algorithme qui consiste à chercher la meilleure combinaison de sortie pour les 4 joueurs selon un catalogue basé sur un arbre (j'ai d'ailleurs développé un petit parser/lecteur automatique de stratégies écrites en littéral dans le code afin de gagner en temps/maux de tête).

L'algo consiste à déterminer le chemin optimum à suivre pour un joueur via un algo A*/Dijkstra puis d'en évaluer le cout/l'impact sur l'ensemble des joueurs encore sur le plateau. Une stratégie est composée de 4 ou 6 sous segments qu'il faut cumuler pour avoir une idée de l'ensemble du chemin optimum.

Le meilleur chemin est déterminé par le test de 72 combinaisons fournies dans un catalogue et qui sont déterminées par différentes solutions :
- 6 combinaisons pour amener par exemple JAUNE et BLEU vers leurs sorties respective (1 par 1 ou en se groupant par 2 : par exemple BLEU rejoint JAUNE, puis tous les deux traversent vers la SORTIE JAUNE puis BLEU rejoint sa SORTIE BLEUE)
- idem pour VERT et ROUGE
--> cela donne 36 combinaisons à multiplier par 2 (soit 72 combinaisons) selon s'il est plus intéressant de faire traverser JAUNE et BLEU puis ROUGE et VERT ou inversement.

Le catalogue ressemble à un truc du genre :

Code: Select all

        ( "Option 001" , "pB>pJ, pB>sB, pJ>sJ." , "pR>pV, pR>sR, pV>sV." ), \
        ( "Option 002" , "pB>pJ, pB>sB, pJ>sJ." , "pV>pR, pV>sV, pR>sR." ), \
        ( "Option 003" , "pB>pJ, pB>sB, pJ>sJ." , "pR>pV, pV>sV, pR>sR." ), \
        ( "Option 004" , "pB>pJ, pB>sB, pJ>sJ." , "pV>pR, pR>sR, pV>sV." ), \
        ( "Option 005" , "pB>pJ, pB>sB, pJ>sJ." , "pR>sR, pV>sV." ), \
        ( "Option 006" , "pB>pJ, pB>sB, pJ>sJ." , "pV>sV, pR>sR." ), \
        ( "Option 007" , "pB>pJ, pJ>sJ, pB>sB." , "pR>pV, pR>sR, pV>sV." ), \
        ( "Option 008" , "pB>pJ, pJ>sJ, pB>sB." , "pV>pR, pV>sV, pR>sR." ), \
        ( "Option 009" , "pB>pJ, pJ>sJ, pB>sB." , "pR>pV, pV>sV, pR>sR." ), \
        ( "Option 010" , "pB>pJ, pJ>sJ, pB>sB." , "pV>pR, pR>sR, pV>sV." ), \
        ( "Option 011" , "pB>pJ, pJ>sJ, pB>sB." , "pR>sR, pV>sV." ), \


Le parser se charge alors d'extraire et d'interpréter la séquence et d'ordonnancer/recycler les calculs.

J'avoue que cette partie m'a un peu fait transpirer mais ça valait le coup.

Par exemple la première stratégie (appelée "option 001") se lit ainsi : le player BLEU ("pB") rejoint (">") le player JAUNE ("pJ") puis traversent (les deux car pB=pJ) en direction de la sortie BLEU (sB), puis player JAUNE (pJ) va vers sa sortie (sJ) puis on passe à la deuxième étape avec ROUGE (pR) et VERT (pV).

Clairement c'est un algo de "bourrin", et un des challenges a été de coder qq chose d'optimum pour passer dans les 15minutes.

Il y a pas mal d'astuces assez sympa afin que cela passe dans le temps imparti (les dernières itérations doivent être vers 14min30 voir 14min45 de run) :
- optimisation de la routine A* pour sortir un résultat rapidement
- utilisation de matrices de connections individuelles (une par joueur) pour ne recalculer que ce qui change pour le dit joueur
- utilisation d'un parser avec ordonnancement des stratégies de manière à réutiliser un max de calculs déjà effectués.

Bien entendu tout cela est dynamique et est mis à jour dès que quelque chose change sur le plateau (pics ou pièges apparus, monstre tué).

Concernant le lot, je voudrais prendre le lot Graph 90+E, car c'est une machine qui m'intéresse beaucoup.

Merci beaucoup

Sly

[Lephe]

Merci beaucoup, ça c'est détaillé ! J'espère que cette première expérience avec Python t'a plu, en tous cas je crois que tu as plu à Python.

À ton tour @ArtichautCosmique. Qu'est-ce qui peut te faire plaisir ?

• 1 lot Goodies n°1 : 1 clé USB TI-83 Premium CE (4 Go) + 1 batterie externe CASIO (2200 mAh) + 1 sac et stylo CASIO + 1 pack de goodies TI-Planète Casio
  
  
• 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