by 
Après la publication du classement de la catégorie Casio dans un article précédent, voici aujourd'hui le classement catégorie HP de notre concours de rentrée 2017 Galactik! 
annales2maths quant à lui arrive au bout de 7 participations à une disposition tripolaire valant 44 958 742,169 9, se classant ainsi 7ème.
Comme promis tous les participants précédents gagnent un compte TI-Planet Premium, et si ils en avaient déjà un il leur est parfaitement possible d'en faire don à une autre personne.
Voici maintenant les mentions honorables ainsi que les gagnants, pour ces derniers dans l'inverse de l'ordre dans lequel ils pourront puiser dans la dotation annoncée afin de composer leur lot.
Dubs en 6ème position reste sur une disposition tripolaire avec son score de 45 202 987,870 6
@Dubs, comment as-tu fait pour devenir multimillionnaire ?
Dimitri U. arrive quant à lui à faire mieux après seulement 2 participations avec un seul amas d'étoiles, terminant avec 75 978 724,712 8 à la 5ème place.
@Dimitri, comment as-tu fait pour accumuler autant de millions ?
C'est en positionnant cet amas unique d'étoiles au centre que TheMachine02 arrive à faire encore mieux après seulement 2 participations avec 84 222 239,645 9 et à finir ainsi 4ème.
@TheMachine02, comment as-tu fait atteindre un aussi bon score ?
En 3ème position Cyril S. met un peu d'ordre en redisposant cet amas d'étoiles central selon un quadrillage triangulaire, arrivant ainsi à atteindre un score de 121 695 771,501.
@Cyril, quel est ton secret ?
En permutant plusieurs étoiles sur ce quadrillage triangulaire, hpfx arrive à monter jusqu'à 140 100 386,222 et donc à se classer 2nd après avoir persévéré pendant 7 participations.
@hpfx, comment t'y es-tu pris pour disposer tes étoiles ?
Honourable distinction for jacobly. By turning over and rotating the previous constellation, he achieved 140 100 386,223. But such participation couldn't be ranked, as the exact same score had already been submitted by someone else. He then managed to be accepted by slightly moving some stars and thus slightly lowering the score to the never submitted 140 100 386,221. This makes 4 participations. But he finally moved to the TI category.
@jacobly, how did you manage to achieve such a high score ?
By rotating this same constellation another time, Hooloovoo ranks 1st by improving the high score up to 140 100 386,223 after submitting 3 participations.
@Hooloovoo, we're waiting for your explanations.
Merci à vous tous pour vos efforts, mais aussi pour vos très nombreux messages positifs d'encouragements ou remerciements ayant accompagné vos participations et comptes rendus de recherche. Nous allons donc dès maintenant commencer à travailler sur un nouveau sujet qui sera proposé aux partenaires et constructeurs pour l'année prochaine - à bientôt on espère.
Et bien évidemment, remerciements au constructeur pour nous avoir fait confiance.
annales2maths quant à lui arrive au bout de 7 participations à une disposition tripolaire valant 44 958 742,169 9, se classant ainsi 7ème.Comme promis tous les participants précédents gagnent un compte TI-Planet Premium, et si ils en avaient déjà un il leur est parfaitement possible d'en faire don à une autre personne.
Voici maintenant les mentions honorables ainsi que les gagnants, pour ces derniers dans l'inverse de l'ordre dans lequel ils pourront puiser dans la dotation annoncée afin de composer leur lot.
Dubs en 6ème position reste sur une disposition tripolaire avec son score de 45 202 987,870 6@Dubs, comment as-tu fait pour devenir multimillionnaire ?
Dubs wrote:Je ne connaissais pas le langage de programmation de la HP Prime et le concours m'a donné un prétexte pour l'apprendre.
Je ne cherchais pas à obtenir le meilleur score, seulement apprendre le langage.
J'ai donc récupéré le source de l'appli Galactik et regardé comment il fonctionnait.
Ensuite je l'ai modifié pour qu'il cherche tout seul le meilleur score possible via force brute.
Je regroupe toutes les étoiles en haut à gauche et les déplace vers le bas/droite. je bouge une étoile d'un pixel, regarde le score et recommence jusqu'à ce qu'elle sorte de l'écran. Là je la replace en haut à gauche et bouge la seconde d'un pixel, etc.
Après une soirée passée à déplacer les étoiles pixel par pixel j'ai arrêté les frais, ça prendrait trop de temps par cette méthode.
Je l'ai améliorée un peu pour aller gagner en vitesse.
La position de départ est tirée aléatoirement, ensuite je bouge chaque étoile de quelques pixels vers un score plus élevé.
Ex: j'ai un score de 40, je bouge la première étoile vers la gauche d'un pixel pour un score de 39, vers la droite pour 40, vers le bas pour 41 et le haut 38.
Je déplace donc cette étoile vers le bas et passe au déplacement de la suivante. Je boucle sur toute les étoiles et retourne à la première jusqu'à ce que le score stagne.
Je sauve la positions des étoiles et le score obtenu.
Je repositionne les étoiles aléatoirement jusqu'à ce que leur position de départ dépasse le score actuel, puis les déplace pixel par pixel pour augmenter un peu le score.
Avec cette méthode et plusieurs heures de calcul j'avais obtenu un score dans les 104 millions.
Cool
Là je me suis dit que ce n'était pas très glorieux comme procédé et que j'allais plutôt essayer d'avoir un bon score en déplaçant les étoiles sans aide logicielle.
J'ai passé quelques soirées à déplacer les étoiles à la main, sans logique particulière, pour arriver à mon score final.
That's all.
Et au passage merci à TiPlanet pour ce concours !
Dimitri U. arrive quant à lui à faire mieux après seulement 2 participations avec un seul amas d'étoiles, terminant avec 75 978 724,712 8 à la 5ème place.@Dimitri, comment as-tu fait pour accumuler autant de millions ?
Dimitri U. wrote:Tout d'abord merci pour ce jeux bien sympathique. Au départ je voulais analyser l'algorithme mais faute de temps j'ai été au simple pour moi ; j'ai voulu faire confiance au hasard. J'ai modifié le programme pour que le déplacement et le changement d'étoile se fassent aléatoirement. J'ai laissé tourner sur mon PC le programme depuis la calculatrice virtuelle. Régulièrement je regardais le score obtenu. Après un certain temps, beaucoup de temps en fait, le meilleur score obtenu était catastrophique. En parallèle j'ai remarqué après quelques essais que j'obtenais mon meilleur score en regroupant dans une même zone toutes les étoiles. Quelques jours avant la fin du concours, je me suis résolu à ne plus faire confiance au hasard et essayer d'augmenter par moi-même mon score honorable, pour finir classer en 5ème position.
C'est en positionnant cet amas unique d'étoiles au centre que TheMachine02 arrive à faire encore mieux après seulement 2 participations avec 84 222 239,645 9 et à finir ainsi 4ème.@TheMachine02, comment as-tu fait atteindre un aussi bon score ?
TheMachine02 wrote:Alors globalement, j'ai commencé par refaire le programme de calcul des scores en C. Après j'ai essayé un premier bruteforce qui partait de positions aléatoires et tentait d'optimiser localement le système planétaire, en cherchant les meilleurs positions. Chose intéressante, j'ai pu créer des images de style heatmap, ce qui m'a permis de me rendre compte qu'on trouvait des distances optimales entre certains couples d'étoiles. Puis j'ai un peu tatonné directement sur émulateur afin de trouver la meilleur position en fonction des couples que j'avais trouvé. Et comme j'avais plus le temps, j'ai rien fait d'autre
En 3ème position Cyril S. met un peu d'ordre en redisposant cet amas d'étoiles central selon un quadrillage triangulaire, arrivant ainsi à atteindre un score de 121 695 771,501.@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 permutant plusieurs étoiles sur ce quadrillage triangulaire, hpfx arrive à monter jusqu'à 140 100 386,222 et donc à se classer 2nd après avoir persévéré pendant 7 participations.@hpfx, comment t'y es-tu pris pour disposer tes étoiles ?
https://tiplanet.org/forum/viewtopic.php?f=49&t=20678&start=10#p223559hpfx wrote:Ha c’est ici qu’on raconte sa vie, je vai battre le record du post le plus long alors
Je vais essayer de me rappeler, c’est déjà une histoire ancienne, vu que ça fait au moins 3 semaines que j’ai plus rien fait.
Chapitre 1 : le temps « soyons bourrin »
Au départ je suis parti sur un brute-force mais sans tester tous les pixels, je découpais en grille de 20 (ça donne rapidement des scores très honorables, et pour cause…)
Puis j’enchaine sur un petit algo « pathfinding » qui recherche à déplacer chacun des points d'abord dans les 4 directions à la recherche d’un minimum local. (puis plus de direction par la suite, [en diag, en cavalier/echec], puis même en sautant carrément plusieurs pixels :facteur 2,3,5…). Je crois que ça faisait en gros ~80 directions possibles.
Ensuite, J’essaie le déplacement deux à deux (2 étoiles au hasard, en testant toutes les combinaisons de déplacement possibles genre 80*80 cas), algo « move2 »
Ensuite J’essaye alors de déplacer toutes les étoiles en même temps (anecdote pour la suite : et là je me rends compte que le meilleur placement possible est au centre), algo « globalmove »
Voilà donc dans un 1er temps, j’enchaine les algo grid20, pathfind, move2, global-move. (plusieurs tests avec des variantes etc…) Les résultats sont très bons . Les étoiles sont a peu prêt disposées en carré (normal vu le choix « grille » du départ)
Et dans ma lancée je me dis que je vais affiner avec une grille plus resserré, mais contrairement à mon attente il se trouve que ça n’améliore pas les résultats…
J’entame un nouvel algo de placement initial : placement aléatoire, puis déplacer les étoiles de manière récursive (pour les 80 directions), je déplace l’étoile même si le score est inférieur à sa position initiale, pour contrer le phénomène « minimum local ».
Je calcul en siècles le temps de faire tous les cas, je suis donc obligé d’implémenter un casseur de récursivité une fois arrivé à 500.000 tests (ce qui m’amène déjà à des profondeurs de récursivité 30). J’appelle cet algo « tree ». c’est assez long car même si je casse après 500k, car il enchaine avec l’étoile suivante du 1er niveau, ça fait donc 500k * le nombre d’étoile.
Une fois mon meilleur arbre de déplacement trouvé pour un « run », je lui applique pathfind, move2, et globalmove. Et j’ai plus qu’à lancer plusieurs fois ce process.
Avec cet algo je serais 4eme de ma catégorie aujourd’hui avec 118 (pour info le meilleur score publié de l’époque était de 44). Les étoiles sont à peu près disposées en hexagone. C’est une réussite.
J’ai pas publié mon résultat, car je m’amusai alors à essayer de faire 100.000.000 tout rond pour le fun, en jouant avec les décimales des étoiles car on pouvait depuis peu avoir des nombres réels. Jusqu’à présent tous mes algo travaillent en entier. je ne suis pas arrivé à supprimer complètement les décimales, pour ça que non publié. J’ai bien remarqué le positionnement en hexagone, mais vu que je croyais être largement devant, que j’y avait passé des heures, je me contentai de 118 (je comptait passer 120 avec de petits ajustements...)
Alors que je travaillai juste à réduire mon score à 100... et bim, je vois qu’un concurrent publie à 140 « et là c’est le drame»
Chapitre 2 le temps « réfléchissons un peu pour changer »
Ok je modifie mon algo « tree » pour faire des déplacements « en étoile » à 30° pour voir, en quelques minutes je monte à 138. Pas mal, mais toujours inférieur à 140.
Et là j’ai enfin l’idée d’essayer de comprendre le calcul...
Très rapidement on voit bien que les points doivent être à une distance de 20 les uns des autres (car c’est « la valeur absolue de la distance moins 20 » qui compte dans le calcul), et que ça doit être centré, car on compare avec la première étoile qui est fixe et au centre.
Du coups depuis mon meilleur résultat (118) je repère en gros la position des étoiles, et je positionne « mathématiquement » les points sur la calto direct (sans algo) juste en modifiant les valeurs de la liste grâce à la notation exponentielle des complexes (par exemple point 1 = Z0 + 20*exp(i*pi/3)) et la direct 138Yes !
Je regarde les placements de tous mes bons scores (entre 110 et 118) et je remarque qu’il y a plusieurs configurations possibles en fait(ça donne de l’espoir), bon après coups j’ai compris que ce n’est pas vrai : il n’y a qu’une seul conf, il s’agit juste de symétrie ou rotations...
Sur cette base, et plein d'espoir, Hop un nouvel algo, au départ : tous les points confondus au centre, 6 déplacements possibles (à 20 pix) … en quelques secondes j’arrive enfin à 140, et je suis premier de quelques millièmes.
Chapitre 3 « j’ai compris »
Alors que Monsieur 140 me repasse devant le lendemain, je comprends qu’il n’y a qu’un seul bon placement, et qu’il faut jouer sur la rotation. En effet, la matrice ne régît que la position relative des points, mais en aucun cas leur placement absolu, on peut donc faire des rotations !
J’ai fait un petit algo qui fait tourner les points autour du centre. Merci la formule de la rotation des complexes : z* exp(i*angle), bon bien sûr il faut le faire par rapport au centre Z0 : (z-Z0)*exp(i*angle)+Z0
Ca marche !
Mais même avec un pas de rotation de pi/1000000 je ne peux pas faire mieux que décimale 0.223 (déjà pris), je publie donc 0.222 et voilà. Le lendemain un 3eme concurrent trouve aussi la méthode et publie 0.221. tout a été hyper vite.
Conclusion
Je me suis éclaté sur ce concours. un gros boulot d'algo (dont certain peu utilisé à la fin) puis clairement une réflexion mathématique.
Un grand merci aux organisateurs. c'était hyper fun.
au passage si critor m'a lu jusqu'ici, comme Zezombye, moi aussi je préfère que ça soit mon pseudo d'affiché.
Au passage,
Ce qui m’intrigue c’est le concurrent hp qui est à 121,
En effet j’ai eu des seuils difficiles à franchir en particulier 118, je serais curieux de savoir sa méthode/algo pour faire 121.
Honourable distinction for jacobly. By turning over and rotating the previous constellation, he achieved 140 100 386,223. But such participation couldn't be ranked, as the exact same score had already been submitted by someone else. He then managed to be accepted by slightly moving some stars and thus slightly lowering the score to the never submitted 140 100 386,221. This makes 4 participations. But he finally 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.
By rotating this same constellation another time, Hooloovoo ranks 1st by improving the high score up to 140 100 386,223 after submitting 3 participations.@Hooloovoo, we're waiting for your explanations.
Hooloovoo wrote:The first step to solving Galactik was to understand how exactly the score is computed from L8.
I'm not going to go over the details of figuring out the dense HPPPL program, but I'll give a brief overview of how the score is computed.
Each point is stored as a complex number in L8. I think the easiest way to think of it is as a weighted complete graph. Basically, there is an operation computed between every pair of points, and the score is the sum of those operations.
There is a in pseudocode, theget_score(L8,weight_matrix)looks like:
There is also set up a list of weights between each edge
- Code: Select all
get_score(L8,weights):
s=0
for p from 2 up to N_PTS:
for i from 1 to p-1:
if i == 1 and weights[i][p]<0:
score += weights[i][p] / (1 + abs(L8[i] - L8[p]))
else:
score += weights[i][p] / (1 + abs(20-abs(L8[i] - L8[p])))
a couple notes on that:
since L8 is a list of complex numbers,abs(L8[ i ]-L8[p])finds the distance between them.
for each pair of points, the distance is evaluated once, and depending on the weight, things are evaluated differently: for positive weights, it is best if the distance is close to 20, and for negative weights, they should be far apart
There is a special case for the first point, such that it is best if all points are close to it, since those edges always have positive weight.
I used simulated annealing in python to figure out some optimal solutions. Once I had that I made it work on the calculator because I could. That got me to 129e6, but the points looked like they were exactly 20 away from one another when plotted, in a hexagonal grid. that shouldn't have surprised me, really.
I assumed that the points all lie on a triangular grid with spacing of 20. I modified the program so it would only check for solutions on that triangular/hex grid, and I got very near the final score, only a few fractions of a point away.
s solution was near the correct local minimum, but I didn't do any optimization on that. small deviations could change the score slightly.
Unfortunately, there is a huge difference between standard IEEE 754 floats and HP's floating point representation. I couldn't write up this next optimizer in python, because I didn't know how exactly the calculator does floating point math!
The next solution I posted, I think, was based on an SA approach running on the virtual Prime starting from the previous solution.
I found that starting the SA optimizer from different rotations of the same pattern (since the energy function doesn't care about rotation, mod weird FP effects) and even different random seeds, resulted in different final scores.
I'm not convinced that there is a general-purpose optimizer that I could use for this. There probably is.
I already had a SA optimizer coded up, and computers are fast, so I decided to use brute force. I started the optimizer from each successive starting location, rotating the original pattern by a small delta each time those until I couldn't get any better.
Merci à vous tous pour vos efforts, mais aussi pour vos très nombreux messages positifs d'encouragements ou remerciements ayant accompagné vos participations et comptes rendus de recherche. Nous allons donc dès maintenant commencer à travailler sur un nouveau sujet qui sera proposé aux partenaires et constructeurs pour l'année prochaine - à bientôt on espère.
Et bien évidemment, remerciements au constructeur pour nous avoir fait confiance.
