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

→ **MyCalcs** profile · by **critor** » 13 Nov 2019, 13:12

Super @Pavel, merci d'avoir anticipé la demande d'explication !

→ **MyCalcs** profile · by **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°.

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 ...

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.

→ **MyCalcs** profile · by **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.

A vrai dire je ne comprends pas pourquoi il existe aussi la version python alors que c'est le défi basic.

→ **MyCalcs** profile · by **cent20** » 13 Nov 2019, 14:27

edgar13 wrote: Et la avec un simple brute force j'ai fait 19013.
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.

→ **MyCalcs** profile · by **edgar13** » 13 Nov 2019, 14:48

cent20 wrote:
edgar13 wrote: Et la avec un simple brute force j'ai fait 19013.
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.

→ **MyCalcs** profile · by **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 ?

→ **MyCalcs** profile · by **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.

→ **MyCalcs** profile · by **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.

→ **MyCalcs** profile · by **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

→ **MyCalcs** profile · by **Azerpogba** » 14 Nov 2019, 17:28

edgar13 wrote:
cent20 wrote:
edgar13 wrote: Et la avec un simple brute force j'ai fait 19013.
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.

On peux avoir le code de la force brute stp