Back to the Code: Les stratégies gagnantes de Recar et Olaf69

STAY CONNECTED, FOLLOW CODINGAME NOW

Back to the Code c'est fini ! Nous avons passé un super moment à regarder les différents replays et à étudier les stratégies de chacun. Nous avons découvert des idées géniales et nous espérons que vous avez apprécié autant que nous cette édition ! 


Recar et Olaf69 ont tous deux mis en place des stratégies pertinentes qui les ont propulsé en haut du leaderboard: vous pouvez découvrir leurs ingrédients spéciaux ici.

Recar:

"1. Je cherche la meilleure zone à remplir en comptant le nombre de cellules neutres à l'intérieur et le nombre de cases à entourer. 
2. Je vérifie si les zones alentour me permettent de remplir des cases plus rapidement qu'en créant un rectangle et j'en déduis la solution optimale.
Pour une partie à deux joueurs, je vérifie quel rectangle mon opposant veut entourer. Si celui-ci est meilleur que le mien, alors je me déplace à l'intérieur de cette zone."

Olaf69:

" Je viens d'uploader sur GitHub le repository git que j'ai créé pour le contest, on peut notamment y trouver la liste de mes commentaires de commit.

Globalement, mon IA est implémentée autour d'un algo de recherche en profondeur dans un arbre. Je me suis dit que pour être efficace il fallait que j'estime à chaque tour les performances d'un maximum de trajets possibles, dans la limite de 100ms.
L'arbre théorique du jeu étant particulièrement grand (de l'ordre de 5^nbPlayer^350 noeuds), il a fallu trouver quelques règles pour limiter les états possibles. A la fin de l'épreuve, voici quelles étaient mes règles d'expansion de l'arbre:
- s'il y a au moins une case neutre autour, je tente chaque case neutre, mais on ne va pas sur une case non-neutre
- s'il n'y a pas de case neutre autour, je m'éloigne en faisant en sorte de ne jamais explorer 2 chemins différents vers une même case non-neutre
En dernier recours, si je n'ai pas trouvé de chemin permettant d'augmenter le score, je vais vers la case neutre la plus proche. Ça peut arriver même s'il reste des cases neutres sur la grille, à cause de ma façon d'estimer le chemin des concurrents.

A chaque expansion, il faut aussi que j'estime le déplacement le plus probable de chaque concurrent. Idéalement, j'aurais aimé implémenter un algo de type alpha-beta, qui consiste a évaluer chaque déplacement possible des concurrents à chaque expansion et à évaluer chaque état, mais c'était complètement irréaliste vu la démultiplication du nombre d'états que ça aurait généré (et les 100ms pour calculer tout ça!!)... du coup je me suis rabattu sur une solution beaucoup plus simple (mais risquée) qui consiste à déplacer les concurrents de façon déterministe suivant ces règles:
- si la case devant lui est neutre, il y va (ça implique de savoir dans quelle direction il va)
- sinon, si son dernier tournant était à droite (resp. gauche), il essaiera d'aller à droite (resp. gauche) sur une case neutre, sinon à gauche (resp.droite) sur une case neutre
- s'il n'y a pas de case neutre autour, il va vers la case neutre la plus proche
Concrètement avec ces règles je suppose que les concurrents n'auront pas d'attitude agressive: ils chercheront d'abord à faire des points avant de venir m'embêter.

A tout début j'avait implémenté une stratégie beaucoup plus défensive, en supposant que les concurrents se déplaçaient récursivement sur TOUTES les cases auxquelles ils avaient accès. ce qui me permettait d'évaluer uniquement des formes que j'était certain de pouvoir fermer, mais qui étaient bien plus petites (et donc moins intéressantes) que ce que je fait avec l'algo final.

En fait, avec ces règles d'expansions j'était encore beaucoup trop limité par le temps: je n'arrivais à estimer que des chemins de faible profondeur (de l'ordre de 10-12, environ 60000 nœuds). 12 cases c'est un peu faible pour former un grand rectangle sur une grille de 20x35! En fait ça me faisait faire des chemins en forme d'escargot!

Une idée qui m'a réellement fait progresser c'est limiter encore les chemins possibles en faisant des pas de 3 cases (uniquement sur des cases neutres). La j'ai commencé à évaluer des chemins de 30 cases voire plus.
Si j'explore tout l'arbre (courant en fin de partie), alors j'essaie avec des pas de 2 cases, puis des pas de 1 case.

Une autre problématique principale a été d'évaluer chaque chemin. Au début j'avait un critère simple: le nombre de points. Mais ce n'était pas très satisfaisant, voilà un exemple de grille illustrant pourquoi:
  00000000001111111111222222222233333  
  01234567890123456789012345678901234  
 +-----------------------------------+  
0|xxxxxxxxxxxx................ooooooo|0    o: cells I own
1|xxxxxxxxxxxx.               o     o|1    O: were I am
2|xxxxxxxxxxxx.              oo     o|2    .: Best path I computed
3|xxxxxxxxxxxx.              o      o|3
4|xxxxxxxxxxxx.              o      o|4    Problem: I won't close a shape for another 22 turns...
5|xxxxxxxxxxxx..Ooooooo      o      o|5    
6|xxxxxxxxxxxx        oo     o      o|6
7|xxxxxxxxxxxx         o    oo      o|7
8|xxxxxxxxxxxx         ooo          o|8
9|xxxxxxxxxxxx           oo         o|9
10|xxxxxxxxxxxx            o         o|10
11|xxxxxxxxxxxx            o         o|11
12|        x  x            o         o|12
13|           x            o         o|13
14|           x            o ooooooooo|14
15|           x            ooo        |15
16|           x                       |16
17|           x                       |17
18|           x                       |18
19|     Xxxxxxx                       |19
 +-----------------------------------+  
  00000000001111111111222222222233333  
  01234567890123456789012345678901234  

Avec le nombre de points uniquement comme critère d'évaluation, entourer une zone toujours plus grande est toujours plus intéressant. Mais du coup on fini par se faire avoir pas les concurrents. J'ai essayé plusieurs formules:
- Nombre de points additionnels / nombre de pas restants --> fermer une petite zone rapidement devient trop intéressant
- Nombre de points total / nombre de pas total --> permet d'optimiser un peu les formes générées, mais celles-ci restent trop grandes
Du coup j'ai finalement opté pour un compromis:
  (Nombre de points additionnels + 20) / (Nombre de pas restants + 20)

Sinon, il y a aussi quelques optimisations qui m'ont permis d'avancer, comme par exemple
- limiter au maximum les appels à la fonction de remplissage.
- optimiser la façon de calculer le score
- optimiser la fonction de recherche de la case neutre la plus proche
- gérer efficacement l'allocation mémoire pour les nœuds de l'arbre de recherche

Et je regrette de ne pas avoir eu le temps d'implémenter toutes mes idées, notamment d'exploiter le retour dans le passé !

Un grand merci à eux pour leur contribution !




Aucun commentaire

Enregistrer un commentaire