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

[edgar13]

L'annonce est pour aujourd'hui?

[critor]

Peut-être. De mon côté elle est presque terminée (hors explications à venir et le pavé de cent20 et son disciple), mais il faut voir aussi du côté PC vu le que le bbcode n'est pas compatible.

[Extra44]

Voila pour ma part mon explication de ma démarche.
NB : L'explication sera malheureusement générale, car mon PC portable qui servait pour les essais a planté (carte mère), et je n'ai plus accès à mes fichiers tns intermédiaires (je n'ai pas encore pu réinstaller le logiciel TI Nspire CAS Software).

Bon ma méthode pour avoir le score max est composé de plusieurs points :
* quelques essais manuels pour voir comment àa marche
* décodage du code (compressé ) et voir à quoi correspondent les variables sur la version ti nspire, donc en Langage LUA
* afficher des résultats pour arriver à décoder le code (affichage consultable dans la console de l'éditeur LUA du logiciel Ti Nspire Software)
* Modifier le code pour n'avoir au final qu'un affichage du score dans la console (plus d'affichage intermédiaire)
* Faire une version LUA sans affichage graphique et qui ne ressort que le résultat final en fonction d'une entrée sous forme de liste
* On peut passer maintenant à faire des algo pour trouver un bon score...
* J'ai essayé le score aléatoire ... mais ce n'est pas fameux
* J'ai remarqué qu'il faut au moins 3 colonies d'une population pour qu'elle puisse croitre ...Donc un minimum de 2x3 = liste de 6 éléments minimum
* J'ai remarqué que si l'ajout d'une colonie n'est pas optimal, il peut réduire fortement le score !
* Ensuite, pour accélérer les recherches, j'ai converti le code LUA en C++ et j'ai compilé des versions successives en C++, pour plus de rapidité. J'ai ajouté parfois ...
- une partie d'algo de recherche aléatoire (entre 6 et 20..22..40 colonies)
- une partie d'algo génétique, mais apparemment je n'ai pas trouvé /obtenu le bon démarrage.
- une partie d'algo d'optimisation de bon résultats,
- Tout cela me permettait d'arriver rapidement à chaque fois aux 17000/18000 / 18800 points.
- Sur un bon résultat, je l'ai modifié à la main, et réussit à obtenir mon score final de 19743 pts
- J'ai fait tourner ma machine pendant 2/3/4 jours avant qu'elle ne plante, (le mercredi de la dernière semaine du concours)
-Puis en changeant de machine (je passais d'un i5 à un i3 ;-( ), j'ai essayé d'autres algos, d'autres paramètres d'algo génétique sans obtenir de meilleur résultats ;-(

Bravo encore aux organisateurs pour ce joli concours, et aux participants !

[critor]

Merci à toi !

Bon ben on va annoncer...

[critor]

Voilà c'est fait, merci à vous tous :
viewtopic.php?f=49&t=23237&p=249024#p249024

On rajoutera les explications manquantes lorsqu'elles arriveront, et si besoin on le rappellera lors du choix de lot.

[Afyu]

Voici comment j'ai procédé pour la résolution du défi en langage historique :

J'ai effectué mes premiers essais sur la ressource NumWorks proposée pour le concours, avec des do(1,c,l) et des do(-1,c,l) qui permettent de placer des civilisations rouges ou bleues en indiquant la position en ligne et en colonne (vivement l'implémentation du getkey() pour simplifier tout ça !).

Après quelques (nombreux) essais, j'ai découvert que le score augmentait bien plus vite lorsqu'on "oubliait" de placer une colonie et qu'on laissait passer une année. J'ai donc essayé de réduire fortement le nombre de colonies à placer et un nombre de colonies autour de 10 semblait être bien.

J'ai également découvert que le score n'augmente pas tant qu'il n'y a qu'une civilisation (donc qu'une seule couleur) de placée. De plus, il faut au minimum 3 colonies d'une même civilisation pour que cette dernière se développe. Donc il faut au minimum 6 colonies (3 pour chaque civilisation) pour que les deux civilisations se développent. Dernier point : pour qu'une civilisation se développe, il faut que les 3 colonies placées soient les voisines d'une même cellule vide pour y faire apparaître une colonie (une ressemblance avec le Jeu de la vie de John Conway ? ).

Partant de ce constat et trouvant que taper des do(+-1,c,l) est assez fastidieux, j'ai commencé à automatiser le placement de mes colonies, en utilisant la programmation en Python. J'ai repris le programme de la ressource NumWorks et je l'ai un peu modifié, mais hors ressource NumWorks, pour gagner en confort (de modification, de vitesse et de capacité de mémoire de travail).

À la fin du programme, j'ai ajouté quelques lignes pour initialiser une liste de colonies à placer, puis pour modifier aléatoirement des éléments de cette liste et pour déterminer et afficher le score obtenu avec cette liste.

Explications Code

On initialise la liste de colonies à placer à (0,0) pour chacune des 42 années (donc 42 colonies). Ensuite, on répète 50 000 fois l'essai suivant : on choisit un nombre entier entre 0 et 9 pour modifier une des 10 premières colonies à placer, puis on modifie le couple de coordonnées de cette colonie à placer, en essayant de placer une colonie Muenne, puis une colonie Atlante.

Code: Select all

from random import randint
liste0=[(0,0)]*42
liste=liste0[:]
st(liste)
for k in range(50000):
    a=randint(0,9)
    liste[a]=(-randint(1,9),-randint(1,9))
    st(liste)
    liste[a]=(randint(1,9),randint(1,9))
    st(liste)

Ensuite, j'ai modifié mon programme pour n'afficher le score obtenu que s'il est meilleur que le meilleur score déjà obtenu. Il faut donc stocker le meilleur score obtenu et comparer chaque nouveau score avec ce meilleur score. On initialise donc une liste scores qui stocke les meilleurs scores obtenus et une liste gagnant qui stocke les listes correspondantes. On stocke la valeur -1 dans scores pour s'assurer que le premier test effectué (sur une liste de 42 couples à (0,0)) stocke bien un score à 0, associé à une liste de couples à (0,0) dans gagnant.

Code: Select all

scores=[-1]
gagnant=[]

Explications Code

Dans le programme, j'ai remplacé la ligne qui affiche "Bon score ? Envoie la liste 'atmu' à ..." par mon test de comparaison et un éventuel stockage du nouvau score obtenu. On vérifie si on a atteint la 42ème année et si le nouveau score obtenu est meilleur que l'actuel meilleur score. Si c'est le cas, on ajoute la nouvelle meilleure liste à gagnant et le nouveau meilleur score à scores et on affiche cette nouvelle meilleure liste, puis ce nouveau meilleur score, l'année (pour vérification) et enfin la longueur de la liste (pour vérification). Le # affiché en début de sortie me permet de faire un copier-coller de cette nouvelle meilleure liste pour remplacer ma liste0, tout en gardant une trace du score associé et sans avoir à commenter ce score pour ne pas avoir d'erreur à l'exécution.

Code: Select all

        if j==42 and s>scores[-1]:
            gagnant.append(liste[:])
            print(liste)
            scores.append(s)
            print("#",s,j,len(liste))

Explications Code

Le stockage de la meilleure liste n'est pas indispensable, un simple affichage suffit. Mais je la stocke pour la reprendre après un certain nombre d'essais infructueux. Je ne sais pas si c'est la meilleure stratégie, mais elle m'a semblée plutôt efficace.
J'initialise à 0 une variable nb_chgt qui stocke le nombre de changements effectués, au même moment que je crée ma liste0. Ensuite, j'ajoute à la fin de mon programme quelques lignes qui permettent d'augmenter le compteur du nombre de changements effectués, puis de récupérer la dernière meilleure liste stockée après un certain nombre de changements effectués.

Code: Select all

   nb_chgt+=1
    if nb_chgt=20:
    nb_chgt=0
    liste=gagnant[-1]

J'aurais sûrement pu éviter de stocker dans la liste gagnant TOUS les meilleurs scores obtenus et ne garder que le dernier. Pour ça, il faut déclarer la variable gagnant comme étant globale et non pas locale, je crois, mais je ne maîtrise pas cette subtilité et je n'ai pas cherché comment faire.

J'ai ensuite laissé tourner ce programme durant de nombreuses heures/jours/semaines, en espérant améliorer mon score jusqu'à l'infini et au-dela !
J'ai remarqué qu'une liste qui comporte des couples de (0,0) entre des colonies assure souvent un meilleur score en les supprimant et en rapprochant du début de la liste les dernières colonies placées.
Par exemple, la liste [(5, 5), (5, 4), (7, 4), (-2, -6), (-2, -5), (-2, -4), (-6, -1), (-2, -1), (-3, -3), (0, 0), (-8, -9)] donne un score de 20300 tandis que la liste [(5, 5), (5, 4), (7, 4), (-2, -6), (-2, -5), (-2, -4), (-6, -1), (-2, -1), (-3, -3), (-8, -9)] donne un score de 20453, simplement en avançant la dernière colonie à la place du (0,0).

Parmi les autres essais que j'ai effectués :
Je vais appeler seed une liste assez courte de civilisations à placer, suivies de couples tous à (0,0) jusqu'à atteindre 42 années.
J'ai essayé de trouver le meilleur seed de 6 de long, puis de 7 de long, jusqu'à 10 de long. J'ai donc modifié le randint(0,9) pour que le choix des colonies à modifier ne soit plus parmi les 10 premières, mais seulement parmi les 6 premières randint(0,5), etc.

Explications Code

Uniquement pour la recherche du meilleur seed de 6 de long, j'ai effectué une recherche exhaustive (enfin, je crois ) en choisissant soit de placer 3 colonies Atlantes suivies de 3 colonies Muennes, soit d'alterner les colonies. C'est lors de ces essais que j'ai constaté qu'on obtenait souvent (toujours ?) un meilleur score en plaçant d'abord les colonies Atlantes. Pour éviter de multiplier les essais, j'ai raisonné en terme de symétrie et de distance. Par symétrie, on peut placer la première colonie (liste[0]) au milieu de la grille (donc en (5,5)) et placer la 2ème colonie (liste[1]) de la même civilisation dans 1/8 de disque et à une distance de maximum 2 de la colonie placée au centre (ce qui laisse donc seulement 5 cellules à tester : (5,4);(5,3);(6;4);(6;3);(7;3) tous les autres cas pouvant être obtenus par symétrie de ces 5). De même, la 3ème colonie (liste[2]) de la même civilisation est à placer à une distance de maximum 2 de chacune des deux premières colonies placées (pour assurer l'apparition d'une 4ème colonie, etc), ce qui limite beaucoup le nombre de positions possibles.
Pour les colonies de l'autre civilisation, je les ai placées en parcourant toute la grille et en respectant une distance de maximum 2 entre les colonies placées avec

Code: Select all

for k in range(c-2,c+2+1):
    cc=(k+9-1)%9+1

la position cc de la nouvelle colonie à placer varie entre c-2 et c+2 avec c la position de la précédente colonie placée de la même civilisation et la position cc de la nouvelle colonie à placer est modifiée si elle est inférieure à 1 ou supérieure à 9 pour être ramenée dans la grille, en considérant que cette dernière est un tore (donc 0 devient 9 et -1 devient 8 et 10 devient 1 et 11 devient 2). Ma précédente approche pour cette distance inférieure à 2 était d'utiliser for cc in range(max(1,c-2),min(c+2,9)+1): qui oublie quelques cas particuliers lorsqu'une colonie est proche d'un bord de la grille, donc à oublier.

Cette recherche exhaustive ressemble donc à :

Code: Select all

liste[0]=(5,5)
liste[1]=(5,4)

for a in range(5,7+1):
  for b in range(3,6+1):
     
    for c in range(1,9+1):
      for d in range(1,9+1):
        print(a,b,c,d)
        for k in range(c-2,c+2+1):
          cc=(k+9-1)%9+1
          for l in range(d-2,d+2+1):
            dd=(l+9-1)%9+1
            for kk in range(c-2,c+2+1):
              ccc=(kk+9-1)%9+1
              for ll in range(d-2,d+2+1):
                ddd=(ll+9-1)%9+1
                liste[2]=(-a,-b)
                liste[3]=(c,d)
                liste[4]=(cc,dd)
                liste[5]=(ccc,ddd)
                st(liste)

Et pour alterner les civilisations, il suffit de remplacer l'ordre 0,1,2,3,4,5 des indices x donnés dans liste[x] par 0,2,4,1,3,5.

J'ai obtenu un score de 19207 avec [(5, 5), (5, 4), (7, 4), (-2, -6), (-2, -5), (-2, -4)] qui est a compléter avec des (0,0) pour atteindre 42 années.

À partir de ce score, j'ai essayé de trouver le meilleur score en complétant avec une 7ème colonie, puis une 8ème, jusqu'à 11 ou 12. Essayer de placer plus de 12 colonies ne m'a jamais donné un meilleur score, alors j'ai fini par ne tester que jusqu'à 12.

Explications Code

J'ai également essayé, en partant d'une liste avec un bon score, de parcourir toutes les positions possibles pour deux couples qui se suivent (de rangs rang1 et rang2) de la liste.

Code: Select all

rang1=9
rang2=rang1+1
for a in range(0,10):
  print(a)
  for b in range(0,10):
    print(b)
    for aa in range(0,10):
      for bb in range(0,10):
        liste[rang1]=(a,b)
        liste[rang2]=(aa,bb)
        st(liste)
        liste[rang2]=(-aa,-bb)
        st(liste)
        liste[rang1]=(-a,-b)
        st(liste)
        liste[rang2]=(aa,bb)
        st(liste)

Explications Code

Autre essai effectué : en partant d'une liste donnant un score de 20266 (liste [(5, 5), (5, 4), (7, 4), (-2, -6), (-2, -5), (-2, -4), (5, 9), (-6,-1), (-6, -8), (-8, -6), (-3, -8), (0, 0), (-6, -5)] à compléter jusqu'à 42 années) j'ai essayé de décaler de 0 ou de 1, horizontalement ou verticalement, vers la gauche ou vers la droite, vers le haut ou vers le bas, chacune des colonies placées en espérant améliorer mon score... sans succès.

Code: Select all

for i1 in [-1,0,1]:
  for j1 in [-1,0,1]:
    for i2 in [-1,0,1]:
      for j2 in [-1,0,1]:
        for i3 in [-1,0,1]:
          for j3 in [-1,0,1]:
            for i4 in [-1,0,1]:
              for j4 in [-1,0,1]:
                print(i1,j1,i2,j2,i3,j3,i4,j4,100*((i1+1)/3+(j1+1)/9+(i2+1)/27+(j2+1)/81+(i3+1)/243+(j3+1)/729+(i4+1)/2187)+(j4+1)/6561)
                for i5 in [-1,0,1]:
                  for j5 in [-1,0,1]:
                    for i6 in [-1,0,1]:
                      for j6 in [1]:
                        for i7 in [-1,0,1]:
                          for j7 in [-1,0,1]:
                            liste=[(5, 5), (5, 4), (7, 4), (-2, -6), (-2, -5), (-2, -4), (5+i1, 9+j1),(-6+i2, -1+j2), (-6+i3, -8+j3), (-8+i4, -6+j4), (-3+i5, -8+j5), (0+i6, 0+i6), (-6+i7, -5+j7), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)]
                            st(liste)

La ligne avec les fractions permet simplement d'afficher le pourcentage d'avancement de la recherche.

J'ai obtenu de nombreux scores entre 20000 et 20453, sans jamais faire mieux. En voyant le détail de la liste proposée par Pavel, j'ai compris (mais un peu tard) qu'une liste qui donne un excellent score ne provient pas forcément d'un seed qui donne un très bon score. Ma recherche des meilleurs seed n'était donc pas la meilleure stratégie, mais quand on ne connait ni le recuit simulé, ni les algorithmes génétiques...

Je tiens à remercier toutes les personnes qui ont permis l'organisation de ce concours avec un aussi grand nombre de lots de qualité ! Merci !!

[critor]

Super, déjà formaté et tout, merci à toi !

[Amiga68000]

Je viens de recevoir mon lot (calculatrice casio 90+E + goodies), vraiment sympa, c'est une très belle calculatrice.
Je la trouve plus ergonomique que la NSpire.

En tous les cas un grand merci à Critor et à l 'équipe pour ces défis et une bonne et heureuse année à tous.

A l'année prochaine

[critor]

Super, merci pour ton retour.

Bon, c'est donc terminé pour les livraisons cette année.

[Zocipal]

Comme qui dirait : Mieux vaut tard que jamais
Est-ce que ce serait possible d'avoir la licence logicielle prévue dans mon lot (celui avec la CX-II T) ?
Merci beaucoup !
A bientôt
J'en profite pour te demander si tu sais ce qu'apporte la version 5.1.3 de la Ti ?