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

**Naity** · 29/02/2016, 11h44

Envoyé par gbip

Tu gères comment les cas où ton vecteur est derrière le vecteur destVect ? (quand tu es en train de reculer par rapport à l'objectif)

Je le gere pas. Je ne compense que si l'angle entre speedVect et DestVect est +-90° (ce qui est inutile car au dessus de 18° ca sert a rien). En théorie, tant que l'angle est de plus de 18°, il n'y a riena compenser.

**ds108j** · 29/02/2016, 11h59

Hop :
https://www.codingame.com/profile/0f...035b5478591331

**Naity** · 29/02/2016, 12h01

Envoyé par ds108j

Hop :
https://www.codingame.com/profile/0f...035b5478591331

Thanks

**TarteAuxFleurs** · 29/02/2016, 12h01

Envoyé par Naity

Je le gere pas. Je ne compense que si l'angle entre speedVect et DestVect est +-90° (ce qui est inutile car au dessus de 18° ca sert a rien). En théorie, tant que l'angle est de plus de 18°, il n'y a riena compenser.

Tu traduis bien cette inégalité là par le booléen suivant ?
-90 <acos(dot(destVect, speedVect) <90
Je deviens un peu maboul, quand j'affiche les infos de mes pods, elles ont un tour de retard avec ce que m'affiche le débug

**Naity** · 29/02/2016, 12h09

Envoyé par gbip

Tu traduis bien cette inégalité là par le booléen suivant ?
0 <acos(dot(destVect, speedVect) <1
Je deviens un peu maboul, quand j'affiche les infos de mes pods, elles ont un tour de retard avec ce que m'affiche le débug

En version réduite, ca ressemble à ca:

Code:

class Pod
{
    private const int MINDIST ... ;
    private const int MINANGLE ... ;
    private const int MAXANGLE ... ;
    
    private Position pos;
    private List<Position> checkpointsList = new List<Position>();
    private Vector speedVect;
    private Vector destVect;
    private double vectAngle = -1;
    private string goalX = "0";
    private string goalY = "0";
	
    {...}
    
    private struct Position
    {
        public int X;
        public int Y;
        public Position(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
    
    private struct Vector
    {
        public int X;
        public int Y;
        public Vector(int x, int y)
        {
            X = x;
            Y = y;
        }
    }

    public Pod (int check, int lap)
    {...}
    
    
    public void UpdatePos(int x, int y, int vx, int vy, int nextCp, int angle)
    {...
        vectAngle = CalculateAngle(destVect, speedVect);
    }
      
    public void ComputeDirection()
    {...
        else if ((vectAngle > MINANGLE | vectAngle < -MINANGLE) & vectAngle < MAXANGLE & vectAngle > -MAXANGLE)
        {
            Position compensation = CalculateCompensationPosition();
            goalX = compensation.X.ToString();
            goalY = compensation.Y.ToString();
        }
    }
    
    private double CalculateAngle(Vector vect1, Vector vect2) //calculate the angle between the speed vector and the destination checkpoint
    {
        double sin = vect1.X * vect2.Y - vect2.X * vect1.Y;  
        double cos = vect1.X * vect2.X + vect1.Y * vect2.Y;
        return Math.Atan2(sin, cos) * (180 / Math.PI);
    }
    
    private Position CalculateCompensationPosition()
    {
        double k = 1.0*(speedVect.X*destVect.X + speedVect.Y*destVect.Y)/(destVect.X*destVect.X + destVect.Y*destVect.Y);
        Vector dotProduct = new Vector((int)Math.Round(k*destVect.X), (int)Math.Round(k*destVect.Y));
        
        int xDist = dotProduct.X - speedVect.X;
        int yDist = dotProduct.Y - speedVect.Y;
        Vector compensateVector = new Vector(speedVect.X + xDist*2, speedVect.Y + yDist*2);
        Console.Error.WriteLine("Vect[{0},{1}] is {2}° away from destination", compensateVector.X, compensateVector.Y, CalculateAngle(compensateVector, destVect));
        return new Position(speedVect.X + xDist*2 + pos.X, speedVect.Y + yDist*2 + pos.Y);
    }
}

**TarteAuxFleurs** · 29/02/2016, 12h11

Envoyé par Naity

En version réduite, ca ressemble à ca:

Code:

class Pod
{
    private const int MINDIST ... ;
    private const int MINANGLE ... ;
    private const int MAXANGLE ... ;
    
    private Position pos;
    private List<Position> checkpointsList = new List<Position>();
    private Vector speedVect;
    private Vector destVect;
    private double vectAngle = -1;
    private string goalX = "0";
    private string goalY = "0";
	
    {...}
    
    private struct Position
    {
        public int X;
        public int Y;
        public Position(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
    
    private struct Vector
    {
        public int X;
        public int Y;
        public Vector(int x, int y)
        {
            X = x;
            Y = y;
        }
    }

    public Pod (int check, int lap)
    {...}
    
    
    public void UpdatePos(int x, int y, int vx, int vy, int nextCp, int angle)
    {...
        vectAngle = CalculateAngle(destVect, speedVect);
    }
      
    public void ComputeDirection()
    {...
        else if ((vectAngle > MINANGLE | vectAngle < -MINANGLE) & vectAngle < MAXANGLE & vectAngle > -MAXANGLE)
        {
            Position compensation = CalculateCompensationPosition();
            goalX = compensation.X.ToString();
            goalY = compensation.Y.ToString();
        }
    }
    
    private double CalculateAngle(Vector vect1, Vector vect2) //calculate the angle between the speed vector and the destination checkpoint
    {
        double sin = vect1.X * vect2.Y - vect2.X * vect1.Y;  
        double cos = vect1.X * vect2.X + vect1.Y * vect2.Y;
        return Math.Atan2(sin, cos) * (180 / Math.PI);
    }
    
    private Position CalculateCompensationPosition()
    {
        double k = 1.0*(speedVect.X*destVect.X + speedVect.Y*destVect.Y)/(destVect.X*destVect.X + destVect.Y*destVect.Y);
        Vector dotProduct = new Vector((int)Math.Round(k*destVect.X), (int)Math.Round(k*destVect.Y));
        
        int xDist = dotProduct.X - speedVect.X;
        int yDist = dotProduct.Y - speedVect.Y;
        Vector compensateVector = new Vector(speedVect.X + xDist*2, speedVect.Y + yDist*2);
        Console.Error.WriteLine("Vect[{0},{1}] is {2}° away from destination", compensateVector.X, compensateVector.Y, CalculateAngle(compensateVector, destVect));
        return new Position(speedVect.X + xDist*2 + pos.X, speedVect.Y + yDist*2 + pos.Y);
    }
}

Merci, je vais chercher l'erreur dans mon code en comparant au tien, mais déjà, séparé les vecteurs des positions, c'est plutôt une bonne idée je trouve, je vais faire ça je pense

**Naity** · 29/02/2016, 12h58

Envoyé par gbip

Merci, je vais chercher l'erreur dans mon code en comparant au tien, mais déjà, séparé les vecteurs des positions, c'est plutôt une bonne idée je trouve, je vais faire ça je pense

https://en.wikipedia.org/wiki/Identi...programming%29

**ds108j** · 29/02/2016, 15h12

J'ai fait les 3 premiers "facile". En python. Pour le moment, ça va

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

Envoyé par Møgluglu

Vous avez cherché des solutions analytiques, pour avoir l'idée de la trajectoire optimale ?
Dans le cas où le vecteur accélération est libre mais de longueur constante (toujours au taquet), la trajectoire doit ressembler plus ou moins à une spline d'ordre 3, non ?
Et dans le cas où le changement d'angle est limité, c'est la dérivée de l'accélération qui est constante, ça doit faire passer à l'ordre 4. À la louche. Faut poser ça proprement, mais si c'est polynomial, alors il doit y avoir moyen de calculer la solution optimale (pour 1 pod tout seul, mais ça serait un bon début...).

En fait je ne vois pas pourquoi tu dis que la dérivée de l'accélération serait constante... Ni comment calculer la spline idéale (minimisant le temps pour faire un tour?) d'ailleurs.

**Naity** · 01/03/2016, 19h14

J'ai rajoute la fonction qui va tout me faire gagner: le generateur de message de taunt aleatoire

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

**Rao** · 01/03/2016, 22h29

Classe

C'est vrai que les messages c'est un bon moyen de s'amuser pour pas cher niveau code, surtout quand t'es une quiche comme moi

Chambrer le groupe de tête ça reste un plaisir de fin gourmet qu'on ne peut pas nous enlever

**ds108j** · 01/03/2016, 22h45

J'ai fini le premier exo sur Mars (en facile) après avoir joué avec les températures. Vous êtes largement plus balèzes que moi les gars !

**rOut** · 01/03/2016, 22h56

Envoyé par Rao

Classe

C'est vrai que les messages c'est un bon moyen de s'amuser pour pas cher niveau code, surtout quand t'es une quiche comme moi

Chambrer le groupe de tête ça reste un plaisir de fin gourmet qu'on ne peut pas nous enlever

Y'a de quoi parce qu'on n'est même pas foutus d'intégrer le top 50

**Naity** · 02/03/2016, 09h41

Envoyé par Rao

Chambrer le groupe de tête ça reste un plaisir de fin gourmet qu'on ne peut pas nous enlever

C'est tellement vrai

Ceci dit, j'ai bien fait attention à prendre un replay ou je met la misère à rOut (ca à mis du temps, le bougre à un algo bien ficelé).

- - - Mise à jour - - -

Envoyé par ds108j

J'ai fini le premier exo sur Mars (en facile) après avoir joué avec les températures. Vous êtes largement plus balèzes que moi les gars !

GG

On est pas (tous) balése. De mon côté j'ai réussi à galérer sur à peu près tous les faciles à l'époque

**rOut** · 02/03/2016, 09h51

Le bougre a surtout un vilain bug qui fait qu'un choix du meilleur parmi un tirage de n vecteurs d'accélération aléatoires est plus efficace qu'un recuit simulé (qui est censé converger plus rapidement vers une accéleration optimale).

**Naity** · 02/03/2016, 11h49

Envoyé par rOut

Y'a de quoi parce qu'on n'est même pas foutus d'intégrer le top 50

Je visais un Top 100 avant l'event, mais ca sera juste pas possible. D'une j'ai pas le temps, mais même si je l'avais, la niveau fait quand même très mal. Même le top 10% va être chaud à chopper.

**rOut** · 02/03/2016, 11h57

La strat gagnante semple clairement être celle qui consiste à utiliser l'un des pods en blocker pour ralentir l'adversaire. Après tout est dans l'efficacité du blocker... Chez moi il a tendance à faire du zèle et à bloquer mon autre pod

**Max_well** · 02/03/2016, 15h17

Bon, moi je pense que j'aurais pas le temps de bosser dessus cette semaine.
Have fun :D

**Hideo** · 03/03/2016, 16h14

Hop, je m'y suis mis tranquillement.
V'la mon lien pour l'OP : https://www.codingame.com/profile/30...c9394e34267031

J'ai du boulot

**Naity** · 03/03/2016, 19h01

Envoyé par Hideo

Hop, je m'y suis mis tranquillement.
V'la mon lien pour l'OP : https://www.codingame.com/profile/30...c9394e34267031

J'ai du boulot

Done

Ouelkaume

**rOut** · 04/03/2016, 21h38

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

Pour une fois que je gagne contre lui

Vous apprécierez les petites esquives !

**Naity** · 05/03/2016, 10h43

Envoyé par rOut

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

Pour une fois que je gagne contre lui

Vous apprécierez les petites esquives !

Joli! J'adore les petits "Biongs" et autres "Bing" avant collision!

**rOut** · 06/03/2016, 12h28

Allez dernière ligne droite

**Naity** · 06/03/2016, 12h48

Envoyé par rOut

Allez dernière ligne droite

Top 1%, on y croit

**rOut** · 06/03/2016, 13h03

C'est trop la misère, je change des trucs et ça n'a aucun effet sauf de me faire redescendre. Le classement bouge tellement avec les gens qui soumettent que c'est de la torture mentale de se voir 18e puis redescendre 30e quand ca se stabilise.

**Naity** · 06/03/2016, 13h22

Envoyé par rOut

C'est trop la misère, je change des trucs et ça n'a aucun effet sauf de me faire redescendre. Le classement bouge tellement avec les gens qui soumettent que c'est de la torture mentale de se voir 18e puis redescendre 30e quand ca se stabilise.

Ouais, je vois ca. J'ai essaye de changer quelques constantes pour remonter dans le top 500 (on se console comme on peut) mais c'est un peu le grand huit ce classement '^^

**rOut** · 06/03/2016, 13h34

C'est quoi ton algorithme en gros ? Tu accélères tes pods vers un point calculé en fonction de (position courante, vitesse courante, position du prochain checkpoint) ?

**Naity** · 06/03/2016, 14h06

Envoyé par rOut

C'est quoi ton algorithme en gros ? Tu accélères tes pods vers un point calculé en fonction de (position courante, vitesse courante, position du prochain checkpoint) ?

C'est ca. Acceleration rapide en compensant le vecteur vitesse, deceleration (vitesse 0) pour "glisser" en direction du point tout en commencent a s'aligner vers le point suivant. Les deux pods ont la meme strategie mais commecent avec 3 tours de decalage pour pas qu'ils ne se gene l'un-l'autre.

C'est basique, j'ai pas retouche au code du weekend dernier pour cause de semaine pas glop avec trop de taff.

**Rao** · 06/03/2016, 15h53

Purée c'est toujours aussi serré le classement? La moindre modif de code, la moindre baisse du perf et tu degringoles 50 places plus bas.
Au fait c'est un truc répandu les algos du top 10, les neural network?

**rOut** · 06/03/2016, 16h17

Ouais c'est toujours un peu serré, d'autant plus qu'il y a assez peu de match finalement, donc pas mal d'aléa dans le classement. Pour bien faire il faudrait laisser tourner pendant plusieurs jours pour stabiliser le tout.
A la fin du challenge ils rajoutent quand même 100 matchs supplémentaires sans modif possible.

Personne ne fait du neural network je crois. Jeff et pb en ont parlé et ont essayé mais je ne pense pas qu'ils aient utilisé ça pour finir.

En gros la stratégie la plus utilisée et la plus efficace pour ce genre de challenge ou il y a trop de coups possible à chaque tour pour tous les évaluer, et ou les deux joueurs jouent simultanément, c'est d'avoue une fonction qui donne une valeur de gain étant donné un coup joué, et de tenter de trouver le coup qui va maximiser le gain potentiel au tour courant. Pour ça, il faut définir cette fonction, et ensuite tu tires des coups potentiels aléatoirement et tu gardes celui qui donne le gain maximum. Mieux encore, tu tires aléatoirement une série de coups aléatoires et tu cherches la série qui maximise le gain potentiel.

En gros ici, par exemple, le gain pour un pod "coureur" serait la proximité du pod avec le checkpoint suivant, voire un bonus si l'on passe un checkpoint. On tire aléatoirement des trajectoires potentielles (soit un angle random au début et on suppose que l'on s'y colle pendant n tours, soit un point ciblé aléatoire, etc...) et on prédit l'avenir en calculant les états successifs sur les n tours, et en supposant également ce que les ennemis vont faire à partir de la situation initiale (par exemple continuer d'accélérer dans la dernière direction prise). On évalue la fonction de gain à chaque tour, on l'intègre sur l'ensemble des coups (par exemple avec une somme pondérée décroissant au fil des tours) et on garde le coup initial de la trajectoire qui donne le meilleur résultat.

Toute la subtilité consiste à définir une bonne fonction d'évaluation: quels critères retenir pour un runner, il faut qu'il passe les CP rapidement, mais pas qu'il reste bloqué si un pod ennemi s'interpose, ainsi qu'une bonne stratégie pour le choix des coups jouées : par exemple des trajectoires avec un angle et un thrust aléatoire à chaque tour simulé ne sont pas très réalistes et sans doute assez peu efficaces par rapport à des trajectoires ciblant un point initial et un thrust constant choisis aléatoirement pour chaque trajectoire.

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

Outils de la discussion

Règles de messages