Seuls les membres ayant 30 points peuvent parler sur le chat.

Forum Casio - Actualités


Index du Forum » Actualités » Concours de rentrée 2019 - Épreuve Python !
LephenixnoirHors ligneAdministrateurPoints: 16017 Défis: 140 Message

Concours de rentrée 2019 - Épreuve Python !

Posté le 30/09/2019 13:04

Notre concours de rentrée 2019 se poursuit avec la deuxième épreuve, en langage Python !



Comme l'année dernière et l'année précédente, TI-Planet et Planète Casio organisent un concours de rentrée ludique et mathématique orienté vers les calculatrices graphiques. Cette année, trois épreuves te sont proposées dans différents langages, avec des calculatrices Casio, TI, HP et Numworks à remporter.

La deuxième épreuve de ce concours est l'épreuve en langage Python. C'est un problème de combinatoire Pokémon aidé par un script Python à lancer sur la plateforme de ton choix.

L'épreuve Python est ouverte jusqu'au Dimanche 3 Novembre à 23h59.



Épreuve Python.
Équilibre ton équipe pour remporter le tournoi Pokémon de TI-Planète-Casio !

Dans cette épreuve, ton objectif est de sélectioner attentivement ton équipe de Pokémon. Tu peux choisir jusqu'à 10 Pokémon (tous différents) et leur donner à chacun une priorité d'attaque. Si leurs compétences se complètement bien, ton score augmentera !

Les scripts et ressources sont fournis dans l'article associé sur TI-Planet. Côté calculatrices, tu peux utiliser le programme avec une Graph 90+E, une Graph 35+E II, ou un modèle plus ancien qui supporte les add-ins comme les Graph 35+ USB, 35+E, 75+ ou 75+E. Tu peux aussi utiliser le script sur ton ordinateur avec Python.

Le programme te fournit une fonction pk pour construire ta main.

• Appelle pk(n,p) pour ajouter le pokémon numéro n à ta main avec une priorité d'attaque p. Il y a 94 Pokémons autorisés au tournoi, donc tu dois choisir n entre 1 et 94.
• Appelle pk(n,p) de nouveau pour changer la priorité d'attaque du Pokémon n si ce Pokémon est déjà dans ta main.
• Appelle pk(n,0) pour retirer le Pokémon numéro n de ta main.

À chaque fois que tu modifies ta main, le programme annonce ton score et un code qui nous permet de vérifier ta solution. L'objectif est de trouver l'équipe de Pokémon qui maximise ton score !

Comme d'habitude, tous les coups sont permis pour trouver la solution, tant qu'il n'y a pas de triche ou partage de solutions entre les participants. Tu peux utiliser tous les outils mathématiques et informatiques que tu veux, y compris modifier le script ou faire jouer un ordinateur à ta place.

Pour télécharger le programme de l'épreuve, consulte la rubrique "Ressources" sur TI-Planet.


Comment participer

Pour participer, il te suffit d'envoyer le code correspond à ta main à info@tiplanet.org avec pour objet concours de rentrée 2019. N'oublie pas de préciser :
• Une adresse mail personnelle (si différence de celle de l'envoi)
• Ton adresse postale complète (avec nom et prénom)
• Si tu le souhaites, ton pseudo TI-Planet ou Planète Casio (affiché sur la liste des résultats)
• Un numéro de téléphone personnel (utile pour ne pas oublier la sélection des lots à la fin du concours)

Tu peux envoyer plusieurs participations, nous ne compterons que la meilleure !


Lots de l'épreuve

L'épreuve de Python comporte 13 lots à remporter. Les candidats qui ont obtenu les 13 meilleurs scores choisiront chacun un lot par ordre décroissant de score.

2 Lots Hélium : 1 calculatrice Graph 90+E, 1 pack de goodies Casio et 1 pack de goodies TI-Planète-Casio
Lot Fluor : 1 licence émulateur Casio, 1 poster Casio, 1 bloc-notes Casio EX-word avec stylo ou trousse ou sac Casio, 1 balle anti-stress Casio LampFree ou calepin Casio ou porte-clés Casio LampFree, 1 catalogue Casio, 1 pack de goodies Casio et 1 pack de goodies TI-Planète-Casio
Lot Néon : 1 licence émulateur Casio, 1 cahier d'exercices Casio, 1 mémo Casio, 1 bloc-notes Casio EX-word avec stylo ou trousse ou sac Casio, 1 balle anti-stress Casio LampFree ou calepin Casio ou porte-clés Casio LampFree, 1 catalogue Casio, 1 pack de goodies Casio et 1 pack de goodies TI-Planète-Casio
Lot Hydrogène : 1 calculatrice HP Prime G2, 1 stylo HP et 1 pack de goodies TI-Planète-Casio
Lot Phosphore : 1 application HP Prime Pro, 1 bloc-notes HP, 1 stylo HP et 1 pack de goodies TI-Planète-Casio
Lot Chlore : 1 calculatrice NumWorks, 1 pack de goodies NumWorks et 1 pack de goodies TI-Planète-Casio
Lot Argon : 1 poster NumWorks, 1 casse-tête ou stylo NumWorks, 1 pack de goodies NumWorks et 1 pack de goodies TI-Planète-Casio
Lot Brome : 1 calculatrice TI-Nspire CX II-T CAS ou calculatrice TI-Nspire CX CAS Ndlessable, 1 licence logiciel TI-Nspire CAS élève, 1 pack de goodies TI et 1 pack de goodies TI-Planète-Casio
Lot Krypton : 1 calculatrice TI-Nspire CX II-T, 1 licence logiciel TI-Nspire élève, 1 pack de goodies TI et 1 pack de goodies TI-Planète-Casio
Lot Iode : 1 calculatrice TI-83 Premium CE Edition Python, 1 cahier TI-83 Premium CE, 1 pack de goodies TI et 1 pack de goodies TI-Planète-Casio
Lot Xénon : 1 licence logiciel TI, 1 cahier TI-83 Premium CE, 1 pin's TI-Nspire CX ou pochette CD TI-Nspire, 1 décalcomanie TI-83 Premium CE, 1 balle anti-stress TI, 1 sac TI, 1 dessous de verre TI ou lunettes de soleil #T3IC ou scellé de sécurité TI, 1 pack de goodies TI et 1 pack de goodies TI-Planète-Casio
Lot Radon : 1 licence logiciel TI, 1 cahier TI-83 Premium CE, 1 polo TI ou T-shirt TI, 1 décalcomanie TI-83 Premium CE, 1 balle anti-stress TI, 1 sac TI, 1 dessous de verre TI ou lunettes de soleil #T3IC ou scellé de sécurité TI, 1 pack de goodies TI et 1 pack de goodies TI-Planète-Casio

Tu peux retrouver tous les détails des choix de goodies et de nombreuses photos sur TI-Planet.


À toi de jouer !

Comme souvent avec ces problèmes, une petite astuce de méthode peut te mener à la victoire. Essaie toutes les idées qui te viennent pour exploser le score de ton équipe Pokémon et figurer dans les 13 vainqueurs !

Article connexe sur TI-Planet : Concours de rentrée 2019 - défi de Python


Fichier joint


Pages : Précédente1, 2, 3, 4, 5, 6, 7, 8Suivante
KikoodxEn ligneMembrePoints: 1450 Défis: 9 Message

Citer : Posté le 06/11/2019 16:31 | #


Bulito a écrit :
Kikoodx a écrit :
Bulito a écrit :
Pour les gagnants du concours Python, vous avez fait comment ? Décryptage du script ? Algo intelligent ? Hasard ?

Hasard ne fonctionne pas.

Pas d'accord, par contre bien sûr, il faut retravailler le meilleur score à la main, mais j'ai trouvé 49,17 en un jour !

Hein ?
J'avais fait ça et obtenu 47.0X en un mois de calcul
Bum-bo wants coins

2+2=5
TituyaHors ligneRédacteurPoints: 524 Défis: 15 Message

Citer : Posté le 06/11/2019 16:34 | #


Avec ces techniques, j'ai facilement trouvé des 49.3 en quelques heures
Casio VS Nokia 3310 ? Qui gagne ?



DisperseurEn ligneMembrePoints: 1636 Défis: 1 Message

Citer : Posté le 06/11/2019 17:38 | #


Lol
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
KikoodxEn ligneMembrePoints: 1450 Défis: 9 Message

Citer : Posté le 06/11/2019 17:49 | #


Well... Uh.
Bum-bo wants coins

2+2=5
PavelHors ligneMembrePoints: 7 Défis: 0 Message

Citer : Posté le 07/11/2019 01:34 | #


Bulito a écrit :
Pour les gagnants du concours Python, vous avez fait comment ? Décryptage du script ? Algo intelligent ? Hasard ?


Je dirais que j'ai fait les trois.

J'ai mis mon code Python qui trouve le meilleur score en quelques minutes dans un dépôt git et je vais essayer d'expliquer dans la suite le fonctionnement de ce code.

1. Quelques observations

Le calcul du score favorise les équipes de dix pokémons.

Les points d'attaque sont des nombres rationnels.

La somme de tous les points d'attaque est censée être normalisée à 1.

Il y a un problème d'arrondi qui probablement peut être exploité pour contourner la normalisation.

2. Optimisation du calcul du score

J'ai commencé par optimiser le calcul du score.

J'ai ajouté une liste "pokemons" qui est remplie une fois au début du programme, contrairement à la fonction "getattack()" qui calcule les compétences des pokémons à chaque appel de cette fonction. J'ai aussi ajouté une fonction "fast_score()" qui utilise cette liste.

Voici le code:

pokemons = []

for l in range(94):
  mseed(42)
  for k in range(l + 1):
    mrandom()
  pokemons.append(mrandint(1, mrandmax))

def fast_score(code):
  pkt = [0.0 for l in range(21)]
  for k in range(10):
    p = code[19 - k] / 93.0
    for l in range(21):
      if pokemons[code[k]] & (1 << l):
        pkt[l] += p
  size = 0
  for k in range(10):
    if code[19 - k] > 0:
      size += 1
  score = 0.0
  for k in pkt:
    if k:
      score += log(e + k * size)
  return score


3. Initialisation de l'équipe de pokémons

Au début du programme, mon équipe de pokémons est composée d'un seul pokémon Bulbizarre avec 93 points d'attaque:

code = [0 for k in range(20)]
code[19] = 93


4. Recherche de la meilleure équipe de pokémons

J'ai utilisé l'algorithme de recuit simulé.

Pour modifier l'état de mon équipe de pokémons à chaque iteration de l'algorithme, j'ai implémenté deux fonctions: "random_pokemon()" et "random_attack()".

La fonction "random_pokemon()" remplace aléatoirement l'un des pokémons par un autre qui n'est pas encore présent dans l'équipe.

La fonction "random_attack()" choisit au hasard deux pokémons de l'équipe et un delta, puis incrémente les points d'attaque de l'un de ces deux pokémons par le delta et diminue les points d'attaque de l'autre de ces deux pokémons du même delta. Les nouveaux points d'attaque sont conservés s'ils donnent un score plus élevé. Cette opération est répétée plusieurs fois.

Voici le code de ces deux fonctions:

def random_pokemon(code):
  n = randint(0, 9)
  v = randint(0, 93)
  if not v in code[:10]:
    code[n] = v


def random_attack(code):
  score_max = fast_score(code)
  for k in range(300):
    while True:
      i = randint(10, 19)
      j = randint(10, 19)
      if i != j:
        break
    d = randint(-93, 93)
    vi = code[i] + d
    vj = code[j] - d
    if vi >= 0 and vi <= 93 and vj >= 0 and vj <= 93:
      code_next = code.copy()
      code_next[i] = vi
      code_next[j] = vj
      score_next = fast_score(code_next)
      if score_max < score_next:
        code[:] = code_next
        score_max = score_next


5. Recherche des meilleurs points d'attaque

Dans la meilleure équipe de pokémons trouvée par l'algorithme de recuit simulé, il y a dix pokémons mais il n'y a que deux pokémons qui ont plus d'un point d'attaque. Ces deux sont Abra et Tentacool.

Pour trouver les meilleurs points d'attaque pour Abra et Tentacool, je vérifie toutes les valeurs possibles et je garde celles qui apportent le meilleur score:

for i in range(ord('2'), 256):
  for j in range(ord('e'), 256):
    code = code_max.replace('2', chr(i)).replace('e', chr(j))
    score = setst(code)
    if score_max < score:
      score_max = score
      print('%.5f' % score, code, i, j)
DisperseurEn ligneMembrePoints: 1636 Défis: 1 Message

Citer : Posté le 07/11/2019 07:12 | #


Et ça te fait quel score ?
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
PavelHors ligneMembrePoints: 7 Défis: 0 Message

Citer : Posté le 07/11/2019 08:00 | #


La plupart du temps, ça converge vers 49.32057 ou 49.32079.
CritorEn ligneAdministrateurPoints: 1426 Défis: 18 Message

Citer : Posté le 09/11/2019 11:52 | #


L'anonymat du classement est dès maintenant levé :
https://tiplanet.org/concours_rentree2019.php?delta=0&infos=1

Bonne lecture.

Ajouté le 10/11/2019 à 16:26 :
Coucou chers gagnants.

Pour ceux qui ne se sont pas encore manifestés là-dessus, ce serait donc sympa de nous fournir quelques lignes d'explication de votre méthode sur ce sujet.
Vous pouvez faire ça ici, sur TI-Planet, ou encore par courriel.

Idéalement d'ici le week-end prochain.

Merci à vous.
DisperseurEn ligneMembrePoints: 1636 Défis: 1 Message

Citer : Posté le 10/11/2019 17:54 | #


Voici donc une petite explication de la technique que j'ai employée pour obtenir mon score:

Face à la fonction pk() dont le code m'as un peut effrayé, j'ai choisis de ne pas essayer de le comprendre et de l'utiliser tel quelle. Tout d'abords j'ai créé une fonction qui prenait en entrée la liste des Pokémon déjà ajoutés et qui me donnait le Pokémon suivant pour obtenir le meilleur score. Cette fonction testait tout simplement un à uns en les ajoutant, en enregistrant leur score puis en les retirant tous les Pokémon (les 94). Néanmoins cette fonction n’agissait pas sur les compétences des Pokémon et n’obtenait pas le meilleur score. J'ai ensuite créé une autre fonction pour exploiter la précédente, qui me donnait la meilleure main à partir d'un Pokémon de "base" que je lui donnais. Par la suite j'ai retiré ce paramètre et j'ai obtenu LA meilleure main de 10 Pokémon sans modifier leurs compétences. N'obtenant ainsi qu'un score autour de 47, j'ai décidé de jouer à la main sur les compétences de chacun de mes 10 Pokémon. Donc en partant du premier, je tentais de modifier ces compétences en augmentant le paramètre concerné dans la fonction pk(). Si je voyais mon score diminuer, alors je revenais sur la meilleure valeur. Et ainsi de suite pour les 10. Ensuite j'ai tenté de remplacer les Pokemon n'ayant pas subis de modification de compétences par d'autres plus performants, en utilisant toujours ma première fonction (suppression du Pokemon à remplacer, appel de la fonction avec la liste des 9 autres Pokemon et obtention du meilleur Pokemon à mettre à la place). Ainsi j'ai obtenu, en affinant la technique et en testant plusieurs configurations, un score d'environ 49,301...
Je suis désolé, j'aurais bien voulu vous partager le code de cette fonction, mais en rédigeant ce message et en la cherchant, je me suis rendu compte que je l'avait supprimée

La - dessus, je tiens à féliciter les premiers de ce classement et à leur dire que je suis toujours dans la course

@Critor: N'ajoute pas trop vite le message, je suis fatigué et j'ai peut - être omis quelque chose qui me reviendra plus tards. Mardi tu pourras la prendre
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
Ne0tuxHors ligneMembre d'honneurPoints: 3287 Défis: 263 Message

Citer : Posté le 11/11/2019 20:55 | #


Félicitations à tous les participants qui se sont intéressés au défi, ainsi qu'aux organisateurs !

Comme il est de coutume je fais un petit retour sur ma méthode. A l'instar de Pavel j'ai repris mon outil de l'an dernier : l'algorithme génétique.

Dans un premier temps il me fallait "modéliser" un individu (Ici il s'agit de la main complète de 10 Pokemon). En y réfléchissant, j'ai réalisé que le code de participation constituait déjà en lui même une modélisation de l'individu !

J'ai donc créé un générateur de main qui tirait aléatoirement 20 caractères et remodelé légèrement la fonction de calcul de score pour l'accélérer. Je n'avais besoin de rien de plus pour faire tourner l'algorithme génétique, qui a très rapidement permis d'atteindre le score maximum "honnête" (voir ci-dessous) de 49.3173.

Sauf que mon générateur de main avait un petit défaut : il incluait un caractère en trop (celui après le tilde dans la table ASCII), normalement hors borne. Dans la pratique cela permettait de gratter quelques digits dans la normalisation des puissances !

Malheureusement le caractère en question n'est pas passé par mail lors de ma participation. D'ailleurs on voit dans le classement que j'en ai deux alors que c'est la même, à un problème de copier/coller près ! J'ai pu rectifier le soucis quelques jours plus tard en comprenant le problème.

Par manque de temps, je n'ai pas effectué la dernière étape pourtant facile du bruteforce sur les caractères spéciaux, sachant que les caractères liés aux Pokemon devaient déjà être les bons. J'ai vu que ça n'avait pas échappé à certains qui ont su apporter cette petite finition qui a fait la différence : bravo !

Merci à ceux qui détaillent leur méthode, on constate qu'on a tous des façons de faire différentes, c'est chouette !
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
TituyaHors ligneRédacteurPoints: 524 Défis: 15 Message

Citer : Posté le 11/11/2019 23:33 | #


Malgré ma place relativement petite dans ce concours (Tout de même 7ème, c'est honorable ), je vous partage ici mes différentes recherches dans ma quête de trouver le meilleur score possible !

L'aire de la recherche :
Avant de chercher l'automatisation, j'avais rempli à la main le score renvoyé par chaque pokémons, me permettant donc d'obtenir une base d'équipe assez complète. Malgré le fait que certains pokémons ne soit pas terribles en équipe, j'obtenais tout de même des résultats convaincants ! (Deuxième version du script). J'avais trouvé 49.936 points !

Puis je cherchais (comme beaucoup) à la main les points d'attaque qui renvoyaient le plus haut score ! J'ai très vite remarqué que seul 2 pokémons pouvaient faire varier drastiquement le score : Abra et Tentacool !

L'aire de l'automatisation :
J'avais déjà formé une équipe me donnant un paquet de points. J'ai donc eu l'idée de lancer un premier script pour chaque pokemon afin de tester si un pokémon renvoyait un score que je n'avais pas vu !
(PETIT POINT : J'ai malheureusement perdu la liste de mes pokémons à cause d'un problème de clef USB ayant été volée ou oubliée... (plus pratique sur clef quand tu bosses au lycée sur le concours pendant les cours d'SI )). Donc les scripts qui suivent ont été réécrits...
for a in range(94):
   pk(a,1)
   s=st
   print("score final =",setst(s))
   if setst(s)>49.3:
     print(f"                    OK pour a = {a}, s={setst(s)} pour {st}")
   pk(a,0)

Puis je testais la priorité d'attaque de chacun de ces pokémons grâce à un script comme ça :

for a in range(150):
  pk(62,a)
  s=st
  print("score final =",setst(s))
  if setst(s)>49.3:
    print("OK !")
    print(a,setst(s),"pour",st)
  pk(62,0)

Grâce à ces petits scripts, j'ai tout de même réussi à trouver des scores comme 49.3158 points !

-Puis à partir d'un moment je me suis demandé comment le code était créé. J'ai vite remarqué que chaque pokémon correspondait à une valeur dans le code (genre par exemple le pokemon numéro 63 correspond à "_" et le pokemon 62 correspond à "^".)

Enfin brefs, les dix premiers caractères du code représentent les pokémons pris. Et cette valeur est facilement manipulable !

J'ai donc créé un script avec tous les caractères possibles (Je n'ai malheureusement pas pensé à la table ASCII). Au final, j'ai pris le problème à l'envers en fait.
J'y ai ajouté une vérification pour savoir si le score trouvé était déjà envoyé par un "concurrent". Et hop ! Plus qu'à laisser tourner !
Ce qui m'a permis de trouver sans effort (Juste beaucoup de temps) des combinaisons auxquelles je n'avais pas pensé ! Puis j'ai cherché automatiquement quel pokemon me donnait cette lettre dans le code !

J'ai pris le sujet à l'envers pour en tirer le plus possible avec ma petite échelle de lycéen lambda... J'ai surtout passé énormément de temps à chercher des choses en tous genres, essayer d'automatiser des bouts de code, je pense sincèrement que ce concours m'a pris plus d'une vingtaine d'heures !
Entre désillusions, avec des tentatives de bruteforce de plusieurs heures sans succès. Ou la joie de voir mon petit programme renvoyer soudainement un "OK pour cette valeur" !

Au final, ce concours m'a permis d'améliorer grandement ma maitrise en python ! Et étonnamment, réussir à obtenir une place sans comprendre une ligne du script fourni :E. Comme quoi, avec le temps et la persévérance on peut réussir même sans tout comprendre !

Bien joué à tous/toutes pour ce concours ! Et particulièrement à Cent20 qui m'a poussé sans le savoir à une compétition personnelle entre lui et moi !
Casio VS Nokia 3310 ? Qui gagne ?



DisperseurEn ligneMembrePoints: 1636 Défis: 1 Message

Citer : Posté le 12/11/2019 07:26 | #


@Ne0tux: Tu peux expliquer brievement le concept d'algorithme génétique stp ?
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
CaptainluigiHors ligneMembrePoints: 607 Défis: 1 Message

Citer : Posté le 12/11/2019 09:02 | #


Voici ma technique assez simple :
1- Tout d'abord j'ai lancé des boucles pour tester toutes les possibilités possibles , et j'ai obtenu environ 46 .
2- J'ai lancée des boucles pour déterminer à partir du score des 46 la meilleure combinaison possible de caractères , et au final j'ai donc obtenu 49.29 ...

Ajouté le 12/11/2019 à 09:03 :
J'ai du passer 20 heures dessus , pour rien
Jouez à Mario sans arrêt sur votre Casio !
Ma chaine YouTube : Tutodev
Cliquez pour découvrir
Cliquez pour recouvrir
City Heroes
Piano Casio
Micro GIMP
Merci d'avoir lu.
De rien !
Super !

M'en fout
C'est pas très bien ...
Ne0tuxHors ligneMembre d'honneurPoints: 3287 Défis: 263 Message

Citer : Posté le 12/11/2019 11:29 | #


@Disperseur : voilà quelques explications, si ce n'est pas clair ou si tu as des questions n'hésite pas.

Le principe de l'algorithme génétique est beaucoup plus simple que ce qu'on pense. Il ressemble à ce que tout un chacun sait de la théorie de l'évolution : les meilleurs individus d'une population survivent et se reproduisent pour créer de nouveaux individus. Les individus les plus mauvais se reproduisent moins et leurs gènes ne sont pas perpétuées d'une génération sur l'autre. A terme les individus les plus adaptés subsistent.

Pour faire tourner cet algorithme il faut définir ce qu'est un individu et expliciter ce que veut dire un "bon" individu par opposition à un "mauvais" individu.

Dans le cadre de cette épreuve, il est clair qu'un individu est une main complète. L'avantage est que le nombre maximum de cartes dans la main est connu : 10. On sait qu'une carte associe à un numéro de Pokemon une puissance. Par conséquent un individu est modélisable par 10 couples [Numéro de Pokemon, Puissance]. Dans la pratique, il était plus simple de considérer le code de participation en tant que modélisation, puisque 20 caractères suffisent à définir intégralement les 10 cartes d'une main.

Pour ce qui est de discerner les bons individus des moins bons, et bien le concours fournissait une fonction qui permettait en donnant un code de participation d'obtenir directement le score associé.

L'algorithme réalise donc les étapes suivantes :

0) Générer au hasard une population d'individus. Dans notre cas cela revient à créer un certain nombre de chaînes de 20 caractères.

1) Calculer le score de chaque individu de la population et les trier du meilleur au moins bon.

2) Faire un tirage au hasard de deux individus que l'on appelle "parents", proportionnellement à leur score (Tirage par roue de la fortune). C'est à dire que plus le score d'un individu est élevé, plus il a de chance d'être choisi comme parent. Cette étape s’appelle la sélection.

3) Échanger des gènes entre deux parents pour créer un ou deux enfants. On parle d'enjambement. Concrètement ici une gêne d'un individu est un couple [Numéro de Pokemon, Puissance]. Dans le cas de la modélisation choisie, une gène est donc constituée de deux caractères de la chaîne. Un enfant c'est donc également une chaine de 20 caractères, dont la plupart sont recopiés d'un premier parent et quelques-uns sont recopiés d'un second.

4) Muter les enfants. Pour ajouter un peu d'entropie et éviter que l'algorithme ne tourne trop sur lui même (Peut-on parler de consanguinité ?), on change aléatoirement mais pas systématiquement une gène d'un enfant.

5) Générer une nouvelle population à partir de tous les nouveaux enfants en gardant quelques-uns des parents. On peut dire qu'il s'agit d'une nouvelle génération. Puis recommencer à l'étape 1).

Quelques remarques :

- Le procédé est stochastique c'est à dire qu'il repose en grande partie sur des tirages aléatoires. Il est donc possible que seuls des optimums locaux soient trouvés et que l'optimum global ne le soit jamais ! Il est donc nécessaire d'ajouter en étape 5) un contrôle de la population capable de "resetter" une partie de la population si l'on sent que ça stagne.

- Le paramétrage est primordial. Notamment le choix de la taille de la population, le nombre de gènes croisées entre les parents pour créer un enfant, le pourcentage de chance de muter les enfants etc.

- L'algorithme est implémentable sur la quasi totalité des calculatrices du concours. Pas forcément besoin du Python d'ailleurs, il faut des tableaux et/ou des chaînes de caractère. Avec plus ou moins de vitesse d'exécution cependant. Sur mon PC perso (Intel Xeon E5-2687W v4, 12 coeurs à 3,5Ghz) le score de 49.3173 est atteint dans la minute.
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
DisperseurEn ligneMembrePoints: 1636 Défis: 1 Message

Citer : Posté le 12/11/2019 12:05 | #


Wow, puissant comme methode !
Tu pense que tu aurais pu trouver un meilleur score ?
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
YoustonesHors ligneMembrePoints: 101 Défis: 0 Message

Citer : Posté le 12/11/2019 16:18 | #


Aie ma tête...
Mais je comprend la théorie et je la trouve super !
Mon cerveau se répète tous les jours la mythique phrase : "Houston, je crois que nous avons un problème"
Edgar13Hors ligneMembrePoints: 5 Défis: 0 Message

Citer : Posté le 12/11/2019 17:48 | #


Bravo,
Moi honnêtement j'ai tout fait à la main.
DisperseurEn ligneMembrePoints: 1636 Défis: 1 Message

Citer : Posté le 12/11/2019 18:05 | #


Edgar13 a écrit :
Bravo,
Moi honnêtement j'ai tout fait à la main.

Et quel score as tu eu ?
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
TituyaHors ligneRédacteurPoints: 524 Défis: 15 Message

Citer : Posté le 12/11/2019 18:07 | #


49.30894. Ce qui le place 14eme ! Pile poil le dernier lot
Casio VS Nokia 3310 ? Qui gagne ?



Edgar13Hors ligneMembrePoints: 5 Défis: 0 Message

Citer : Posté le 12/11/2019 18:08 | #


14eme
DisperseurEn ligneMembrePoints: 1636 Défis: 1 Message

Citer : Posté le 12/11/2019 18:10 | #


Bravo quand même, 14e ça reste respectable
perso je suis 12e
Mes meilleurs jeux
N'hésitez pas, notez !

Jeux BasicCasio / CBasicCasio:
-World Tank War II
-Apollo 11
-GeoGraph ! Élu Jeu du Mois de Mars 2019 !
Jeux C:
-Planétarium 2 ! Chef d'Oeuvre !


√(2+2-2+2-2+2+2-2-2-2) = 0
Pages : Précédente1, 2, 3, 4, 5, 6, 7, 8Suivante

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2019 | Il y a 55 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd