Codingame - La programmation hantée. Concours de fantômes dans la console fin Fevrier

**Rao** · 06/03/2016, 18h03

ok super, merci pour l'explication !

T'façon en guise de pénitence pour mon mauvais classement je vais apprendre java et si je fais pire encore par la suite j'apprendrai php et je descendrai un à un les échelons de la déchéance du code

**rOut** · 06/03/2016, 20h06

Next contest : https://www.codingame.com/contests/smash-the-code

Purée, bon ben plus qu'a attendre le classement final. https://www.codingame.com/leaderboar...9d41618620a89c

J'ai réussi à gratter plein de places sur la fin, mais je sais pas si c'est vrai ou pas

**rOut** · 06/03/2016, 21h46

https://www.codingame.com/replay/85209144

Le tour 110 c'est chaud, le runner jaune esquive subtilement une attaque en tenaille, mais l'autre décide de tirer avantage et en profite pour propulser l'un de ses pods sur le CP suivant de jaune...

- - - Mise à jour - - -

Pour moduler un peu ce que j'ai dit au dessus, tous les mecs du top 10 ou quasiment sont partis sur une selection des coups à jouer à l'aide d'une algorithme de sélection génétique. En gros ils génèrent n séquences de coups aléatoires, gardent une partie des meilleurs, font muter certains coups dans la séquence, mélangent d'autres ensemble, et gardent les meilleures, etc etc...

Tout est dans la définition de "meilleure" ensuite, dans les fonctions d'évaluation, dans la qualité de la prédiction des coups ennemis et de la prédiction des mécanismes du jeu.

**Rao** · 06/03/2016, 23h03

oui j'ai lu ça sur irc
me suis inscrit au suivant on verra ce que c'est, mais je commence à prendre le coup après 1 an de code lol
va falloir que je fasse des recherches sur les algos que tu as détaillés

**Rao** · 07/03/2016, 07h28

Bon j'ai limité la casse de mon point de vue.
Je suis dans le premier tiers (on se rassure comme on peut

)

**Naity** · 07/03/2016, 07h43

GG pour ton top 1% r0ut.

J'ai aussi "limite la casse" avec mon top 500 (ou top 20%) mais c'est pas brillant non plus '^^

Et foudge, ca s'est joue a un poil de cul entre nous deux

Rao, c'est quoi ton profil?

Je met l'OP a jour. Si j'ai oublie qq1, qu'il fasse signe

Coders Strike Back (27.02.2016 - 06.03.2016). Classement:

Spoiler Alert!

**ds108j** · 07/03/2016, 07h47

Pas encore sur les events.

La je me suis un peu emmêlé les pinceaux avec mes compteurs sur le puzzle Chuck Norris (le premier en facile). Faut que je continue à travailler dessus.

PS : Vous ne faites pas beaucoup de Python ! Suis-je le seul à utiliser ce langage ?

**Max_well** · 07/03/2016, 08h26

Bon, je finis dans le premier tiers avec le code du challenge San Francisco, je m'en sors pas trop mal :D
Bien joué les gens !

**rOut** · 07/03/2016, 08h51

Halala, GG à tout les participants en tout cas.

Je suis un tout petit peu triste parce que j'avais l'espoire de garder ma 20e place, mais les 100 matchs supplémentaire en ont décidé autrement. J'aurais pas dû utiliser autant de random peut être

**Naity** · 07/03/2016, 09h27

Envoyé par ds108j

PS : Vous ne faites pas beaucoup de Python ! Suis-je le seul à utiliser ce langage ?

J'y ai rapidement touché à l'IUT mais je me sens rapidement mal à l'aise devant les langages qui ne me demandent pas le type de donné quand je défini une variable (et les langages interprétés que je considère - à tort - comme de la magie noire

).

**Nattefrost** · 07/03/2016, 12h00

Envoyé par ds108j

Pas encore sur les events.

La je me suis un peu emmêlé les pinceaux avec mes compteurs sur le puzzle Chuck Norris (le premier en facile). Faut que je continue à travailler dessus.

PS : Vous ne faites pas beaucoup de Python ! Suis-je le seul à utiliser ce langage ?

C'est aussi mon langage favori, j'ai récemment trouvé un taf de webdev python/django. Ce qui explique aussi que j'aie pas joué à codingame depuis un moment

. Sinon je fais aussi du c#, lua (modding) ainsi que perl (des scripts cgi quick n dirty). A l'inverse de Naity les langages à typage statique m'embêtent, j'ai toujours l'impression -à tort également- que le compilo est là pour me ralentir.

**Rao** · 07/03/2016, 12h42

@Naity :
https://www.codingame.com/profile/7d...9b2d8021486711
Bravo à tous, contrairement à max_well heureusement que je n'ai pas réutilisé le code de sf.

**Naity** · 07/03/2016, 13h26

Envoyé par Rao

@Naity :
https://www.codingame.com/profile/7d...9b2d8021486711
Bravo à tous, contrairement à max_well heureusement que je n'ai pas réutilisé le code de sf.

Je ne vois pas de quoi tu parles

Je t'ai ajoutè à l'OP ainsi que dans les classements des deux events

- - - Mise à jour - - -

Envoyé par Nattefrost

A l'inverse de Naity les langages à typage statique m'embêtent, j'ai toujours l'impression -à tort également- que le compilo est là pour me ralentir.

Les compilos sont tes amis, il faut les aimer aussi

- - - Mise à jour - - -

Envoyé par Nattefrost

C'est aussi mon langage favori, j'ai récemment trouvé un taf de webdev python/django.

Mon favori, c'est LabVIEW, mais il est pas supporté par le site

**rOut** · 08/03/2016, 21h13

Haaan c'est trop bien la sélection génétique, je viens de torcher Mars lander level 3 sans même avoir à réfléchir. Il suffit d'un modèle correct de la simulation, d'une fonction de comparaison de solutions (super facile à écrire !), paf tu rentres ça dans une boucle générique et yop là ça marche tout seul!

**TarteAuxFleurs** · 08/03/2016, 21h17

Envoyé par rOut

Haaan c'est trop bien la sélection génétique, je viens de torcher Mars lander level 3 sans même avoir à réfléchir. Il suffit d'un modèle correct de la simulation, d'une fonction de comparaison de solutions (super facile à écrire !), paf tu rentres ça dans une boucle générique et yop là ça marche tout seul!

C'est à dire ? Tu testes N solutions et tu gardes la meilleure ?

**Møgluglu** · 08/03/2016, 21h33

Envoyé par rOut

Haaan c'est trop bien la sélection génétique, je viens de torcher Mars lander level 3 sans même avoir à réfléchir. Il suffit d'un modèle correct de la simulation, d'une fonction de comparaison de solutions (super facile à écrire !), paf tu rentres ça dans une boucle générique et yop là ça marche tout seul!

T'as plus qu'à appliquer la selection génétique au code et tester automatiquement les solutions sur le site, et tu auras un programme qui code à ta place.

**rOut** · 08/03/2016, 21h51

Ouais la programmation génétique c'est encore autre chose, j'ai des problèmes concrets où l'essayer, mais c'est juste un peu plus chiant à écrire (genre faut préparer un arbre d'opérations à combiner et tout...)

(click droit fullscreen pour voir la vidéo, on voit 1/1000 des solutions explorées en gris, et en vert quand on en trouve une qui ne se crashe pas)

- - - Mise à jour - - -

Envoyé par gbip

C'est à dire ? Tu testes N solutions et tu gardes la meilleure ?

Ouais, je prend N solutions plus ou moins random, je fais des enfants (éventuellement mutants) en les croisant entre elles, je garde les N meilleures, je rince et je répète.

- - - Mise à jour - - -

Là, ma solution c'est la suite de commandes (angle, thrust) qu'il faut sortir pour résoudre le problème. Enfin plus précisément, la suite de (dangle, dthrust) puisque qu'on ne peut bouger que de ±15° et de ±1 thrust par turn. Initiallement, je pars d'une solution ou je ne fais rien pendant autant de tours qu'il faut pour me crasher, et de 19 autres solutions randoms de tailles diverses (la longueur dépend du temps mis pour se crasher).

Je mélanges et je secoues pendant 80ms à chaque tour, et je garde la meilleure (celle qui se crashe le plus pres de la cible, ou encore mieux qui ne se crashe pas et qu'a le plus de fuel).

Je recommence à chaque tour en repartant de la dernière solution trouvée, moins le tour qui vient de se passer.

Pour les enfants, ils apparaissent avec une certaine proba et je prends deux solutions random, je coupe à un endroit random et je prend le début de l'une avec la fin de l'autre. Chaque enfant va ensuite muter, c'est à dire que quelques steps sont ajustées aléatoirement. Je complète avec des actions random ou bien je coupe suivant le temps mis pour se crasher.

**Naity** · 08/03/2016, 22h06

C'est beau

Tu construit ca comment?

**rOut** · 08/03/2016, 22h21

Ben je ne sais pas trop quelle est ta question, mais disons:

Si T est mon type de solution, j'ai besoin de trois fonctions:

Code:

T make_random()
T make_mutant(T)
T make_child(T, T)
bool is_better(T, T)

Et après je les utilise dans une fonction générique qui fait ce que j'ai décrit au dessus.

J'ai juste à mettre à jour mes quatre fonctions suivant le problème à résoudre et c'est réglé.

**Foudge** · 09/03/2016, 01h16

Et pour ta vidéo ?

**rOut** · 09/03/2016, 08h47

Ben je dessine avec cairo dans une fenêtre pendant que mon programme tourne et j'ai fait un screencast avec GNOME 3... rien de magique pour le coup

**ducon** · 09/03/2016, 08h57

Envoyé par ds108j

PS : Vous ne faites pas beaucoup de Python ! Suis-je le seul à utiliser ce langage ?

Non non, j’utilise Python moi aussi.

**TiNitro** · 09/03/2016, 13h43

Ouais, je me disais bien qu'il faudrait que je passe à un truc dans ce genre, parce que mon heuristique à la mano, j'en ai déjà un peu bavé pour le Mars niveau 2, alors clair que je mettrais des plombes pour le niveau 3.

rOut, Tu mesures comment la distance ? c'est le sujet, si on veux pouvoir évaluer suffisamment de solutions, de ne pas passer trop de temps à calculer cette distance...

**rOut** · 09/03/2016, 14h27

Quelle distance ? La distance entre le point de crash et la zone d’atterrissage ?

Je calcule la trajectoire complète, jusqu'à intersection avec un segment de la surface, et ensuite je mesure la distance en ajoutant la distance du point d'intersection à un des points de la surface, plus les longueurs des segments de la surface de ce point jusqu'à un des points délimitant de zone d'aterrissage.

C'est clairement gourmand (~11µs par trajectoire en moyenne en début de simulation), mais ça passe quand même la plupart du temps, c'est ça qui est fort.

Après j'ai pas cherché à optimiser cette partie là, et ça doit pouvoir se faire beaucoup mieux.

**TarteAuxFleurs** · 09/03/2016, 14h31

Moi j'ai pas compris ta démarche... Tu fais tout le calcul de trajectoire en local, c'est ça ? Mais après tu sors quoi ? Un fichier compilable avec une suite d'instruction que tu fous dans le truc codingame et c'est tout ?
Ou tout les calcules sont fait dans l'IDE codingame ?

**rOut** · 09/03/2016, 15h05

Ben non tous les calculs sont faits dans l'IDE codingame.

Après j'ai aussi une version purement locale, qui utilise le code de prédiction pour calculer l'état que codingame est censé me donner sur l'entrée standard et qui me permet de faire ma vidéo et de tester avec des infos de debug que mon système marche bien.

- - - Mise à jour - - -

En gros j'ai un code comme ça

Code:

void main() {
  cin >> parametres_initiaux;

  auto etat_courant = {};
  cin >> etat_courant;

  while (true) {
#ifndef CODE_EN_LOCAL
    cin >> etat_courant;
#else
    etat_courant = prediction(etat_courant);
#endif

    auto actions = calcule(etat_courant);

#ifndef CODE_EN_LOCAL
    cout << actions;
#else
    dessine(actions);
#endif
  }
}

Et j'ai qu'a définir CODE_EN_LOCAL à la compilation pour faire une version locale avec dessins de debug.

J'aurais aussi pu écrire un programme qui fait le boulot de l'exécuteur de codingame et le faire tourner pour qu'il communique les nouveaux états de la même manière que sur codingame, mais c'était plus simple d'avoir tout le code dans le même fichier source.

**ds108j** · 09/03/2016, 15h27

Je viens de finir Chuck Norris, je m'attaque au type MIME.

**Naity** · 09/03/2016, 19h12

J'ai trouve ca sur le fofo officiel, ca peut etre interressant:

https://docs.google.com/document/d/1...h.z6ne0og04bp5

**TarteAuxFleurs** · 09/03/2016, 20h55

Envoyé par rOut

Ben non tous les calculs sont faits dans l'IDE codingame.

Après j'ai aussi une version purement locale, qui utilise le code de prédiction pour calculer l'état que codingame est censé me donner sur l'entrée standard et qui me permet de faire ma vidéo et de tester avec des infos de debug que mon système marche bien.

- - - Mise à jour - - -

En gros j'ai un code comme ça

Code:

void main() {
  cin >> parametres_initiaux;

  auto etat_courant = {};
  cin >> etat_courant;

  while (true) {
#ifndef CODE_EN_LOCAL
    cin >> etat_courant;
#else
    etat_courant = prediction(etat_courant);
#endif

    auto actions = calcule(etat_courant);

#ifndef CODE_EN_LOCAL
    cout << actions;
#else
    dessine(actions);
#endif
  }
}

Et j'ai qu'a définir CODE_EN_LOCAL à la compilation pour faire une version locale avec dessins de debug.

J'aurais aussi pu écrire un programme qui fait le boulot de l'exécuteur de codingame et le faire tourner pour qu'il communique les nouveaux états de la même manière que sur codingame, mais c'était plus simple d'avoir tout le code dans le même fichier source.

Ok, merci bien

**rOut** · 09/03/2016, 22h30

Tiens ils ont rajouté le Rust dernièrement

Discussion: Codingame - La programmation hantée. Concours de fantômes dans la console fin Fevrier

Outils de la discussion

Règles de messages