Bonjour à tous, je m'appelle Olya. Il y a deux semaines, un autre concours s'est terminé à CodinGame - un concours de programmation de bots pour le jeu. Je suis entré dans le top 300 du classement mondial, donc je veux vous dire pourquoi les concours sont cool et partager mes secrets. Ivan Spaceorc , qui est entré dans le top 100 de la même compétition, partagera également des secrets.
Vous apprendrez comment participer avec succès à des compétitions de programmation d'IA de jeu.
Qu'est-ce que CodinGame?
codingame.com est une plateforme éducative pour les développeurs de tous âges et niveaux de formation. Vous pouvez écrire en 26 langues : de C # et Python à Bash et Haskell. Le plus cool est que les tâches ne sont pas ennuyeuses et incompréhensibles, mais de vrais jeux avec une bonne interface graphique:
Un concours est une compétition de 10 jours qui a lieu une fois tous les deux mois. Tout le monde peut participer, il n'est pas nécessaire d'être finaliste d'ACM ICPC. Bien sûr, pour atteindre le sommet, vous devez au moins comprendre les algorithmes typiques de l'intelligence artificielle de jeu.
Mais pour passer quelques soirées avec intérêt, les connaissances les plus élémentaires suffisent. Dans chaque concours, il y a un code prêt à l'emploi pour lire les données d'entrée. Il ne reste plus qu'à lire les règles, à écrire sans prétention sinon - et à se battre!
Code de kutulu
«Cthulhu Code» est le dernier concours, qui s'est déroulé du 15 au 25 juin. Pour connaître l'intrigue et le but, une description suffit:
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
Ce qui peut mentir pour toujours n'est pas mort du tout. Et la mort meurt dans un mystérieux éon.
Vous et votre équipe de chercheurs avez découvert le tombeau de Cthulhu. C'est la pire décision de votre vie, car il n'était pas prêt à se réveiller et a maintenant faim de votre mort. Mais la crypte est un vrai labyrinthe, et vous ne vous souvenez plus où était la sortie ... Si elle est toujours là!
Oh ... et il semble que Cthulhu n'était pas seul, et maintenant il envoie les Profondeurs pour vous.
Essayez de rester en vie le plus longtemps possible, mais n'oubliez pas que vous seul ne durerez pas longtemps ...
Les règles
Je dirai tout de suite qu'au lieu de lire une description textuelle des règles, vous pouvez regarder une vidéo de l'analyse des règles et des tactiques de base de Tinsane :
Sinon, lisez la suite.
La carte
Dans le jeu, quatre joueurs marchent sur la carte générée - plus précisément, le graphique des cellules connectées les unes aux autres. Plus sur la carte courent des serviteurs ennemis, dont le but est de rattraper et d'effrayer les joueurs.
Personnages
- Le chercheur est l'un des acteurs. Va dans n'importe quelle direction sur une cellule. Il a des super pouvoirs, mais plus sur eux plus tard.
- Vanderer est un monstre vert. Apparaît sur la carte tous les 5 tours, à partir de points précédemment connus. Il génère plus de 3 à 6 coups, recherche le joueur le plus proche et commence la poursuite. Va seulement une case par tour. S'il n'a pris personne en N étapes, il disparaît de la carte.
- Slasher - similaire à la mort avec une faux. Apparaît à la place d'un joueur dont la santé est tombée en dessous de 200 points et reste sur la carte jusqu'à la fin de la partie. "Voit" un joueur s'il n'y a pas de murs entre eux. Si en 2 coups la cible n'est pas perdue de vue, le coup suivant saute à l'endroit où le joueur a été vu pour la dernière fois.
La survie
Si le vagabond ou le slasher entre dans la cellule avec le joueur, le joueur perd 20 points de vie. De plus, les joueurs perdent un certain nombre de points de vie à chaque tour sans raison. Mais s'il y a des chercheurs vivants dans le rayon de deux cellules, alors un peu moins de santé est perdue.
Les superpuissances des chercheurs
- PLAN - Augmente la santé de 2 points en 5 tours. Si d'autres chercheurs tombent dans le rayon d'action, alors l'effet s'étend à eux et le créateur de l'effet reçoit +2 points de vie pour chacun. Vous pouvez utiliser 2 fois par partie.
- YELL - fait peur au joueur dans la cellule suivante. L'action prévue pour le prochain tour se transforme en ATTENTE (le joueur restera immobile). Cela est utile si le vagabond poursuit l'ennemi et que vous souhaitez le remplacer.
- LUMIÈRE - illumine les cellules dans un rayon de 5, vous pouvez utiliser 3 fois par partie. Aide à effrayer les vagabonds: lorsqu'ils comptent le chemin vers la cible la plus proche, chaque cellule illuminée compte pour 4.
La fin du jeu
Un joueur meurt si sa santé tombe à zéro. Après 200 coups, les joueurs survivants commencent à perdre de la santé plus rapidement et le jeu se termine presque immédiatement.
Les développeurs du concours donnent les règles aux joueurs, mais les joueurs qui réussissent se rendent sur Github et lisent le code de l'arbitre .
Tactiques
Je dois dire tout de suite que je ne suis pas reparti de zéro. Le 16 juin, Kontur a organisé des centres de codage dans sept villes - des réunions pour ceux qui souhaitent discuter du concours et s'amuser dans un environnement agréable ( photo ).
J'ai réussi l'examen à l'université et je ne suis pas arrivé au centre d'Ekaterinbourg, mais j'ai profité du bonus des organisateurs - le kit de démarrage. Il est disponible en deux langages - C # et TypeScript , et il implémente déjà l'ensemble de l'infrastructure: la logique de lecture de l'état du jeu à chaque tour, ainsi que les classes qui caractérisent le jeu lui-même (telles que l'état et les actions possibles), et certaines auxiliaires (par exemple, un minuteur personnalisé) . J'ai pu immédiatement commencer à écrire la chose la plus intéressante - mon cerveau bot chercheur.
Vanya Dashkevich ( Spaceorc ) est l'un des leaders de la plaque tournante d'Ekaterinbourg. Il siège à CodinGame depuis plus d'un an, a participé à sept concours et à cinq a atteint le top 100 mondial:
J'ai découvert auprès de Vanya les détails de la décision, ce qui lui a valu la 64e place du classement mondial, et j'ai comparé sa décision avec la mienne.
[1] Venez aux hubs: vous pouvez y trouver des liens vers des kits de démarrage, discuter des règles, trouver des tactiques et rencontrer des gens intéressants.
Qu'au début du concours, qu'à la fin, l'algorithme de choix du prochain coup se ressemble:
- Générez toutes les actions disponibles pour le bot;
- Appliquez-les à l'état actuel;
- Évaluer les résultats de ces mouvements;
- Choisissez le meilleur.
Générer des actions disponibles
Ollisteka : Déjà à cette étape, j'ai commencé à appliquer l'heuristique - je me suis imaginé à la place de ce chercheur, et j'ai décidé ce qui serait bien et ce qui ne l'était pas. Puis-je aller à la prochaine cellule libre? Ajoutez un tel mouvement. J'ai toujours un plan inutilisé, et il n'y a aucun Wanderer ou slasher à proximité qui m'attaquera au prochain tour? Ajouter.
Selon le même schéma, LIGHT et YELL sont tombés dans la liste des actions possibles, mais leur utilisation ne m'a fait que baisser dans le classement. Par conséquent, je les ai toujours supprimés de la mise en œuvre finale.
[2] N'ayez pas peur d'inclure la fantaisie: pour commencer, une simple heuristique et quelques opérateurs conditionnels suffisent.
Application d'un AVC
Le processus d'application d'un mouvement à un état de jeu est appelé simulation. La présence de la simulation vous permet d'utiliser des techniques de programmation avancées de l'IA: minimax , algorithmes génétiques , Monte Carlo Tree Search et autres.
Ollisteka : C'est cette étape qui se rapporte à ma "sous-simulation". "Nedo" - parce qu'après mon départ, les autres joueurs devraient partir, les ennemis devraient partir ou réapparaître. Cependant, j'étais trop paresseux pour faire une simulation complète pour quatre joueurs et un grand nombre d'ennemis avec une logique non triviale. Par conséquent, je n'ai changé ma santé que si j'étais seul ou en groupe, et je n'ai pas rencontré d'errant ce tour-ci.
spaceorc : Mon approche habituelle ces derniers temps a été en deux étapes:
- vous arrivez sur scène de quelque façon que ce soit lorsque les organisateurs ouvrent toutes les règles et déposent la source de l '«arbitre» sur Github;
- vous prenez l'arbitre et écrivez, en le regardant, une simulation.
La simulation est complète, avec toutes les nuances, mais inefficace. Je parie généralement sur la vitesse et la profondeur de la recherche ... Mais une simulation complète vous permet de lancer de nombreuses correspondances localement et de comparer différentes stratégies. J'ai testé la simulation complète avec CodinGame - j'ai prédit les positions des sbires, sachant comment les rivaux sont tombés (c'est-à-dire, le prochain mouvement), et compris les écarts. Lorsque la simulation complète a été prête, j'ai commencé à en écrire une rapide - pour le faire simplement, en en ayant une qui fonctionne.
[3] Vous voulez atteindre le sommet? Vous devrez comprendre les règles et écrire une simulation.
Simulation d'adversaires
spaceorc : a écrit Monte Carlo Tree Search, mais ça a été pire parce qu'il y avait trop peu de temps pour faire le tri. En général, cette approche m'est venue plus ou moins uniquement dans Ultimate Tic-Tac-Toe . Les adversaires ont joué de la même façon - simulation par coup plus score, mes coups - SCTM et jouent jusqu'à la fin. Il a ainsi été possible de simuler une cinquantaine de jeux à la fin en 50 ms. Ce n'est pas suffisant pour les SCTM, alors je l'ai coupé et je suis revenu à l'idée originale.
En conséquence, une simulation rapide est devenue incomplète:
- cessé de considérer les vagabonds à plus de 8 cellules de moi;
- cessé d'apparaître les vagabonds, car ils apparaissent déjà en 5 mouvements, et c'est ma profondeur de recherche approximativement.
Pour cette raison, la profondeur de la recherche a augmenté. J'ai également essayé de simuler uniquement les mouvements (sans YELL, LIGHT, PLAN) de mes adversaires, mais cela s'est avéré pire.
Fonction d'évaluation
La fonction d'évaluation aide à choisir le meilleur de tous les mouvements disponibles. Il prend l'état du jeu à l'entrée, et sur la sortie donne un nombre avec une estimation - plus il est grand, meilleur est l'état du jeu pour le joueur actuel.
Ollisteka : Quels paramètres ont été inclus dans mon évaluation:
- la santé de mon chercheur;
- vagabonds:
- s'il est susceptible de venir ici le prochain coup, alors c'est un mauvais coup;
- si je suis sur la même ligne que lui, alors plus il est éloigné, mieux c'est;
- s'il se nourrit également de moi, alors la distance est encore plus importante.
- libérer les cellules autour, pour ne pas tomber dans une impasse;
- d'autres chercheurs, qui préfèrent rester à proximité;
- PLAN actuel: si ma santé descend en dessous de 230, alors le traitement est une bonne idée.
À un moment donné, j'ai essayé d'évaluer les slashers, mais quand je les ai retirés, j'ai été élevé à quelques dizaines de places dans le classement. Si je travaillais mieux sur leur logique, alors ils feraient peut-être plus de bien.
En conséquence, mon évaluation pourrait être plus petite, mais comme on dit, cela fonctionne - ne touchez pas.
spaceorc : J'ai essayé de jouer avec les fonctions d'évaluation, mais cela n'a pas très bien fonctionné ... En général, certains de ceux qui se sont révélés être beaucoup plus élevés que moi dans le classement n'ont pas passé beaucoup de temps, mais ont trouvé de bonnes fonctionnalités pour l'évaluation. Je n'y ai pas fait face. Ma fonction d'évaluation finale comprenait:
- le nombre de points (la tournée sur laquelle est décédé + santé);
- Corbeau ;
- distance par rapport aux chercheurs étrangers.
[4] Expérience: modifiez les coefficients des paramètres de la fonction d'évaluation, ajoutez de nouveaux paramètres et supprimez les anciens.
Choisir le meilleur coup
Nous trions les mouvements par ordre décroissant, prenons le premier, utilisons-le.
Optimisation
Concourir pour une place dans le top cent ne suffit pas pour avoir une bonne fonction d'évaluation et une simulation complète. Plus le bot fonctionne rapidement, plus les jeux seront simulés dans une tranche de temps. Plus il y a de jeux, plus le mouvement actuel est le plus optimal. Plus le mouvement est optimal, plus la place dans le classement est élevée.
Ollisteka : J'ai profité du fait que la carte peut être représentée sous forme de graphique - j'ai calculé à l'avance les longueurs de tous les chemins de cellule en cellule et je n'y ai pas passé de temps à chaque fois.
spaceorc : Sur CodinGame, la simulation a fonctionné rapidement, en 50 ms elle a fait plusieurs dizaines de milliers de coups. En raison de quoi:
- Masques de bits et code dangereux.
- Explorer - int, vagabond - int, slasher - int.
- Tout état mutable tient dans 128 octets, donc tout fonctionne très rapidement avec lui.
- La coordonnée est en octets, car la plus grande carte avait 222 cellules libres.
- La file d'attente doit être - var queue = stackalloc octet [255].
- Pré-calcul des chemins, des distances et d'autres choses.
Je l'ai fait tout le temps ces derniers temps, c'est très bien. Soit dit en passant, j'écris toujours beaucoup de tests pour une telle simulation, sans laquelle elle ne peut tout simplement pas être déboguée.
[5] Vous voulez concourir pour une place dans le top 100 - vous débarrasser du code inefficace.
À quoi cela a conduit
Ollisteka : Tout au long du concours, mon bot est resté régulièrement dans le top 300. À un moment donné, j'étais même à la 84e place du classement mondial, mais ensuite j'ai fait une nouvelle version et je ne suis pas revenu ¯ \ (ツ) / ¯ Après avoir terminé à la 290e place, je suis très heureux pour trois raisons:
- C'est le premier concours auquel j'ai participé à part entière, car par le passé j'étais trop occupé par les études.
- J'ai aimé le jeu lui-même - il était clair comment jouer et quoi faire pour gagner.
- Top 15% mondial - ça a l'air cool :)
Il était évident que pour arriver au sommet, il fallait faire une simulation complète et rapide. Mais je ne voulais pas faire ça, alors j'ai juste ajouté des paramètres à la fonction d'évaluation et changé les constantes magiques.
spaceorc : Je suis plutôt satisfait du résultat, je suis allé dans le top 100 ... Mais je devais quand même travailler davantage sur la fonction d’évaluation, un fort biais vers la simulation s’est avéré. Et je suis un peu fatiguée au final, mon imagination ne suffisait pas ...
En conclusion
Découvrez CodinGame et essayez-vous! En juillet, ils promettent un nouveau concours - venez dans les hubs, nous coderons les bots ensemble.
Liens utiles:
UPD Merci dbf pour le commentaire: Code of Kutulu a été téléchargé en multijoueur . Vous pouvez ainsi mettre en pratique les connaissances acquises dans l'article! :)