Forums Casio - Discussions

Index du Forum > Discussions > Triconcours et l'épreuve de force
Hackcell
En ligne
Membre
Points: 900
Défis: 6
Message
Posté le 20/09/2018 10:16

Triconcours et l'épreuve de force :

Hello tout le monde, depuis peu, à débuté l'épreuve de force (non plutôt bien choisi, vous verrez pourquoi plus tard ) en python du tri-concours de la rentrée 2018.

Le but, obtenir un score maximal, envoyer la réponse et décrocher un lot... Plus sérieusement, c'est un poil plus complexe, il s'agit de régler virtuellement 30 potentiomètre pour allumer jusqu'à 252 ampoules (21 * 12). Pour ce faire, vous utilisez la fonction pot en indiquant le numéro du potentiomètre (de 0 à 29) à régler et la valeur du potentiel que vous souhaitez lui assigner(entre 0 et 1), faîtes ceci pour les 30 potentiomètre (ou pas, chaque potentiomètre est réglés de base sur 0) regarder le résultat et envoyé ce dernier a Planète TI.

Jusqu'ici, c'etait les informations disponibles sur l'annonce du concours, maintenant, passage aux données Secret Défense que j'ai pû obtenir via un poil de rétro-ingenering et que je vous partage au péril de ma vie...

Tout d'abord, le calcul des scores, pour l'instant, j'ai déterminer que votre score vaut : Amp_all - (Alim + Amp_grill/2 + Gaspi/5 + pertes/10)
avec:
-Amp_all le nombre d'ampoules allumé
-Alim l'alimentation utilisé
-Amp_grill le nombre d'ampoules grillée
-Gaspi l'énergie gaspillée
-Pertes l'énergie perdu

Ces différentes fonctions sont calculés comme suit:
-Alim est la simple somme du potentiel assigné à chaque potentiomètre
-Gaspi est l'énergie de l'alimentation utilisé pour allumer les ampoule déjà allumé (avec 252 ampoules, ça peut monter très vite)
-Pertes est cette fois ci l'énergie utilisé mais qui ne suffit pas à allumer une ampoule

La définition de perte peux vous semblez étrange, à moins que vous ayez connaissance de l'élément suivant :
-Chaque potentiomètre est 'relié' a un certain nombre d'ampoules, ainsi chaque ampoules reçois de l'énergie de différentes potentiomètre
-Pour savoir si une ampoules s'allume, elle regarde donc la somme de l'énergie reçu par les différents potentiomètre qui lui sont attaché, ensuite, la loi est simple, moins de 1, éteinte, entre 1 et 2 (bornes incluses) allumée, plus de 2, grillee.

Un autre point intéressant à noter, est ce que l'on pourrait appeler la discrétisation des valeurs prise par le potentiomètre, en effet, il s'agit ici d'un programme informatique, le potentiel ne peux donc pas être continue, il est discret, ainsi il n'admet qu'un nombre finis de valeurs entre 0 et 1 (bornes incluse), plus précisément, 101 valeurs, avec un écart de un centième entre chaque.

A partir de là, on peut calculer le nombre de possibilités, attention.... 30 potentiomètre, avec 101 possibilité, ça fait, ça fait... Bravo, ça fait bien 101^30, soit un ordre de grandeur de 10^31.. Oui oui, un 1 et 31 zéros derrière, pour vous donner une idée, voici sa tête :

roulement de tambour
Tada
1347848915332905650585522351309777516867383425202804564353001
(tapez donc 101**30 dans votre console python)


C'est donc bien une épreuve de force , même si le brute force ne me semble pas être une bonne idée

Cependant, il existe un grand nombre de possibilités qu'il n'y aurait pas besoin de chercher, ce sont celles où la somme des potentiels est strictement inférieurs à 1, dans de telles conditions, aucune lampe ne pourrai s'allumer.

Ainsi, on fait de plutôt bon score en mettant tout les potentiomètre à la valeur X avec 1≤ 30X ≤ 2, ça peut paraître barbare, mais on peut obtenir de plutôt bon score sans se fouler...

Enfin, si jamais je m'appellais 3blue1brown, je vous parlerai sans doute du fait qu'il s'agit là de trouver le maximum d'une fonction dans un espace à 30 dimensions, fonction qui n'est pas continue sur cette espace, même si je la soupçonne d'être continue par morceau (mais le démontrer....) et qu'il existe des méthodes pour trouver des maximum pour ces fonctions, mais c'est pas tout à fait mon niveau, donc on vas s'arrêter là (malheureusement pour vous ).

Pour ma part, il est minuit vingt le 20 septembre 2018, et je pense avoir trouvé une solution à presque 212 points.
Si vous voulez aussi partager des astuces et des informations sur l'algorithme, n'hésitez pas, ça ne rendra le concours que plus compétitifs et amusant <3



Pages: 1, 2 | Suivante

Critor
En ligne
Administrateur
Points: 985
Défis: 0
Message
Citer : Posté le 20/09/2018 13:13 | #
Merci pour ton analyse fort intéressante !
Je l'ai liée depuis TI-Planet.

Je donnerai des précisions à certains points prochainement. @+
Hackcell
En ligne
Membre
Points: 900
Défis: 6
Message
Citer : Posté le 20/09/2018 13:17 | #
De rieni, si mes insomnies peuvent être utiles
Et merci pour la pub

J'ai hâte de voir ça
----------------------------------
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
Kikoodx
Hors ligne
Membre
Points: 806
Défis: 7
Message
Citer : Posté le 20/09/2018 13:48 | #
Pour la brute force ça reste possible si quelqu'un fait un programme bien optimisé et qu'il le laisse tourner quatre semaines je pense.
Réfléchie la brute force.
----------------------------------
Lbl 1
Goto 1


Une boucle optimisée
Drak
Hors ligne
Rédacteur
Points: 1920
Défis: 38
Message
Citer : Posté le 20/09/2018 13:50 | #
C'est une épreuve de force... Où il faut réfléchir...

Mais où va le monde ?!
----------------------------------
Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
Kikoodx
Hors ligne
Membre
Points: 806
Défis: 7
Message
Citer : Posté le 20/09/2018 13:53 | #
Réfléchir c'est dépassé
----------------------------------
Lbl 1
Goto 1


Une boucle optimisée
Nemhardy
Hors ligne
Grand maître des Traits d'Esprit
Points: 1232
Défis: 54
Message
Citer : Posté le 20/09/2018 13:58 | #
Oui, enfin si tu fais un bruteforce sans réfléchir, si je fais confiance au calcul de Hackcell et ses ~10⁶⁰ possibilités, à raison de l'ordre du milliard d'opération par seconde, il te faudra quand même de l'ordre de 10^51 secondes pour explorer le tout. Je te laisse convertir ça en millénaires pour avoir une petite idée de ce que ça prend comme temps…

Après une approche tu peux effectivement réfléchir à faire du bruteforce, mais en réfléchissant un peu plus pour limiter la taille de ton espace à explorer, pas exemple !

----------------------------------
N'attendez pas qu'il n'y ait plus de miel : スススススススススススススススススススススススススス養蜂家スススススススススススススススススススススススススススススススススススス蜂家
Pavel
Hors ligne
Membre
Points: 5
Défis: 0
Message
Citer : Posté le 20/09/2018 14:00 | #
Une petite précision. Chaque potentiomètre a 94 positions. Ce qui correspond au nombre de caractères ASCII imprimables (codes 33 - 126) utilisés pour encoder les solutions.
Ne0tux
Hors ligne
Membre d'honneur
Points: 3231
Défis: 261
Message
Citer : Posté le 20/09/2018 14:17 | #
Le must ça serait que les 30 caractères de la solution optimale (s'il y en a une) forment une phrase du style "Vive la programmation Python!".

Merci Hackcell au passage pour ton analyse.

Drak, je pense qu'il faut se forcer à réfléchir, c'est pour ça...
----------------------------------
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Kikoodx
Hors ligne
Membre
Points: 806
Défis: 7
Message
Citer : Posté le 20/09/2018 14:25 | #
Nemhardy a écrit :
Oui, enfin si tu fais un bruteforce sans réfléchir, si je fais confiance au calcul de Hackcell et ses ~10⁶⁰, à raison de l'ordre du milliard d'opération par seconde, il te faudra quand même de l'ordre de 10^51 secondes pour explorer le tout. Je te laisse convertir ça en millénaires pour avoir une petite idée de ce que ça prend comme temps…

Après une approche tu peux effectivement réfléchir à faire du bruteforce, mais en réfléchissant un peu plus pour limiter la taille de ton espace à explorer, pas exemple !

88087814028947e+40 ans

C'est ce que je compte faire, comme mal indiqué dans un message plus haut :
KikooDX a écrit :
Réfléchie la brute force.


Pavel a écrit :
Une petite précision. Chaque potentiomètre a 94 positions. Ce qui correspond au nombre de caractères ASCII imprimables (codes 33 - 126) utilisés pour encoder les solutions.

Si c'est vrai c'est intéressant.
Cela ferait (sauf erreur) 94³⁰ possibilités, ou
un long nombre
un long nombre
156255606166664794744820432128893757248925435391359137611776
qui est un multiple de 10⁵⁹...
Je pense que je ne sais plus compter

EDIT : j'ai corrigé ma bêtise

Ajouté le 20/09/2018 à 14:26 :
J'ANNULE TOUT !

Ajouté le 20/09/2018 à 14:30 :
Ce qui fait effectivement ~10⁶⁰...
C'était mon intervention indispensable.
Merci à tous
----------------------------------
Lbl 1
Goto 1


Une boucle optimisée
Lephenixnoir
Hors ligne
Administrateur
Points: 13201
Défis: 136
Message
Citer : Posté le 20/09/2018 15:19 | #
Enfin, si jamais je m'appellais 3blue1brown, je vous parlerai sans doute du fait qu'il s'agit là de trouver le maximum d'une fonction dans un espace à 30 dimensions, fonction qui n'est pas continue sur cette espace, même si je la soupçonne d'être continue par morceau (mais le démontrer....) et qu'il existe des méthodes pour trouver des maximum pour ces fonctions, mais c'est pas tout à fait mon niveau, donc on vas s'arrêter là (malheureusement pour vous ).

Effectivement, moi je pense tenter de maximiser la fonction dans un espace à 30 dimensions, et peut-être un peu plus... je ne peux pas gagner mais je peux bien essayer si j'ai le temps (évidemment j'ai une piste, je m'y prends pas au hasard...)
----------------------------------
Rise.
Hackcell
En ligne
Membre
Points: 900
Défis: 6
Message
Citer : Posté le 20/09/2018 15:42 | #
Contents de voir que le sujet plaît
@Pavel Pour les 101 position, j'ai fait ça rapidement, il est donc possible que j'ai raté quelque doublons :/
Donc merci

Et puis comme Lephe, j'ai un petit algorithme qui recherche un maximum de façon 'intelligente' (seulement en 30D par contre ), mais bon, ce serait donné toutes mes cartes, donc après la fin du concours je vous le révélerai

Et pour le 101**30 de l'ordre de 10**31, personne dis rien
----------------------------------
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
Critor
En ligne
Administrateur
Points: 985
Défis: 0
Message
Citer : Posté le 20/09/2018 21:29 | #
Donc pourquoi est-ce qu'au lieu de float j'utilise une espèce de mfloat bizarre qui en pratique est un sous-ensemble des rationnels, ceux de dénominateur 93 ?

Certainement pas pour vous embêter. Non la discrétisation des potentiomètres n'était au départ pas voulue.

Nous avons donc 252 lampes et 30 potentiomètres, soit 282 états à stocker.
C'est... beaucoup. En tous cas pour certaines calculatrices.

Prenons un exemple :
from sys import *
>>> getsizeof(1<<0)
28
>>> getsizeof(1<<29)
28
>>> getsizeof(1<<30)
32
>>> getsizeof(1<<59)
32
>>> getsizeof(1<<60)
36
>>> getsizeof(1<<89)
36
>>> getsizeof(1<<90)
40

Comme vous le voyez, la taille d'un entier en Python progresse avec son nombre de bits.
Mais on peut empêcher cette progression en faisant en sorte que les entiers utilisés ne dépassent jamais une certaine valeur.

Avec les floats, c'est différent. Il suffit parfois d'opérations enfantines pour les faire grossir :
>>> 1.2-.1
1.0999999999999999


Le facteur limitant est ici le lecteur en ligne NumWorks, avec ses 6K supposés de mémoire de travail.

Déjà, il se trouve qu'au départ ça ne rentrait même pas en mémoire. Sauf à réduire drastiquement le nombre de lampes ou de potentiomètres, et donc l'espace de recherche pour ceux qui voudraient tenter un bruteforce.

Mais supposons donc qu'à force de réduire ces 2 paramètres ça finisse enfin par rentrer, tout juste donc.
Toucher un potentiomètre implique de toucher à plein de floats dans les tableaux de lampes/potentiomètres. Et parmi ces nombreuses opérations, certaines vont faire grossir des floats dans le tableau, déclenchant ainsi un besoin de réallouer l'espace occupé.
C'est ce que nous avons eu, à peine 2-3 appels à pot(k,v) et ça explosait la mémoire de travail du lecteur en ligne NumWorks.

D'où l'idée de représenter les états des lampes et potentiomètres non plus par des flottants mais par des entiers, ici les numérateurs de fractions de dénominateur 93.
Dark storm
Hors ligne
Membre d'honneur
Points: 10697
Défis: 174
Message
Citer : Posté le 20/09/2018 21:41 | #
Je pose ça là comme ça, mais les algos génétiques, avec une bonne dose de matière grise, une tasse de café, et un soupçon de chance, ça marche pas si mal que ça
----------------------------------
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
Critor
En ligne
Administrateur
Points: 985
Défis: 0
Message
Citer : Posté le 20/09/2018 22:35 | #
Tu peux tenter; on peut très bien afficher ton score sans le classer. C'est prévu et géré automatiquement cette année, et c'est déjà le cas pour le participant n°0 qui verrouille l'exemple donné dans chaque annonce :
https://tiplanet.org/triconcours.php

Et d'ailleurs aucune raison de se limiter aux admins; ce serait amusant que les constructeurs tentent eux aussi. Je serais bien curieux de voir dans quel ordre ils se classeraient.
Hackcell
En ligne
Membre
Points: 900
Défis: 6
Message
Citer : Posté le 21/09/2018 07:55 | #
Ça a tourné toute la nuit, et 221 point, seul problème, si mon algorithme de recherche de maximum est 'assez' efficace, une fois arrivé à un max, je relance le tout avec un point aléatoire, cependant, quand ledit point vaut -500 et quelques, de 1 c'est long, de deux, de tout les points aléatoire tester, aucun ne vas au dessus de 206... Faut que je trouve un moyen de commencer à un point intéressant... Ca va pas être simple..
----------------------------------
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
Dark storm
Hors ligne
Membre d'honneur
Points: 10697
Défis: 174
Message
Citer : Posté le 21/09/2018 08:12 | #
Presque 223 (222,928) points pour ma part. Je vais voir si je peux changer de méthode (là c'est pas du tout pratique ni optimisé…)
----------------------------------
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
Hackcell
En ligne
Membre
Points: 900
Défis: 6
Message
Citer : Posté le 21/09/2018 13:57 | #
J'arrive pas à obtenir plus de 207 >_<
Mais bon, j'ai une petite modif à faire, qui pourrait faire des miracles, sinon je tenterai une recherche de maximum différente

Ajouté le 21/09/2018 à 14:00 :
J'ai démasquer le concurrents mystère
----------------------------------
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
Dark storm
Hors ligne
Membre d'honneur
Points: 10697
Défis: 174
Message
Citer : Posté le 21/09/2018 14:01 | #
Qui ça ? Perso je suis le n°11
----------------------------------
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
Hackcell
En ligne
Membre
Points: 900
Défis: 6
Message
Citer : Posté le 21/09/2018 21:01 | #
Bon, le miracle attendu n'a pas eu lieu (j'ai gagné environ 0.2 point).

J'avais pour intention de bricoler un autre algorithme de recherche de maximum basé sur une sorte de gradient à 30 dimensions, mais je me suis arrêtée 5 minutes pour regarder la suggestion de DS, un algorithme génétique, résultat, j'en ai codé un en une bonne heure, la page Wikipédia qui explique comment réaliser un telle algorithme est plutôt bien faite, donc au final j'ai pas eu tant besoin de réfléchir, j'ai pas eu besoin de café, en revanche, j'aurais sans doute besoins de chance

Donc merci DS pour ta suggestion.

Pour être plus précis, voici les paramétrés de mon algo:
— Population : 100 individus
— Génome : 30 chiffre de 0 à 1
— Système de score : Celui de base pour le concours
— Sélection : Trie des individus par score en commençant par le meilleur, choix des accouplements via un (np.random.random()*10)**2 (pas optimal, je pourrais gérer ça de manière plus souple, mais ça ira pour l'instant). Je réalise 49 accouplements, puis j'ajoute le meilleur de la génération précédente s'il ne s'est pas reproduit et complète avec des individus aléatoires.
— Empattement : 70%
— Mutation : 1% (Avec du recul, je devrai l'augmenter un poil)

Et puis c'est tout, pour l'instant ça grimpe gentiment et j'en suis à 210,7 points

Ajouté le 21/09/2018 à 22:58 :
L'algorithme commence à sortir des maximum, sauf qu'il a un peu de mal a s'extraire de ces maximum locaux, il est temps de tourner les boutons pour voir ce que ça fait
----------------------------------
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
Nemhardy
Hors ligne
Grand maître des Traits d'Esprit
Points: 1232
Défis: 54
Message
Citer : Posté le 21/09/2018 23:10 | #
Pour éviter de rester coincé dans des minima locaux, tu peux regarder des approches de type «recuit simulé», je n'ai jamais été très convaincu par les résultats (mais n'ai pas approfondi énormément la question ceci-dit), mais le principe avec l'analogie physique à le mérite d'être rigolo je trouve…
----------------------------------
N'attendez pas qu'il n'y ait plus de miel : スススススススススススススススススススススススススス養蜂家スススススススススススススススススススススススススススススススススススス蜂家

Pages: 1, 2 | Suivante

Index du Forum > Discussions > Triconcours et l'épreuve de force

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2018 | Il y a 26 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire indépendant, géré bénévolement et n'est donc pas affilié à Casio | Toute reproduction de Planète Casio, même partielle, est interdite
Les fichiers, programmes et autres publications présents sur Planète Casio restent la propriété de leurs auteurs respectifs et peuvent être soumis à des licences ou des copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd