Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Discussions


Index du Forum » Discussions » Triconcours et l'épreuve de force
Hackcell Hors ligne Maître du Puzzle Points: 1524 Défis: 11 Message

Triconcours et l'épreuve de force

Posté le 20/09/2018 10:16

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


1, 2 Suivante
Critor Hors ligne Administrateur Points: 2571 Défis: 18 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 Hors ligne Maître du Puzzle Points: 1524 Défis: 11 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
Kikoodx Hors ligne Ancien labélisateur Points: 3011 Défis: 11 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.
ouais ouais
Drak Hors ligne Rédacteur Points: 1925 Défis: 40 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 Ancien labélisateur Points: 3011 Défis: 11 Message

Citer : Posté le 20/09/2018 13:53 | #


Réfléchir c'est dépassé
ouais ouais

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 !


Pavel Hors ligne Membre Points: 30 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: 3524 Défis: 265 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 Ancien labélisateur Points: 3011 Défis: 11 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
ouais ouais
Lephenixnoir En ligne Administrateur Points: 24146 Défis: 170 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...)
Mon graphe (24 Mars): (gint#27 ; (Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; ...) || (shoutbox v5 ; v5)
Hackcell Hors ligne Maître du Puzzle Points: 1524 Défis: 11 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
Critor Hors ligne Administrateur Points: 2571 Défis: 18 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 En ligne Labélisateur Points: 11631 Défis: 176 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
Critor Hors ligne Administrateur Points: 2571 Défis: 18 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 Hors ligne Maître du Puzzle Points: 1524 Défis: 11 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..
Dark storm En ligne Labélisateur Points: 11631 Défis: 176 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
Hackcell Hors ligne Maître du Puzzle Points: 1524 Défis: 11 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
Dark storm En ligne Labélisateur Points: 11631 Défis: 176 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
Hackcell Hors ligne Maître du Puzzle Points: 1524 Défis: 11 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

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…
1, 2 Suivante

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 102 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd