π
<-
Chat plein-écran
[^]

Concours de rentrée 2019 - défi langage historique

Re: Concours de rentrée 2019 - défi langage historique

Message non lude critor » 13 Nov 2019, 13:12

Super @Pavel, merci d'avoir anticipé la demande d'explication ! :)
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Concours de rentrée 2019 - défi langage historique

Message non lude cent20 » 13 Nov 2019, 14:20

Pavel a écrit:Voici quelques explications de ma méthode pour obtenir 21960 points.

J'ai commencé à jouer sur ma TI-83 Premium CE mais je n'étais pas assez patient pour attendre au moins 15 secondes après chaque tour et j'ai vite abandonné cette idée. Ensuite, j'ai légèrement modifié le script Numworks en remplaçant Kandinsky avec tkinter et j'ai continué à jouer sur un PC. La version modifiée du script se trouve dans ce dépôt.

Je me suis beaucoup amusé avec le mode interactif de ce jeu et en même temps j'ai remarqué les particularités suivantes de ce jeu:
  • il faut trois colonies de la même civilisation pour que les colonies commencent à se multiplier
  • le calcul du score n'est pas sensible au décalage horizontal ou vertical et toute solution peut être transformée en l'un des deux types de solutions suivantes:
    • la toute première colonie est en position (0, 0) et cette colonie est Muenne
    • la toute première colonie est en position (0, 0) et cette colonie est Atlante

Pour maximiser le score, j'ai utilisé l'algorithme de recuit simulé et j'ai réécrit le calcul du score en C.

J'ai passé beaucoup de temps à ajuster les paramètres de l'algorithme et j'ai aussi remarqué les points suivants:
  • les solutions où la première colonie est Atlante ont tendance à apporter plus de points
  • les meilleures solutions prennent moins de 12 tours pour réaliser le semis

Enfin, ma méthode a pris la forme suivante:
  • au premier tour, mettre une colonie Atlante à (0, 0)
  • à chaque itération de recuit simulé, faire les modifications suivantes:
    • changer aléatoirement l'un des 10 prochains tours en plaçant une colonie sur une position libre
    • vérifier les 10 prochains tours un par un en essayant tous les 163 mouvements possibles et garder une combinaison avec le score maximum
  • recommencer plusieurs fois avec différentes séquences de nombres pseudo-aléatoires

Pour être sûr d'avoir de bonnes séquences de nombres pseudo-aléatoires, j'ai pris l'algorithme WELL512.

Après plusieurs heures, j'ai eu la chance de trouver une séquence de nombres aléatoires permettant à mon code de converger vers 21960 en quelques minutes. Je suis très heureux que cette solution, en même temps, apporte beaucoup de points et crée un monde absolument stable dans lequel les deux civilisations coexisteront pendant des millions d'années.

Enfin, voici un lien vers mon code en C.


Pour la cuisson, moi je met au four thermostat entre 180° et 220°. :D

C'est en lisant ses explications et en ne comprenant pas tout que j'en arrive à me demander comment j'ai réussi à me classer 2ème ... Et pourtant j'en étais fier de mon 20972 obtenu à force de faire des tirages aléatoires + optimiser l'algo de tirage aléatoire + coloriages sur des grilles de sudoku ... :whistle:

Il va me falloir un peu plus de temps pour écrire le compte rendu. Faut que je comprenne tout ce que j'ai fait déjà, et comme je suis parti dans toutes les directions il me faut retrouver le chemin logique.
Image
Enseignant de mathématiques et d'informatique. Spécialité NSI : Des projets, des tutos, mais aussi de l'art
Calculatrice NumWorks : Des applications et des jeux, scripts, 📙 Découvrir la NumWorks
Avatar de l’utilisateur
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 45.9%
 
Messages: 1007
Images: 64
Inscription: 17 Mai 2012, 09:49
Localisation: Avignon
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: nsi_xyz

Re: Concours de rentrée 2019 - défi langage historique

Message non lude edgar13 » 13 Nov 2019, 14:23

Alors moi aussi j'ai commencé sur TI 83PCE mais c’était très long! :( Avec la ti 83 PCE j'ai compris que 6 colonies suffisaient pour devenir autonomes et qu'il fallait mieux ne rien faire pour gagner plus de points.
Finalement lundi soir à 20h Zocipal m'a un peu aidé il m'a fait remarqué que le programme existait aussi en python. Et la avec un simple brute force j'ai fait 19013. :whistle:
A vrai dire je ne comprends pas pourquoi il existe aussi la version python alors que c'est le défi basic. :?
Mes programmes sont ici: archives_cat.php?auteur=201254
Avatar de l’utilisateur
edgar13Modo
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 97.4%
 
Messages: 589
Images: 24
Inscription: 04 Jan 2019, 20:31
Localisation: Sur TI-Planet voyons
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: 1ere année de license maths-info
YouTube: Non
Twitter/X: Non
Facebook: Non
GitHub: Non

Re: Concours de rentrée 2019 - défi langage historique

Message non lude cent20 » 13 Nov 2019, 14:27

edgar13 a écrit: Et la avec un simple brute force j'ai fait 19013. :whistle:
A vrai dire je ne comprends pas pourquoi il existe aussi la version python alors que c'est le défi basic. :?


Si tu as obtenu 19013 ce n'est pas une force brute (qui donne le meilleur tirage) mais une force aléatoire.
Il existe une version python CAR c'est le langage historique de la numworks.
Image
Enseignant de mathématiques et d'informatique. Spécialité NSI : Des projets, des tutos, mais aussi de l'art
Calculatrice NumWorks : Des applications et des jeux, scripts, 📙 Découvrir la NumWorks
Avatar de l’utilisateur
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 45.9%
 
Messages: 1007
Images: 64
Inscription: 17 Mai 2012, 09:49
Localisation: Avignon
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: nsi_xyz

Re: Concours de rentrée 2019 - défi langage historique

Message non lude edgar13 » 13 Nov 2019, 14:48

cent20 a écrit:
edgar13 a écrit: Et la avec un simple brute force j'ai fait 19013. :whistle:
A vrai dire je ne comprends pas pourquoi il existe aussi la version python alors que c'est le défi basic. :?


Si tu as obtenu 19013 ce n'est pas une force brute (qui donne le meilleur tirage) mais une force aléatoire.
Il existe une version python CAR c'est le langage historique de la numworks.

Si c'était une force brute mais je ne l'ai fait tourner que 2h. :)
Après j'ai dormi. :D
Avatar de l’utilisateur
edgar13Modo
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Prochain niv.: 97.4%
 
Messages: 589
Images: 24
Inscription: 04 Jan 2019, 20:31
Localisation: Sur TI-Planet voyons
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: 1ere année de license maths-info
YouTube: Non
Twitter/X: Non
Facebook: Non
GitHub: Non

Re: Concours de rentrée 2019 - défi langage historique

Message non lude NeOtuX » 13 Nov 2019, 15:27

Félicitations à tous les participants et aux instigateurs de l'épreuve !

J'ai trouvé ce défi particulièrement intéressant pour les raisons suivantes :

- Contrairement au défi précédent, l'ordre des éléments a un sens ce qui complique les choses ;

- La lois de l'automate cellulaire ne sont pas explicitement lisibles dans le code ce qui pousse à l'expérimentation "on calc" ;

- L'automate n'est pas "bijectif", mais "surjectif" (Désolé si ce ne sont pas les bons termes, qu'on me corrige s'il y a mieux). Autrement dit, même si on trouve une configuration de la 42e année qui donne un bon score, on ne peut pas remonter le temps pour déterminer une séquence d'implantation des colonies (Pas à ma connaissance du moins).

Pour ce qui est de ma méthode, j'ai pressenti que l'algorithme génétique n'était pas terrible à l'état brut (voir la première raison ci-dessus). J'ai donc rapidement implémenté en Python un recuit simulé (Rien de sorcier sur la forme) mais j'ai vite compris que TOUT reposait sur le paramétrage et surtout sur la définition du "mouvement élémentaire", qu'il faut définir avec beaucoup de soin et de façon intelligente. Par manque de temps et d'investissement je n'avais ni l'un ni l'autre donc j'ai coupé court...

J'aurais vraiment aimé explorer ce problème, mais n'ai finalement fait que quelques essais directement sur nSpire (Très belle animation d'arrière plan au passage) en remarquant globalement les mêmes observations que celles postées précédemment sur ce topic.

J'ai hâte de lire toutes les méthodes employées et je n'exclus pas d'en expérimenter quelques-unes pour le plaisir !

@Pavel : au sujet de ton implémentation, est-ce que le choix du C a été motivé par le générateur de nombres pseudo-aléatoires ou par soucis de rapidité d'exécution ?
Avatar de l’utilisateur
NeOtuXMembre UPECS
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 53.9%
 
Messages: 192
Inscription: 18 Mai 2012, 08:58
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Concours de rentrée 2019 - défi langage historique

Message non lude Pavel » 13 Nov 2019, 17:32

NeOtuX a écrit:@Pavel : au sujet de ton implémentation, est-ce que le choix du C a été motivé par le générateur de nombres pseudo-aléatoires ou par soucis de rapidité d'exécution ?


J'ai choisi C pour pouvoir calculer le score le plus rapidement possible.
Avatar de l’utilisateur
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Prochain niv.: 83.6%
 
Messages: 107
Inscription: 19 Sep 2018, 10:50
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Concours de rentrée 2019 - défi langage historique

Message non lude ggauny@live.fr » 13 Nov 2019, 20:33

Bonsoir,
@Lephe et Cent20, merci pour vos messages sympathiques. Oui j'ai aimé ces défis même en sachant
que je ne pouvais pas gagner, mais : "l'important est de participer...."

Je suis content de voir que des gamins du Collège ou du Lycée soient aussi bons. Moi je ne connais pas les "recuits" et autres algorithmes mathématiques.
Avatar de l’utilisateur
ggauny@live.frPremium
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 43.4%
 
Messages: 283
Inscription: 11 Mar 2015, 20:43
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: Concours de rentrée 2019 - défi langage historique

Message non lude Lephe » 14 Nov 2019, 13:56

- L'automate n'est pas "bijectif", mais "surjectif" (Désolé si ce ne sont pas les bons termes, qu'on me corrige s'il y a mieux). Autrement dit, même si on trouve une configuration de la 42e année qui donne un bon score, on ne peut pas remonter le temps pour déterminer une séquence d'implantation des colonies (Pas à ma connaissance du moins).

Ça semble être le plus général avec ces automates type Jeu de la Vie. Pire encore, dans le Jeu de la Vie non seulement toutes les configurations ne sont pas atteignables, mais en plus il est impossible de déterminer de façon automatique si une configuration choisie l'est (le problème est indécidable). ;)

@Pavel : au sujet de ton implémentation, est-ce que le choix du C a été motivé par le générateur de nombres pseudo-aléatoires ou par soucis de rapidité d'exécution ?

J'en profite pour signaler que C n'a pas vraiment de générateur aléatoire sérieux dans sa bibliothèque standard, contrairement à C++. ^^

Je suis content de voir que des gamins du Collège ou du Lycée soient aussi bons. Moi je ne connais pas les "recuits" et autres algorithmes mathématiques.

Il faut admettre que la recherche sur ce sujet est récente ! Certaines techniques que j'apprends en informatique et qui sont ancrées dans toute la théorie datent des années 90 (je pense à des résultats de compilation en particulier). Donc ça n'est probablement pas enseigné depuis très longtemps... :)

Edit : Je ne suis plus au collège et au lycée depuis longtemps par contre :'D
Avatar de l’utilisateur
LephePartenaire
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Prochain niv.: 67.7%
 
Messages: 386
Inscription: 15 Juin 2018, 19:53
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Concours de rentrée 2019 - défi langage historique

Message non lude Azerpogba » 14 Nov 2019, 17:28

edgar13 a écrit:
cent20 a écrit:
edgar13 a écrit: Et la avec un simple brute force j'ai fait 19013. :whistle:
A vrai dire je ne comprends pas pourquoi il existe aussi la version python alors que c'est le défi basic. :?


Si tu as obtenu 19013 ce n'est pas une force brute (qui donne le meilleur tirage) mais une force aléatoire.
Il existe une version python CAR c'est le langage historique de la numworks.

Si c'était une force brute mais je ne l'ai fait tourner que 2h. :)
Après j'ai dormi. :D

On peux avoir le code de la force brute stp :)
Image
Avatar de l’utilisateur
AzerpogbaAmbianceur
Niveau 13: CU (Calculateur Universel)
Niveau 13: CU (Calculateur Universel)
Prochain niv.: 60%
 
Messages: 397
Images: 16
Inscription: 04 Déc 2018, 19:40
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: Etude sup

PrécédenteSuivante

Retourner vers News Divers

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 36 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
731 utilisateurs:
>710 invités
>16 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)