π
<-
Chat plein-écran
[^]

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

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

Unread postby critor » 13 Nov 2019, 13:12

Super @Pavel, merci d'avoir anticipé la demande d'explication ! :)
Image
User avatar
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Level up: 41.8%
 
Posts: 41470
Images: 14480
Joined: 25 Oct 2008, 00:00
Location: Montpellier
Gender: Male
Calculator(s):
MyCalcs profile
YouTube: critor3000
Twitter: critor2000
GitHub: critor

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

Unread postby cent20 » 13 Nov 2019, 14:20

Pavel wrote: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
User avatar
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Level up: 45.9%
 
Posts: 1009
Images: 64
Joined: 17 May 2012, 09:49
Location: Avignon
Gender: Male
Calculator(s):
MyCalcs profile
Twitter: nsi_xyz

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

Unread postby 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
User avatar
edgar13Modo
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Level up: 97.4%
 
Posts: 589
Images: 24
Joined: 04 Jan 2019, 20:31
Location: Sur TI-Planet voyons
Gender: Male
Calculator(s):
MyCalcs profile
Class: 1ere année de license maths-info
YouTube: Non
Twitter: Non
Facebook: Non
GitHub: Non

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

Unread postby cent20 » 13 Nov 2019, 14:27

edgar13 wrote: 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
User avatar
cent20VIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Level up: 45.9%
 
Posts: 1009
Images: 64
Joined: 17 May 2012, 09:49
Location: Avignon
Gender: Male
Calculator(s):
MyCalcs profile
Twitter: nsi_xyz

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

Unread postby edgar13 » 13 Nov 2019, 14:48

cent20 wrote:
edgar13 wrote: 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
User avatar
edgar13Modo
Niveau 12: CP (Calculatrice sur Pattes)
Niveau 12: CP (Calculatrice sur Pattes)
Level up: 97.4%
 
Posts: 589
Images: 24
Joined: 04 Jan 2019, 20:31
Location: Sur TI-Planet voyons
Gender: Male
Calculator(s):
MyCalcs profile
Class: 1ere année de license maths-info
YouTube: Non
Twitter: Non
Facebook: Non
GitHub: Non

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

Unread postby 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 ?
User avatar
NeOtuXMembre UPECS
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Level up: 56.3%
 
Posts: 192
Joined: 18 May 2012, 08:58
Gender: Male
Calculator(s):
MyCalcs profile

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

Unread postby Pavel » 13 Nov 2019, 17:32

NeOtuX wrote:@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.
User avatar
PavelPremium
Niveau 7: EP (Espèce Protégée: geek)
Niveau 7: EP (Espèce Protégée: geek)
Level up: 83.6%
 
Posts: 107
Joined: 19 Sep 2018, 10:50
Gender: Male
Calculator(s):
MyCalcs profile

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

Unread postby 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.
User avatar
ggauny@live.frPremium
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 43.4%
 
Posts: 283
Joined: 11 Mar 2015, 20:43
Gender: Not specified
Calculator(s):
MyCalcs profile

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

Unread postby 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
User avatar
LephePartenaire
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Level up: 67.7%
 
Posts: 386
Joined: 15 Jun 2018, 19:53
Gender: Male
Calculator(s):
MyCalcs profile

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

Unread postby Azerpogba » 14 Nov 2019, 17:28

edgar13 wrote:
cent20 wrote:
edgar13 wrote: 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
User avatar
AzerpogbaAmbianceur
Niveau 13: CU (Calculateur Universel)
Niveau 13: CU (Calculateur Universel)
Level up: 60%
 
Posts: 397
Images: 16
Joined: 04 Dec 2018, 19:40
Gender: Male
Calculator(s):
MyCalcs profile
Class: Etude sup

PreviousNext

Return to News Divers

Who is online

Users browsing this forum: No registered users and 70 guests

-
Search
-
Social TI-Planet
-
Featured topics
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
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
934 utilisateurs:
>915 invités
>14 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)