🙋🏾 🚳 👢 Poursuite de la participation (et victoire) à la Russian AI Cup 2019 🧐 💳 🛒

Bonjour à tous, je m'appelle Andrey Tokarev , et encore une fois, je voudrais partager mon expérience de participation et de victoire à la Coupe AI russe.

Si quelqu'un ne le sait pas, la Russian AI Cup (ci-après RAIK) est un championnat de programmation d'intelligence artificielle où nous (ou plutôt notre programme) devons contrôler un ou plusieurs personnages (unités) qui se font concurrence. Cette année, le jeu était un jeu de plateforme à deux dimensions, rappelant les jeux informatiques du début des années 90, et les unités étaient des hommes armés qui étaient censés tuer les mêmes hommes que l'ennemi. Vous pouvez en savoir plus à ce sujet dans l' annonce.

Cette fois, il n'y a pas eu de réunion lorsque l'ordre du jour est venu pour le début du RAIK, alors allons droit au but.

Premier coup d'oeil

J'ai donc parcouru les règles, essayé le jeu. La première impression était - que faire ici? Comme les unités n'avaient pas d'inertie et que les niveaux initiaux étaient sans cycles fermés, l'ennemi pouvait toujours nous coller s'il le voulait, et se défendre contre cela était impossible. Et dans cette situation, vous comprenez, les possibilités sont très limitées. Vous n'esquiverez pas les balles. Mais mes premières craintes ne se sont pas concrétisées, bien que le facteur chance soit élevé, les règles se sont avérées assez jouables.

Je n'ai pas immédiatement commencé à me développer, quelques jours ~~sont tombés idiots~~a décidé de réfléchir. Je n'ai rien trouvé de spécial. Il est clair que vous devez éviter les balles, courir après les trousses de premiers soins et, si possible, ne laissez pas l'ennemi prendre une trousse de premiers soins et tout ça. Il existait encore un vague plan pour trouver des positions stratégiquement avantageuses et tournait autour d'elles, mais il n'était pas tout à fait clair comment distinguer ces positions.

Début

Alors c'est parti. Par habitude, je convertis les objets de données du module linguistique en mes propres structures de données. Oui, cela prend du temps, mais pas beaucoup, mais j'obtiens plus de flexibilité, je travaille dans un environnement plus familier, et pendant que je me convertis, il vaut mieux commencer à comprendre comment fonctionne le monde du jeu. Bien sûr, pas tout d'un coup, mais au besoin. Par exemple, je n'ai pas recréé les mines jusqu'à ce que la situation politique au championnat m'oblige à recourir à des mesures extrêmes. J'ai copié approximativement la logique de Smartgayev, en ajoutant seulement une vérification de la présence d'un mur entre moi et l'ennemi. J'ai regardé, ils semblent bien fonctionner, donc nous pouvons supposer que nous avons un monde de jeu.

Simulation

Nous passons maintenant au passe-temps le plus préféré de tous les participants RAIK: nous écrivons une simulation! Après avoir lu le chat du championnat, il est devenu clair qu'écrire une simulation précise est mauvais. J'ai donc immédiatement marqué pour la précision. Il s'est avéré, comme cela s'est produit, même avec un simple rebond du plafond, il y avait une divergence au sein du teck. Il était possible, bien sûr, de le bricoler pendant plusieurs jours et d'augmenter considérablement la précision, mais, tout d'abord, on ne sait pas quel serait le bénéfice de cela. Deuxièmement, j'étais trop impatient et, comme toujours, je voulais voir le résultat le plus rapidement possible. J'ai donc décidé de commencer à écrire la stratégie elle-même, et j'ai pensé que je corrigerais ma courbe de simulation, si nécessaire. Avec le recul, je dois dire que j'avais peut-être tort.
Il vaudrait la peine de ramener immédiatement la simulation à la normale, et il a donc fallu y apporter des corrections jusqu'à la fin du championnat, et elle est quand même restée tordue.

Base stratégique

Ensuite, nous procédons selon le scénario standard: nous générons la séquence d'actions des ~~robots~~ unitaires, simulons un changement dans le monde du jeu et soumettons le tout à l'entrée de la fonction d'évaluation (OF). Si dans le football (tournoi de l'année dernière), il était inefficace de courir après le ballon avec un nombre aléatoire complet de joueurs (il y a trop peu de chances de frapper le ballon, surtout sous l'angle droit), alors il n'y a pas un tel problème. Fondamentalement, nous avons besoin d'une simulation pour deux choses: esquiver les balles et trouver le chemin. Quelques scénarios d'action complètement aléatoires suffisent pour échapper aux balles. Plusieurs dizaines de scénarios fonctionneront également pour rechercher un chemin plus ou moins, au moins, sur des cartes pas si difficiles.

Au fait, la recherche du chemin - il est clair que compter jusqu'à la fin n'est pas toujours possible, vous devez donc être en mesure de déterminer la distance. En utilisant la même simulation, on pourrait calculer plus ou moins précisément les distances dans le temps. Mais ici, je l'ai aussi simplifié, juste compté les distances le long d'une grille rectangulaire. Cette simplification a bien sûr eu des conséquences sur des cartes complexes. Parfois, mes unités étaient encore confuses dans la recherche d'armes, alors que l'ennemi commençait déjà à tirer. Certes, ces incidents étaient assez rares.

Le choix de la cible était assez simple: s'il n'y a pas d'armes, on va aux armes, s'il y a des armes, on va à l'ennemi, et s'il y a peu de "santé", on va à l'armoire à pharmacie. Dans le cas des trousses de premiers secours et des armes, les objets plus proches de l'ennemi en tant que cible ont été exclus. Pour une raison quelconque, la priorité sur les armes pour moi était d'abord sur la machine.

La première fonction d'évaluation comprenait deux composantes: la santé (pas la mienne, mais une unité) avec un grand coefficient, et la distance jusqu'à la cible avec un petit coefficient.
Ceux. l'itinéraire a été choisi dans lequel il ne tombe pas sous les balles, mais s'approche en même temps de la cible le plus rapidement possible. Il est important de se souvenir du meilleur itinéraire trouvé pour le prochain tick, sinon une situation peut se produire lorsque nous trouvons une bonne option, mais ne l'avons pas donnée au prochain tick.

Nous allons à l'avant, et les premières améliorations

En regardant les batailles, il était clair que si l'ennemi avait une esquive normale, il était presque impossible de le pénétrer à longue distance. C'est un gaspillage de balles. J'ai donc ajouté une condition simple pour tirer: ne tirer que si l'ennemi est à moins de 7 mètres. De plus, si la distance est très grande, cela vaut la peine d'être rechargé, même si une seule balle manque dans le clip. Ces deux conditions simples ont ajouté un peu.

Ce fut la première version que j'ai envoyée. Le même jour, j'ai réalisé qu'une arme à feu est plus rentable qu'une mitrailleuse. De plus, il a ajouté à l'OB une autre distance à l'ennemi, au cas où le tir ne serait pas proche. Ainsi, lors du rechargement, il a essayé de garder ses distances.

Le départ a été assez réussi. Je ne me souviens pas à quel point la stratégie a réussi à augmenter dans le classement avant la réinitialisation (quelque part autour des trois à cinq premiers), et après la réinitialisation, elle a augmenté en toute confiance.

La principale amélioration de la version suivante est due à une tentative de contrôle des trousses de premiers secours. Là encore, tout était simple: la distance entre les trousses de premiers soins et l'ennemi était calculée, et s'ils étaient à peu près égaux, on pensait que la trousse de premiers soins était tirée, et donc, celle dont elle est la plus proche. Cela a été pris en compte par la fonction d'évaluation. Ceux. en théorie, l'unité a tenté de se positionner de manière à masquer autant de trousses de premiers secours que possible. En théorie, bien sûr, mais pas en pratique.

Après cela, je n'ai pas envoyé de mises à jour depuis longtemps. À ma grande surprise, la stratégie a d'abord atteint la 1ère place, puis est ressortie de plus de 100 points. Tout le monde pensait probablement que je coupais quelque chose de cool, et j'ai été choqué de voir comment cette misérable stratégie a explosé. Misérable, parce que, bien, il y a un contrôle maladroit des trousses de premiers secours, il y a deux ifs pour le tir, mais en gros c'est une esquive simple et un mouvement basé sur une courbe de simulation.

Essai

Je voudrais en parler séparément, car des tests appropriés sont une partie très importante du développement, et de nombreux participants semblent ignorer cet aspect. L'accident est intuitivement mal compris par les gens.

Supposons que nous effectuions un test et après 40 matchs, nous voyons un score de 27:13 en faveur du nouveau. C'est tout, nous avons trouvé le Graal, arrêtons le test et acceptons les changements. En fait, même avec des forces égales, il y a environ 2% de probabilité d'une telle situation.

Autre exemple, nous lançons 100 jeux et acceptons les modifications si le score est de 55:45 ou plus. Avec une probabilité de 2,8%, une version peut jouer de cette façon, qui en réalité devrait perdre avec le même score. Quelques pour cent de l'erreur peuvent ne pas sembler très importants, mais si 90% de nos modifications échouent, cela signifie que chaque quatrième modification acceptée échouera. Donc, même 100 jeux sont toujours un test moyen, mais moins - rien du tout.

Bien sûr, le lancement de plusieurs centaines de jeux peut prendre un temps indécent. Il existe différentes options, vous pouvez exécuter des tests la nuit, conduire en arrière-plan, louer du temps au serveur ou rendre la stratégie rapide :) Mes premières versions ont fonctionné en moyenne, quelque part, pendant 5 secondes. au jeu, si chanceux avec ça.

Si la stratégie est lente, vous pouvez générer localement des versions tronquées - moins de recherches, moins de micro-ticks, par exemple. Je l'ai utilisé dans le football (ancien RAIK), aucun problème n'a été remarqué. Peut-être que la qualité est perdue quelque part, mais, en tout cas, c'est plus rentable que de vérifier les changements sur 20 jeux.

Améliorations

Cette fois, je n'évaluerai pas les améliorations en nombre. Premièrement, ils étaient tous petits (moins de 20%) et donc inexacts. Deuxièmement, ambigu, c'est-à-dire la nouvelle version pourrait en toute confiance battre la précédente et jouer moins bien contre les autres. Et troisièmement, je ne m'en souviens tout simplement pas.

, . , . , , .
. .. , , . , , -. , . , , . .
, , . , , , , , . , . , .
, ? , , . . , . .

-

Objectivement, vous devez tirer dans la direction où le tapis. l'attente de dommages est la plus élevée. Il est clair que analytiquement cela ne peut pas être calculé, et là où les mathématiques n'aident pas, comme nous le savons, la simulation vient à la rescousse. Nous tirons dans toutes les directions possibles et essayons d'esquiver l'ennemi de chaque balle individuellement. À chaque pool, nous attribuons la valeur minimale de dégâts qu'il infligera avec précision. Dans le cas d'une balle conventionnelle, c'est soit 0 soit ses dégâts, et dans le cas d'une fusée il y a 3 options.

Maintenant, nous connaissons le tapis. s'attendre à des dommages dans chaque direction séparément, à partir de cela, nous pouvons facilement calculer le tapis. attendez chaque direction du tir et choisissez le meilleur. Ce serait bien d'utiliser cette fonction dans l'énumération pour que l'unité soit correctement positionnée, mais c'était trop lent pour l'appeler pour chaque scénario. Il était appelé une fois par tick pour chaque unité, et maintenant le tir n'était plus effectué à distance, mais si les dégâts attendus dépassaient une certaine limite. L'augmentation était significative et dans le cas du bazooka, cela semblait assez clair - maintenant le mien pouvait même viser quelque part sur le mur afin de frapper l'ennemi avec une onde de choc.

Mais étant donné que je ne pouvais pas insérer cette fonction dans la recherche, il y avait un problème que les conditions de la prise de vue dans la recherche et en réalité étaient différentes. Je ne savais pas comment résoudre ce problème, je devais vivre avec.

Après cela, il n'y a eu aucun changement très important jusqu'au dernier jour où j'ai introduit l'auto-dynamitage. Il a ajouté une pénalité s'il n'y avait plus de saut au moment où l'ennemi a tiré, car une chute rendrait plus difficile l'esquive. J'ai essayé de prédire le chemin de l'ennemi à la trousse de premiers soins, s'il a peu de vies, et donc un contrôle légèrement amélioré sur eux. Lui-même a commencé à courir après les trousses de premiers soins de 60% de sa santé, au lieu de 50%. Il a ajouté la distance entre les siens dans le PF afin qu'ils n'interfèrent pas les uns avec les autres et que le bazooka n'en élimine pas immédiatement deux. Au final, il a ajouté un mod agressif au cas où la situation ne changerait pas longtemps et que je perdrais aux points, sinon le mien se coincerait parfois.

résultats

Comme je l'ai dit, j'ai rapidement atteint la première place du classement. À l'exception de courtes périodes, j'y suis resté jusqu'à la fin. Dans les manches, la situation était un peu pire: 4ème place en première, 3ème en seconde. Cela indique que j'ai bien joué contre des joueurs forts, mais pas assez stable contre des joueurs faibles. Ceci est clairement démontré par l'un des matchs du 2e tour, où kostya200300, qui était alors à la toute dernière place, m'a battu à 0!

Auto-dynamitage

Comme la plupart des participants, je n'étais pas enthousiasmé par la possibilité d'auto-explosion. Cela a considérablement augmenté le facteur aléatoire déjà considérable. Mais il était clair que l'on ne pouvait pas s'en passer. C'est vrai, je ne voulais pas vraiment faire ça, et je l'ai repoussé jusqu'au dernier jour. Cette technique est assez simple, si nous nous tenons au sol, l'ennemi est dans un rayon d'explosion et nous avons assez (maximum deux) mines, puis nous mettons des mines et tirons au fond. Je pose une condition supplémentaire: après l'explosion, j'obtiens un net avantage, c'est-à-dire soit gagner immédiatement, soit tuer plus d'adversaires que les leurs. Je pensais que depuis que j'aspire à un haut lieu, alors changer un par un n'est pas rentable. Eh bien, c'est comme aux échecs, si vous jouez pour gagner, alors tout échanger n'est pas rentable. C'est ainsi que j'ai envoyé mes guerriers dotés de compétences kamikazes à la bataille finale.

Le final

Comme je l'ai déjà écrit, la note ne parle que de l'équilibre des pouvoirs avec les concurrents les plus proches, et je n'avais pas de stabilité contre des rivaux plus faibles. À cet égard, l'élimination des participants à la finale a été un gâchis pour moi. D'un autre côté, la propagation massive de l'idéologie terroriste le dernier jour a introduit une nouvelle propagation de la répartition des forces. Bref, malgré le leadership confiant du classement, il n'y avait aucune confiance dans la finale, il n'y avait que de l'espoir. Après la première moitié de la finale, il est devenu clair que la lutte principale sera entre moi et Ivan Tyamgin. J'ai mené à un petit nombre de points, tandis que les autres étaient loin derrière.

Pendant la pause, j'ai ~~traîné~~ramasser l'auto-détonation - quelque chose a été corrigé (il s'est avéré que les mines ne devraient pas être placées en haut des escaliers), il a ajouté quelques contre-mesures contre la détonation. Et réparé la simulation, car jusqu'à présent, la mienne s'accrochait au coin.

Le début de la deuxième partie du tour final a été réussi pour moi, l'écart a commencé à se creuser lentement et a atteint un maximum d'environ 20 points. Je me suis même un peu détendu et au lieu de rafraîchir la page de résultats toutes les 3 minutes, j'ai commencé à jouer aux échecs au téléphone. Quand j'ai regardé à nouveau, l'écart était déjà d'environ 7 points, puis il est rapidement passé au 1er. Je me demande ce qu'ils donnent pour la 2ème place? 1 heure à la fin, encore une fois il y a un écart. 30 minutes, l'écart est catastrophiquement réduit. 10 minutes - seulement 3 points! Une minute ... la victoire semble! Vanya n'a perdu pour moi que 3 points. C'est dans la dispersion aléatoire. Les autres ont 50 points ou plus de retard.

À propos des bugs amusants

Déjà après la finale, j'ai remarqué que dans certains jeux, mes unités se comportaient étrangement - elles n'évitaient pas les balles quand elles semblaient pouvoir, et même, comme si, les attraper spécialement. Il s'est avéré que pendant la pause de la finale, j'ai fait une erreur - quand il a été déterminé si l'ennemi pouvait me faire exploser, il fallait calculer lequel des miens se trouvait dans le rayon de l'explosion. Ici, j'ai mélangé les coordonnées de ma propre unité et celle d'une autre et j'ai supposé à tort que l'explosion se produirait où je suis, et donc garanti de tomber dans le rayon de l'explosion. La véritable explosion a déjà été considérée du bon point, donc dans la simulation, l'ennemi lui-même pourrait exploser loin de moi. Habituellement, cela ajoutait simplement une grande constante à l'estimation, mais cela n'affectait vraiment rien. Cependant, si l'ennemi n'avait pas assez de mines pour me faire exploser, il s'est avéré qu'il était rentable pour moi d'attraper une ballede sorte que l'ennemi avait déjà suffisamment de mines, et j'ai obtenu l'ajout même à l'évaluation. Peut-être était-ce dû au manque de sommeil ou à une canette de bière bue, mais en fait, des erreurs se produisent toujours.

Conclusion

Le jeu, bien que moins spectaculaire que le football, n'en était pas moins intéressant du point de vue stratégique. Le seuil d'entrée était relativement bas, ce qui a favorablement affecté le nombre de participants. J'ai ressenti beaucoup d'émotions pendant le mois du championnat, à la fois de joie et d'émotions, et pour cela je remercie les organisateurs. Je remercie également tous les participants, en particulier Vanya Tyamgina, de ne pas m'avoir ennuyé en finale.

Poursuite de la participation (et victoire) à la Russian AI Cup 2019