Re: Concours de rentrée 2019 - défi langage historique
Posté: 13 Nov 2019, 13:12
Super @Pavel, merci d'avoir anticipé la demande d'explication !
News, programmes, tutoriaux, forum sur les calculatrices TI !
https://tiplanet.org/forum/
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.
edgar13 a écrit: 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.
cent20 a écrit:edgar13 a écrit: 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.
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 ?
- 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).
@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 ?
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.
edgar13 a écrit:cent20 a écrit:edgar13 a écrit: 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.