by 
Après la publication du classement de la catégorie HP dans un article précédent, voici enfin aujourd'hui le classement catégorie NumWorks de notre concours de rentrée 2017 Galactik! 
Mention honorable pour MMBC_Chris qui passe à une disposition quadripolaire lui obtenant un score de 46 412 928 après 2 participations. Toutefois il a par la suite changé pour la catégorie TI.
Iamissam arrive quant à lui à faire mieux après 3 participations avec un unique amas d'étoiles central, terminant avec 55 490 249 à la 6ème place.
Mention honorable avec un amas d'étoiles un peu plus excentré pour Cyril S. mais avec un peu plus d'ordre avec des dispositions remarquables en triangle et en carré, qui arrive ainsi à faire encore mieux avec 77 653 887. Il a par la suite opté pour la catégorie HP.
@Cyril, quel est ton secret ?
En 5ème position Tom H. scinde la constellation en 2 pôles mais ordonne intégralement l'un d'entre eux selon un quadrillage triangulaire, arrivant ainsi à atteindre un score de 97 436 116, 3 participations.
En reprenant cet ordonnancement triangulaire mais avec un unique amas d'étoiles, Jujuwalrus arrive à monter jusqu'à 105 120 352 et donc à se classer 4ème après avoir persévéré pendant 7 participations.
Mention honorable avec une disposition partiellement triangulaire mais centrale pour Lephenixnoir, qui arrive ainsi à faire monter les enchères à 107 711 143. Il a toutefois la malchance d'être administrateur de Planète Casio et ne pouvait donc pas être classé.
@Lephenixnoir, comment t'y étais-tu pris pour disposer tes étoiles ?
Avec quelque chose de similaire, Thomas M. arrive à monter jusqu'à 110 530 628 et à se classer 2nd, si si, après avoir persévéré pendant 5 participations.
Avec une disposition centrale intégralement ordonnée selon un quadrillage triangulaire, Oakwood arrivait initialement à faire mieux, 111 004 247.
Toutefois, il a volontairement envoyé par la suite une configuration moins optimale, expliquant tout à son honneur qu'il pouvait se payer la calculatrice NumWorks et préférait laisser leur chance à d'autres candidats, terminant ainsi 3ème avec 110 381 793 après un total de 7 participations.
Toutes nos félicitations à proghy_v2. Avec une organisation triangulaire centrale, il culmine à 113 492 545 et décroche ainsi la 1ère place après 3 participations.
@proghy_v2, explique-nous vite comment tu as fait !
Very honourable distinction for jacobly. With a similar but maybe more central constellation, he achieved 117 905 625. But he then moved to the TI category.
@jacobly, how did you manage to achieve such a high score ?
Merci à vous tous pour les efforts, mais aussi pour vos très nombreux messages positifs d'encouragements ou remerciements ayant accompagné vos participations ou comptes rendus de recherche, et qui nous ont fait bien chaud au coeur. En effet, ce concours a nécessité de notre part un investissement bénévole très conséquent ainsi qu'une forte abnégation puisque nous n'avons compté :
Mention honorable pour MMBC_Chris qui passe à une disposition quadripolaire lui obtenant un score de 46 412 928 après 2 participations. Toutefois il a par la suite changé pour la catégorie TI.
Iamissam arrive quant à lui à faire mieux après 3 participations avec un unique amas d'étoiles central, terminant avec 55 490 249 à la 6ème place.
Mention honorable avec un amas d'étoiles un peu plus excentré pour Cyril S. mais avec un peu plus d'ordre avec des dispositions remarquables en triangle et en carré, qui arrive ainsi à faire encore mieux avec 77 653 887. Il a par la suite opté pour la catégorie HP.@Cyril, quel est ton secret ?
Cyril S. wrote:Quand j’ai découvert le concours, pour des raisons de facilités, j’ai commencé à chercher dans la catégorie Numworks, où j’ai posté un premier score trouvé empiriquement. Bien qu’appréciant les calculatrices, je suis totalement novice dans la programmation sur calculatrice ou simplement le transfert de fichiers.
Puis j’ai chargé le programme pour ma Casio CP400 (que j’ai depuis deux mois), même si les lots ne m’intéressait pas vraiment. Après avoir essayé de déplacer fastidieusement les étoiles et pensé que soit j’avais mal fait l’importation, soit que le programme était bogué, j’ai chargé l’émulateur HP Prime, et j’ai vraiment commencé à être méthodique.
J’ai commencé par placer toutes les planètes en haut de l’écran, j’ai descendu la première, puis les autres une à une, afin d’établir un tableau répertoriant les différentes interactions avec des --, -, +, ++, tableau qui correspondra à la matrice G. Cela m’a permis de voir la distance 20 revenant pour les interactions positives.
J’ai ensuite copié le programme dans Notepad++, afin de l’indenter, et l’analyser en détail. J’ai découvert le fonctionnement du ranseed, puis compris comment le score était calculé. J’ai créé une liste avec les valeurs du ranseed(42) que j’ai exportée vers Excel, elle m’a permis de créer la matrice G.
Puisqu’il fallait placer les planètes avec une distance de 20, sur papier, j’ai disposé les planètes sur un maillage en formant des triangles équilatéraux en fonction des valeurs de G, en trouvant les coordonnées avec un peu de trigonométrie. Et j’ai obtenu un score aux alentours de 121 millions.
Pour essayer d’améliorer, j’ai repris Excel et créé une succession de matrices afin d’y calculer directement le score et d’utiliser les algorithmes du solveur. Que ce soit clair, il s’en sort peut être bien pour une fonction du second degré, mais là, il y a beaucoup trop d’extrema locaux, et globalement, il n’a presque jamais été en mesure d’améliorer la position initiale donnée, parfois quelques centièmes grappillés quand même.
J’ai fini par trouver à la main encore une réponse un peu meilleure avec 124,4 millions que je n’ai pas postée. Je comptais la garder pour revenir dans la catégorie HP, après avoir posté des résultats dans d’autres catégories, mais des vacances m’ont empêché de poursuivre mes recherches.
Je regrette quand même de ne pas avoir posté le score de 9,4 millions que j’avais trouvé sur CP400, puisqu’aucun score n’a été envoyé avec cette version du programme.
Ce concours était très intéressant, j’ai découvert la HP Prime via son émulateur, et je l’ai vraiment appréciée, la programmation y est compréhensible assez vite.
En 5ème position Tom H. scinde la constellation en 2 pôles mais ordonne intégralement l'un d'entre eux selon un quadrillage triangulaire, arrivant ainsi à atteindre un score de 97 436 116, 3 participations.
En reprenant cet ordonnancement triangulaire mais avec un unique amas d'étoiles, Jujuwalrus arrive à monter jusqu'à 105 120 352 et donc à se classer 4ème après avoir persévéré pendant 7 participations.
Mention honorable avec une disposition partiellement triangulaire mais centrale pour Lephenixnoir, qui arrive ainsi à faire monter les enchères à 107 711 143. Il a toutefois la malchance d'être administrateur de Planète Casio et ne pouvait donc pas être classé.@Lephenixnoir, comment t'y étais-tu pris pour disposer tes étoiles ?
https://www.planet-casio.com/Fr/forums/lecture_sujet.php?id=14990#150945Lephenixnoir wrote:J'ai implémenté un pur algorithme génétique. Ce type d'algo consiste à prendre un population, ici un ensemble de solutions avec leurs scores. Il applique ensuite un cycle bien précis :
1. Évaluation : On calcule le score de chaque configuration
2. Sélection : On ne garde que les meilleures
3. Croisement : On croise les meilleures entre elles pour recréer de la population
4. Altération : On modifie aléatoirement quelques positions (pour éviter de stagner)
5. On recommence à l'étape 1.
Les deux premières étapes sont simples à s'imaginer. Pour la troisième, j'avais deux manières de croiser deux configurations. Dans chacune d'elles, je considérais pour chaque étoile, sa position dans la première configuration, puis dans la deuxième. La première méthode choisissait, pour placer cette étoile dans la configuration fille, une position au hasard sur le segment. La seconde aussi, mais elle se mettait au même endroit (au même rapport de distance, ie. le même barycentre) pour toutes les étoiles, ce qui donnait une sorte de rotation qui préservait bien le score.
Pour l'altération, je faisais vibrer toutes les étoiles sur une amplitude de λ autour de leur position. Tant que le score maximal de la population grandissait, λ restait fixe, mais s'il stagnait, λ devenait plus petit pour permettre de gagner de la précision. Si ça ne suffisant pas, λ devenait très grand pour tenter de débloquer la situation.
Je faisais tourner ça sur 65'000 à 4 millions de générations selon les cas (plus le score semblait prometteur et plus je faisais durer la simulation), en partant de configurations entièrement aléatoires. En le faisant tourner quelques minutes, je sortais plusieurs configurations à plus de 9 millions, mon meilleur score étant 9846814.67 sur Casio et 107711137.32 sur Numworks.
Comme ça ne suffisait pas pour rattraper les premiers, j'ai imaginé un autre système (que je n'ai malheureusement pas eu le temps d'implémenter). Ça consistait à traduire les relations entre les étoiles en forces et à appliquer de la mécanique sur le système. En gros, en combinant la somme de toutes les forces, le système aurait convergé naturellement vers un équilibre local. En plus de ça, j'aurais fait vibrer doucement toutes les planètes avec l'algorithme génétique pour éviter de stagner.
Avec quelque chose de similaire, Thomas M. arrive à monter jusqu'à 110 530 628 et à se classer 2nd, si si, après avoir persévéré pendant 5 participations.
Avec une disposition centrale intégralement ordonnée selon un quadrillage triangulaire, Oakwood arrivait initialement à faire mieux, 111 004 247.
Toutefois, il a volontairement envoyé par la suite une configuration moins optimale, expliquant tout à son honneur qu'il pouvait se payer la calculatrice NumWorks et préférait laisser leur chance à d'autres candidats, terminant ainsi 3ème avec 110 381 793 après un total de 7 participations.
Toutes nos félicitations à proghy_v2. Avec une organisation triangulaire centrale, il culmine à 113 492 545 et décroche ainsi la 1ère place après 3 participations.@proghy_v2, explique-nous vite comment tu as fait !
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&p=223473#p223473proghy_v2 wrote:Déjà si vous me connaissez pas, c'est normal. Je m’intéressais aux calculatrices quand j'étais au lycée, j'ai posté quelques programmes z80 sur le site avant TI Planet, mais dès que j'ai eu un pc portable mon intérêt s'est détourné des calculatrices, donc je suis pas resté longtemps sur TI Planet.
Et puis la semaine dernière s'était Halloween, et je me disais que plus beaucoup de site changeaient de look pour l'occasion, alors je suis venu checker pour voir s'il y avait toujours des beaux artworks Halloween ici. Et je suis tombé sur la news qui annonçait la fin du concours, ça m'a trigger.
J'ai réinstallé wabbitemu pour tester le programme TI mais j'ai pas réussi, il me disait qu'il y avait pas assez de mémoire sur la calculatrice, wtf. Pas envie de me casser la tête, je suis parti sur la version Numworks en js. Comme je suis un quiche en js j'ai utilisé js2py pour convertir tout ça en python. J'ai juste réécris la fonction recalc() à la main pour qu'elle soit performante. Après j'ai testé a peu près tous les algos de la librairie scipy.optimize. Les algo de minimisation locale arrivaient à rien, la fonction est pas assez régulière / linéaire / différentiable que sais-je. Du coup je suis parti sur l'algo « differential evolution ». J'ai essayé pas mal de combinaisons de paramètres pour l'algo et rapidement j'arrivais dans les 106 millions, mais difficile de faire mieux.
Je me suis dit que j'avais plus le choix, qu'il fallait réfléchir. J'ai regardé le code et je me suis mis en tête d'exprimer la fonction avec la matrice de distance en entrée plutôt qu'avec des coordonnées de points. J'avais l'intuition que la fonction serait bien plus régulière et que les algo à descente de gradient pourraient converger. Et ils ont très bien convergé en effet : plus de 150 000 000 millions ! Alors j'ai essayé de placer des points dans le plan qui correspondaient à ces distance, mais c'était pas possible évidemment. J'ai alors ajouté aux problème de minimisation les contraintes pour que les distances vérifient les 3 inégalités triangulaires dans tous les triangles. Encore une fois ça converge bien, plus de 130 millions, je crois avoir touché au but. Mais non, la solution est toujours pas constructible en termes de points.
Je me suis dit qu'il manquaient encore des contraintes au niveau des quadrilatères. J'ai exprimé la longueur de la 6ème longueur en fonction des 5 autres. On se retrouve avec 2 cas :
cas convexe :
f^2=a^2+b^2-2*a*b*cos(arcos((a^2+e^2-c^2)/(2*a*e))-arcos((e^2+b^2-d^2)/(2*e*b)))
cas concave :
f^2=a^2+b^2-2*a*b*cos(arcos((a^2+e^2-c^2)/(2*a*e))+arcos((e^2+b^2-d^2)/(2*e*b)))
Je fais tourner mon algo avec ces contraintes... « math domain error » :/
Donc je prolonge ma fonction arcos pour qu'elle soit continue, pseudo-périodique parce que... je voyais pas quoi faire d'autre qui ait du sens.
Et l'algo a convergé vers un truc pourri, genre 80 millions. Je sas pas si c'est mes contraintes qui étaient trop fortes, ou la fonction pas assez comme il faut. J'ai ragequit, je suis retourné sur l'algo génétique, et au bout d'un moment j'ai trouvé des bon paramètres, ça me donnait dans les 113 millions, suffisant pour être premier.
Après j'ai essayé une autre lib de minimisation qui s'appelle pygmo. L'algo self adaptative differetial evolution arrivait à trouver dans les 110 millions sans se casser la tête à choisir les paramètres. L'algo CMA-ES a réussir à atteindre les 116 millions (fallait juste diviser la sortie de la fonction par un million sinon il stagnait dans les 108 millions). J'ai pas posté ce dernier résultat parce que c'était plus de minuit par contre ^^
Au final j'ai appris pas mal de trucs sur python et la algo de minimisation, c'était cool.
Very honourable distinction for jacobly. With a similar but maybe more central constellation, he achieved 117 905 625. But he then moved to the TI category.@jacobly, how did you manage to achieve such a high score ?
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&start=10#p223474jacobly wrote:I used simulated annealing programmed in C to get all of my scores. Initially I assumed that I was restricted to integer coordinates which was difficult to optimize and didn't produce very good scores. Then I found out that other people were getting higher scores with fractional coordinates so I switched to a continuous algorithm. At some point I noticed that most of my good configurations had the stars near a "hexagonal" lattice of points where each point is 20 units away from 6 other points. I used this information to create another discrete implementation that only considered the points on this lattice. This let me find close to an optimal score fairly quickly, which I could then polish off by alternating two continuous algorithms. Since I was working with binary floats the whole time, I had no reasonable way to fully optimize the last digit when computed with decimal rounding error, and I ended finding a solution within an ulp of first place in 3 categories.
Merci à vous tous pour les efforts, mais aussi pour vos très nombreux messages positifs d'encouragements ou remerciements ayant accompagné vos participations ou comptes rendus de recherche, et qui nous ont fait bien chaud au coeur.
En effet, ce concours a nécessité de notre part un investissement bénévole très conséquent ainsi qu'une forte abnégation puisque nous n'avons compté :- ni notre temps, avec littéralement 4 mois de préparation qui sont à rajouter aux 3 mois s'étant écoulés depuis son lancement
- ni les goodies, nombre d'entre eux provenant de nos stocks personnels pour lesquels nous avons raclé jusqu'au fond des tiroirs, afin d'accompagner généreusement et équitablement un maximum de lots par catégorie
- ni notre argent, avec des frais d'expédition atteignant déjà 3 chiffres alors que les envois ne sont même pas terminés
