concours de rentrée 2019 - Le défi historique en python


Accueil > Projets > concours de rentrée 2019 - Le défi historique en python

Par Fedyna K., Robert Vincent en novembre 2019

Après le concours de rentrée 2019 - Le défi python / Pokemon passionnant nous nous sommes attaqué au défi historique, proposé par les sites internet tiplanet.org et planet-casio.com et les équipes de bénévoles passionnés qui animent ces communautés.

Le contexte

Il existait autrefois au coeur du grand océan appelé Pacifique un empire, l’empire de Mu. Grâce à l’énergie du soleil qu’ils avaient réussi à maîtriser complètement les Lémuriens menaient une vie tranquille et prospère. A la même époque, une autre civilisation celle de l’Atlantide régnait au centre de l’autre océan, l’Atlantique. Les Atlantes eux aussi savaient contrôler la puissance du soleil et ils avaient construit un puissant empire.
Mais un jour, la guerre éclata entre la terre de Mu et l’Atlantide pour une raison si insignifiante que l’histoire elle-même l’a oubliée. La guerre dura longtemps, de nombreuses années, car les forces des deux puissances étaient égales. Jusqu’au jour où les hommes firent usage de l’arme solaire. C’est ainsi que ces deux grandes civilisations disparurent, englouties au fond des deux océans…

Tu n’as rien compris ? Normal, cela fait parti du challenge !
(Lire l’intégralité du défi : Concours de rentrée 2019 - défi langage historique)

Il était possible de participer avec un script en Casio-Basic, Ti-basic, ou en Python.
Nous avons bien évidement choisi le langage Python pour sa souplesse, et la capacité que nous avions à le faire tourner sur un PC sur divers IDE python.

Dans la suite de l’article, le "nous" fait référence au participant 16 et au participant 17, car nous avons réalisé les recherches en commun.

Premier tests

Tout commence par des premiers tests à la main, et en tout premier lieu nous avons commencé par neutraliser le traitement graphique du script, les affichages textes, pour chercher à l’aveugle par ce que sinon cela n’est pas assez difficile...

Script nettoyé (ZIP - 1.9 ko)
Script nettoyé

Tout commence avec des tirages aléatoires très aléatoires sans aucune réflexion, et ayant réussi à fabriquer une liste de 5 couples avec un score acceptable (on le pense alors !), on essaye de l’améliorer, et de tirer d’autres listes de 5 couples acceptables.

  1. import random
  2. def aleat5():
  3.     m = 42
  4.     l = [(-2,-2), (2,3), (-2,-4), (2,5), (-4,-3)] # la liste de départ
  5.     while len(l)<m:
  6.         l.append((0,0))
  7.     scoremax = st(l)
  8.     print("score liste : ", scoremax)
  9.     equipe = [1, -1]
  10.     l = []
  11.     tirage = 0    
  12.     while scoremax <100000:
  13.         tirage+=1
  14.         l = []
  15.         for i in range(5):        
  16.             random.shuffle(equipe)
  17.             l.append((equipe[0]*random.randint(1,9),equipe[0]*random.randint(1,9)))
  18.         while len(l)<m:
  19.             l.append((0,0))
  20.         scorerandom = st(l)    
  21.        
  22.         if scorerandom > scoremax:
  23.             print("Meilleur score", scorerandom)
  24.             print("Liste",l[0:5])
  25.             scoremax = scorerandom
  26.         if tirage%1000==0:
  27.             print("Tirages aléatoire : ",tirage)

Télécharger

Cette méthode est un échec, les scores générés ne dépassent pas 100 !
Nous pensions que 100 était en score acceptable car on l’a comparé naïvement au score maxi de 43.x obtenu sur le défi précédent.

Et si on en tirait 10 couples ?

Au lieu de tirer 5 couples, on décide d’en tirer 10. Pour rappel à ce stade nous sommes toujours aveugle, nous n’avons aucun rendu graphique à analyser pour affiner notre stratégie.

  1. import random
  2. def aleat10():
  3.     m = 42
  4.     scoremax = 100
  5.     print("score aleat5 : ", scoremax)
  6.     equipe = [1, -1]
  7.     tirage = 0    
  8.     while scoremax <100000:
  9.         tirage+=1
  10.         l = []
  11.         for i in range(10):        
  12.             random.shuffle(equipe)
  13.             l.append((equipe[0]*random.randint(1,9),equipe[0]*random.randint(1,9)))
  14.         while len(l)<m:
  15.             l.append((0,0))
  16.         scorerandom = st(l)        
  17.         if scorerandom > scoremax:
  18.             print("Meilleur score", scorerandom)
  19.             print("Liste",l[0:10])
  20.             scoremax = scorerandom
  21.         if tirage%1000==0:
  22.             print("Tirages aléatoire : ",tirage)

Télécharger

Assez rapidement, on obtient des score aux alentours de 16000-17000

Meilleur score 16685.07457023799
Liste [(-8, -3), (-4, -6), (-9, -1), (-1, -1), (4, 7), (-5, -4), (5, 9), (6, 7), (-4, -3), (-2, -5)]
Meilleur score 17304.672747006774
Liste [(7, 6), (5, 7), (7, 5), (-4, -7), (-3, -5), (-5, -5), (-3, -9), (-6, -5), (-3, -5), (-9, -8)]

Comme au pays des aveugles les borgnes sont rois, on décide alors de continuer les tirages aléatoires de n couples et dans le même temps de développer notre propre couche graphique histoire d’y voir quelques choses et de laisser passer un peu de lumière ...

Tirages aléatoires de n couples

  1. def aleatn(annee):
  2.     m = 42
  3.     scoremax = 100
  4.     print("score kiki : ", scoremax)
  5.     tirage = 0    
  6.     while scoremax <100000:
  7.         tirage+=1
  8.         l = []
  9.         for i in range(annee):
  10.             l.append(((-1)**i*random.randint(1,9),(-1)**i*random.randint(1,9)))
  11.         while len(l)<m:
  12.             l.append((0,0))
  13.         scorerandom = st(l)
  14.         if scorerandom > 15000:
  15.             print("bon score", scorerandom)
  16.             print("Liste",l[0:annee])
  17.         if scorerandom > scoremax:
  18.             print("========== Meilleur score : ", scorerandom)
  19.             print("================== Liste = ",l[0:annee])
  20.             scoremax = scorerandom
  21.         if tirage%1000==0:
  22.             print("Tirages aléatoire : ",tirage)

Télécharger

Bien évidemment, on lance les fonctions aleatn(annee) avec des valeurs pour la variable annee comprise entre 1 et 42 mais tout ceci est très long, un unique script tourne sur un unique IDE Python.

La problématique du multi-thread

Nous n’arrivons pas à faire tourner nos scripts en multi thread sur Python en utilisant les outils adéquates, nous commençons donc par faire du multi thread manuel :

2 PCS = 2 scripts qui tournent 😄
3 IDE = 3 scripts qui tournent. 😅
2 PCS avec 3 IDE = 6 scripts 🤣

Et puis sur pycharm nous arrivons enfin à faire tourner 10 /12 scripts en //
(Oui enfin, nous avions une autant de fichiers que de threads, cela ressemblait vraiment à un classeur d’élève de 2nde)

Maîtrisant le "multi thread" cela fut le début de folles nuits des tirages aléatoires

« Il faut bien occuper le Ryzen 7 2700 et ses 16 threads ! »

La première nuit, les fonctions aleatn(annee) furent lancées avec tous les entiers possible entre 4 et 14.

« Je vais me coucher. J’ai lancé les 10 scripts en parallèle on verra demain matin si on a cassé le score de Pavel »

Et le lendemain matin les résultats furent dépouillées.

Des nouvelles de la couche graphique

En parallèle, nous nous sommes occupés de recréer l’interface graphique en l’améliorant légèrement pour pouvoir voir comment le programme fonctionnait et, accessoirement, ce que l’on obtenait avec nos tirages.

Nous avons choisit tKinter pour ce travail et fixé un cahier des charges :

  • Un espace pour voir la grille.
  • Un petit commentaire pour expliquer le fonctionnement de la GUI.
  • Une reconnaissance de l’entrée des touches pour entrer les do() plus vite.
  • Un espace pour entrer des commandes spéciales (st() par ex). La détection des touches doit être désactivée pour saisir
  • Un historique :
    • Une grille (plus visuelle).
    • Sous forme de texte.

Ainsi, il a fallu créer la fenêtre :

  1. interface = Tk()
  2. interface.resizable(False,False)
  3. interface.title('Concours AT//MU')
  4.  
  5. # Utilisable
  6. utilisable = Frame(interface,borderwidth=0)
  7. utilisable.pack(side=LEFT)
  8. canevas = Canvas(utilisable,width=500,height=400,bg="white")
  9. canevas.pack(side=TOP)
  10. saisie = StringVar()
  11. barreSaisie = Entry(utilisable,width=60,textvariable=saisie)
  12. barreSaisie.pack(side=RIGHT)
  13. barreSaisie.configure(state="readonly")
  14. label = Label(utilisable,text="'W' pour (ne plus) ecrire")
  15. label.pack(side=LEFT)
  16. labelScore = canevas.create_text(10,240,text="An : 0 // Score = 0",anchor=NW)
  17. canevas.create_text(10,270,text="Appuyez sur + ou - sur le clavier numerique pour choisir votre camp",anchor=NW)
  18. canevas.create_text(10,290,text="Puis, toujours sur le clavier numerique, selectionnez votre colonne puis votre ligne avec les",anchor=NW)
  19. canevas.create_text(10,305,text="touches 1 a 9.",anchor=NW)
  20. canevas.create_text(10,325,text="Attention, la case (1;1) est la case en haut a gauche !",anchor=NW)
  21. canevas.create_text(10,345,text="Pour passer une annee, appuyez sur le point du clavier numerique.",anchor=NW)
  22. canevas.create_text(10,365,text="Pour recommencer une partie, appuyez sur 'R'.",anchor=NW)
  23. canevas.create_text(10,385,text="Il est possible de rentrer des commandes speciales a tout moment en appuyant sur 'W'.",anchor=NW)
  24.  
  25. # Historique
  26. historique = Frame(interface,borderwidth=0)
  27. historique.pack(side=RIGHT)
  28. canevasHist = Canvas(historique,width=400,height=230,bg="white")
  29. canevasHist.pack(side=TOP)
  30. listeHist = ScrolledText(historique,width=50,height=11)
  31. listeHist.pack(side=BOTTOM)

Télécharger

Ceci étant fait, on crée une fonction récupérant les événements claviers :

  1. isWriting = False
  2. commande = ["","",""]
  3. index = 1
  4.  
  5. def event(touche):
  6.     global isWriting,index,commande
  7.     touche = touche.keysym
  8.     if touche == "w":
  9.         if isWriting:
  10.             barreSaisie.configure(state="readonly")
  11.             saisie.set("do("+commande[0]+","+commande[1]+","+commande[2]+")")
  12.         else:
  13.             barreSaisie.configure(state="normal")
  14.             saisie.set("")
  15.         isWriting = isWriting == False # paradoxe du menteur
  16.     if touche == "r":
  17.         init()
  18.         dr(2,0,0)
  19.     if touche == "plus" and not isWriting:
  20.         commande[0]="1"
  21.     if touche == "minus" and not isWriting:
  22.         commande[0]="-1"
  23.     if touche == "BackSpace" and not isWriting:
  24.         commande[index-1] = ""
  25.         if index > 1:
  26.             index -= 1
  27.     if touche == "1" and not isWriting and index<3:
  28.         commande[index] = "0"
  29.         index += 1
  30.     if touche == "2" and not isWriting and index<3:
  31.         commande[index] = "1"
  32.         index += 1
  33.     if touche == "3" and not isWriting and index<3:
  34.         commande[index] = "2"
  35.         index += 1
  36.     if touche == "4" and not isWriting and index<3:
  37.         commande[index] = "3"
  38.         index += 1
  39.     if touche == "5" and not isWriting and index<3:
  40.         commande[index] = "4"
  41.         index += 1
  42.     if touche == "6" and not isWriting and index<3:
  43.         commande[index] = "5"
  44.         index += 1
  45.     if touche == "7" and not isWriting and index<3:
  46.         commande[index] = "6"
  47.         index += 1
  48.     if touche == "8" and not isWriting and index<3:
  49.         commande[index] = "7"
  50.         index += 1
  51.     if touche == "9" and not isWriting and index<3:
  52.         commande[index] = "8"
  53.         index += 1
  54.     if touche == "Return":
  55.         try:
  56.             eval(saisie.get())
  57.             saisie.set("")
  58.             index=1
  59.             commande=["","",""]
  60.         except:
  61.             print("aie")
  62.     if touche == "period" and not isWriting:
  63.         do(0)
  64.     if not isWriting:
  65.         saisie.set("do("+commande[0]+","+commande[1]+","+commande[2]+")")

Télécharger

Attention : On prend bien soin de lier cette fonction à la fenêtre :
interface.bind("<Key>",event)
Cette ligne envoie à la fonction event() la valeur quand une touche est pressée.

Mais, un problème de taille était toujours présent, modifier la couche graphique pré-codée avec kandinsky :

Voici donc ce qu’on a pu faire :

  1. def dr(camp,xHist,yHist):
  2.     global s,j,w,labelScore
  3.     sw=320
  4.     d=min(sw//n,221//n)
  5.     b=sw-1-n*d
  6.    
  7.     for i in range(0,n*d+1,d):
  8.         canevas.create_rectangle(b,10+i,b+n*d,i+11,fill=hexColor(0,0,0),outline="")
  9.         canevas.create_rectangle(b+i,10,b+i+1,n*d+10,fill=hexColor(0,0,0),outline="")
  10.         canevasHist.create_rectangle(b,10+i,b+n*d,i+11,fill=hexColor(0,0,0),outline="")
  11.         canevasHist.create_rectangle(b+i,10,b+i+1,n*d+10,fill=hexColor(0,0,0),outline="")
  12.        
  13.     if camp != 0 and camp != 2:
  14.         t=255-(255*abs(ma[yHist][xHist])//w)
  15.         canevasHist.create_rectangle(b+xHist*d+1,yHist*d+11,b+xHist*d+d,yHist*d+10+d,fill=camp<0 and hexColor(t,t,255) or camp>0 and hexColor(255,t,t),outline="")
  16.         listeHist.insert(END,str((xHist*camp+camp,yHist*camp+camp))+"\n")
  17.     elif camp == 0:
  18.         listeHist.insert(END,"(0, 0)\n")
  19.     else:
  20.         listeHist.delete(1.0,END)
  21.        
  22.     for y in range(0,n):
  23.         for x in range(0,n):
  24.             t=255-(255*abs(ma[y][x])//w)
  25.             canevas.create_rectangle(b+x*d+1,y*d+11,b+x*d+d,y*d+10+d,fill=ma[y][x]<0 and hexColor(t,t,255) or ma[y][x]>0 and hexColor(255,t,t) or hexColor(255,255,255),outline="")
  26.             if camp == 2:
  27.                 canevasHist.create_rectangle(b+x*d+1,y*d+11,b+x*d+d,y*d+10+d,fill=ma[y][x]<0 and hexColor(t,t,255) or ma[y][x]>0 and hexColor(255,t,t) or hexColor(255,255,255),outline="")
  28.            
  29.            
  30.     canevas.itemconfig(labelScore,text="An: "+str(j)+" // Score: "+str(s)[:10])

Télécharger

On remarque que les couleurs sont générées au moyen d’un code RGB, or tKinter n’accepte que des chaines de caractères, donc (cours de NSI ;) ), on convertit les valeurs en hexadécimal et on crée un code de la forme "#rrggbb"

  1. def hexColor(r,g,b):
  2.     r = "0" + hex(r)[2:]
  3.     g = "0" + hex(g)[2:]
  4.     b = "0" + hex(b)[2:]
  5.     return "#"+r[len(r)-2:len(r)]+g[len(g)-2:len(g)]+b[len(b)-2:len(b)]

Télécharger

On obtient ainsi le résultat suivant :

Bon au cours du développement de cette couche graphique, on a constaté que Pavel avait codé la sienne de son coté et qu’il l’avait rendue publique pendant le concours. Heureusement bien peu ont compris l’importance de ces simulations graphiques.

Analyse des résultats

A partir de là, nous avons commencé à faire des tirages aléatoires sans IA.

Les 30 000 000 de tirages réalisés pendant la nuit furent analysés en détail, et des grilles de sudoku furent coloriées pour identifier les positions initiales de 6 couples ayant de gros scores.

Nous avons eut confirmation que cela ressemblait au jeu de la vie et avons compris quelques règles :

- Il faut semer 3 cases différentes mais proches d’une même colonie pour avoir un développement exponentiel.
- Quand les colonies Atlantes et Muennes se rencontrent, elles se détruisent. Une trop forte densité d’une colonie amène aussi à son auto destruction par le centre.
- Il existe des états stables mais nous ne les avons pas trouvé optimaux en terme de score à la fin de l’an 42.
- Le score monte plus vite si les deux colonies se développent, donc aleatn(5) ne produira jamais un gros score, aleatn(6) lui peut faire un gros score.

Pour affiner les résultats, nous avons décidé de sauvegarder les bonnes listes et non plus uniquement les meilleurs listes.

Nuits de folie : 6 à 12 scripts qui tournent en parallèle

  1. listealeat = []
  2. tirage = [0 for k in range(42)]
  3.  
  4. best_list =  []
  5. best_scor = 0
  6.  
  7. good_list = []
  8. good_scor = []
  9. good_indice = 0
  10.  
  11. def sauvegarde(sauveliste,score,tirage,annee):
  12.     global best_indice, best_scor, good_list, good_scor, good_indice, best_list
  13.     if score > 15500: #Le chiffre de 15500 a régulièrement été augmenté
  14.         # On sauvegarde les listes de couples donnant 15500 min
  15.         good_list.append(sauveliste)
  16.         good_scor.append(score)
  17.         good_indice+=1
  18.     if score > best_scor:
  19.          # On sauvegarde la meilleur liste trouvée
  20.         best_list = sauveliste[0:annee]
  21.         best_scor = score
  22.         print("\n======= Meilleur score ======== tirage n° ",tirage, "sur",annee, "années ======== ")
  23.         print("Score : ",score)
  24.         print("liste = ",best_list[0:annee])
  25.  
  26. def calcule_score(liste,tirage,annee):
  27.     m=42
  28.     sauveliste = liste
  29.     # print(sauveliste)
  30.     # input()
  31.     while len(liste)<m:
  32.         liste.append((0,0))
  33.     score = st(liste)
  34.     sauvegarde(sauveliste,score,tirage,annee)
  35.  
  36. def forcealeat(annee,nbtirage):
  37.     global best_scor, good_indice
  38.     for j in range(nbtirage):
  39.         listealeat = []
  40.         tirage[annee]+=1
  41.         for i in range(annee):
  42.                 listealeat.append(((-1)**i*random.randint(1,9),(-1)**i*random.randint(1,9)))
  43.                 # le choix de faire un coup négatif un coup positif peut se discuter...
  44.                 random.shuffle(listealeat)
  45.         calcule_score(listealeat,tirage[annee],annee)  
  46.     print(30*"##")
  47.     print("fini,",nbtirage, "tirages de",annee, "couples aléatoires")
  48.     print("bonne liste : ",good_indice)
  49.     print("MeilleurScore : ",best_scor)
  50.     print("liste = ",best_list)
  51.  
  52. def forcealeatgeometrie6(annee,nbtirage):
  53.     global best_scor, good_indice
  54.     for j in range(nbtirage):
  55.         listealeat = []
  56.         tirage[annee]+=1
  57.         col1 = random.randint(1,6)
  58.         lig1 = random.randint(1,9)
  59.         col2 = random.randint(1,9)
  60.         lig2 = random.randint(1,6)
  61.         listealeat.append((col1,lig1))
  62.         listealeat.append((col1+1,lig1))
  63.         listealeat.append((col1+2,lig1))
  64.         listealeat.append((-1*col2,-1*lig2))
  65.         listealeat.append((-1*col2,-1*(lig2+1)))
  66.         listealeat.append((-1*col2,-1*(lig2+2)))
  67.         random.shuffle(listealeat)
  68.         calcule_score(listealeat,tirage[annee],annee)  
  69.     print(30*"##")
  70.     print("fini,",nbtirage, "tirages de",annee, "couples aléatoires")
  71.     print("bonne liste : ",good_indice)
  72.     print("MeilleurScore : ",best_scor)
  73.     print("liste = ",best_list)

Télécharger

Quelques nuits de folies plus tard ...

Jeux avec le moteur graphique

A l’aide du moteur graphique, on a pu analyser les figures donnant des états stables. C’est à dire qu’à partir d’une configuration donnée, on obtient une configuration qui n’évolue plus dans le temps.

Ainsi, on obtient les résultats suivants :

1er état stable :

Avant :

Après :

2ème état stable :

Avant :

Après :

Un 3ème, très joli :

Avec ces états, on observe un autre comportement du programme, les bords interagissent entre eux.

Tirages aléatoires avec IA

Nos résultats étaient satisfaisants et ils nous permettait d’obtenir un score supérieur à 18 000, mais beaucoup de tirage étaient gâchés car l’algorithme manquait de discernement.

Nous avons alors repris les coloriages et amélioré notre script de tirage. L’heure de l’IA avait sonné. Oui on utilise facilement le mot IA alors que ... on a juste réfléchit et que les scripts sont eux toujours aussi stupides.

  1. def forcealeatIA(annee, nbtirage):
  2.     global best_scor, good_indice
  3.     for j in range(nbtirage):
  4.         listealeat = []
  5.         tirage[annee] += 1
  6.         na = random.randint(1, 9)
  7.         ma = random.randint(1, 9)
  8.         nlist = [max(na - 1, 1), na, min(na + 1, 9)]
  9.         mlist = [max(ma - 1, 1), ma, min(ma + 1, 9)]
  10.         pa = random.randint(1, 9)
  11.         qa = random.randint(1, 9)
  12.         plist = [max(pa - 1, 1), pa, min(pa + 1, 9)]
  13.         qlist = [max(qa - 1, 1), qa, min(qa + 1, 9)]
  14.         for i in range(annee // 2):
  15.             listealeat.append((random.choice(nlist), random.choice(mlist)))
  16.             listealeat.append(((-1) * random.choice(plist), (-1) * random.choice(qlist)))
  17.         random.shuffle(listealeat)
  18.         goodliste(listealeat, tirage[annee], annee)
  19.     print(30 * "##")
  20.     print("fini,", nbtirage, "tirages de", annee, "couples aléatoires")
  21.     print("bonne liste : ", good_indice)
  22.     print("MeilleurScore : ", best_scor)
  23.     print("liste = ", best_list)

Télécharger

Ce script a réalisé à lui tout seul plus de 20 000 000 de tirage, déjà parce qu’il était beau, et ensuite parce que nous voulions obtenir une liste significative de tirage ayant un score > 18 000.

forcealeatIA(6,7000000) nous au ainsi donné 154 tirages certifiés >18 000

Ces tirages ont alors été mélangés aléatoirement, histoire de s’assurer vérifier que un autre ordre ne nous donnerait pas un meilleur score

  1. def improve_liste():
  2.     global goodliste
  3.     listetraiteeok = 0
  4.     for listeatraiter in goodliste:
  5.         listetraiteeok += 1
  6.         annee = len(listeatraiter)
  7.         for i in range(100000):
  8.             listemelange = listeatraiter[0:annee]
  9.             random.shuffle(listemelange)
  10.             calcule_score(listemelange, i, annee)
  11.         if listetraiteeok % 10 == 0:
  12.             print("liste mélangées :", listetraiteeok, "1000 fois")

Télécharger

La variable goodliste contenait à ce moment là une liste de listes, nos 154 listes que nous avons mélangés 100 000 fois procédant ainsi à 15 000 000 nouveaux tirages.

In fine, nous avons obtenu trois 4 listes ayant un score supérieur à 19 000

[(-1, -4), (-2, -5), (8, 1), (-3, -5), (7, 1), (7, 3)]
[(2, 3), (2, 4), (-6, -7), (1, 2), (-6, -9), (-5, -7)]
[(5, 3), (7, 3), (7, 4), (-1, -7), (-3, -7), (-1, -6)]
[(5, 5), (4, 5), (4, 3), (-6, -8), (-5, -8), (-4, -8)]

MeilleurScore : 19207.913058803344
liste = [(5, 5), (4, 5), (4, 3), (-6, -8), (-5, -8), (-4, -8)]

Dernière approche gagnante

La dernière approche (gagnante) fut de procéder par force brute sur des listes ayant un bon patrimoine génétique.

Nous avions à notre disposition des nombreuses listes courtes avec des scores supérieur à 18 000 voir 19 000. Et si nous cherchions à les rallonger ?

Certains résultats obtenus par forcealeatIA(9,1000000) étaient surprenant. Certaines listes de 9 couples avaient un bon score, mais si on ne prenait que la liste des 6 premiers couples le score était mauvais.

Un script sur mesure fut donc codé.

  1. def add_liste(listeatraiter, annee, rangsup=1):
  2.     liste = listeatraiter.copy()
  3.     # on essaie avec (0,0)
  4.     liste.append((0, 0))
  5.     listescore = liste.copy()
  6.     calcule_score(listescore, 0, annee + 1)
  7.     if rangsup - 1 > 0:
  8.         add_liste(liste, annee + 1, rangsup - 1)
  9.     liste.pop(len(liste) - 1)
  10.     # on essaie avec (+,+)
  11.     for i in range(1, 10, 1):
  12.         for j in range(1, 10, 1):
  13.             liste.append((i, j))
  14.             listescore = liste.copy()
  15.             calcule_score(listescore, 10 * i + j, annee + 1)
  16.             if rangsup - 1 > 0:
  17.                 add_liste(liste, annee + 1, rangsup - 1)
  18.             liste.pop(len(liste) - 1)
  19.     # on essaie avec (-,-)
  20.     for i in range(-9, 0, 1):
  21.         for j in range(-9, 0, 1):
  22.             liste.append((i, j))
  23.             listescore = liste.copy()
  24.             calcule_score(listescore, 10 * i + j, annee + 1)
  25.             if rangsup - 1 > 0:
  26.                 add_liste(liste, annee + 1, rangsup - 1)
  27.             liste.pop(len(liste) - 1)
  28.  
  29. an = len(goodliste)
  30. add_liste(goodliste, an, 2)
  31. print(good_list)

Télécharger

La variable goodliste contenait à ce moment là une unique liste, que l’on voulait compléter.

add_liste(goodliste, an, 1) quelques secondes, 163 tirages
add_liste(goodliste, an, 2) quelques minutes, 26 569 tirages
add_liste(goodliste, an, 3) quelques heures, plus de 4 000 000 de tirages.

Nous n’avons pas testé add_liste(goodliste, an, 4) par manque de temps.

Par contre, sur 6,8,12 thread le script add_liste(goodliste, an, 3) a tourné non stop sur des listes sélectionnées avec amour au moyen des scripts forcealeatIA(annee, nbtirage) qui continuait à tourner, dès fois que ...

Chronologie des scores obtenus

Avec quelques extraits des messages envoyés au maître de cérémonie.

15/10 17:00 : 15016

Pour l’instant on pédale dans la semoule
global s,j,w # sjw : je ne sais pas si c’est fait exprès mais ...

15/10 19:34 : 17142

On n’a toujours aucun graphique ni aucune idée de ce qui se passe mais si ça ressemble fortement à des multiplications matricielles

16/10 14:16 : 18157

Score de la nuit sur 10 000 000 de tirages pas vraiment optimisés

23/10 10:30 : 18860

Objectif 19000 avant la fin de la journée

23/10 11:30 : 19117

Prochain objectif : 19430 (pour doubler un autre candidat)

24/10 10:07 : 19675

Finalement 19430 n’était qu’une formalité.

Maintenant pour aller jusqu’à 21700 il va falloir trouver une autre méthode, celle-ci est un peu longue, mais comme il faut chauffer un peu la maison je ne suis responsable d’aucun meurtre supplémentaire de pingouin.

24/10 21:13 : 20180

500 points de plus ! Et c’est pas fini !

28/10 22:12 : 20475

Il me tarde de savoir comment a fait Pavel parce que j’ai tout donné et que j’ai 7 scripts qui moulinent sur mon PC...

28/10 22:12 : 20972

Je ne perds pas espoir de finir 1er, mais stratégiquement je me dis que j’ai peut-être intérêt à envoyer mes scores le dernier jour pour que le 1er ne puisse pas réagir ...

C’est beau de rêver ... 20972 fut notre meilleur score.

Conclusions

Une estimation basse du nombre de tirages que nous avons réalisé donne 100 000 000 de tirages. Mais comme les scripts tournaient non stop en parallèle, nous pensons qu’on s’approche plus des 200 000 000 de tirages et simulations diverses pas du tout optimales.

Ne maîtrisant pas encore les exports / imports CSV en python nous avons été limité par la nécessité d’arrêter manuellement les scripts, de copier / coller les bons résultats et de relancer les scripts, mais pour le défi de l’année prochaine nous seront prêt.

Félicitation une nouvelle fois à Pavel qui a dominé les 3 épreuves mais semble ne pas partir avec les mêmes connaissances de base que le simple visiteur des sites Tiplanet et planetcasio.

L’année prochaine, il est probable que l’on donnera le concours python en devoir maison facultatif aux élèves de spé NSI de terminale de notre lycée, histoire de voir s’ils ont fixé des connaissances et s’ils font preuve d’initiative et d’autonomie.

Se classer dans les 10 premiers : 18/20, coefficient 0,42
Se classer devant le prof : 20/20, coefficient 0,666