Bonjour à tous les membres ! Avec notre concours de rentrée tout juste terminé, voyons comment vous avez résolu notre deuxième défi, le défi Python de Quetzalcoatl ! 
La participation à cette épreuve aura été similaire à la première, avec
141 participations soumises par 20 personnes. 11 d'entre vous se sont déclarés de la team TI, et 4 de la team Casio (les autres n'ont rien indiqué). Merci beaucoup pour toute la science que, comme on va le voir tout de suite, vous avez déployé pour optimiser ce défi ! o/
Cette épreuve consistait à traverser une caverne à l'aide de l'excavatrice transformée en ballon. Comme l'épreuve précédente, l'objectif était de minimiser la quantité d'énergie dépensée, dont j'ai
détaillé le calcul dans un topic quand on a réalisé que c'était moins évident que prévu.
Le contrôle du ballon se faisait en spécifiant des triplets :
• L'accélération verticale du ballon, ay.
• La vitesse de changement de forme, da.
• La durée de validité du contrôle.
Les coûts étaient répartis sensiblement ainsi :
• 10 points par contrôle effectué.
• Un léger coût sur les changements de forme, croissant avec |da|.
• 7 points par collision, sachant que si on s'enfonce dans la roche le nombre de collisions à chaque instant peut être très élevé.
Voyons voir ce que vous avez pu trouver ! L'analyse ci-dessous est purement la mienne, j'aurai sans doute raté des détails croustillants, donc n'hésitez pas à préciser dans les commentaires.
Le classement
17. 
Golden Man (
) :
6058.5 (Programme :
q5.py)
Comme dans l'article précédent, la première participation ici est aussi une des plus malines. Avec un seul ordre d'une seule unité de temps, Golden Man fixe la vitesse verticale à -0.27 et descend en ligne droite jusqu'à la ligne d'arrivée. Le script auto-complète la séquence d'instructions en ne faisant rien jusqu'à la fin.
Soumettre des ordres coûte cher, donc cette idée est logique. Mais les collisions coûtent infiniment plus cher, et à plusieurs moments le ballon est entièrement dans la roche. Or, l'algorithme codé par Critor évalue en gros la surface de l'intersection de l'ellipse du ballon avec la roche, et pénalise d'un multiple élevé de cette surface, donc le score explose.
16. Ptitjoz (
) :
2165.3 (Programme :
q124.py)
Ptitjoz est le premier à faire des paraboles. Comme vous l'avez sans doute remarqué, la première composante de chaque ordre est l'accélération verticale du ballon. Sur la période indiquée par chaque ordre, le ballon fait donc une parabole montante ou descendante.
Le passage de la première section est très propre avec absolument aucune collision. Et il y a une technique intéressante au niveau de la section infranchissable, où le ballon plonge dans la roche pour se mettre dans une position favorable à la remontée. C'est une mécanique intéressante qu'on aurait pu vous inciter à exploiter. Mais le jeu était équilibré de façon à punir inconditionnellement les collisions, donc ça n'est pas arrivé : il n'était jamais intéressant de faire des concessions.
15. Nagero (
) :
1980.5 (Programme :
q131.py)
Comme le programme d'exemple, la participation de Nagero ne s'écarte pas trop des accélérations verticales ±1. Ça a l'avantage d'éliminer des paramètres dans la recherche d'un chemin, mais ça oblige à faire beaucoup de vagues et donc passer beaucoup de points sur les ordres.
La trajectoire évite quand même la plupart des passages difficiles et pourrait presque attraper le dernier lot à quelques instructions près sur la fin !
14. Arm234 (
) :
1132.5 (Programme :
q104.py)
Comme si ce n'était pas assez de le faire une fois, Pavel a là aussi écrit
une version pour ordinateur du programme de l'épreuve, et Arm234 est le premier de ce classement à s'en être servi.
Quelque chose qui devient assez vite évident lorsqu'on cherche de façon interactive, c'est que malgré l'insistance du sujet à vous faire utiliser des paraboles, il est parfaitement possible d'avancer en ligne droite en spécifiant une accélération verticale nulle pendant une période donnée.
À partir de là, le jeu devient surtout d'identifier les segments qu'on peut parcourir et d'utiliser une série d'instructions économe en score pour fixer la vitesse verticale et la forme du ballon, puis ne rien faire pendant toute la durée de chaque segment, ce qui ne coûte aucun point au score !
On retrouve de nouveau la parabole directe au niveau du passage infranchissable, puisque quitte à passer en force autant ne pas consommer en plus des appels à modifier_vol().
Arm234 wrote:J’ai choisi de ne rien faire avec la calculatrice (j’ai une NumWorks), car je trouvais cela assez compliqué pour pouvoir réaliser les différents textes, j’ai donc avancé à tâtons avec l’émulateur pour pc avec TKinter en me sevrant des captures d’écran des premiers qui m’ont beaucoup servi pour savoir où aller et quels tracés réaliser.
(message original)13. 
CaptainLuigi (
) :
825.5 (Programme :
q119.py)
CaptainLuigi a lui aussi utilisé le programme de Pavel. En fait ça se voit assez vite au formatage du code puisque l'outil génère une version compacte avec une boucle for. Sauf fourberie particulière, les personnes qui n'ont utilisé que leur calculatrice ont gardé la séquence de modifier_vol() donnée en exemple. Donc qui utilise quoi se devine assez bien au premier coup d'oeil.
Cette participation est la toute dernière à ne pas avoir aggressivement abusé de lignes droites partout, et doit son placement au passage rigoureux de tous les points serrés, qui totalise un nombre faible de collisions (n'oubliez pas que la surface de l'intersection compte, ici on frôle à peine).
CaptainLuigi wrote: J'ai tenté 2/3 fois sur Casio, vers 1000 environ .
Mais à force d'attendre l'importation des modules qui prenait 20,30 secondes, j'ai jeté un coup d'œil à l'outil que Pavel avait développé , et très rapidement j'ai fait ce score un peu plus décent de 825.5
(j'avais une participation bien en dessous mais invalide
)
(message original)12. 
Tituya (
) :
537.5 (Programme :
q15.py)
Pour quelqu'un qui dit ne pas avoir cherché beaucoup, Tituya a cherché droit au but : c'est fait à la main, on a les lignes droites, un passage impeccable de toutes les sections, et le ballon ne change même pas de forme ! Un total de 21 instructions directes et efficaces.
À partir de là, le chemin ne change plus fondamentalement et on va surtout voir moins de collisions sur la section infranchissable et moins d'instuctions.
Tituya wrote: Voilà ma méthode : J'ai simplement essayé de faire les trajets le plus cours possible. Sachant que les trajets les plus cours sont ceux allant droit, j'ai construit mon programme en jouant sur ça et en essayant d'éviter au maximum les murs.
Rien de plus, rien de moins. J'ai moins été intéressé par ce concours, je n'ai pas plus cherché que ça.
(message original)11. 
Wistaro (
) :
499 (Programme :
q64.py)
Le programme soumis par Wistaro a la propriété unique de soumettre une instruction par unité de temps. Toutes les (0,0,1) ne coûtent aucun point, mais il en reste 24 autres. Et pourtant, son score est en-dessous de 500 points !
Le secret ? Un ajustement aléatoire habile (quoique manuel) des instructions. Quasiment tout le monde a travaillé manuellement sur ce défi, et ce n'est pas surprenant étant donné la complexité du calcul des collisions et l'absence d'un cadre formel facile dans lequel attaquer le problème.
Je ne vous cache pas qu'après le premier défi je ne m'attendais pas du tout à ce qu'on recoive une participation de ce style !
Wistaro wrote:Ma méthode pour ce concours n'est pas vraiment surprenante. J'ai tout d'abord commencé par lancer le programme sur ma calculatrice
(TI-Nspire CX CAS munie de Khi-CAS + micropython). j'ai tâtonné à la main pour essayer de comprendre le rôle de tous les paramètres.
J'ai aussi essayé de décortiquer le code source en Python, mais ça n'a pas servi à grand chose vu mon faible niveau dans ce langage
Une fois cela bien compris, j'ai utilisé le programme pc de
Pavel pour essayer de trouver la trajectoire la plus optimisée. Je le remercie beaucoup d'ailleurs, ça m'a bien aidé, même si je trouve que ça nous facilitait la tâche
Après plusieurs essais infructueux, j'ai fini par atteindre 499 en jouant sur les différents paramètres de manière aléatoire. J'ai réussi une fois à faire 480, mais malheureusement je n'ai pas pensé à sauvegardé la trajectoire
(message original)10. commandblockguy (
) :
462.5 (Programme :
q26.py)
La participation de CommandBlockGuy pousse tellement le concept de ligne droite à bout que son programme est structurellement une alternance entre des paraboles pour changer de direction et des lignes droites pour progresser dans la caverne (sauf au passage du premier pincement où il enchaîne deux paraboles).
Vous pouvez voir que le chemin emprunté est le même pour toutes les soumissions restantes, mais le score continue de descendre drastiquement. Il y a plusieurs raisons pour ça, mais une en particulier était volontaire. À l'origine, Critor avait proposé que la première composante de chaque instruction soit la vitesse verticale (ce qui est somme toute plus logique physiquement parlant). Voyant les retours sur le premier défi, j'ai suggéré d'utiliser l'accélération à la place.
Spécifier une accélération constante par morceaux fait bien sûr des paraboles au lieu de lignes, mais ce n'est pas tout. Ça ajoute au problème une variable cachée qui est la vitesse verticale. En particulier, on ne peut pas juste déplacer des instructions d'un endroit à un autre de plan de vol, parce que si la vitesse verticale est différente au points de départ et d'arrivée, leur effet diffère aussi.
Derrière tout ça il y avait aussi l'idée que des changements sur le début du plan de vol se répercutent assez violemment sur la fin et nécessitent de réajuster la fin. J'espérais que les candidats qui partent sur un début différent les uns des autres restent « coincés » dans ces espaces de solutions, évitant ainsi qu'il n'y ait qu'une seule solution comme au premier défi.
commandblockguy wrote:This time, I basically just did everything manually, trying to minimize my number of collisions. I would have tried to automatically test solutions again, but I was much busier for this round than the last one. I ended up with a best score of 455.5, but because that was already taken I slightly changed it to get a score of 462.5.
(message original)9. Filoji (
) :
454.5 (Programme :
q13.py)
Un autre aspect qu'on a voulu essayer, et qui dans le cas de Filoji a joué en notre défaveur, était de publier les images des trajets empruntés par tout le monde. Comme la variable cachée (la vitesse) n'est pas visible sur les images, contrairement au premier défi ça ne donne pas toute l'information sur la solution.
On a pensé que ça aiderait tout le monde à trouver des astuces (par exemple le fait qu'on pouvait faire des lignes droites) et motiverait un peu ceux qui avaient du mal. Qu'en avez-vous pensé ? Est-ce que ça vous a aidé, ennuyé ? Et par extension, même question sur les infos publiques du troisième défi (où il y a infiniment plus d'informations cachées).
Filoji wrote:C'est pas compliqué dans la vie, il faut tricher !
Donc, pour commencer, j'ai vu que le concours commençais, mais c'était le même type de challenge que le précédent...
Je me suis dit "Après tout, tente !", et c'est ce que j'ai fait.
Je ne vais pas vous mentir, j'ai préféré le 1er, car je le trouvais plus simple à comprendre. En plus, je n'ai pas vraiment d'histoire sur celui-ci, j'ai très vite réussis à trouver une solution qui m'avais placé en ~5ème, et je me suis arrêté là. Comment j'ai réussis à faire ça ? Ben j'ai juste regarder les participations ennemis. Je trouvais ça bien à la base de voir l'avancement des autres, mais quand le seul but pour moi était de recopier le chemin des autres, je me suis très vite lassé.
(message original)8. Ti64CLi++ (
) :
406.8 (Programme :
q138.py)
Parfois on se demande ce qu'on ferait sans Pavel.
Ti64CLi++ wrote:Alors pour cette fois, j'ai tout fait avec l'utilitaire de
Pavel (au passage, merci pour tout
), j'ai tenté une première fois, où j'ai obtenu un score d'environ 600 il me semble, puis un deuxième jet m'a permis d'atteindre les 490.
Enfin, j'ai fais joujou avec les paramètres, sans trop jamais vraiment me pencher dessus, ce qui m'a permis d'avoir ce score de 406,8.
(message original)7. Jeffitus (
) :
234 (Programme :
q136.py)
Le saut entre TI64CLi++ et Jeffitus est flagrant : presque 200 points. Il y a bien sûr quelques instructions en moins, mais ce que fait vraiment la différence c'est la quantité de collisions au niveau du passage infranchissable.
Quand Critor a suggéré ce sujet j'ai tout de suite pensé que je pouvais générer les deux courbes définissant le plafond et le sol en tirant aléatoirement les coefficients d'une décomposition de Fourier pour deux fonctions. Mais ça posait un problème qui est que les courbes pouvaient facilement se croiser. Dans l'exemple ci-dessous, l'amplitude permet aux courbes de traverser tout l'écran, et les composantes majeures du profil spectral sont partagées pour éviter les intersections. Mais on peut toujours s'en sortir avec deux (voire une seule) lignes droites.
Du coup j'ai changé de méthode et j'ai généré la position du plafond et la
hauteur de l'espace naviguable à partir des profils spectraux. De cette façon, il était facile de garantir que le résultat serait toujours positif, et on a beaucoup plus facilement des passages serrés.
En fin de compte, Critor a choisi une instance avec un passage infranchissable, ce qui vous obligeait à faire des compromis. On a vu au début de ce classement qu'éviter à tout prix les collisions joue le rôle le plus important dans les bons scores, et ça se voit encore même dans le top 10.
Jeffitus wrote:The first score I submitted was done by hand, using a script written by commandblockguy for the PC. I'll note that initially I didn't really touch the second parameter, since I didn't really understand what it was doing at first. I saw that some people were talking about Pavel's GUI version, so I decided to try that out and sure enough I began getting better scores. It was also around that time that Afyu mentioned the second parameter, and I started looking into how it worked. With that knowledge I was able to get below 400 easily, and below 300 soon after that. I think I probably could have improved my score more, but since I really only started trying to improve just a few days before the contest ended I'm pretty happy with how my score turned out.
(message original)6. Ne0tuX (
) :
217 (Programme :
q111.py)
Ne0tux a lui aussi faire la plupart de la recherche à la main. Au fond, le défaut sans doute de ce défi, c'est qu'il y a un aspect de grind assez conséquent. C'était aussi le cas dans le passé (par exemple pour le
problème de sélection d'équipe Pokémon en 2019) mais dans ces cas-là on pouvait aussi approcher la solution à l'ordinateur.
Je ne suis pas surpris qu'il y ait eu très peu de scripts pour ce défi, et à autres paramètres égaux je trouve ça dommage (ceci n'engage que mon opinion). Le troisième défi tranche beaucoup en vous tous faisant programmer une solution, et selon si vous avez aimé ça pourra influencer le format des prochaines éditions. N'hésitez pas à dire en deux ou trois mots ce que vous avez préféré, ça nous informe beaucoup.
Ne0tux wrote:J'ai de nouveau tiré profit d'Omega en ligne pour valider ma participation, mais je dois remercier Pavel car c'est avec sa GUI que j'ai testé mes idées. C'est la première fois que je ne produis aucun algorithme d'optimisation ; je me suis contenté d'appliquer au mieux la stratégie déduite du code et des participations visibles. Le fait de voir ce qu'ont fait les autres était une nouveauté. D'un côté, j'ai trouvé intéressant de constater (au début tout du moins) que des scores proches avaient parfois des visuels différents. D'un autre côté, accéder à ces visuels était une solution à moindre effort comparé à tout expérimenter soi-même. Ma double nature humain/développeur m'a fait choisir la facilité en m'intéressant aux 2-3 premiers visuels du classement et c'est ainsi que j'ai validé quelques d'intuitions obtenues par le code : possibilité de faire des lignes droites à moindre coût, besoin d'un minimum de collision pour un score minimum.
(message original)5. LeGmask (
) :
213.6 (Programme :
q108.py)
Comme la dernière fois, je vous laisse avec les explications brutes du top 5, qui sont déjà on ne peut plus complètes par elles-mêmes.
Vous noterez quand même, si vous lisez le code, que les débuts sont extrêmement proches. L'usage de lignes droites réduit drastiquement le nombre de possibilités de chemin. Mon espoir qu'il y ait ultimement plus d'une solution vraiment compétitive n'était donc qu'à moitié fondé, car seule les instructions de fin diffèrent vraiment d'une soumission à l'autre.
LeGmask wrote:Sérieusement, en vrai pour tout vous dire ce concours était d’autant plus simple que le premier niveau compréhension, peut-être un peut trop, et trop répétitifs par rapport au dernier concours, mais je ne m’en pleins pas on a déjà l’immense chance d’avoir de superbe concours rien que pour nous 😊
Ce qu’il en est de ma solution : bien bah tout d’abord je me suis empréssée de faire une adaptation de labgui le script de
Pavel pour le premier concours (
https://gist.github.com/LeGmask/88eaf69 ... eb16d79dbd ) je m’apprêtait a voir avec
cent20 pour faire profiter la team numworks de cette avantage ou tout le monde, sauf que
Pavel ma devancé. J’avais fini mon script le matin 9h quelques heures après,
Pavel qui nous sort ca version :notlikethis: . Néanmoins j’ai essayé les deux et je trouvais ma version adaptée de labgui bien plus efficace que la nouvelle fournis par
Pavel. J’ai alors cherché un peut avec mon nouvel outil et fait un score aux alentours de 590 de mémoire.
Après cela j’ai laissé passez beaucoup de temps, semaine de DS + préparation à mon championnat de voile à Dunkerque… première semaine des vacances j’ai réussi le mercredi (étant en « formation » avant) à regarder un peut, et j’ai réussi à descendre juste en dessous de
Afyu, l’idée que j’avais vu est que si ont réduisait le serpentin avec le 2e paramètre, il fallait faire ajouter l’inverse pour annuler le fait qu’avancer consomme du score… Le weekend de cette première semaine de vacance j’ai donc pus trouver mieux que le score actuel de
Pavel qui avait 218, je me place donc premier avec 216.5.
Arrivée à Dunkerque,
Pavel reprend sa place avec 211, puis
Afyu passe devant aussi, de plus qui dit championnat de France ne dit pas beaucoup de temps libre, la journée sur l’eau le soir dodo. J’ai néanmoins trouvé un peu de temps et réussi à me placer devant
Afyu, a ce moment la j’ai donc décidé de faire un algorithme pour optimiser le tout, cette algorithme ajoutait simplement aléatoirement de petites valeurs au différentes variable, et finissait par toujours retomber sur 211, avec plus de temps j’aurais peut-être pus trouver mieux mais je ne pense pas que c’était faisable.
J’ai finalement été dépasser par
Tiny_Hacker, et
cent20 mais je n’avais pas vraiment le temps de faire une amélioration, puis bon j’ai déjà un lots avec une calculatrice je n’avais pas non plus la motivation de faire beaucoup mieux 😊.
Encore une fois grand merci pour ce concours, et je repose mon idée, d’une évaluation automatique pour le concours afin d’éviter a
critor de tout faire à la main. J’ai ici décider d’aider ceux qui en avait vraiment besoin afin de rétablir l’équilibre par rapport au premier défi ou je me suis fait aider.
(message original)4. cent20 (
) :
213.502 (Programme :
q127.py)
cent20 wrote:Ma méthode en quelques mots
cent20 wrote:Un algorithme dynamique, arborescent, basé sur des séries génétiques, analysé par une IA dédié à cet usage dont je ne peux pas révéler à cet instant, tous les secrets.
Comment tout ceci fonctionne ? Il est temps de révéler tous mes secrets.
C'est assez simple. Commençons par définir ce qu'est un algorithme
Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions permettant de résoudre une classe de problèmes
J'ai donc mis au point un algorithme, il était arborescent car le défi l'était, l'optimisation d'un trajet dépendait du précédent. Le caractère génétique vient du fait qu'une fois que j'ai obtenu une bonne série, mon IA l'étudie à nouveau pour l'optimiser si cela est possible. Comme je l'ai
promis dans le forum, il est temps de vous révéler les secrets de cet algorithme.
- Code: Select all
# Attendre que le grand Pavel propose un outil de recherche sur PC
Boucle de recherche : Quand vous arrivez à la dernière étape, il suffit de boucler sur la première- Code: Select all
'''
Proposer une solution
L'optimiser
Regarder les réponses des autres utilisateurs
Mettre une baffe à l'IA pour qu'elle s'adapte
Proposer une meilleur solution, inspiré des autres propositions.
Analyser mon score à mi chemin et comprendre que s'il est supérieur au score de la meilleur proposition # # c'est que rien ne va.
Mettre à nouveau une baffe à l'IA pour qu'elle s'adapte
Troller sur le forum en racontant n'importe quoi, l'essentiel est de faire croire que votre score est imbattable.
Prendre beaucoup de plaisir, et c'est le plus important, à chaque palier franchis dans la progression, ils ont été exposé clairement par Pavel et Afyu donc inutile de les réexpliquer.
'''
Quelques regrets - Avoir trop chauffé Afyu, qui m'a grillé brillamment pour le coup.
- Avoir cru, trop tôt, que Pavel avait trouvé le meilleur score, j'aurais pu obtenir le 211 mais mon algo de recherche ne pouvait pas y arriver à cause de son fonctionnement : "Regarder les réponses des autres utilisateurs"
J'ai adoré ce deuxième défi, trouver les différentes astuces lors de la recherche est vraiment jouissif.
J'ai vaguement codé une optimisation itérative sur des intervalles prédéterminé pour gratter la 3ème place, mais n'ayant pas mis assez de décimales un joueur à pu s'intercaler entre mon résultat et celui de Afyu.
(message original)3. TIny_Hacker (
) :
213.501 (Programme :
q139.py)
TIny_Hacker wrote:Thank you for this awesome contest!
When I first entered, I was not really attempting to get a good score but figured that since there were hardly any entries I might as well see what I could come up with since even a huge score would get me into the top 13.
I discovered Pavel's GUI searching for information on Planet-Casio, and I messed around trying to get a path that got as few collisions as possible. I ended up with a huge score, which I never bothered to submit.
After messing around some more, I realized I could move in straighter segments by making a small segment before the current and aiming it in the direction I wanted to go. After making a path like this, I ended up with a score of 1,029.5 which I deemed good enough to submit. After more people started sending their solutions and getting better scores, I decided to look back into my current path again. After removing quite a few collisions, I got a score of 647.5, which roughly followed the path that the people ahead of me used. I have to admit, this contest was quite addicting for me!
After a few more days, I had managed to reduce my score to 449.5, and I couldn't seem to figure out how to get it any lower. I realized that there must be a key thing I was missing, seeing the 200 point difference between my score and the scores below me. The next day, Afyu gave me a hint which helped quite a bit, and I discovered the trick to getting into the 200s! The next day, I made a modified version of the GUI which displayed my score for every step along the path, so that I could make sure I was always improving rather than getting the same or a worse score. After a few hours of trying paths, I managed to get my score to 216.5, which I "broke" in order to make it fit into the ranking since 216.5 had already been taken by Pavel. I finally was able to reduce my score to 214, which I submitted and gave up on reducing afterward. However, around 45 minutes before the deadline, I realized that my chances of getting a TI-Nspire were much less than I thought because I had forgotten that there was only one NumWorks in the prizes this time!
However, Afyu told me that one of my segments was too short, and when I compared my path to the ones in front of me that was true! I discovered that the reason I had missed that earlier was that the decrease in the score is not immediate, and so it did not appear to be a better path because I was comparing it in my tweaked version of Pavel's GUI. After I reached 213, I changed some more code in Pavel's GUI to allow me to change the middle argument more precisely, and I was able to sneak my score into 3rd!
(message original)2. Afyu (
) :
213.5 (Programme :
q110.py)
Afyu wrote:J'ai découvert l'énoncé avec 4 jours de retard et j'ai commencé mes recherches sur la ressource
NumWorks avec le
Workshop officiel.
J'ai placé des commandes
modifier_vol(n1, n2, n3) en tatonant, jusqu'à avoir une solution convenable.
J'ai alors 22 étapes et une consommation à 3567.5.
Par exemple, la longue ligne droite entre le premier et le deuxième stalactite est coupée en 4 segments mis bout à bout... inutilement.
Puis, j’ai fait un deuxième essai à 2034.5 et ensuite un troisième à 1964.5 et un à 1666 avant d'arriver à mon essai à 1054.5 que j’ai décidé d'envoyer.
Après plusieurs essais et 9 scores plus tard, j'arrive à 541.5 et je décide de passer (enfin !) par un algorithme pour optimiser tout ça.
J'ai repris la ressource proposée pour la
NumWorks (version
Workshop officiel) et j'en ai supprimé la partie graphique (faute de savoir comment l'adapter sur ordi, en utilisant
tkinter plutôt que
kandindky pour le module graphique) et j'ai ajouté quelques lignes pour créer 3 listes d'initialisation
coord1init,
coord2init et
coord3init qui contiennent respectivement : les valeurs utilisées comme 1er paramètre, celles utilisées comme 2ème paramètre et celles utilisées comme 3ème paramètre. Et maintenant, avec un peu de recul, je me demande s'il n'aurait pas été plus pertinent de créer des triplets de nombres (un triplet pour chaque commande
modifier_vol(n1, n2, n3) plutôt que 3 listes. En fait NON, car sauvegarder puis récupérer régulièrement plein de triplets c'est plus compliqué que de sauvegarder 3 listes.
Dans le script j'ai également créé une variable
scoremax qui contiendra mon meilleur score. J'ai également créé 3 listes
coord1,
coord2 et
coord3 qui sont les listes de paramètres sur lesquelles je vais travailler (et qui sont en lien avec les 3 listes d'initialisation). Je modifie aléatoirement une valeur d'une ou de plusieurs de ces 3 listes et je calcule la consommation obtenue. Concrètement, je tire un nombre aléatoire compris entre 0 et la longueur de coord1 - 1. Je stocke ce nombre dans la variable
rang1. Ensuite, je modifie
coord1[rang1] en lui ajoutant ou en lui retirant une certaine valeur ou en ne la modifiant pas, avec l'instruction
coord1[rang1]+=0.01*(randint(0,2)-1) qui ajoute ou retire 0.01 ou ne fait rien. Je fais de même avec
coord2 et
coord3. Ensuite, je compare la consommation obtenue, donc
state[4], avec mon
scoremax. Si le score obtenu est meilleur (donc plus petit), alors je copie les 3 listes
coord1,
coord2 et
coord3 dans mes listes d'initialisation/sauvegarde
coord1init et ses consœurs et je stocke mon nouveau meilleur score dans
scoremax. Ensuite, au tour de boucle suivant, je modifie de nouveau une valeur dans une ou plusieurs des 3 listes et je compare le score obtenu avec mon meilleur score et ainsi de suite. Tous les 3 tours de boucle, donc tous les 3 changements (qui sont successifs), je récupère la valeur de
coord1init et ses deux voisines pour les copier dans
coord1,
coord2 et
coord3. C'est une sorte de réinitialisation de mes 3 listes de travail aux paramètres du dernier meilleur score obtenu.
J'ai parfois adapté ce nombre de boucles à parcourir avant cette réinitialisation, suivant si je voulais permettre un grand nombre de changements ou au contraire rester proche de mon actuelle meilleure solution (finalement 3 boucles était un bon choix).
J'ai également adapté la précision des valeurs que je souhaitais pour les 3 paramètres. Le dernier paramètre semble être toujours un entier (mettre une valeur non entière donne le même le score que mettre uniquement la partie entière).
Avec la publication du classement et des solutions de chacune et chacun des gagnants du premier défi, j'ai vu qu'il pouvait y avoir une histoire de nombre de décimales. J'ai donc tenté de réduire le nombre de décimales de mes paramètres (par exemple, je remplace un 2.42 par 2.4 dans la liste
coord1init et je relance mon algorithme jusqu'à obtenir de nouveau mon meilleur score, les autres valeurs ayant alors été légèrement modifiées pour compenser l'écart entre 2.42 et 2.4, et je recopie alors ces autres valeurs qui ont été renvoyées avec mon 2.4 ; si avec 2.4 ça ne me renvoie pas une nouvelle solution avec mon meilleur score, alors je teste avec 2.41, en étant moins exigeant, puis ensuite avec 2.4).
Mon premier score obtenu avec mon algorithme était 537.5 (le 11/10). Je passe sous la barre des 500 le même jour, puis sous la barre des 400 le 16/10 et enfin sous la barre des 300 le 17/10 et je suis finalement arrivé à 265.325 le 21/10. Ensuite, rien. Le néant. Plus aucune amélioration pendant 2 jours.
LeGmask, que je remercie
grandement ici pour son aide, m'a entendu me plaindre de cette stagnation de mon score sur le chat et m'a donné quelques conseils, en particulier celui d'utiliser l'interface graphique proposée par
Pavel - que je remercie
grandement ici pour son script généreusement partagé dans les commentaires (page 3).
LeGmask m'a proposé une version améliorée par ses soins, qui m'a aidé à comprendre l'importance et l'influence des 3 paramètres et de la variable
state[2]. Avant d'utiliser cette interface graphique, j'avais compris qu'on pouvait tracer un segment (droit) avec un triplet de la forme
(0, 0, n) avec
n un entier. J'avais également compris que le dernier paramètre influait sur la longueur du morceau de courbe placé et que le premier paramètre modifiait l'inclinaison ou la hauteur d'arrivée. Le 2ème paramètre restait assez flou pour moi et j'ai laissé mon algorithme choisir la valeur la plus adaptée pour obtenir un bon score. En suivant les conseils de
LeGmask et avec l'interface graphique de
Pavel, j'ai compris que le 2ème paramètre modifiait la valeur de
state[2] et que la consommation de chaque morceau de courbe placé était bien moindre lorsque
state[2] avait pour valeur 0.5 (ce qu'on peut retrouver en lisant le code du script donné pour le défi, à l'endroit du calcul du score, donc de
state[4], et ça concerne en particulier la variable
dapi qui sanctionne tout écart de
state[2] avec la valeur 0.5). Une solution simple serait de modifier le 2ème paramètre de la 1ère commande
modifier_vol(n1, n2, n3) afin de mettre la variable
state[2] à 0.5 et de ne plus modifier cette valeur. Le problème est que
state[2] joue sur l'épaisseur du tracé et qu'il est nécessaire de modifier cette valeur pour réduire l'épaisseur du trait pour passer certains passages étroits de la cave sans toucher les bords (en fait : le passage sous chacun des 3 stalactites). Il faut donc momentanément s'éloigner de cette fameuse valeur 0.5 le temps de passer sous les stalactites pour y revenir aussi vite que possible en modifiant le 2ème paramètre du premier morceau de courbe placé après un passage étroit.
Une observation grandement facilitée par l'utilisation de l'interface graphique m'a permis de comprendre que
state[0] contient la position horizontale à la fin du dernier morceau de courbe placé (la cave est en fait divisée en 128 "tranches verticales" qui donnent une abscisse comprise entre 0 et 127, stockée dans
state[0]), de même
state[1] contient la position verticale,
state[2] contient un paramètre toujours compris entre 0 et 1 et qu'il vaut mieux conserver à 0.5 lorsque c'est possible (c'est le 2ème paramètre des commandes
modifier_vol(n1, n2, n3) qui modifie la valeur de
state[2]) et
state[4] contient la consommation totale (donc le score). Pour
state[3], je ne sais pas... J'ai également observé l'évolution de la consommation suivant la valeur prise par
state[2]. Si
state[2] vaut 0.5, alors chaque nouveau morceau de courbe placé (et qui conserve le fait que
state[2] vaut 0.5) consomme 10 s'il est droit (1er paramètre égal à 0) et 20 s'il est courbé (1er paramètre non nul) et ce peu importe sa longueur (donnée par le 3ème paramètre). Si
state[2] ne vaut pas 0.5, alors le calcul est différent et la consommation d'un morceau de courbe placé augmente de 3 lorsque sa longueur (3ème paramètre) augmente de 1. L'utilisation de l'interface graphique m'a permis de comprendre que le 2ème argument pouvait se contenter de prendre pour valeur 0.5 ou -0.5, en effet les valeurs strictement comprises entre -0.5 et 0.5 ne sont pas très productives et les valeurs en-dehors de cet intervalle ne changent rien du tout par rapport à un -0.5 ou un 0.5) ce qui a grandement augmenté l'efficacité de mon algorithme de recherche puisque la partie
coord2[rang2]+=0.01*(int(0,2)-1) est devenue
coord2[rang2]=0.5*(int(0,2)-1) avec seulement 3 valeurs possibles pour chaque 2ème argument.
Donc, pour minimiser la consommation globale, il faut essayer de garder
state[2] à 0.5 en modifiant la valeur du 2ème paramètre, ou revenir à ce 0.5 dès que possible. Il faut également minimiser le nombre de commandes
modifier_vol(n1, n2, n3) car chaque nouvelle commande a un coût fixe. Il faut donc favoriser de longs morceaux (traversant le plus grand nombre possible de "tranches verticales", peu importe la position verticale (
state[1]) de départ et d'arrivée), si possible en ligne droite.
Un dernier point : les collisions. Chaque collision consomme 7 ou 14 (ou plus). Il faut donc à tout prix réduire le nombre de collisions. Il est possible de parcourir la grotte sans collision à l'exception du passage sous le 3ème stalactite. Ce passage entraîne 4 ou 5 collisions dans la plupart des cas. En fait, j'ai modifié mon algorithme de recherche pour l'orienter sur l'optimisation de ce nombre de collisions et surtout j'en ai demandé l'affichage. Le nombre de collisions est calculé deux fois dans chaque "tranche verticale" de cave et prend la forme d'un nombre entier compris entre 0 et 12, inclus. J'ai créé une liste (
colli) qui contient ces nombres de collisions et ça donne une liste de 255 entiers compris entre 0 et 12, inclus.
Une de mes tactiques pour améliorer mon score a été de minimiser ma consommation sans prendre en compte le nombre de collisions, puis de modifier mes 3 listes de coordonnées pour réduire le nombre de collisions lors du passage sous le 3ème stalactite puis de réduire le nombre de collisions après le 3ème stalactite. N'ayant d'abord pas utilisé l'interface graphique de Pavel, j'ai tenté d'optimiser le début du parcours (quitte à casser la suite du parcours), puis le passage sous le 3ème stalactite (quitte à casser la suite du parcours) puis de corriger la fin du parcours, et tout ça en jouant sur les valeurs de la liste
colli qui contient le nombre de collisions tout au long du chemin parcouru. J'ai ainsi créé un 2ème algorithme ayant pour seul but de réduire le nombre de collisions sous le 3ème stalactite. En fait, dans la liste
colli, le passage sous le 3ème stalactite correspond aux 169 et 170ème valeurs (donc d'indices 168 et 169). Dans l'idée, j'ai lancé mon script en mettant comme condition de réussite/affichage le fait d'avoir les 168 premières valeurs égales à 0, donc avec aucune collision avant le passage critique, puis comme condition d'avoir la somme
colli[168]+colli[169] (écrite sous la forme
sum(colli(168:170]) dans mon script) égale à 4 (en fait 2+2), puis comme condition d'avoir les derniers termes de la liste
colli tous égaux à 0.
J'ai tenté à de très nombreuses reprises d'avoir strictement moins de 4 collisions sur le parcours complet, mais rien n'y a fait, ni avec mon algorithme de recherche, ni avec la version adaptée pour la réduction du nombre de collisions, ni avec l'interface graphique de
Pavel améliorée par
LeGmask je n'ai réussi à réduire le nombre de collisions strictement en-dessous de 4.
Le 26/10 j'ai finalement obtenu 220.0 avec 4 collisions en tout, puis 221.0 mais avec 5 collisions. En supprimant cette 5ème collision, j'ai finalement obtenu 214. Le 27/10
Pavel envoie un score à 211 que j'ai réussi à obtenir quelques heures plus tard en imitant son trajet, sauf pour la fin. (On peut en effet remplacer deux segments droits qui coûtent 10 et 10 lorsque
state[2] vaut 0.5 par un morceau courbé qui coûte 10+10 directement). En partant du trajet à 214.0, il restait une optimisation à faire, qu'il a faite avant moi. Bien joué ! J'ai passé de longues heures à essayer de réduire encore le score, pour éventuellement passer à 208 en raccourcissant un morceau courbé dans un passage étroit (donc sans avoir
state[2]=0.5) et en rallongeant un segment droit, mais sans succès. J'ai également essayé de réduire le nombre de morceaux (-10 ou -20) tout en ayant une collision supplémentaire (+7 ou +14) mais sans y parvenir. 211.0 est peut-être le meilleur score possible, après tout...
En dégradant ce 211.0 j'ai obtenu 213.98 puis 213.56 puis 213.5 (justement en modifiant le 2ème paramètre du morceau qui contient la portion en rouge et en le mettant à 0.25 plutôt qu'à 0.5, le trait est moins fin mais donne toujours 4 collisions et la consommation globale est alors de 213.5). Il m'a semblé impossible d'obtenir un score strictement compris entre 211.0 et 213.5 et mon algorithme n'a pas trouvé non plus. Le participant qui est juste derrière moi a obtenu 213.501 et le suivant 213.502. En fait, il est possible d'obtenir des scores compris entre 213.500 et 213.501. Par exemple, en mettant 0.2501 plutôt que 0.25 au 2ème paramètre du morceau de courbe qui contient la zone en rouge, on obtient un score à 213.5002
et en mettant 0.25001 on obtient 213.50002
(message original)1. Pavel (
) :
211 (Programme :
q103.py)
pavel wrote:J'ai commencé par modifier le code cave.py pour en faire une version interactive qui peut être contrôlée avec les touches du clavier:
https://gitea.planet-casio.com/Pavel/caveguiEn jouant avec cette version interactive, j'ai essayé de comprendre le comportement du système. Voici ce que j'ai appris:
• il y a trois paramètres à contrôler (l'accélération verticale, le changement de forme du ballon, la durée)
• la vitesse horizontale est constante
• les mouvements à vitesse constante et avec la forme initiale du ballon sont gratuits
• pour le deuxième paramètre, seules trois valeurs doivent être utilisées: 0, 0.5, -0.5
• quand le deuxième paramètre est -0.5, la duree doit etre 1
• il faut minimiser la quantité d'instructions avec l'accélération ou le changement de forme du ballon différent de zéro
• il faut minimizer la durée de deplacements avec la forme du ballon différente de sa forme initiale
• il faut minimizer la quantite de collisions
Regarder des images des solutions des autres participants m'a aussi aidé à apprendre quelques astuces.
Comme il est très facile d'obtenir de bons scores simplement en jouant avec la version interactive du code, je n'ai même pas essayé de coder un algorithme qui trouvera la solution automatiquement.
(message original)Conclusion
Ce défi est pas mal de grind, avec peu de possibilités d'optimiser le résultat à l'ordinateur (ou en tous cas, pas assez de compétition pour vous inciter à le faire). La précision des passages fait quand même qu'un plan visuel ne suffisait pas à s'en sortir, il fallait aussi traiter chaque collision prudemment tout en limitant le nombre d'instructions.
Personnellement je suis partagé entre ce genre de format et ce qu'on trouve au troisième défi avec de l'IA à programmer. D'un côté jouer directement sur la calculatrice est plus accessible, d'un autre les sujets « paramétrés » (on donne une famille d'instances à résoudre) offrent beaucoup plus de liberté. Qu'est-ce que vous en pensez, vous ?
En tous cas, merci infiniment à tous les participations pour vos envois et vos commentaires. On se retrouve bientôt pour les résultats du défi du Léviathan !
by 
