C'était mercredi, il y avait une réunion ennuyeuse ordinaire au travail. Le designer s'est gratté derrière l'oreille et le testeur s'est enterré au téléphone. Une voiture a démarré devant la fenêtre et j'ai reçu une lettre par téléphone - la
Coupe AI russe 2018 a commencé. Autour, personne ne se doutait de rien, et à ce moment-là, je savais déjà exactement ce que je ferais dans le mois et demi à venir.
Bonjour à tous, je m'appelle
Andrey Tokarev et je voudrais partager mon expérience de participation à la
Russian AI Cup 2018 .
Qu'est ce que c'est
Russian AI Cup est un concours annuel d'intelligence artificielle organisé depuis 2012. Ici, vous devez écrire un algorithme qui contrôle quelqu'un ou quelque chose, et ces quelqu'un ou quelque chose se font concurrence. Cette année, il a fallu contrôler des robots jouant au football.
J'avais déjà une certaine expérience de jeu dans de telles compétitions. En particulier, j'ai participé à la Russian AI Cup 2016 (sans prix) et à la Mini AI Cup 2018 (2e place).
On y va
Tout d'abord, j'ai créé mes classes du monde du jeu, des objets, pris un vecteur bidimensionnel et tridimensionnel des compétitions passées et téléchargé le tout dans le référentiel Git. Bien sûr, vous pouvez utiliser des objets du module linguistique, mais il n'y a pas de vecteurs, ils ne peuvent pas être modifiés, et en effet, il est plus pratique d'utiliser vos propres classes. Ce que je n'ai pas réécrit, c'est le cours d'arène, il me convenait tel quel et il n'y avait pas besoin de le changer.
La simulation
Ici, nous avons un monde de jeu, et que pouvons-nous y faire?
Mais cela ne s'avère rien, jusqu'à ce que nous puissions simuler le monde du jeu, pas même déterminer si la balle vole dans un filet vide. Nous annulons donc la simulation. Le code de simulation ne fait pas partie du pack de langue, il est fourni dans une langue que je ne connais pas. Mais sa syntaxe C est similaire, donc copier-coller + définition des fonctions nécessaires, et la sim est prête à 90%. Là où il fallait diriger mes mains, j'ai essayé de le faire avec précaution, car alors les erreurs ici peuvent être coûteuses et les attraper ne sera pas facile. J'ai quand même réussi à faire quelques erreurs, mais cela m'a coûté un peu de sang.
Il est immédiatement devenu clair que si vous utilisez une simulation honnête (100 micro ticks), cela ne suffit pas, il est beaucoup plus rentable de calculer 100 options avec un microtique qu'une option avec 100 microtiks. J'ai quand même laissé 2 microtiques pour que l'écart ne soit pas trop important.
Bases de la stratégie
Et donc nous avons un monde de jeu et nous pouvons simuler son changement. Et maintenant?
Il existe différentes approches. Lorsqu'il y a peu de mouvements possibles et que la profondeur n'est pas très grande, vous pouvez le prendre par force brute: triez tous les mouvements, même les mouvements de retour de l'adversaire, ils ont à nouveau leurs propres mouvements ... minimax Lorsqu'il y a beaucoup de mouvements, vous pouvez les limiter artificiellement, par exemple, vous pouvez prendre des directions qui sont des multiples de 15 degrés, sauter à chaque dixième tick et utiliser la même minimax. Mais cette approche me semble adaptée lorsque le résultat n'est pas trop sensible aux petits changements de mouvements, ici une déviation d'un degré en direction du robot entraînera de grandes déviations après la collision.
L'autre extrême, lorsque nous faisons des mouvements sans recherche exhaustive, est une sorte d'heuristique. Cette approche peut être viable, mais créer un joueur de football fort avec une pure heuristique est très difficile.
Mais la combinaison des deux méthodes semble prometteuse: vous pouvez d'abord vous déplacer dans une direction aléatoire, puis terminer le jeu avec une heuristique qui peut courir jusqu'au ballon et sauter au bon moment. La même heuristique combinée peut être utilisée pour prédire les mouvements de l'adversaire. Plus tôt, j'avais déjà utilisé quelque chose de similaire dans la compétition, et cette méthode ne s'est pas avérée plus ou moins mauvaise.
Et donc nous écrivons l'heuristique (dans le jargon RAIK-ovsky intelligent guy ou tout simplement intelligent)!
Comme je voulais voir le résultat le plus rapidement possible, smartgay a été écrit à la hâte et il s'est avéré plutôt stupide (même le code est honteux). Je viens de calculer le temps après lequel le robot pourrait attraper le ballon en fonction de la vitesse actuelle du ballon et de la vitesse maximale du robot, et j'ai couru au point où le ballon serait à ce moment-là (les collisions n'ont pas été prises en compte). Il ne savait pas sauter et ne tenait même pas compte de la hauteur du ballon, il pouvait facilement courir sous le ballon, et si le ballon s'éloignait trop vite, il courait généralement dans la direction opposée. Puisque smart n'était pas capable de sauter, je l'ai d'abord fait sauter à une distance fixe du ballon, et un peu plus tard le choix du moment du saut est tombé sur les épaules d'un grand hasard! L'absence d'un choix rationnel d'un saut s'est avérée être un gros inconvénient, mais plus à ce sujet plus tard. Mais en général, une smart clean n'a pas l'air mal, et parfois même marqué des buts, mais aussi dans leurs propres buts.
Ensuite, nous avons besoin d'une fonction d'évaluation (OF).
Le FO initial ressemblait à ceci: (1000 - tick) * objectif + ballon.z + une fonction de la position relative du robot et du ballon de sorte qu'il monte jusqu'au ballon même s'il ne peut pas l'atteindre. Ici, l'objectif peut être -1,0,1 selon qu'il y a un objectif et à qui, et tick est le tick depuis le début de la simulation sur laquelle l'objectif a eu lieu. La dernière chose est que le robot ne repousse pas constamment l'objectif.
Maintenant, nous faisons tourner le robot dans une direction aléatoire un nombre aléatoire de tiques, puis nous transférons le contrôle à l'intelligent, qui le mène à la balle, à un moment aléatoire, il saute et
frappe la balle qui manque. De plus, il vaut mieux courir non pas au centre de la balle, mais avec un décalage aléatoire d'une petite distance, afin que le robot puisse frapper à un angle.
La simulation a duré un temps fixe de 2 secondes, et à la fin l'OF a été appelé. Un tel scénario a été répété plusieurs fois pour chaque robot et le meilleur a été sélectionné en fonction de la note.
Jusqu'à présent, cette stratégie a un sérieux inconvénient: elle n'a pas de mémoire - tout est calculé à partir de zéro à chaque tick, ce qui signifie que la stratégie peut voir un objectif sur un tick et ne pas le trouver le suivant. Ce n'est pas le cas, vous devez le réparer - nous enregistrons la meilleure option trouvée pour chaque robot et la réutilisons dans le prochain tick. De plus, les robots sont désormais au courant des affaires de l'autre, par exemple, si le premier va frapper le ballon, le second ne court pas après le ballon, mais essaie de faire une passe.
Gardien de but
Nous avons besoin d'un gardien de but. Mon gardien de but était fondamentalement différent de l'attaquant en ce qu'il s'activait lorsque le ballon approchait d'une certaine distance du but, sinon il reviendrait simplement à son point de base.
Résumé
Maintenant, nous avons une bonne stratégie de base qui peut faire tout ce qui est nécessaire et sur laquelle on pourra s'appuyer à l'avenir.
Peut-être que tout ce qui est décrit ci-dessus semble simple et logique, mais honnêtement, au début de la compétition, il n'y avait pas une image aussi claire de la stratégie qui semblait plus proche de la fin, et il a fallu deux semaines pour la mettre en œuvre, et cela représente 1/3 de la compétition.
Un peu sur les tests
Au fil du temps, les Grails qui doublent la puissance du jeu se produiront de moins en moins, et nous devrons choisir des changements qui donnent une augmentation de + 10-20% des objectifs. Et puis il s'avère que de si petits gains ne sont pas si faciles à identifier. Pour un résultat complet, vous avez besoin de centaines de buts marqués, et avec une fréquence de buts d'une fois par minute, cela représente de très nombreuses heures de temps de jeu. Pour cette raison, je n'ai presque pas testé de stratégies sur le serveur, mais j'ai effectué de longs tests locaux par rapport aux versions précédentes. Mais même tester localement tout changement pendant une demi-journée ne serait pas très pratique. Par conséquent, j'ai appliqué un petit "truc" - j'ai testé des stratégies tronquées. Si, par exemple, sur un serveur, je passais plus de 50 options par robot, puis seulement 10 localement, cela me permettait de faire des tests dans un temps tolérable.
Améliorations
Ensuite, je décrirai les principales améliorations et leur évaluation sous la forme suivante: par combien de pour cent la nouvelle version marque plus d'objectifs qu'elle n'en reçoit de l'ancienne. C'est-à-dire si par exemple un nouveau bat l'ancien avec un score de 120: 100 c'est + 20%, s'il fait 2 fois plus alors c'est + 100%.
- Votre gardien de but doit battre les buts. S'il ne réussit pas, donnez-lui plus de temps, augmentez le nombre d'options jusqu'à x10. + 15%
- Parfois, lorsque le gardien de but frappe le ballon, il part en vol libre et alors qu'il a le temps de retourner à sa place, il marque déjà un but. Immédiatement après avoir frappé le ballon, nous essayons de le remettre à sa place et d'ajouter la tique à laquelle il est revenu à l'évaluation avec un petit coefficient négatif. + 20%
- Un coup de pied supplémentaire sur le ballon devant le but d'un autre augmente les chances d'un but, nous donnerons un bonus dans l'OF pour cela. + 60%
- Expérimentez avec nitro! Il me restait encore quelques jours avant le premier tour, mais j'ai décidé de tester le nitro à l'avance. Intuitivement, il m'a semblé que le nitro affecterait grandement le gameplay, car sur un tank, vous pouvez sauter au plafond ou survoler tout le terrain. Pour commencer, j'ai appris à utiliser la nitro uniquement pour l'attaquant, et même alors uniquement dans les airs, mais je n'ai pas encore récupéré les paquets. Le nitro a été utilisé pendant le vol dans la direction désormais aléatoire maintenant tridimensionnelle. Le résultat a été, pour le dire légèrement, pas très, je n'ai pas réussi à presser plus de + 20%, et l'utilisation de nitro au sol n'a pas donné de résultats. Le problème avec nitro a donc été temporairement mis de côté, bien qu'à partir de ce moment, j'ai essayé de réaliser des tests avec nitro activé.
- Trop de randomisme! Le hasard est bon, bien sûr, il donne parfois des trucs auxquels vous ne pouvez même pas penser, mais d'un autre côté, quand il y en a trop, la probabilité que tout coïncide est très faible. Et j'en avais trop. J'ai décidé d'essayer de transférer le moment du saut sur la base analytique. Comme il n'y avait pas d'accélération horizontale dans l'air (oubliez nitro), il était facile de calculer le moment de la rencontre du robot et de la balle (t1), et la hauteur de la balle à ce moment (h1). Maintenant, nous calculons le temps (t2) après lequel le robot sera à une hauteur de h1, sautons maintenant. Ici, nous obtenons une équation quadratique, si elle n'a pas de solution ou t2 <t1, sautons tôt, sinon nous sautons.
Le résultat m'a un peu choqué, vissant le bon saut à la fois à l'attaquant et au gardien de but, les tests ont montré + 200%, soit la nouvelle version a battu l'ancien 3 fois dans les buts, le vrai Graal! C'était le 17 janvier, après avoir téléchargé la stratégie sur le serveur, il a gagné une cote de 200+ en une séquence de 20 matchs gagnants et a dirigé le bac à sable pendant un certain temps.
- Nous apprenons au gardien de but à jouer. Jusqu'à ce que mon gardien de but s'active, il se tenait comme un pilier. Marche latérale facile: x = ball.x / 4 a légèrement augmenté.
- L'adversaire ne doit pas être prédit, mais supposé! En regardant à travers les matchs, j'ai remarqué que j'obtiens souvent un but après que le gardien de but frappe la balle directement sur l'adversaire et qu'il marque un but pour moi à la volée. Pour frapper la balle en contournant l'adversaire, vous devez d'abord déterminer où il peut être au nième tick. Bien sûr, nous ne prendrons pas en compte nitro. Je pourrais encore déterminer la vitesse du robot analytiquement, il semble y avoir l'intersection de deux cercles. Mais il ne pouvait pas faire face au territoire accessible. Eh bien, au diable avec lui, nous sommes des programmeurs (pas par l'éducation), la machine compte pour nous. Divisez l'avion en n directions, déplacez le robot dans chaque direction, les points d'extrémité seront les sommets du polygone, qui détermine la portée.
Comment l'utiliser? J'ai ajouté une coche où l'adversaire peut toucher le ballon pour la première fois, avec un bon coefficient dans l'OF. Étant donné que ce n'est plus un scénario d'actions spécifique, mais une sorte de nuage de portée a été envisagé pour l'adversaire, j'ai retiré les robots ennemis dès qu'ils sont entrés en contact avec le sol.
Résultat + 40%. De plus, cette approche a deux gros avantages: la suppression des robots ennemis dans le premier accélère la simulation, et cela, à son tour, permet de trier plus d'options, et dans le second, nous n'avons pas à nous soucier du contrôle de l'adversaire. Conclusion: profit!
- Des erreurs stupides, mais sans elles. Il y a deux lignes dans le simulateur officiel:
if abs(ball.position.z) > arena.depth / 2 + ball.radius: goal_scored()
Je ne sais pas qui comment, mais j'ai laissé la fonction abs () telle quelle, mais en vain. La ligne abs () (à ne pas confondre avec std :: abs ()) prend des valeurs entières, ce qui signifie que les décimales sont tronquées. En pratique, cela signifie que je n'ai enregistré le but que lorsque le ballon était déjà à un mètre derrière la ligne de but. Remplacez abs () par fabs ()! Ce n'est pas la première fois que cette abs () me fait défaut.
- Nitro à nouveau. Le deuxième tour approchait et il n'y avait nulle part où remettre l'utilisation normale du nitro. Il a optimisé son utilisation, a pris en compte la définition d'un saut, a autorisé l'utilisation du gardien de but et a également commencé à collecter délibérément des colis par le gardien de but.
- Revenons à la simulation. J'ai déjà dit que 100 options avec un microtik sont plus rentables qu'une option avec 100 microtics. C'est vrai, mais cela ne signifie pas qu'avec un Mikrotik, tout va bien, sans mesures supplémentaires, les écarts étaient assez graves, ce qui a empêché de jouer au football à un niveau professionnel. Pour améliorer la précision de la simulation, j'ai appliqué les méthodes suivantes:
- Pendant le saut, deux Mikrotik supplémentaires.
- Lorsque nous combinons beaucoup de microtiques, alors en se déplaçant, il est plus correct d'utiliser la vitesse moyenne et non la vitesse finale.
- En utilisant la recherche binaire, nous trouvons la tique dans laquelle la collision se produit, et nous effectuons deux sous-tactiques: l'une avant la collision, l'autre après. (Je n'ai pas pris en compte la collision de la balle avec une surface plane, là l'écart me semblait insignifiant.)
- Courir le long d'une surface incurvée causait encore de grandes différences et parfois le gardien de but manquait à cause de cela. Par conséquent, lorsque mon gardien de but était sur une surface incurvée, j'ai utilisé 10 microtics.
En moyenne, environ 1,4 mikrotiks par tick ont été obtenus, et la précision était proche de l'idéal. Bien sûr, je n'ai pas vissé ces optimisations à la fois, mais progressivement. Je ne sais pas à quel point ils ont influencé la puissance du jeu, mais je pense que c'est très important.
Qu'avons-nous
Grâce à un grand nombre d'améliorations significatives, la stratégie a progressé régulièrement dans le classement et avant le deuxième tour, elle a presque atteint le jalon historique - 5000 Elo, gagnant en toute confiance du terrain en premier lieu.
Parfois, vous ne pouvez même pas croire quelles combinaisons émettent au hasard. Merci à la gentille communauté anonyme pour la découverte.La semaine dernière
Dans le cadre d'une si bonne marge, je me suis permis de ne pas rechercher de petites améliorations, mais de chercher quelque chose de plus global, notamment en ce qui concerne les jeux 3x3. Cependant, les expériences visant à un jeu plus d'équipe, ou à inculquer un troisième joueur dans un rôle spécial, ou à apprendre au gardien de but à sortir pendant l'échec, ont échoué. La semaine entière a été passée presque en vain. Malgré cela, quelques jours avant la finale, j'étais toujours en tête du classement.
Et maintenant, le dernier jour avant l'arrivée de la finale, je commence à perdre contre un, puis un autre et même un troisième concurrent. Si vous n'ajoutez pas, vous pouvez rester sans prix. Il ne s'est rien passé toute la semaine, que puis-je faire le dernier jour? L'ambiance était - au moins abandonner.
La résurrection
Après avoir vu quelques matchs perdus, j'ai remarqué que tout le monde saute
comme des chèvres sur nitro, passe le ballon en l'air, mais le mien ne peut pas l'obtenir. J'ai essayé la chose la plus simple qui puisse conduire à ce comportement - j'ai ajouté la hauteur de la balle au moment de l'impact avec un coefficient solide dans l'OF. Résultat + 50%, wow! Inspiré par le résultat, j'ai commencé à tordre intensément les paramètres (ce que j'ai négligé pendant toute la compétition), ajouté de nouvelles options de recherche, ajouté un contrôle du temps à la fin, ce qui m'a permis d'utiliser le temps au maximum sans risquer ma vie. À la fin de la journée, il s'est avéré + 150-200%, soit la nouvelle version a battu la précédente presque trois fois dans les buts! Oui, oui, celui-là même qui, près d'une semaine avant la finale, s'est affaissé et a atteint une note sans précédent de 5000+ dans l'histoire du championnat. Sur le serveur, la stratégie a été testée avec succès quelques heures avant la finale. Après cela, je l'ai préparé pour le lancement final: désactivation des assertions, ajout de contrôles de division à zéro, téléchargement à nouveau sur le serveur et passage en mode veille.
Dernière partie finale
La première partie des finales a eu lieu la nuit. J'ai suivi les résultats jusqu'à ce que je m'endorme, je me lève tôt le matin. 3 vagues ont été jouées (dans une vague chacune joue avec chacune), j'ai perdu un seul match contre
TonyK , et comme Anton perdait parfois encore face à d'autres joueurs, j'étais en tête avec une marge de 7 points (2 points pour la victoire). Un écart assez sérieux pour 3 vagues, mais pas assez pour se détendre.
Le dernier jour, bien sûr, je n'avais pas l'intention de faire quoi que ce soit de grave, essentiellement tordu les paramètres. Plusieurs modifications ont été apportées, mais comme tout a été testé à la hâte, je n'étais même pas complètement sûr que l'effet était positif. En général, l'augmentation était de 0 à 20%. Mais Anton a ajouté de manière significative et au moins a commencé à jouer pas pire que moi.
Rien à faire, j'ai dû envoyer ce qui est, et espérer de la chance et une réserve de points.
Deuxième partie finale
Heureusement, les matchs ont été organisés de telle sorte qu'au début, les dirigeants ont joué entre eux, donc il n'y avait pas lieu de s'inquiéter, le tout premier match était contre TonyK. La chance était de mon côté, j'ai gagné le premier combat, ainsi que tous les autres matchs de cette vague, tandis que TonyK a perdu un point de plus. Un écart de 10 points pour deux vagues à la fin est presque impossible à jouer, il était désormais possible de se détendre.
Résultat final: 352 victoires et 2 défaites (toutes deux d'Anton), 1ère place avec une marge de 12 points.
Merci et autres ordures
En général, j'ai vraiment aimé la tâche de cette année, c'était «pour moi» (la simulation est à moi, et la tridimensionnalité ne me fait pas peur) et les matchs étaient spectaculaires, je pense qu'il était intéressant de regarder non seulement les participants.
Je remercie les organisateurs pour la merveilleuse compétition.
Je tiens également à remercier tous les participants, en particulier Anton Kozlovsky (
TonyK ) pour la compétition en finale, Ivan Tyamgin (
tyamgin ) pour la compétition dans le bac à sable et Alexey Dichkovsky (
Commandos ) pour s'être abstenu de participer et ainsi augmenté mes chances de gagner.
Bonne chance à tous dans le prochain RAIK!