Tron battle : le debrief de ThomasNzO

STAY CONNECTED, FOLLOW CODINGAME NOW
Bonjour,
Comme prévu, je vais vous dévoiler la stratégie qui ma permis de rivaliser avec les meilleurs joueurs du concours TRON de Codingame.
Je vais essayer de bien détailler mes propos pour que cela soit accessible même au moins geek d'entre nous ;)


Préambule

Pour maximiser les performances de mon algorithme, j'ai immédiatement décidé de travailler avec des vecteurs (tableaux) le plus souvent possible. Je me suis interdit tout utilisation d'objets complexes de type Liste ou encore de classe custom pour :
  •  Limiter l'allocation mémoire avec l'opérateur new excessivement couteux pour ce type de problème.
  •  Accélérer les accès mémoires.
Pour exemple, toutes les listes / piles de mon algorithme sont des vecteurs 1D à taille fixe définie à l'initialisation, accompagnées d'un curseur indiquant la position de la listes / piles.
  • L'allocation mémoire est faite une fois.
  • Les espaces mémoires sont contiguës.
  • Mais, une grande quantité de mémoire est souvent inutilisée.
 Toujours dans un soucis de performance, j'ai préféré limiter la récursivité et utiliser le pendant itératif. Le code perd en lisibilité mais au profil d'une diminution du temps d'exécution. Ceci est surtout vrai pour les routines qui sont souvent sollicitées (comme l'heuristique de l'algorithme de recherche que nous verrons plus tard).
  

Stratégie

J'ai organisé ma stratégie en 3 phases :
- Phase 1 : Définition du contexte de recherche
Cette première phase permet d'initialiser la recherche du meilleur coup (ou du moins ce que j'aurais défini comme meilleur coup ;) ). Le contexte de recherche est toujours différent selon la situation de jeu. Par exemple le nombre de survivants, le nombre de joueurs enfermés, etc ...
- Phase 2 : Calcul des solutions jusqu'à X millisecondes
C'est le cœur de l'algorithme. Notre bot a de 0 à 4 choix possibles pour le prochain coup; cette phase va essayer d'évaluer chacune de ces possibilités pour pouvoir les comparer.
 - Phase 3 : Choix de la solution et affinage
Une fois les différentes possibilités de coup évaluées, il va falloir en choisir une. La chose se complique quand certains coups sont considérés égaux par la phase précédente;  il faudra tout de même en choisir une.

Phase 1 : Définition du  contexte de recherche

J'étudie tout d'abord la situation pour chacun des joueurs :
est-il enfermé ? C'est à dire, existe-t-il des cases qui sont accessibles par lui et par un autre joueur ?
- S'il est enfermé, à combien de case a-t-il accès ? Ca ne représente pas le nombre de coup max du joueur, mais je sais qu'au delà le joueur sera forcément mort si personne d'autre ne meurt avant lui. (J'appellerais cette information "sa vie" pour la suite).
- S'il n'est pas enfermé, combien de case contrôle-t-il ? Une case contrôlée est une case à laquelle le joueur peut avoir accès avant tout autre joueur.
A quelle distance est-il de moi ? Je ne prend pas la valeur de Manhattan (ou vol d'oiseau) mais la distance en considérant les murs déjà en place.
Avec un algorithme itératif, il est possible de récupérer toutes ces informations. Voici une illustration de ce que cela donne :

Ces informations récupérées, je vais pouvoir construire mes hypothèses de recherche.

Choix des joueurs "A simuler" pour la phase 2

Je vais choisir l'ensemble des joueurs que je vais considérer pour ma phase 2. Pour cela, je vais considérer uniquement les joueurs qui ne sont pas enfermés. Pour les autres, je les exclu de ma recherche et j'utiliserai uniquement l'information de "leur vie" dans la phase 2 pour prendre en compte leur mort future.

Choix de ma cible

Pour évaluer mes coups, je me focaliserai sur un joueur: le joueur le plus proche de moi. Après plusieurs implémentations, j'ai constaté qu'il était important de prendre en compte le joueur le plus dangereux. J'ai défini la dangerosité par la distance entre lui et moi. Je pense qu'il doit être possible d'avoir une définition plus précise de la dangerosité mais cela me convenait bien.

Choix de ma stratégie

Dans les dernières heures du concours, j'ai implémenté un système de mode de jeu qui me permet de changer la façon d'évaluer mes coups en fonction de la situation :
  • - Si le joueur cible contrôle plus de cases que moi, alors je vais me défendre.
  • - Si le joueur cible contrôle moins de cases que moi, alors je vais l'attaquer.
Nous verrons plus tard comment cela se traduit.
Me voila paré pour la phase 2 :)

Phase 2 : Calcul des solutions jusqu'à X millisecondes

 Mes  quelques souvenirs d'étudiant m'ont rappelé un algorithme de recherche en profondeur pour des jeux au tour par tour à deux joueurs : l'algorithme minmax.
J'ai donc implémenté cette recherche en essayant de l'adapter à N joueurs. Je n'entrerai pas dans le détail de l'algorithme minmax (http://fr.wikipedia.org/wiki/Algorithme_minimax) mais plutôt sur l'heuristique (fonction d'évaluation d'une position) et sur les trois versions d'implémentations de l'algorithme de recherche, qui à chaque nouvelle mise dans l'arène m'ont fait gagner quelques places.

I - L'heuristique

Description

Pour rappel, l'heuristique est la fonction qui va me permettre d'évaluer une situation de jeu. Cela me permettra ensuite de les comparer entre elles et de les ordonnées. Pour imager l'utilisation de l'heuristique, prenons un exemple en se passant de l'algorithme minmax :
  • si je joue HAUT cela me donnera une situation de jeu J1. Le score de J1 par l'heuristique est s1.
  • si je joue BAS cela me donnera une situation de jeu J2. Le score de J2 par l'heuristique est s2.
Si s1 est supérieur à s2 alors je jouerais HAUT, et vice et versa.
Pour le calcul de l'heuristique, j'utilise le même principe que dans la phase 1: le contrôle de case par joueur.

Je suis le joueur bleu, et ma cible est le joueur orange (selon ma phase 1). Le joueur rouge est enfermé, alors je n'en tiens pas compte. Une fois le calcul des zones terminé, j'obtiens le score de tous les joueurs non enfermés et vivants (ici deux). C'est là qu'interviens le mode défini en phase 1 (pour rappel, attaque ou défense) :
  • Si je suis en mode attaque, alors la valeur de la situation de jeu est la différence entre mon score et le score du joueur cible.
  • Si je suis en mode défense, alors la valeur de la situation de jeu est égale à mon score.
Dans la situation ci-dessus, selon ma phase 1, je suis en mode attaque car pour la situation actuelle (la grille de droite) je contrôle plus de cases que mon joueur cible. Les valeurs des situations de jeu sont donc :
  • pour Haut, 30 - 7 = 23
  • pour Gauche, 28 - 9 = 21
Haut est donc "meilleur" que Gauche, selon mes estimations.
En mode défense, je ne tiens compte que de mon score car j'essaye de survivre le plus longtemps possible en espérant qu'une autre personne meurt avant moi, ou que ma cible actuelle me laisse tranquille et espérer trouver une cible plus faible.
Le mode attaque ou défense peut changer d'un coup à l'autre en fonction de l'évolution de la partie. Par exemple si je commence en mode défense et que ma cible s'éloigne de moi, je peux, quelques coups plus tard, avoir une nouvelle cible (un autre joueur est plus proche de moi) et cette fois ci avoir l'avantage sur elle (contrôle de case). Je passerai donc en mode attaque pour tenter de détruire ma nouvelle cible.

Prise en compte des morts dans l'heuristique

J'en tenté de trouver une solution pour anticiper la mort des joueurs dans l'heuristique et après plusieurs essais, j'ai fini par opter pour cette règle :
Si on considère dans l'algorithme de calcul de zone de l'heuristique qu'un pas représente le moment où l'algorithme a effectué un mouvement pour chaque joueur (dans l'exemple ci-dessus, le nombre de pas final pour Haut est 11 et le nombre de pas final pour Gauche est 9), alors :
Dans le calcul des zones, si le pas actuel est supérieur à la vie d'un des joueurs enfermés, alors on supprime le joueur et tout ses murs sur la situation de jeu en cours de calcul.
Cela permet de simuler la libération de l'espace et d'inclure ce nouveau potentiel dans le score de chacun. (En faite l'implémentation est un peu plus complexe car je dois "réactiver" des positions considérées fermées pour un joueur, et ce conditionnellement selon certaines règles liées à des distances).

Implémentation partielle des "cases à choix"

Comme l'a soulevé Manwe dans son article, certaines cases sont soumises à un choix. Toutes les cases d'une zone de contrôle ne sont en réalité pas toutes accessibles, car emprunter un chemin peut fermer l'accès à d'autres cases.
C'est une chose que j'ai constaté trop tard dans le concours et après plusieurs tentatives sur papier à J-3 de la date de fin, j'ai laissé tomber.
Cependant j'avais déjà implémenté ceci, qui est l'application de la règle ci-dessus mais seulement au premier coup :
Je considère chacun des mouvements possibles comme des groupes (Ici trois groupes, Haut, Droite et Bas).  La valeur d'un groupe est le nombre de cases accessibles par le mouvement initial + le score des groupes qui lui sont connectés.
Ici :
  • pour Haut : Score = Groupe 1 = 2
  • pour Droite : Score  =  Groupe 2 + Groupe 3 (car connecté) = 26
  • pour Bas  : Score  =  Groupe 3 + Groupe 2 (car connecté) = 26
Pour calculer mon score final, je prend le max des scores des groupes. Mon score ici sera donc 26 (et non 28 si je gardais mon calcul précédent).
Je procède de même pour tout les joueurs.
C'était un début de l'algo de Manwe :p

Optimisation de l'heuristique

Dans les derniers jours du concours j'ai pris du temps pour optimiser mon heuristique avec quelques astuces (surtout au niveau des allocations mémoires) et j'ai fini pas passer de 110 000 ms à 30 000ms.



II - Implémentation de l'algorithme de recherche, minmax

Version à profondeur fixe
Dans cette première version j'ai implémenté minmax avec une profondeur fixe (égale à 5 si je me souviens bien) pour parcourir l'arbre des coups possibles. Voici une représentation graphique de l'arbre et de son parcourt :
Dans cet exemple à 4 joueurs, le joueur 3 est enfermé donc il est exclu de l'arbre de recherche. L'arbre représente une profondeur de 4.
On sent bien que le choix de la profondeur influe énormément sur le temps de réponse. D'autant plus que pour cette implémentation de recherche en profondeur, on ne peut tirer aucune conclusion tant que toutes les possibilités n'ont pas été parcourues.
Autrement dit, si au bout des 100ms le calcul n'est pas terminé, alors on ne peut pas prendre de décision. Il faut donc fixer une profondeur assez faible pour être sûr que l'algorithme répondra dans les temps.
Cependant le temps d'exécution de l'algorithme de recherche dépend avant tout de l'état de la partie. En début de partie, une recherche à profondeur 4 peut prendre 50ms et en fin de partie que 2ms. (Moins de cases accessibles, moins de possibilités => arbre plus petit).
A cette époque j'avais ajouté l'élagage alpha-beta dont je vous passerai les détails (car pas présent dans la solution finale) http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta.

Version à profondeur modulable

Cette deuxième version est la même que la première, à la différence que pour chaque nouveau coup, je calcul la profondeur de recherche en fonction du temps que j'ai passé à calculer pour le coup précédant :
  • Si cela a été rapide, alors j'incrémente la profondeur.
  • Si cela a été long (ou pire, n'a pas eu le temps de calculer), alors je décrémente la profondeur.
De ce fait, la profondeur se module en fonction de la situation de jeu. Cependant la recherche pour un coup N se fait toujours à profondeur fixe !

Version de recherche en largeur

J'ai fini par laisser tomber la recherche en profondeur pour une recherche en largeur. Le principe est plutôt simple :
Je fais une recherche à profondeur 1, et j'obtiens une solution (du moins une évaluation de toutes les positions de la profondeur). Si j'ai le temps de faire une nouvelle recherche à une profondeur 2, alors je la fais, et ainsi de suite.
Les grande différences avec l'implémentation précédente :
- Il faut appliquer l'heuristique sur tous les nœuds de l'arbre, et non sur les feuilles uniquement dans la version précédente.
- Il faut pouvoir conserver l'état d'une position pour pouvoir y revenir et calculer les états suivants. En effet dans l'algorithme de parcourt en profondeur, il suffisait d'appliquer le coup inverse pour revenir à l'état précédent. En terme de mémoire, une seule grille suffisait. Pour cette nouvelle implémentation, toutes les grilles de la profondeur courante doivent être conservées pour pouvoir y revenir lors de la profondeur suivante.
Cet algorithme permet donc de donner une réponse en utilisant 100% du temps imparti. (Dans les fait j'utilisais 70ms pour les raisons invoquées sur le forum). Si je suis à la profondeur N et que je n'ai plus le temps, j'ai au moins une solution pour la profondeur N-1.
A la fin de la phase 2, je peux comparer mes coups entre eux et déterminer ceux qui sont bon et mauvais (en fonction de leur score). Cependant il arrive souvent que certains coups soient égaux. C'est ce qui va impliquer la phase 3.

Remarque:
Pour discriminer les coups égaux, j'aurais pu inclure de nouveaux paramètres dans l'heuristique pour les différencier (par exemple les critères de sélection de la phase 3). Mais j'ai tendance à penser qu'en additionnant des choux et des bananes on perd en cohérence et on se retrouve à travailler avec des coefficients multiplicateurs sur différents critères... ce qui amène parfois et des solutions aberrantes. Car il ne faut pas oublier que l'heuristique se traduit par une et une seule valeur.
J'ai donc préféré travailler en deux temps pour ne pas mélanger toutes les notions.

 

Phase 3 : Choix de la solution et affinage

Si j'obtiens plusieurs coup "meilleurs" et égaux entre eux alors :

Pass 1 : Non fermeture des espaces potentiels

Pour chacun de ces coups, je regarde les cases contigus à ma nouvelle position. Si l'une d'entre elles appartient à un joueur qui va mourir avant moi (c'est à dire enfermé avec une vie plus faible que la mienne) alors j'exclu ce coup des coups possibles.

Pass 2 : Maximiser la compacité de mes murs

Pour chacun des coups restants, je compte le nombre d'espace occupé autour de ma nouvelle position et je choisi celle qui maximise ce nombre. Ainsi je m'assure de ne pas générer un "gruyère" et de maximiser mes chances de parcourir le plus de cases possible.

Je crois que j'ai fait le tour :)
Je pense qu'il me manque vraiment l'algorithme qui permet de calculer le nombre de cases réellement accessibles en fonction des points pivots (des choix à faire). Je l'aurais intégré à plusieurs endroits dans ma solution.
J'espère que j'ai su être clair ;)
a+
Thomas Nicoullaud

Aucun commentaire

Enregistrer un commentaire