concours de rentrée 2019 - Le défi python / Pokemon


Accueil > Projets > concours de rentrée 2019 - Le défi python / Pokemon

Par Fedyna Kevin, Robert Vincent en novembre 2019

En naviguant par hasard sur le site tiplanet.org, nous sommes tombé sur un défi Python et comme se perfectionner en python était l’un de nos objectifs, autant joindre l’utile à l’agréable.

Pour le défi python 2019 des sites internet tiplanet.org et planet-casio.com , il fallait se constituer une main de 10 pokemons maximum et leur attribuer une priorité d’attaque.

Pour cela, un script Python va offrir à ta calculatrice la fonction pk(n,p) pour ajouter un Pokémon à ta main, avec :
n, le numéro de Pokémon de 1 à 94
p, la priorité d’attaque que tu souhaites donner au Pokémon en question (1 par défaut)

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.

Premiers tests "à la main"

Comme beaucoup de joueurs, nous avons commencé par générer des mains au petit bonheur la chance, gratifié d’un score maximum de 44,2 nous sommes vite passé à une autre méthode.

Nous aurions bien voulu commencer les recherches sur la NumWorks, mais les problèmes de mémoires dont-elle souffre rendent ces recherches impossibles.

Ajouter quelques lignes de codes au script de 3.7 ko aurait fait planter la calculatrice.

Nous sommes donc passé sur Thonny et y avons exécuté nos scripts pythons

Attaque n°1 : 10^n tirages aléatoires

Après avoir neutralisé les fonctions print, les affichages des scripts du concours, et rajouté quelques variables globales, une boucle de tirage aléatoire fut codée :

  1. import random
  2.  
  3. score, scoremax = 0.0, 0.0
  4. code, codemax = 0.0, 0.0
  5. tentative = 0
  6.  
  7. def tiragemain():
  8.   for i in range(1,11,1):
  9.     pokemonaleatoire = random.randint(1,94)
  10.     score=pk(pokemonaleatoire,i)
  11.   return score,code
  12.  
  13. while score<49.3:
  14.   # Les trois lignes ci-dessous réinitialisent le script, qui tourne sans s'arrêter
  15.   na,pkl=21,[]
  16.   lnm =["Bulbizarre","Herbizarre","Florizarre","Salameche","Reptincel","Dracaufeu",
  17.         "Carapuce","Carabaffe","Tortank","Chenipan","Chrysacier","Papilusion","Aspicot",
  18.         "Coconfort","Dardargnan","Roucool","Roucoups","Roucarnage","Rattata","Rattatac",
  19.         "Piafabec","Rapasdepic","Abo","Arbok","Pikachu","Raichu","Sabelette","Sablaireau",
  20.         "Nidoran F","Nidorina","Nidoqueen","Nidoran M","Nidorino","Nidoking","Melofee",
  21.         "Melodelfe","Goupix","Feunard","Rondoudou","Grodoudou","Nosferapti","Nosferalto",
  22.         "Mystherbe","Ortide","Rafflesia","Paras","Parasect","Mimitoss","Aeromite","Taupiqueur",
  23.         "Triopikeur","Miaouss","Persian","Psykokwak","Akwakwak","Ferosinge","Colossinge","Caninos",
  24.         "Arcanin","Ptitard","Tetarte","Tartard","Abra","Kadabra","Alakazam","Machoc","Machopeur",
  25.         "Mackogneur","Chetiflor","Boustiflor","Empiflor","Tentacool","Tentacruel","Racaillou",
  26.         "Gravalanch","Grolem","Ponyta","Galopa","Ramoloss","Flagadoss","Magneti","Magneton",
  27.         "Canarticho","Doduo","Dodrio","Otaria","Lamantine","Tadmorv","Grotadmorv","Kokiyas",
  28.         "Crustabri","Fantominus","Spectrum","Ectoplasma"]
  29.   mrandmax,mrand,mfmax,nn,mp=2**31-1,0,93,getlinechars(True)-na,na//2
  30.   tentative = tentative+1
  31.   score,code = tiragemain()
  32.   if score>scoremax:
  33.     scoremax = score
  34.     codemax = code
  35.     print("################# tirage n°",tentative,"score =", scoremax,"avec le code", codemax,"#################", round(score,8))

Télécharger

Le résultat n’est pas optimal, on ne tire aléatoirement que les Pokemons en passant naïvement que les forces sont forcement des entiers entre 1 et 10

Mais on arrive à fabriquer des scores aux alentours de 46,2
En une nuit, on arrive péniblement à réaliser entre 4 et 7 millions de tirages.

A ce stade de la recherche, compte tenu de nos hypothèses, on cherche une solution optimale parmi 3 x 10^19 possibilité. Toute force brute est impossible.

Attaque n°2 : Recherche des Pokemon forts !

On décide de faire tourner le script précédent et de mémoriser les compositions des mains supérieures à 46

On va donc réaliser quelques millions de tirages, et dénombrer les Pokemons qui ont permis de faire une main supérieure à 46

  1.   if score>46:
  2.     for i in listeobtenu:
  3.       benchmark46(i,score)

Télécharger

Le lendemain, nous avons un histogramme qui nous donne des Pokemons performant.

[0, 54, 25, 143, 11, 99, 39, 23, 5, 10, 6, 11, 9, 17, 10, 31, 70, 13, 12, 10, 48, 15, 38, 51, 18, 6, 21, 33, 13, 19, 5, 8, 13, 48, 13, 33, 35, 5, 31, 24, 31, 9, 33, 94, 28, 13, 5, 106, 16, 8, 34, 51, 27, 6, 13, 3, 36, 33, 42, 4, 17, 9, 72, 311, 3, 16, 30, 25, 32, 74, 13, 60, 172, 40, 12, 62, 44, 1, 8, 38, 6, 32, 15, 22, 21, 101, 25, 24, 73, 19, 26, 5, 33, 4, 18]

Le Pokemon 63 (Abra) est sorti 311 fois dans la nuit dans des mains valant plus de 46 points. Le 64 lui était très mauvais, et il n’était que dans 3 mains valant plus de 46 points.

Attaque n°3 : Tirages aléatoires sur liste optimale

Le deuxième jour, nous avons poursuivi les tirages aléatoires mais sur des listes optimales générées à l’aide de l’histogramme de la veille.

Liste large :
[ 3 , 5 , 16 , 33, 43, 47, 51, 58, 62, 63, 69, 71, 72, 73, 75, 76, 85, 88 ]

Liste short :
[ 3 , 5 , 16 , 47, 62, 63, 69, 72, 75, 85, 88]

Au lieu de tirer au hasard un pokemon parmi 94, on le tirait dans une liste prédéfini à diverses positions (nous pensions que la force était la position, donc un entier entre 1 et 11)

  1. def tiragemain():
  2.   listeobtenu =[]
  3.   top = [ 3 , 5 , 16 , 47, 62, 63, 69, 72, 75, 85, 88]
  4.   random.shuffle(top)
  5.   for i in range(1,11,1):    
  6.     pokemonaleatoire = top[i-1]
  7.     listeobtenu.append(pokemonaleatoire)
  8.     score=pk(pokemonaleatoire,i)
  9.   for i in listeobtenu:
  10.     benchmark(i,score)
  11.   if score>47:
  12.     for i in listeobtenu:
  13.       benchmark47(i,score)
  14.   return score,code,listeobtenu

Télécharger

5 000 000 de tirages plus tard, pas de grandes améliorations, 47.6 est notre meilleur score, mais c’est déjà un joli résultat.

Attaque n°4 : Valeur moyenne des mains

Toutes les tentatives pour optimiser la valeur moyenne des mains ont échouées.
Le calcul lui même de cette moyenne n’étant pas concluant.

Attaque n°5 : Recherche des Pokemon forts sur R

En lisant le forum associée à ce défi sur Planète casio, on croit comprendre qu’il n’y a pas un nombre fini de combinaison, donc si on tire n dans les entiers entre 1 et 94, p lui serait un réel. On relance les scripts précédents et miracle on passe au dessus de 47.8.

  1. def tiragemain():
  2.   listeobtenu =[]
  3.   for i in range(1,11,1):    
  4.     pokemonaleatoire = random.randint(1,94)
  5.     listeobtenu.append(pokemonaleatoire)
  6.     score=pk(pokemonaleatoire,uniform(0,2**31-1))
  7.   if score>46:
  8.     for i in listeobtenu:
  9.       benchmark47(i,score)
  10.   return score,code,listeobtenu

Télécharger

Après avoir affiné la liste des pokemons optimaux, on relance les autres scripts qui mélangent, permutent, tirent d’après la liste optimale, et on obtient nos premiers score à 48.

0^uxOeh%_##>(6#))*&#
48.12835164090643

^heO0xku#_D#’’#%$*.0
48.14694065075124

Attaque n°6 : Élimination des plus faibles

N’étant pas certains d’avoir la main optimale, on essaye de remplacer un pokemon par tous les autres pour voir si le score s’améliore. Cette méthode ne permet pas de progresser.

Attaque n°7 : Tentative de spécifications des fonctions

On décide alors de documenter le code, de le décrypter, d’essayer de voir si on ne peut pas faire le problème à l’envers, c’est une attaque par spécification du code.

  1. def mmod(a, b):
  2.     # retourne la partie décimale de a a vérifier
  3.     # si a est un entier, retourne 0
  4.     # ?? intérêt , a % b économise de la mémoire
  5.     return a % b
  6.  
  7.  
  8. def getplatform():
  9.     # retourne la valeur 1
  10.     # ?? intérêt ?
  11.     return 1
  12.  
  13.  
  14. def getlinechars(o=False):
  15.     # Cette fonction est une bague. Elle est appelée une unique fois avec true
  16.     # et alors getlinechars(True) retourne 99
  17.     c = 2 ** 31 - 1
  18.     k = getplatform()
  19.     # ?? k = 1 ;-)
  20.     if k >= 0:
  21.         # k = 1 donc est exécuté dans 100% des cas ...
  22.         c = [53, o and 99 or 29, o and 509 or 21, 31, 32, c, c][k]
  23.     return c  # c= 99  ... sauf astuce et codage plus bas ^^
  24.     # pas défaut, en l'absence de True getlinechars() retourne 29

Télécharger

Les premières fonctions sont faciles à spécifier.
Les variables sont rigolotes :

  1. na = 21
  2. # 42/2 ? :-) Utilisé 2 fois, jamais modifié
  3. mrandmax = 2 ** 31 - 1
  4. # valeur max d'un entier positif signé codé en 32 bits... spé NSI inside
  5. mrand = 0
  6. # rien d'aléatoire ici, sera modifié par la fonction mseed()
  7. mfmax = 93
  8. # 94-1
  9. nn = getlinechars(True) - na
  10. # nn = 99-21 = 78 (sans calculatrice !)
  11. mp = na // 2
  12. # mp = 10, jamais modifié, utilisé une seule fois f° pk

Télécharger

mais nous sommes restés coincés sur les fonctions getattack(), clean() et surtout pk().

Par contre la fonction setst() nous a passionné !

Le script original à peine modifié, commenté et codé en pep8 (ZIP - 3.7 ko)
Le script original à peine modifié, commenté et codé en pep8

Attaque n°08 : Manipulations autour du code réponse

La liste des pokemons est codée en dur dans le script, mais il n’en est rien de leurs qualités ni de la valeur de force optimale pour chaque pokemon. Cette dernière est donc calculée. Or la chaîne de caractère du code réponse semble peu varier lorsque de l’on tire depuis une liste fixé de Pokemons.

Nous comprenons que :

  • La partie gauche code la liste des Pokemons
  • La partie droite leur force
  • Pour un code "ABCDEFGHIJ0987654321", on a 10 couples (un exemple est ici en gras) qui définissent les 10 pokémons et leurs points d’attaque.
  • On peut faire de jolie permutation sans changer le score obtenu car les couples n’influent pas les uns sur les autres
  • Il n’y a aucune clé de vérification, on peut tester des codes au hasard sans avoir la moindre idée de la main des Pokemons et de leur forces
  • Les forces sont codés par des caractères ASCII, on n’est plus du tout dans R mais de retour dans N.
  1. def i2c(k):
  2.     # Transforme un nombre décimal en chaine de caractère
  3.     return chr(k + 33)
  4.  
  5.  
  6. def c2i(c):
  7.     # transforme une chaine de caractère ayant un élèment en valeur décimale
  8.     # cette valeur décimale sera comprise entre 32 (a) et 89 (z)
  9.     return ord(c) - 33

Télécharger

En modifiant à la main la partie droite de la chaîne de caractère, on arrive à modifier très substantiellement le score, à la hausse comme à la baisse.

Notre premier 49 est obtenu en bricolant à la main la chaîne de caractère.

u^KhxO_%#l"""l"""%%%
Out[17] : 49.031613189324844

C’était assez jouissif il faut dire, en changeant un caractère parmi les 10 derniers, notre score pouvait plonger OU augmenter bien plus vite que tous nos algorithme de tirages aléatoires qui tournaient des nuits complètes...

Ce code réponse ne contient que 20 caractères, on connaît déjà les 10 premiers (du moins on le pense) il ne nous reste plus qu’à utiliser la force brute sur les dix derniers caractères.

Attaque n°09 : Force brute pour traiter les chaines de caractère du code réponse

Grace à notre compréhension obtenue avec l’attaque n°08, on a supposé que pour une liste de 10 pokémons, il existe une suite de forces optimales.

On a ainsi écrit un petit script permettant de trouver cette suite optimale :

  1. lc = [None,"!","!","!","!","!","!","!","!","!","!"]
  2. carac = '!"#$%&'+"'"+'()*+^;_,-./0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
  3. def cons(liste):
  4.     # Construit le code
  5.     global cc
  6.     cc = ""
  7.     for j in range(len(liste)):
  8.         cc = cc+liste[j]
  9. def turboBoost(pokemons,vitesse=1,style=1):
  10.     # Prend une main de pokemon et lui donne des steroides
  11.     # la chaine finale sous forme de liste pour modifier les caracteres
  12.     lc[0]=pokemons
  13.     # les caracteres a tester (tout ce qui est possible)
  14.     for l in range(vitesse+3):  
  15.         # creation du code par test (5x ou 4x pour trouver "l'etat stable" a tout les coups)
  16.         # vitesse 1 = rapide, vitesse 2 = lent mais plus sur
  17.         for i in range(1,11):
  18.             # On initialise tout
  19.             global cc
  20.             cons(lc)
  21.             scores = [0]
  22.            
  23.             for k in range(len(carac)):
  24.                 # On recense le score pour chaque caractere
  25.                 lc[i] = carac[k]
  26.                 cons(lc)
  27.                 score = setst(cc)
  28.                 scores.append(score)
  29.             # On prend le gagnant, c'est notre partie de cle
  30.             lc[i] = carac[scores.index(max(scores))-1]
  31.             # on cree le code final
  32.             cons(lc)
  33.          # style pour la fonction (purement cosmetique)
  34.         if style:
  35.             print(int((l+1)*100/(vitesse+3)),"%")
  36.             if vitesse == 1:
  37.                 print("====="*(l+1)*2+"....."*(8-(l+1)*2))
  38.             if vitesse == 2:
  39.                 print("===="*(l+1)*2+"...."*(10-(l+1)*2))
  40.     score = setst(cc)
  41.     print(cc+" :",score,": "+code)

Télécharger

On remarque qu’il est nécessaire d’avoir une liste pour modifier les éléments de la chaîne de caractères un par un à une position donnée.

Rien qu’avec ce script, on a pu augmenter considérablement le score des meilleurs Pokémons issus des attaques précédentes :

Avant :

u^KhxO_%#l"""l"""%%%
Out[17] : 49.031613189324844

Après :

turboBoost("u^KhxO_%#l")
25 %
==========..............................
50 %
====================....................
75 %
==============================..........
100 %
========================================

u^KhxO_%#l"""^""1""" : 49.29025926955508 : u^KhxO_%#l"""d""3"""

Cette optimisation du membre de droite nous permettait de faire la même chose pour le membre de gauche.

On a alors écrit une fonction utilisant notre fonction d’optimisation pour tester chaque caractères pour le membre de gauche en optimisant le score à chaque fois pour trouver le code parfait.

  1. def chasseAuxPokemons(vitesse=1):
  2.     # La vitesse 1 m'a prise 9h mais a bien fonctionnée
  3.    
  4.     lcp = ["!","!","!","!","!","!","!","!","!","!"]
  5.     for l in range(vitesse+3):  
  6.         for i in range(10):
  7.             # On initialise tout
  8.             global cc
  9.             cons(lcp)
  10.             scores = [0]
  11.            
  12.             for k in range(len(carac)):
  13.                 # On cree la liste de Pokemons avec les caractères
  14.                 lcp[i] = carac[k]
  15.                 cons(lcp)
  16.                 # On applique le booster de performances dessus (rapide et sans les barres de %)
  17.                 turboBoost(cc,1,0)
  18.                 # On recense les scores
  19.                 score = setst(cc)
  20.                 scores.append(score)
  21.             # On prend le gagnant, c'est notre nouveau Pokemon
  22.             lcp[i] = carac[scores.index(max(scores))-1]

Télécharger

Grace à cette fonction, on a pu obtenir le TOP résultat, le fameux 49,31730 :

_h#^g0KuOS""""""""7u : 49.31730339247606

On a donc envoyé des scores légèrement en dessous pour pouvoir nous qualifier dans les premiers.

Attaque n°10 : Force brute oui mais ...

Nous avions exclus quelques caractères de cette force brute, on a donc réussi uniquement à obtenir le premier TOP résultat qui était déjà pris, le fameux 49,31730 mais pas au delà. Quand les premiers 49.319 et 49.32 ont commencé à sortir, nous avons compris que nous avions trop traîné, et qu’en intégrant d’autres caractères de la table ASCII nous aurions pu finir premier. Nous pensions que 49,31730 était le résultat optimal, nous n’avons pas testé davantage alors qu’on avait à priori la bonne méthode.

Mais notre échec relatif nous à gonflé à bloc pour le défi historique, que nous avons fait en python cela va de soit et sur PC car la mémoire de la NumWorks à la date d’octobre 2019 ... enfin vous voyez de quoi on veut parler, sinon il suffit de lire ceci : Script qui refuse de s’exécuter sur la Numworks N0100 pour comprendre de quoi il retourne.

Conclusions

Nombres de tirages réalisés au total : entre 20 000 000 et 30 000 000 maximum.
3 scripts tournaient au maximum en même temps, sur deux ordinateurs distincts.

L’année prochaine, il faudra compter sur nous ! Et cette fois-ci on commencera le défi le jour J et pas en retard. Pavel va devoir ... heu non rien du tout, Pavel est très au dessus du niveau moyen. ;-)

Nous remercions les organisateurs des sites tiplanet et planetcasio pour ce bon moment, cette recherche était passionnante, nous a réveillé la nuit (histoire de vérifier que les scripts tournaient bien) et maintenant les listes en python n’ont plus de secret pour nous.

Sur un autre sujet, nous supplions l’équipe de NumWorks d’augmenter la mémoire allouée aux scripts python sur la N0100 et la N0110. Ne pas pouvoir écrire un script de plus de 4ko est une absurdité !

Mots-clés