♻️ 😴 🧕🏿 Mon bot pour la Russian AI Cup 2019 🔈 🤰🏾 ↕️

Il se trouve que ce championnat a été le premier pour moi où j'ai pu prendre une place digne, pour laquelle je n'ai pas honte, j'ai donc décidé d'écrire l'article tout à l'heure. Le chemin que je suis allé à cet endroit: 1192e place au championnat de la 13e année, 241e au championnat de la 17e année, 91e au championnat de la 18e année et, enfin, 16e (et 5e e dans le bac à sable).

Réflexions générales

Je crois que l'une des principales raisons de la performance relativement réussie de l'IRAC a été un changement dans l'approche de rédaction de votre stratégie.

Avant, j'essayais d'écrire immédiatement quelque chose de gros et de compliqué, sans étapes intermédiaires, et la première version ne pouvait être remplie que deux semaines après le début du championnat, mais dans le passé je ne pouvais pas le mettre tout le temps alloué et la première version n'était remplie qu'après la finale .

Tout cela a conduit au fait que si d'autres participants pouvaient tester leurs stratégies de vie, je n'avais toujours pas de solution toute faite, bien que mauvaise. Par conséquent, quand il a été possible de remplir, il s'est avéré que l'approche choisie ne fonctionnait pas ou fonctionnait mal, et comme beaucoup de temps et d'efforts ont été investis, il n'a pas été possible de la changer radicalement.

J'ai donc décidé que cette fois je ferais différemment. Sur la base de l'expérience des participations précédentes, j'ai remarqué que le bot de départ, malgré toute sa primitivité, a été écrit de manière assez rationnelle, et, en le développant, vous pouvez lentement ajouter et tester de nouvelles fonctionnalités, et vérifier immédiatement les stratégies des autres participants. Surtout, j'étais convaincu d'essayer cette approche l' article de T1024 de l'année dernière .

J'ai également décidé par moi-même que plus l'approche est complexe, moins elle est efficace entre mes mains. Par exemple, cela n'a aucun sens d'utiliser la génétique où il est possible de faire une recherche exhaustive, et s'il est possible de trier moins d'options, mais toutes, ou plus, mais la génétique, il est préférable de choisir la première option. De plus, en lisant des articles Commando, J'ai conclu que des optimisations spécifiques pour la tâche seront toujours plus efficaces que l'algorithme général.

Néanmoins, même maintenant, j'avais trois ou quatre jours de retard, avant d'avoir réussi à remplir la première version du bot, à l'époque ils étaient déjà en guerre dans le bac à sable.

Qu'est-ce que j'ai fait à ce moment? J'ai écrit un simulateur, dont j'ai appris l'importance des championnats passés. Contrairement à l'année dernière, où le pseudo-code du simulateur était immédiatement disponible, cette année, toutes les mécaniques devaient être lues dans la documentation. Heureusement, en guise de compensation, les mécanismes de jeu n'étaient pas assez compliqués et simples, donc je n'ai eu aucun problème particulier.

Versions antérieures

Donc, ayant dans mes mains un simulateur prêt à l'emploi, quoique tordu, brut, la première chose que j'ai faite a été de foirer les esquives (fonction Dodge). Depuis cette fois, j'ai décidé d'agir aussi simple que possible, les évasions ont été rendues aussi simples que possible - nous vérifions le mouvement dans neuf directions (4 axiales, 4 diagonales et debout) et regardons laquelle de ces directions l'unité recevra le moins de dégâts.

Le reste des fonctionnalités du bot est resté presque complètement comme Quickstart. La désignation de la cible était également aussi primitive que possible - une chaîne de si qui sélectionne l'action la plus appropriée pour l'unité: à l'ennemi, de l'ennemi, à la trousse de premiers soins, aux armes, etc.

Étonnamment, cette approche, devenant progressivement plus compliquée, mais ne changeant pas son essence, a permis d'atteindre presque le sommet avant le premier tour (une fois que le bot était même en deuxième position dans le bac à sable) et de rester généralement quelque part autour des dix premières places.

Néanmoins, cela ne pouvait pas durer éternellement, et le bot devait être amélioré. Cependant, il n'y avait aucune idée de quoi et comment s'améliorer, toutes les tentatives de changer quelque chose dans la stratégie ont conduit au fait qu'elle perdait l'ancienne version. Des modifications mineures ont été apportées, mais rien de plus.

Le manque d'idées a conduit au fait que dans les manches 1 et 2, j'ai pris respectivement 29 et 19 places, et bien que je sois allé en finale, il est devenu clair que quelque chose devait être radicalement changé. C'est avant la finale (et après la finale) que le plus grand nombre de modifications importantes ont été apportées.

Déjà quelque part au milieu du championnat, j'ai essayé d'expérimenter un mouvement plus intelligent, mais toutes les tentatives ont échoué. L'idée initiale était de choisir la direction où la différence entre la chance de frapper son bot sur l'ennemi et l'ennemi sur son bot était maximale. Pour cette expérience, j'ai passé presque tout le temps alloué à la finale, avec un résultat nul.

Par conséquent, pour les cartes finales à plusieurs niveaux, le bot s'est avéré complètement non préparé. La chaîne des ifs a donné des résultats relativement bons sur les cartes à un seul niveau des tours 1 et 2, mais s'est avérée inadaptée aux cartes à plusieurs niveaux de la finale, je n'avais pas non plus de système de navigation pour les cartes complexes, car sur les cartes simples, il était possible de passer du code de démarrage.

— .

Toutes les commandes de tir sont dans la fonction AimHelper.

Tout ce qui est décrit ci-dessous implique que la cible est l'unité ennemie visible la plus proche du bot.

Il n'y a que trois types d'armes, mais chacune d'elles nécessite sa propre approche. Il vaut mieux simplement tirer plus souvent avec une mitrailleuse, viser mieux avec un pistolet, puis il est important de tirer avec un lance-roquettes pour infliger plus de dégâts à l'ennemi qu'à vous-même.

Initialement, il n'y avait pas de visée du tout, le bot visait juste le centre de l'unité. Plus tard, une prédiction du mouvement de l'unité a été ajoutée si elle est dans un vol incontrôlé (chutes ou mouches depuis le jumppad). Pour ce faire, j'ai simplement simulé le mouvement de l'unité jusqu'à ce que la distance que la balle peut parcourir pendant N ticks devienne égale à la distance à l'unité.

Lors des tests contre le bot de départ, il a remarqué son habitude très désagréable de sauter constamment de haut en bas, et si le bot visait toujours le centre de l'ennemi, cela conduisait la vue à se déplacer constamment et la propagation augmentait très rapidement au maximum. Pour la contre-action, un code a été ajouté pour vérifier si la chance de frapper avec l'angle de visée actuel est meilleure ou égale à la chance de frapper avec un nouvel angle de visée, nous ne changeons pas le point où nous visons et n'augmentons pas l'écart.

Avec le tir, c'était plus difficile, l'un des principaux problèmes du bot de départ était qu'il ne vérifiait pas s'il se toucherait avec une explosion. Pour une raison quelconque, j'ai aimé le lance-roquettes la plupart des trois types d'armes, et c'était donc la première priorité. Il fallait apprendre au bot à ne pas se saper.

La fonction HitChance a été écrite, qui divise le secteur de tir de l'unité en N rayons et vérifie chaque rayon pour une collision avec une cible. En outre, lorsqu'il est touché, l'AOE de l'explosion a été vérifiée, s'il s'agit d'un lance-roquettes. Chance de toucher = nombre de coups par rayon ou explosion / nombre de rayons.

Cela nous a permis de déterminer les chances statiques de nous frapper ainsi que l'ennemi, mais sans tenir compte du fait que l'ennemi lui-même pouvait activement esquiver. Il y avait d'autres problèmes, par exemple, la fonction ne tenait pas compte des tirs aléatoires sur les mines.

C'était suffisant pour lutter contre des ennemis pas si rusés, mais contre des sommets qui esquivent bien les balles, la fonction n'a pas donné de résultat adéquat. Une nouvelle approche était nécessaire.

La fonction HitPredict divise également le cône de tir en rayons N, mais au lieu de réémettre, nous utilisons une simulation où une balle est tirée à la fois dans l'une des directions et il est vérifié si l'ennemi peut esquiver.

Pour vérifier les esquives, la fonction Dodge est également utilisée, ce que le bot a utilisé pour lui-même, mais avec beaucoup de temps de simulation et de nombre de microtics. Cette méthode d'évaluation s'est avérée assez précise, mais trop pessimiste. Si vous l'utilisez uniquement, le bot tire trop rarement.

Dans la première version, la fonction ne renvoyait que la chance de toucher, de 0 à 1, plus tard, il a été ajouté le calcul de la valeur moyenne en HP de la cible, ainsi que la chance de tuer par coup.

En fin de compte, les deux fonctions ont travaillé ensemble. La fonction HitPredict a été utilisée jusqu'à quatre fois, une pour chaque unité. Le résultat du calcul de chaque fonction a été converti en vitesse, ce qui a montré à quel point il est rentable / dangereux de tirer en ce moment. Les valeurs s'additionnent. Si la valeur totale était inférieure à zéro, la prise de vue était bloquée. Pour le lance-roquettes, il fallait que la vitesse soit supérieure à zéro.

Il est devenu possible de tirer avec plus de confiance dans les cas où un allié bloque le tir ou pénètre dans l'AOE d'un lance-roquettes, vous pouvez lui tirer dans le dos en sachant que l'allié aura le temps d'esquiver, ou il est simplement bénéfique pour nous de tirer. Par exemple, nous perdrons une unité, mais nous en retirerons deux à la fois.

Pour le lance-roquettes, l'approche a également été efficace, un coup au bon moment est beaucoup plus efficace que deux coups, quand la chance de toucher est nulle. Sous cette forme, le tir était en finale, ce qui permettait de prendre la 16e place.

Maintenant, les jetons qui ont été ajoutés après la finale.

Visée précise: si l'angle entre le viseur actuel et le viseur souhaité n'est pas trop grand, nous visons le viseur à un débit de données afin de ne pas augmenter la diffusion.

Angle d'information pour le pistolet: curieusement, la puce est très simple, mais elle ne m'est pas venue à l'esprit auparavant. L'interdiction de tirer si le facteur de dispersion (scatter / max scatter) est supérieur à 0,6 a fourni le pourcentage de victoires en mode 1x1 en 3: 1 contre la version qui a tiré sur le CD d'armes. La réduction du facteur à 0,3 a fourni le même pourcentage de victoires contre la version avec le paramètre 0,6. Ainsi, l'une des optimisations les plus simples s'est avérée être l'une des plus efficaces.

Visualisation du fonctionnement de la fonction HitPredict, les trajectoires où le coup est garanti sont marquées en rouge.

La navigation

Jusqu'à la fin de la navigation, il n'y avait aucun mot. Un algorithme légèrement amélioré du bot de départ a été utilisé, et cela était généralement suffisant.

Par conséquent, lorsque des cartes complexes ont disparu, le bot a eu beaucoup de mal. Un algorithme de recherche BFS urgent a été écrit de toute urgence, qui cherchait un chemin sans tenir compte de son accessibilité physique, simplement par des tuiles. Pour que le bot passe le chemin trouvé, diverses béquilles ont été utilisées. Tout cela a fonctionné de façon très tordue, et parfois cela n'a pas fonctionné du tout, mais le bot peut toujours accéder aux armes et aux trousses de premiers secours, et ne pas sauter sur le champ.

Après la finale, la navigation a été considérablement améliorée et, selon mes observations, elle s'est comportée encore plus efficacement que de nombreux participants avec de meilleurs algorithmes de recherche de chemin.

Principe de travail: le bot recherche la cellule la plus éloignée sur le chemin à l'intérieur du carré 5x5, visible depuis le centre du bot, et suit jusqu'à ce point.

Néanmoins, jusqu'à la fin, il est resté un code incroyablement béquille qui ne fonctionnait que sur les cartes finales et tombait sur d'autres, plus complexes.

Sentier balisé vert trouvé diykstroy. Le bot suit le point marqué d'un carré blanc.

Fonction de déplacement et d'estimation

Avant la finale, il n'y avait pas de fonction d'évaluation, au lieu de cela, une chaîne de ifs était utilisée, qui par ordre de priorité fixait le bot à la cible conformément aux conditions données. Par exemple, la première était une recherche d'armes si le bot n'en a pas, puis une recherche d'une trousse de premiers soins si nous sommes blessés, etc.
Cela a fonctionné sur des cartes simples, même si elles étaient tordues, car les priorités ont changé très rapidement et ne prennent pas en compte divers facteurs supplémentaires.

Par conséquent, une fonction d'évaluation a néanmoins été écrite.

paramètres principaux

La santé de l'unité, le plus gros bonus.
. — , — .
— , . (1 — / . ), , . , , .
. , , .
, , , .
.
, .
.
Un gros bonus si nous pouvons toucher l'ennemi avec l'auto-dynamitage.

Les deux derniers paramètres n'étaient pas en finale.

Tous ces bonus sont calculés pour chaque tick, additionnés et la valeur totale est moyenne. De plus, il existe des paramètres estimés qui sont calculés une fois pour chaque direction.

Bonus pour se déplacer vers l'ennemi le plus proche.
Bonus pour vous déplacer vers la trousse de premiers soins la plus proche. Moins nous avons de santé, plus le bonus est fort.
Bonus pour passer à l'arme la plus proche si nous n'avons pas d'arme, ou pour passer à une arme avec une priorité plus élevée que le bot.
Bonus pour passer à lootbox min si le bot en a moins de deux.
Bonus pour passer à la trousse de premiers soins la plus proche de l'ennemi, si nous sommes plus proches de la trousse de premiers soins que l'ennemi.
Le bonus le plus intéressant. Il a été ajouté après la finale. Vous permet d'empêcher le robot ennemi d'être traité. Selon les observations, cela s'est avéré assez efficace.

Remarques

La profondeur de simulation est de 30 ticks.
Le comportement des robots ennemis n'est pas simulé. Le jeu est très dynamique et prévoir correctement le mouvement de l'ennemi est très difficile et pas particulièrement nécessaire. Il pourrait être utile d'éviter les suicides insensés, mais cela n'a jamais été fait.
Pour éviter les problèmes d'évasion des balles, si elles sont sur le terrain, nous simulons avec une qualité de 100 microtiques par tick (comme dans le jeu), sinon nous la réduisons à 5.
Vous pouvez remarquer qu'aucun coefficient d'atténuation n'est appliqué. C'était peut-être une erreur.

L'ancienne option de déplacement se trouve dans MoveHelperOld, la nouvelle dans MoveHelper.

Mon bot (à droite) garde la trousse de premiers soins

Mines

Les mines doivent être décrites séparément. Si au départ ce n'était pas un élément de gameplay très important, il était censé exploiter les points clés. Après le test bêta, la possibilité d'exploser des mines a été soudainement ajoutée si elles étaient touchées par une balle ou une explosion. De plus, il a été possible de placer la mine et de la saper du même coup.

Autrement dit, si vous dépensez seulement deux ticks, vous pouvez prendre n'importe quelle unité ennemie avec vous. L'ennemi a reçu 1000 points pour notre mort, mais nous avons reçu 1000 + sa santé au moment de la démolition pour sa mort. Si vous répétez cela deux fois, vous pourriez obtenir une victoire avec une très forte probabilité.

L'exploit s'est avéré si fort qu'un participant, qui se trouvait quelque part à la 15e place du classement général, a glissé de façon inattendue à la 4e place en finale, simplement en raison d'un kamikaze compétent.

(La différence est que dans le classement général, il y a des cartes simples et complexes. Sur les cartes simples, le suicide est pire.)

En finale, la stratégie a utilisé des mines, mais n'a pas utilisé d'auto-détonation intentionnelle. Après la finale, quand il y avait une lutte pour des prix supplémentaires, le module TryPlantMine2 a été ajouté, qui implémente le demoman. Au début, en raison d'erreurs dans le code, le module n'était pas particulièrement efficace, mais dans la dernière version, il était possible de tout réparer, et la stratégie a immédiatement commencé à grimper en flèche. C'est arrivé au point qu'elle a même volé dans le top 3, même si elle a quelque peu glissé.

Principe de travail: si nous sommes dans une position qui vous permet de mettre une mine et que vous pouvez tirer au plus tard cinq ticks, nous simulons trois options: abattre simplement, mettre une mine et tirer, deux mines et tirer. Pour les ennemis et les alliés, nous simulons le mouvement en utilisant la même fonction Dodge, en vérifiant s'ils peuvent sauter hors de la zone d'explosion avant que nous soyons prêts à saper (pas sûr de combien il était nécessaire). Pour chaque option, nous vérifions à quel point il est bénéfique pour nous sur les points, si nous sommes dans le noir, nous sommes sapés (de cette façon, nous pouvons être sapés même en sachant que deux de nos unités et un ennemi mourront, mais nous gagnerons toujours)

L'effet de l'autodestruction sur la note

résultats

Les solutions simples peuvent souvent être plus efficaces que les plus complexes, mais cela a sa propre limite. Avec cette approche, vous pouvez atteindre un niveau assez élevé, mais tomber dans le piège lorsque le potentiel d'amélioration de la stratégie est déjà épuisé, et sans changements radicaux pour augmenter la force de la stratégie est impossible. Pour l'avenir, vous devriez penser à une sorte d'option intermédiaire.

Conclusion

En général, j'ai aimé ce championnat, même si je suis partisan, car c'est la première fois que je réussis à prendre une place. Néanmoins, sans même considérer mes sentiments subjectifs, cette année, beaucoup a été réalisé à un niveau supérieur.

Pour la première fois, il a été possible de communiquer par télégramme avec une personne responsable de la partie technique, et qui a répondu rapidement à toutes les questions, dont un grand merci à lui.
Pour la première fois, un visualiseur intégré normal était présent dans le localranner. Auparavant, pour générer des graphiques de débogage, vous deviez écrire les vôtres.
Enfin, au lieu de l'utilitaire gênant et buggy Repeater, le bouton "Répéter le jeu" est ajouté dans le LAN.

Des inconvénients, bien sûr, est un énorme exploit avec des mines.

Et j'espère que mes réalisations dans ce championnat ne sont pas accidentelles et que la prochaine fois je pourrai au moins gagner une place, et encore mieux prendre une position plus élevée (rêver n'est pas nuisible).

Le code bot peut être consulté sur le github: github.com/silentnox/CodeSide

Mon bot pour la Russian AI Cup 2019