Bonjour à tous!
Je suis un étudiant de troisième année et au tout début de mes études à l'université, j'ai découvert la
Coupe Ai russe , puis la
Coupe Mini Ai , les compétitions d'intelligence artificielle, et j'ai commencé à y participer activement, montrant de bons résultats. Cette fois, l'IRAC est tombé dans la séance, donc rien ne pouvait m'arrêter :) Et aujourd'hui, je veux vous dire comment j'ai réussi à prendre la deuxième place.
Les règles du concours peuvent être consultées sur le site Web du concours, ainsi que dans cet
article . Lien vers mon profil:
russianaicup.ru/profile/TonyK .
D'une part, la tâche de cette année était similaire à celle des années passées, et il semblait que la solution idéologique serait très similaire aux précédentes (Agar IO et Mad Cars); après environ une semaine, je vais m'ennuyer et me lasser de participer.
D'un autre côté, j'ai compris que j'avais beaucoup appris lors des précédentes compétitions de physique et maintenant je peux appliquer cette expérience, pas marcher sur l'ancien râteau et, au final, montrer un meilleur résultat.
En ce qui concerne la visualisation, j'ai décidé que j'aurais suffisamment de projections sur différents axes ou que j'afficherais sous un certain angle. Mais je me suis trompé, et sans le visualiseur magique intégré à Local Runner, que les organisateurs ont ajouté plus tard, je devrais emprunter des visualiseurs 3D aux aimables participants qui ont passé la phase de test bêta à les écrire et à les mettre dans le domaine public.
Cette fois, le pseudo-code du simulateur était disponible, qui égalisait les possibilités de ceux qui savaient comment inverser la physique et écrire un bot cool, et ceux qui ne pouvaient pas inverser la physique, mais qui pouvaient également écrire un bot fort. Je pense que c'était une bonne décision de la part des organisateurs.
La première chose que j'ai faite a été de réécrire le code du simulateur à partir de la documentation en C ++, puis de mesurer le temps du simulateur sur mon ancien ordinateur et sur le serveur. Dans le deuxième cas, cela s'est avéré deux fois plus rapide, bien que ce soit prévu. J'ai pensé combien de fois et à quelle profondeur je pouvais simuler. Il est immédiatement devenu évident qu'il fallait oublier la simulation honnête de 100 microtiques (sur le serveur, une tique de la physique était divisée en 100 "microtiques"), et il faudrait résoudre les problèmes avec précision de manière détournée.
Du fait que le shell a été organisé de manière à ce que la demande d'action pour chaque robot soit appelée séparément à chaque tick, j'ai implémenté une logique simple: au moment où le premier robot est sollicité pour une action, le programme recherche des actions pour tous les robots, se souvient et donne l'action du premier, et quand l'action est demandée au reste des robots, elle rend ce dont elle s'est souvenue.
J'étais impatient d'envoyer bientôt le bot au combat. J'ai décidé de générer des trajectoires aléatoires et de choisir la meilleure. En même temps, il voulait que l'ensemble généré permette d'effectuer des actions complexes, par exemple, faire le tour du ballon du côté droit, puis frapper.
Une trajectoire est un plan d'action. Au départ, la trajectoire était la suivante:
- définir l'action sous un angle aléatoire;
- sur un tick aléatoire de la trajectoire, changez l'angle pour un autre aléatoire;
- sauter une fois dans un tick aléatoire de la trajectoire.
Un tel espace de trajectoires était un bon ajustement pour une recherche aléatoire avec le nombre de simulations que je (et, probablement, tout le monde à l'époque) pouvais me permettre avec le simulateur brut de la documentation. De bonnes trajectoires étaient souvent devinées, et comme la meilleure trajectoire de la tique précédente était préservée, la recherche s'est avérée étirée dans le temps.
Tous les objets ont été placés dans le simulateur: mes robots, les robots de l'adversaire et la balle. L'évaluation était la plus simple: la somme des distances du ballon au but ennemi à tous les points de la trajectoire et les grandes valeurs du but à quelqu'un. Profondeur de simulation 200 ticks. Les ennemis sont prédits à leur dernière vitesse.
J'ai immédiatement ajouté une action distincte pour le deuxième robot, ainsi que l'annulation forcée du saut, si pendant le vol il n'y avait pas de contact avec le ballon, afin de ne pas sauter en vain. En même temps, mes robots ont pris plus de la moitié du temps et connaissaient la meilleure trajectoire l'un de l'autre. Maintenant, les premiers
buts ont commencé pour des adversaires forts, qui avaient déjà un gardien de but et une logique plus compliquée.
Il s'est avéré en outre que je ne considérais pas la distance aux portes ennemies, mais jusqu'au point du côté du centre du champ (mélangé
x et
z ), mais cela n'affectait en rien la stratégie. C'est bien qu'après la correction ça n'ait pas empiré. Cela se produit souvent lorsque vous écrivez un bot.
Puis il a ajouté le gardien de but en modifiant le score: il m'a infligé une pénalité pour le ballon dans ma moitié de terrain et pour le but, et a également estimé la distance du gardien de but à mon but. Maintenant, le gardien de but se tenait au but et a frappé le ballon. Une optimisation importante a été que si le ballon n'est pas dans ma moitié de terrain, alors 90% du temps est donné à l'attaquant et 10% au gardien de but, sinon 50%.
L'évaluation des trajectoires des robots en chaque point a été multipliée par 0,9 ^ de profondeur, j'ai dérivé ce coefficient de manière empirique, comme l'ensemble de la notation. Les valeurs des coefficients n'ont pas changé depuis très longtemps selon le principe "ça marche".
Il a commencé
à gagner les premiers et à monter rapidement dans le classement. La phase bêta est terminée.
Pendant longtemps, je n'avais aucune idée de la stratégie, les versions étaient notables pour des modifications mineures, des corrections de bugs (il s'est avéré que je considérais la force de rebond moyenne comme
(MAX_HIT_E - MIN_HIT_E) / 2 ), et également optimisé le simulateur. Un rôle important a été joué par le nombre de trajectoires que j'ai réussi à trier par tick, donc je me suis concentré sur l'optimisation. Suppression des sinus et des racines carrées. Ajout d'une vitesse nulle improbable sur la trajectoire avant ou après avoir changé l'angle. Score légèrement changé.
La 16e version est
restée longtemps en tête du classement, mais une semaine après la fin des tests bêta, comme prévu, beaucoup ont commencé
à gagner .
J'ai essayé d'affiner la trajectoire avec la somme des distances les plus proches de l'ennemi au ballon, et j'ai eu un comportement très intéressant. Mes robots, quand ils ne pouvaient pas frapper de manière rentable, commençaient souvent à bloquer les ennemis, brisant leurs trajectoires et les empêchant de courir jusqu'au ballon, parfois cela s'est avéré très réussi et insidieusement.
Ensuite, j'ai fixé la précision en sautant. Si quelqu'un saute sur la tique actuelle, nous effectuons d'abord 1 microtik deux fois, puis les 98 microtics restants, puis j'ai essayé le coefficient heuristique pour compenser la perte de précision dans le cas où, pour certains microtics, la vitesse maximale est atteinte. Les améliorations ont
grandement aidé et il y avait des hits plus précis et pré-calculés.
À cette époque également, j'ai commencé à afficher sur le site parmi les informations de débogage le nombre d'itérations que j'ai réussi à terminer. Il y en avait 250 à 200 ticks, au total j'ai eu 50 000 ticks de simulations pendant le temps alloué à ma stratégie par tick.
J'ai ensuite activé les trajectoires de mutation. Cela a grandement amélioré la stratégie. Dans environ la moitié de toutes les itérations, ce n'est pas la nouvelle trajectoire qui a été utilisée, mais la meilleure avec des valeurs légèrement modifiées, qui a permis de converger quelque part, par exemple, vers un maximum local. Cela
s'est avéré être une stratégie
solide à l'époque, que j'ai décidé de laisser jusqu'au premier tour, même si c'était encore deux semaines entières avant. Mais après quelques jours, elle a cessé de dominer le sommet.
J'ai passé un certain temps à m'éloigner de l'aléatoire complet, par exemple, j'ai essayé avec une recherche ternaire de trouver l'angle auquel le robot devait accélérer pour frapper la balle. Mais cela n'a pas toujours fonctionné et je n'ai pas compris comment développer davantage cette idée.
Mes robots ne savaient sauter qu'une seule fois par trajectoire, mais lorsqu'ils étaient au sol et voulaient sauter, puis frapper la balle en l'air, ils ne savaient pas que lorsque vous touchez la balle, vous pouvez sauter une deuxième fois, frappant ainsi la balle fort, et pas seulement le pousser.
Cela a été corrigé, et maintenant le simulateur, quand il a remarqué que quelqu'un pouvait frapper la balle au tick actuel, a reculé d'un tick et a forcé le robot à sauter avec une force maximale. Maintenant, debout sur le sol, le robot savait qu'il repousserait le sol et non pas seulement pousserait, mais frapperait la balle avec un deuxième saut.
J'ai compris que lorsque nitro et un autre robot seraient ajoutés, tout serait plié à cause du manque d'itérations. Aussi à différents endroits, j'ai eu de gros problèmes de précision, que je ne savais pas comment résoudre. Je n'ai vu aucune
solution analytique ni aucun
mode de gestion intelligent .
J'avais besoin d'une stratégie complètement nouvelle, ou d'un simulateur magique qui combine précision et vitesse, et dans la phase finale me fournira suffisamment de trajectoires pour itérer. Je n'ai pas trouvé de nouvelle stratégie (étonnamment) et j'ai commencé à travailler sur un simulateur.
"Simulateur intelligent"
La première chose que je voulais faire avec précision.
J'ai simulé 100 Mikrotiks à la fois, bien qu'une collision - ou un autre événement - se soit produite sur l'un de ces cent Mikrotiks. Si vous l'ignorez, les objets entrent en collision plus tard que dans la réalité (toujours au 100e microtics), et rebondissent donc différemment. Vers la fin de la trajectoire, cette petite erreur peut se transformer en une grosse imprécision. Par exemple, nous pensons que la balle atteint le but ennemi, mais en réalité elle rebondira
dans la nôtre depuis le poteau.
Il est facile de voir que dans une situation où une collision se produit sur le
i ème microtics, au lieu de compter les 100 microtics, il suffit de compter les premiers
i - 1 microtics à la fois (en fait, l'étape physique est considérée pendant un certain temps
dt , et maintenant ce temps sera
t * (i - 1) , où
t est le temps correspondant à un Mikrotik). Vous devez maintenant simuler 1 microtique (
dt = t ) et les
100 - i micros restants. Nous obtenons exactement le même résultat en seulement trois simulations au lieu d'une centaine. Le seul problème est que nous ne savons pas sur quels microtics la collision se produira.
Étant sur un tick fixe de la simulation, nous pouvons faire n'importe quel nombre de microtics de 1 à 100 dans une simulation et voir s'il y a une collision ou non. Dans ce cas, l'image sera comme ceci: au début il n'y a pas de toucher, mais à partir d'un certain nombre de microtiques et jusqu'à une centaine il y a un toucher. Sauf dans de très rares cas, quand il n'y a pas de contact au début, alors il y a un contact sur un segment de la microtique, puis à nouveau il n'y a plus de contact.
Par conséquent, il est possible de trouver le Mikrotik où la collision s'est produite en utilisant une recherche binaire pour 10 simulations dans le pire des cas. Et comme décrit précédemment, pour trois simulations, vous pouvez obtenir l'état du monde à travers 100 microtiques avec une précision parfaite.
En fait, il y avait plusieurs autres types d'événements en plus d'une collision, et plusieurs pouvaient se produire pendant une tique, donc seul le premier événement était localisé avec une dichotomie, puis le deuxième événement était localisé au suffixe restant de la dichotomie de tique, et ainsi de suite. Ainsi, une tique a été considérée comme des segments de plusieurs microtiques par simulation, jusqu'à ce que tous les événements aient été comptés.
Les problèmes ont donc été résolus avec précision. Mais en raison du fait qu'il y avait 5 objets dans la simulation, et selon les règles finales, il devait y en avoir 7, et tous se sont souvent écrasés, en moyenne les dichotomies ont été appelées trop souvent, et cela a fonctionné de manière prohibitive. J'ai donc procédé à la deuxième étape du développement du simulateur - optimisation.
Évidemment, lorsque la trajectoire de l'un des robots passe, tous les autres objets dans lesquels ce robot ne s'écrase pas se déplacent de la même façon à chaque fois. Il est clair que recalculer leurs états avec un simulateur - par exemple, calculer de lourdes collisions avec l'arène - n'est pas nécessaire.
Avant de trier les trajectoires d'un robot particulier, il suffit de simuler honnêtement et de se souvenir pour les objets restants de leurs états à tout instant, puis de simplement prendre ces états de la mémoire. Nous appelons ces objets statiques, et un robot dont la trajectoire est triée est dynamique.
Si soudainement un objet dynamique influence (a une collision) avec un objet statique, nous ajoutons cet objet statique aux objets dynamiques jusqu'à la fin de la simulation de la trajectoire courante. En fait, au stade du stockage des états pour les objets statiques, un graphique des influences les uns sur les autres est construit, puis il est utilisé pour transférer correctement les objets statiques vers des objets dynamiques. Par exemple, un robot ennemi a frappé la balle, et nous avons généré un chemin où nous renversons le robot ennemi avant qu'il ne frappe la balle. Maintenant, la balle volera plus loin, et pendant la simulation, lorsque le robot ennemi est ajouté à des objets dynamiques, il est nécessaire de noter que la balle doit être ajoutée aux objets dynamiques un peu plus tard, à la tique à laquelle le robot ennemi frapperait la balle si nous ne le gênions pas. . Dans le cas général, cela se fait récursivement selon le graphe d'influence.
Désormais, le simulateur ne calcule pas tous les objets, mais uniquement les objets dynamiques, ce qui correspond en moyenne à un objet et demi au lieu de sept, et les longues dichotomies sont beaucoup moins utilisées. Cela s'est avéré très rapidement et n'a plus à souffrir en finale avec des robots supplémentaires - cool!
La 26e version avec un nouveau simulateur et une profondeur de simulation réduite de 200 à 100 a été envoyée au premier tour. Mais il contenait quelques bugs, et il n'y avait aucun avantage évident.
Le dernier problème de précision est resté: le mouvement le long de l'arrondi de l'arène. Dans ce cas, pour atteindre une précision absolue, il est nécessaire de compter honnêtement 100 microtiques. La solution était étonnamment simple: toujours sauter de toutes les surfaces à l'exception du sol. Pas d'arrondi - pas de problème.
De plus, pendant un certain temps, j'ai optimisé, affaibli et, en regardant des jeux avec des stratégies plus intelligentes, j'ai ramassé de nouvelles constantes de score. C'est devenu beaucoup mieux, la stratégie est montée haut dans le classement et la 37ème version a obtenu le meilleur résultat de toutes mes stratégies dans le bac à sable tout le temps avant la finale.
À partir de ce moment, j'ai loué une machine à 32 cœurs dans un service cloud pour exécuter mes stratégies les unes contre les autres et j'ai commencé à expérimenter beaucoup avec tout de suite. Changé les constantes. J'ai essayé d'utiliser ma propre stratégie pour prédire les actions de l'ennemi, mais cela n'a pas aidé même dans les matchs contre ma stratégie.
En résolvant l'équation, il a appris à calculer la dernière action de l'ennemi et a commencé à prédire son comportement ultérieur. Ajout du support pour nitro: un point aléatoire sur la surface de la sphère est sélectionné pour l'action. Plusieurs modifications mineures ont été apportées. Mais il n'y a pas eu beaucoup de progrès. Au début du deuxième tour, 4-5 sommets me gagnaient régulièrement
Pourtant, je ne désespérais pas. J'avais deux améliorations que je comptais mettre en œuvre avant la finale, et j'espérais qu'elles amélioreraient considérablement la stratégie. J'ai décidé de ne pas les aborder jusqu'à ce que le bac à sable commence selon les règles finales, et plutôt de passer du temps à déboguer et à optimiser ce qui a déjà été fait pour minimiser les risques de bugs malveillants au cours de la dernière semaine, lorsque chaque minute compte.
La dernière semaine avant le début de la finale.
La première amélioration que j'ai apportée a été la suivante. Dans les matches, dans le cas général, la plupart de mes problèmes, et toute autre stratégie survient lorsque l'adversaire prend possession du ballon. Il le frappe en quelque sorte, passe, en général - contrôle. Il est impossible de prédire la trajectoire de la balle et de prévoir d'autres actions rentables dans ce cas, il reste à faire «quoi que ce soit» jusqu'à ce que l'adversaire commette une erreur et transfère le contrôle de la balle à mes robots. Et après cela, vous devez essayer de ne pas effectuer de telles actions qui pourraient conduire au fait que la balle sera à nouveau avec l'ennemi.
En d'autres termes, au moment de planifier la trajectoire, je veux prendre en compte les positions possibles des adversaires et essayer de ne pas y frapper le ballon. J'ai décidé d'utiliser un champ potentiel à quatre dimensions (les trois premières dimensions sont les coordonnées, le côté des cubes est égal au diamètre du robot et la quatrième dimension est le temps), que je remplirai, générant des trajectoires ennemies aléatoires.
Plus tard, lors de l'évaluation de la trajectoire de mon robot, j'ai calculé la somme de tous les cubes qui ont traversé la balle aux points correspondants dans le temps, et multipliée par un coefficient qui dépasse toutes les autres valeurs du score. Autrement dit, le champ potentiel a été pris en compte avec la priorité la plus élevée après l'objectif. Cela permettait également de supprimer les ennemis de la simulation après les 30 premières tiques (l'ennemi pouvait faire quoi que ce soit pendant ce temps lorsqu'il était au sol, et de telles prévisions inexactes à distance ne faisaient qu'interférer) s'ils n'étaient pas dans l'air (il semblait que personne ne serait dans l'air pour changer la trajectoire de manière complexe à l'aide de nitro).
En générant des trajectoires aléatoires pour l'ennemi, il a été possible de connaître le temps minimum qu'il lui a fallu pour frapper la balle. Cette valeur a été utile pour résoudre le problème avec les premiers sauts de mon gardien de but hors de la porte. Beaucoup de buts ont été marqués pour moi parce que mon gardien de but a sauté tôt et est devenu incontrôlable dans les airs. Après cela, l'ennemi a facilement prédit comment mon gardien de but volerait et, s'il le pouvait, a changé la trajectoire du ballon avant que mon gardien de but ne l'atteigne. Maintenant, j'ai annulé le saut du gardien de but si l'ennemi peut frapper la balle plus tôt que mon gardien de but ne le prévoit.
Il s'est avéré que, sans dommage significatif à la stratégie, il est possible de calculer la trajectoire non pas à chaque tick, mais à travers un. En réduisant de moitié le temps d'exécution, j'ai ainsi doublé le nombre moyen d'itérations. Un peu de magie se produit ici. Il semble que si nous comptons les trajectoires de chaque seconde et que nous doublons le nombre d'itérations, le nombre moyen d'itérations ne changera pas. Mais en fait, le simulateur comptera deux ticks (200 microtiks) par simulation au lieu d'un. Et les trajectoires seront déjà profondes de 50 et non de 100. C'est pourquoi le nombre moyen d'itérations doublera.
Resté quelques jours avant la finale. Bien que ma stratégie ait commencé à concéder moins de buts en raison d'un bon contrôle du ballon, je n'ai pas commencé à mieux marquer. J'ai donc dû la motiver avec un coefficient quand bientôt pour le but d'un adversaire. Plus un but est marqué rapidement, plus le ratio est élevé. Et ce coefficient croît beaucoup pour dépasser le reste du score et ne pas avoir peur du champ potentiel, quand, par exemple, il reste 10 ticks avant de marquer.
Ajout d'un calcul de l'endroit où l'ennemi envoie du nitro. Cela a été fait en utilisant la force brute avec une certaine étape. De plus, le gardien de but a commencé à reconstituer les réserves de nitro, quand rien ne menace mon objectif.
La deuxième amélioration majeure a été d'utiliser minimax. Si l'utilisation de forces d'impact différentes pour l'ennemi pendant la construction de trajectoires statiques affecte le vol de la balle, alors pendant la recherche, les deux options ont été considérées, avec une force d'impact maximale et minimale de l'ennemi, et le minimum des estimations a été pris.
En finale, j'avais 7 options de trajectoires lorsque le robot était au sol:
- 2 coins sans saut;
- 2 coins avec un saut;
- 2 angles avec saut et vitesse codirectionnelle nitro;
- 2 angles avec un saut et nitro compense la gravité;
- 1 coin avec un saut;
- 1 angle avec saut et vitesse codirectionnelle nitro;
- 1 coin avec un saut et nitro compense la gravité (non utilisé en raison d'un bug, remarqué lors de l'écriture d'un article).
et deux options lorsque le robot est en l'air:
- nitro à un point aléatoire sur la surface de la sphère et force d'impact aléatoire;
- force d'impact aléatoire.
Il y avait de la compétition quelques heures avant les finales, mais ma stratégie était clairement meilleure. Il semblait que tout avait déjà été fait, je n'avais pas dormi plus d'une journée et rien ne dépendait de moi. Il restait à regarder. Deux heures avant la finale, Andrei a envoyé son graal fraîchement cuit et a remporté avec succès la première place. L'historique de sa participation se trouve ici:
habr.com/en/post/440398 .
Dans l'intervalle entre les étapes de la finale, j'ai ajouté un champ potentiel éloignant le ballon de mon but, indépendamment de tout le reste, et cela, il me semble, m'a égalé avec Andrei. Mais il était déjà tard, car j'avais perdu 7 points en première mi-temps, et même 3/3 victoires en seconde mi-temps n'étaient pas suffisantes.
L'IRAC est une compétition difficile et les prix sont remis aux participants très, très difficiles. Lorsqu'un participant est en haut de la table, pour lui, ce n'est pas seulement du divertissement - c'est une lutte. Il y a beaucoup de petites choses à considérer lors de la rédaction d'une stratégie solide. Chaque décision prise peut affecter de manière significative le résultat.
Le code source de la stratégie sera disponible
ici .