[AI Masters] Rencontre avec Scarak: "J'ai eu le déclic quand j'ai vu mon bot réussir à faire des tâches simples, et apprendre"

3          

La programmation d'IA peut être un peu complexe d'approche pour ceux qui ne s'y sont encore jamais risqué. Beaucoup de développeurs hésitent à se lancer, et c'est dommage, car l'IA est probablement l'un des domaines les plus passionnants de la programmation. Pour vous aider à découvrir l'IA, nous avons décidé de donner la parole à des CodinGamers talentueux pour qu'ils vous parlent de leur vision du bot programming, et ce qui fait qu'ils sont passionnés d'IA. La série de billets de blog s'appelle "AI Masters". Aujourd'hui, on commence avec Darren Kent, AKA Scarak


"I think the greatest part of programming is the challenge in looking at a puzzle and finding a way to solve it. It is immensely gratifying when your code comes together and completes the task it was meant to". Darren graduated from a Bachelor in Computer Science at Dixie State University, Utah, in 2014. He has been programming for about 6 years now, but becoming a developer was not in his career path at first. The real trigger was when he took his first extra programming class at college, that lead him to discover that he loved to program. So he decided to switch to a CS degree. 

Darren discovered CodinGame when he was still fairly new to programming: "CodingGame definitely gave me a fun way to become a better programmer. It made it pretty easy to jump in and get going too. The IDE was simple and easy to use and the ability to choose what language I used was awesome! I quickly became more familiar with my programming languages and then I found myself trying to reinforce the algorithms that I had learned in my classes. I am a hands on learner so being able to take those algorithms and apply them to an actual use was not only fun, but it allowed me to see how they work even more clearly."

Learning by himself, experimenting, being thrilled by results, and persevering. Passion for coding was there to stay. Darren was in the second year of his CS degree when he turned to AI. "I had just finished my AI class and I was in love with the thought that I could make a bot learn, explore, and do simple tasks." What he learned from school was never enough so he had to turn to the Internet for new ideas on AI concepts... until he tried his first AI game on CodinGame. 

"The first thing I saw was the Tron Light Cycle Battles. I was excited to put my programming skills to the challenge and create a bot to combat other bots. Plus it was Tron, who doesn't love Tron Light Cycles?" he jokes. Even though it was his first time coding on a competitive level, he started to be obsessive with the competition, finding himself checking his scores hourly and constantly trying to improve his code. 



The hardest part in AI is probably doing the first step in uncharted territory. Darren's advice to beginners would be: "Just jump in and try it. There is nothing to lose, so there is nothing to fear. I would start with the most basic of AI you can come up with. Even if it is just moving the bot around the game board, that is great. From there, just add a bit more and more based on the challenge. At first don't worry about your score, just do your best. If you have extra time do some research and find some algorithms you want to try and improve your bot with. In between AI competitions I highly recommend doing the single player puzzles. They will help you hone your skills and give you a fun environment to do it in."

When he graduated, Darren found himself constantly on CodinGame trying to keep his skills fresh. "The platform is always being updated giving me more challenges and the interface is great. In the end, I feel my activity on CodinGame was a large contributor in getting the job I have today", he says. Darren is now a programmer for Deep Silver Volition, a video game development studio, doing what he loves. And he deserves it... So hats off, a thousand times!



Nous sommes 300 000 ! MERCI !

1          

Il y a un an, nous avons lancé la nouvelle version de CodinGame, la plateforme qui permet de coder et progresser en programmation à travers des jeux. Nous avions la conviction - et nous l'avons toujours ! - que la programmation doit être un plaisir pour tous. A présent, après plusieurs mois de travail acharné, d'innombrables gouttes de sueur mais encore plus de smileys heureux, on veut vous dire merci... En 12 mois, on est passés d'une poignée d'irréductibles fans à une communauté de plus de 300 000 développeurs dans 170 pays. Nous sommes tellement fiers d'être soutenus par vous tous, développeurs engagés et passionnés.

Alors, à chacun(e) d'entre vous :


Mais les (belles) choses ne font que commencer... Nous serons à San Francisco en Février prochain à la DeveloperWeek pour présenter un jeu d'Intelligence Artificielle spécialement créé pour la conférence. Ce jeu vous permettra de vous mesurer à des joueurs de tous les Etats-Unis dans une compétition en live de Bot Programming. Si vous avez la chance de pouvoir vous déplacer, nous serons heureux de vous offrir des entrées gratuites à la DeveloperWeek, dont nous sommes partenaires.

JobStore fait une pause

0          

Cet été, nous avons lancé CodinGame JobStore, un nouveau service destiné à vous permettre de trouver un job qui corresponde à ce que vous recherchez. L'idée était de vous permettre de postuler auprès d'entreprises qui vous intéressent, sur la base de vos compétences principalement, en vous servant de votre profil de CodinGamer comme d'un portfolio professionnel de développeur (pour un matching de compétences).

Le concept était simple : vous jouez/codez, vous démontrez ce que vous savez faire, et vous décrochez un job qui vous correspond. Quand on vous a demandé dans une enquête ce que vous pensiez de ce projet, vous avez été 80% à nous répondre que vous aimiez l'idée. 

Pendant 5 mois, plus de 150 entreprises ont offert 250 postes dans le cadre de la Beta. En tout, elles ont reçu plus de 1200 candidatures de votre part, et plusieurs ont mené à des embauches : nous sommes fiers de ça. 

Bien que ces données soient plus qu'encourageantes, grâce à vos commentaires et retours, nous avons pensé que nous pourrions faire encore mieux. Seulement, dans l'immédiat, il y a d'autres projets sur lesquels nous aimerions concentrer nos efforts. Alors JobStore va faire une pause. Mais le service est fortement susceptible de revenir dans le futur, amélioré et transformé, parce que nous avons le sentiment que nous pouvons créer quelque chose de plus efficace, plus fun, et plus innovant, et parce que nous pensons que vous méritez ce niveau de qualité. 

Nous avons la conviction qu'il est primordial pour une startup de pouvoir tester de nouvelles choses et en tirer des leçons. On essaye de faire ça autant qu'on le peut. Expérimenter et essayer. Imaginer, vous demander ce que vous en pensez, garder l'idée ou la jeter. On a envie de pouvoir continuer comme ça, et on espère que vous serez d'accord avec nous sur ce point :) 

Merci à tous ceux qui ont essayé JobStore et félicitations à ceux qui ont décroché des jobs ! Vous pouvez bien sûr continuer à postuler auprès de nos sponsors à travers les WorldCups qui ont lieu tous les deux mois et via les Jeux Sponsorisés :)

Bonnes fêtes de fin d'année!

1          

Salut à tous,

La saison des vacances d'hiver est là ! On voulait vous souhaiter de super fêtes de fin d'année et vous remercier d'être là, en espérant que vous appréciez toujours de passer du temps avec nous sur la plate-forme.
On a plein de projets dans le pipe, et comptons sur vous pour nous aider à faire de CodinGame la meilleure plate-forme pour les développeurs du monde entier :)

Joyeuses fêtes,

L'équipe CodinGame

Découvrez le nouvel IDE !

1          


Depuis cette semaine, la nouvelle version de l’IDE est disponible. Nous avons essayé de récolter un maximum d’avis pour le rendre plus ergonomique et vous permettre de prendre plus de plaisir à coder sur la plate-forme. Si vous n’avez pas eu l’occasion de le découvrir encore, voici les grands changements:


1. UN EDITEUR DE CODE PLUS GRAND:
Nous avons élargi au maximum l’éditeur, pour vous permettre de coder plus facilement (vous pouvez même le basculer en mode plein écran, grâce au bouton en haut à droite :)).

Macintosh HD:Users:mariamartin:Desktop:screenshots:IDE EDITEUR DE CODE.png

2. CHOIX DU LANGAGE:
Vous pouvez directement choisir le langage de votre choix à travers l’onglet en haut à droite de l’éditeur de code.

Macintosh HD:Users:mariamartin:Desktop:screenshots:IDE CHOIX LANGAGE.png

3. JEUX DE TEST:
Vous pouvez lancer plusieurs jeux de test en même temps, ils se mettront automatiquement sur la liste d’attente.

Macintosh HD:Users:mariamartin:Desktop:screenshots:IDE JEUX DE TEST.png

4. PARAMÈTRES:
L’onglet paramètres vous permet d’accéder aux fonctionnalités telles que:
-le mode d’édition
-la fermeture automatique des accolades
-le mode normal ou expert (on vous laisse découvrir par vous-mêmes :)).
-le choix de la langue (français ou anglais)


Macintosh HD:Users:mariamartin:Desktop:screenshots:PARAMETRES.png

5. RESULTATS:
Vous pouvez désormais accéder à votre score depuis l’onglet "résultat" et partager vos exploits avec tout le monde !


Macintosh HD:Users:mariamartin:Desktop:screenshots:RESULTAT.png

6. DISCUSSIONS:
Nous avons directement intégré le fil de discussions dans l’IDE pour vous permettre de discuter plus facilement avec vos amis :)


Macintosh HD:Users:mariamartin:Desktop:screenshots:DISCUSS.png


Un grand merci à tous ceux qui ont contribué et n’hésitez pas à nous donner votre avis !

Code VS Zombies - Bilan du contest

0          

Pour le contest Code VS Zombies, vous incarniez un justicier solitaire bien décidé à sauver ses congénères humains de la furie sanguinaire d'une horde de zombies déchainés. Le contest était du type "Optimisation" : vous aviez 24 heures pour programmer le comportement de votre personnage en essayant de sauver le plus d'humains possible tout en détruisant les zombies. Pour grimper dans le classement, il fallait optimiser son code pour imaginer la stratégie la plus efficace. 



PODIUM & CLASSMENT


6170 joueurs ont participé au contest, et 3963 ont terminé dans le leaderboard: bravo à tous !

Sur the podium: eldidou (France, C++), y_kawano (Japon, C#), et ftpud (Lettonie, C#). Félicitations à tous les trois !


LE JEU 


L'objectif du jeu était d'aider Ash à sauver les humains en détruisant les zombies. Ce jeu étant de type "optimisation", vous deviez non seulement sauver les humains pour être bien classé(e), mais vous deviez le faire en maximisant votre score. Pour réaliser un bon score, vous deviez essayer de détruire un maximum de zombies en un même tour tout en maintenant les humains en vie.

Une première stratégie consistait à se rapprocher d'un humain pour le protéger et attendre que tous les zombies se rapprochent. Afin de passer tous les tests, il fallait choisir un humain que l'on pouvait atteindre avant qu'un zombie ne le dévore. Un tel algorithme ne cherchait pas à maximiser le score, mais il était possible de l'affiner pour par exemple s'éloigner de l'humain et des zombies pour sauver l'humain au dernier moment et augmenter les chances de détruire plusieurs zombies en un seul tour.

Les algorithmes les plus avancés nécessitaient de simuler les règles du jeu pour évaluer plusieurs déplacements et sélectionner celui qui rapportait le plus de points. Sauf que cette stratégie était très gourmande en temps de calcul et qu'il était donc impératif de choisir avec précaution les mouvements. Pour plus de précisions, nous vous invitons à lire la stratégie du gagnant eldidou.

Et vous ? Comment avez-vous procédé ? Expliquez nous votre stratégie via le post dédié sur le Forum.




REJOIGNEZ NOTRE PROCHAIN CONTEST, "CODERS STRIKE BACK":

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

0          

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 !