Publication participations concours Galactik rentrée 2017

[Adriweb]

Bravo, et très intéressant

[proghy_v2]

Moi j'ai pas de compte planet casio alors je vais raconter ma vie ici.

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.

[jacobly]

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.

[Adriweb]

Congratulations to you two as well, very interesting

[hpfx]

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 138 Yes !
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.