Alors

Mon nom, comme l'année dernière, est Andrei Rybalka, mais cette fois, j'ai 33 ans. Et, puisque j'étais dans le top 10, j'ai décidé de partager à nouveau mon approche pour écrire un bot de jeu pour la Russian AI Cup 2018 .

Cette fois, la tâche était le football. La tâche elle-même rappelait quelque peu celle de l'IRAC 2014, quand il s'agissait du hockey, mais la solution était complètement différente.

Cette fois, le monde était tridimensionnel et cette tridimensionnalité était pleinement utilisée. Le jeu lui-même rappelait le plus la Rocket League .

Je ne vais pas ennuyer la partie introductive, il est plus facile de montrer à quoi cela ressemblait. Vous pouvez regarder les jeux sur le site ou sur la vidéo:

Pour que la vie ne nous semble pas trop douce, les développeurs, en plus du non-déterminisme du monde du jeu, ont également divisé le tick du jeu en 100 subwoofers, ce qui a initialement mis fin à une simulation précise pour la plupart des participants, et encore plus pour moi, ayant l'intention d'écrire un bot en Java lent.

Aussi, je dois dire que le championnat est divisé en tours, ce qui serait probablement plus correct d'appeler des tours.

En bref sur le système de tournois

Pour commencer, 2 semaines sont accordées pour le développement. Puis le premier tour passe. Les 300 meilleurs vont plus loin.

Après le tour, les règles du jeu changent (en particulier, du nitro est ajouté au jeu) et 2 autres semaines sont accordées, après quoi le deuxième tour passe.

Ensuite, les règles sont à nouveau compliquées (le troisième joueur est ajouté), une autre semaine est donnée et nous jouons la finale.

Mais ce n'est pas la fin. Après les finales, il y a une autre semaine, à la fin de laquelle le bac à sable s'arrête simplement, et les 6 meilleurs, hors vainqueurs des finales, sont également décernés. La différence fondamentale entre la finale du bac à sable et la finale du championnat est que dans le bac à sable, les jeux sont créés dans un format aléatoire, et pas seulement dans le format de la manche en cours.

Histoires de participation

La partie technique sera plus faible. Pour qui l'histoire n'a pas d'intérêt, vous pouvez faire défiler vers le bas jusqu'à ce qu'elle devienne bonne.

Premier tour

Il a commencé, comme la plupart, par une semaine de beta. J'ai passé beaucoup de temps, plus de 4 heures chaque soir.
Avant de remplir la première version, il a fallu plusieurs itérations
nous codons jusqu'à ce que nous commencions à battre la version précédente - nous collectons - nous considérons la version actuelle de la précédente - nous répétons .

Je n'étais pas pressé avec le premier remplissage et c'est arrivé quelques jours avant la manche. Et, puisque, jusqu'à présent, mon bot n'a joué avec personne, je ne savais pas dans quel genre de monde j'étais et quelles positions dans le classement je pouvais revendiquer. Quand j'ai vu que j'avais déjà remporté plus de 100 matchs de suite sans une seule défaite, je me suis calmé.

En général, la première défaite que j'ai subie était, semble-t-il, à la 12e place, dans le temps imparti, et le premier match perdu de suite était déjà dans le top 10.

Bref, je me suis rendu compte que j'avais des chances d'entrer dans le deuxième tour, où va le top 300.
Par conséquent, je n'ai pas poursuivi la position et je n'ai rien inondé d'autre pour le tour, mais j'ai simplement continué à travailler.

À ce moment-là, j'ai vu qu'il y avait encore beaucoup d'espace à améliorer sans connecter de nitro (qui est apparu après le 1er tour), alors je me suis concentré sur la partie principale de la stratégie, réalisant qu'avant le deuxième tour, il y aurait plus de 2 semaines ou plus et j'aurais le temps de fixer le nitro.

Deuxième tour

La première semaine, je programmais activement, mais je n'ai toujours pas connecté nitro. Je voulais le faire la deuxième semaine. Mais tout s'est passé différemment, car à la fin de la première semaine, j'avais contracté une pneumonie. Je n'ai pas pu programmer, donc je viens de télécharger ce que c'était, et, on peut dire, la participation active au championnat pour moi à cet endroit était terminée.

Au cours des 3 prochaines semaines avant la fin du championnat, j'ai travaillé sur une stratégie d'un montant de peut-être 20 heures.

En conséquence, au deuxième tour, mon bot, en principe, ne savait pas qu'il y avait du nitro dans le jeu, mais a quand même pris la 16e place.

Finale

En finale, un troisième joueur a été ajouté.

J'ai écrit en Java lent, et non en C ++, car 7 personnes sur 8 sont plus élevées que moi dans le classement, et avant cela, mon bot tombait souvent en timeout, donc avec l'avènement du troisième joueur, il a commencé à tomber dans 100% des jeux. Heureusement, les jeux dans le bac à sable sont créés dans un format aléatoire, donc je
perdu seulement tous les trois matchs et donc pas trop volé. Il semble être tombé à la 18e place.

Sauf pour la programmation, l'édition des coefficients dans la fonction d'évaluation et l'exécution des tests, puis pour la première fois, après le début de la maladie, je me suis assis au bot le soir de la veille de la finale. Il a ajouté une nitro très simple dirigée strictement vers le haut pour que deux attaquants arrêtent de courir au même point et entrent en collision là-bas, et réduisent tout ce qu'il pouvait pour un jeu 3x3, à partir de la profondeur de rendu et se terminant avec la précision de simulation, seul le bot n'est pas mort par timeout.
Sous cette forme, il a joué la finale.

Dans l'intervalle entre les deux moitiés de la finale, je me suis de nouveau assis dans le bot et j'ai passé quelques bonnes heures 10. Les changements concernaient pour la plupart la sélection dynamique des coefficients, l'interruption précoce de la génétique, etc. En général, je cherchais un équilibre entre la précision et la profondeur et la vitesse des erreurs de calcul.
En plus de la lutte contre la vitesse, il a apporté quelques modifications supplémentaires:

• Envoyé un attaquant distant (par rapport au ballon) à un point au milieu entre le ballon et le but de l'adversaire
• J'ai un peu fixé nitro (la description se fera dans la partie technique). C'était encore extrêmement simple, mais il est devenu beaucoup plus efficace.

Total, après avoir passé les tests et vu le score de 395: 254 par rapport à la version précédente, je me suis calmé. Cela m'a permis de prendre la 9e place en finale.

Sandbox Finale

J'ai continué à faire mal et je n'ai pas travaillé sur le bot pendant la majeure partie de la semaine. La veille de la fin, j'ai vu que plusieurs personnes téléchargeaient de nouvelles versions, qui gagnent souvent contre moi et peuvent jeter des bacs à sable hors des prix. J'ai donc passé quelques heures de plus.

Le seul changement majeur est que j'ai déterré ma branche dans Git il y a trois semaines, dans laquelle j'ai eu une simulation du mouvement de l'ennemi en utilisant mon algorithme simplifié. A cette époque, cela fonctionnait mal, mais je l'ai rappelé, j'ai effectué des tests, j'ai vu
qui surpasse la version précédente a presque doublé et inondé. Au total, au moment de l'arrêt, j'étais à la 10ème place du classement général, ce qui correspond à la 4ème en finale du bac à sable.

Comment tout cela fonctionne (partie technique)

Je m'excuse à l'avance en cas d'inexactitudes dans la terminologie. De plus, j'écris de mémoire, il est donc possible que quelque part je ne décrive pas la version finale.

Les algorithmes génétiques sont donc au cœur. Le chromosome se compose de plusieurs gènes:

• Nombre fractionnaire dans la plage -PI..PI, spécifiant la direction du mouvement
• Un entier compris entre 0 et 10 qui spécifie le nombre de répétitions de cette action
• Nombre fractionnaire de 0 à 1. Si la valeur est supérieure à un certain seuil, faites un saut

Le génotype peut comprendre un nombre différent de chromosomes, mais de telle manière que le nombre total d'actions (y compris les répétitions) est de 40.

Au départ, je crée plusieurs dizaines de génotypes aléatoires. J'y ajoute:

• La trajectoire à droite sur le ballon
• Trajectoires directes dans toutes les directions, seulement 10 pièces avec un décalage de 36 degrés
• Un génotype qui ne fait tout simplement rien (sans lui, le bot court toujours quelque part, même s'il se trouve déjà au point optimal)
• Meilleur génotype de la tique précédente

Ensuite, tout est simulé et exécuté via la fonction d'évaluation. N meilleurs génotypes "survivent" et sont clones M fois avec des mutations. Lors de la mutation, chaque gène change dans une plage donnée avec une probabilité de 10%. Eh bien, cela a été répété depuis plusieurs générations.
Il n'y a pas de croisement, dans ce problème je n'y vois aucun sens.

Au total, le nombre maximum possible de trajectoires par tick par joueur de football était d'environ 800, mais en fait, dans la plupart des cas, il était beaucoup moins, car dans certains cas (par exemple, lorsque dans un avenir proche nous ne pourrons définitivement pas toucher le ballon), le mouvement des joueurs a été remplacé par de simples heuristiques. De plus, N, M et le nombre de générations dépendaient de la situation sur le terrain. Tout d'abord, de la distance au ballon. De plus, l'erreur de calcul est interrompue avant la date prévue (mais pas avant la 5e génération) si une trajectoire avec une estimation acceptable est trouvée.

Macro

Le gardien court jusqu'au point devant le centre du but. Mes tests ont montré qu'il était préférable pour moi de jouer en étant devant le but, et non à l'intérieur, comme la plupart des joueurs du haut.

La position du point a dévié du centre en fonction de plusieurs facteurs: la position et la direction du vol du ballon, le point où le ballon a frappé mon but, si un but est prévu, l'emplacement de l'adversaire attaquant le plus proche, etc.

Si le ballon est du côté de l'adversaire et vole vers son but, on peut opter pour le nitro.

Si mon gardien de but peut frapper le ballon plus tôt que mon attaquant (plus quelques conditions supplémentaires), alors l'attaquant ignore le ballon et court jusqu'à un point au milieu entre le ballon et le but de l'adversaire. Je suis passé par beaucoup d'options, où exactement lui courir. Dans mon cas, celui-ci a fonctionné le mieux.

Sinon, si le ballon est trop loin, l'attaquant court en ligne droite jusqu'au point de contact le plus proche du ballon avec le sol, dans lequel il peut intercepter le ballon (si nous n'avons pas le temps pour le premier point de contact - vérifier le suivant, etc.)

Sinon (lorsque le ballon atteint), l'attaquant court à l'endroit où la fonction d'évaluation lui dit. Oui, et aussi, si le nitro se trouve à proximité et que nous pouvons le ramasser, nous le sélectionnons.

Dans un match 3x3, le deuxième attaquant est plus susceptible de viser le ballon et avec moins de course en avant, s'attendant à une passe du gardien de but. Mais s'il fonctionne toujours, alors un autre point est choisi - plus près de la ligne médiane.

De plus, chaque tick simulait une fois la balle 100 ticks en avant avec 100 microtiques (avec mise en cache).

Cette trajectoire a été utilisée dans de nombreux endroits. Par exemple:

• Pour déterminer les points de contact de la balle avec le sol
• Pour savoir si le ballon menace mon objectif et si le gardien de but doit passer en mode simulation

La même trajectoire exacte a été utilisée dans la simulation des trajectoires des joueurs, afin de ne pas compter la balle à chaque fois. Mais seulement jusqu'à la première collision du ballon avec n'importe quel joueur de football.

Au fait, écrire Footballist était paresseux, les mots Player, Robot étaient réservés par stratégie,
donc ma classe wrapper s'appelait simplement Mec :)

La simulation

Dans la plupart des cas, il est allé avec un microtique, mais dans certaines situations, il est passé en mode précis avec un grand nombre de microtiques (au début, il était de 100, puis il a été réduit à 50 dans un jeu 2x2, car les tests ont montré que la différence de résultats était dans la marge d'erreur, et à 10 en 3x3, car sinon volé dans les délais d'attente).

En mode précis, j'ai basculé soit au moment du rebond, soit en étant si proche de la balle qu'une collision au prochain tick est possible. De plus, il y avait aussi une masse de petites béquilles, de hacks, d'optimisations, dans lesquelles je ne comprendrai pas moi-même.

Par exemple, le ballon volant était toujours simulé avec 1 Mikrotik, mais si après le prochain Mikrotik j'ai vu qu'il y avait eu une collision, il a reculé à la position précédente et l'a simulée à nouveau avec une plus grande précision.

De plus, j'ai également fait semblant d'être d'autres joueurs (les miens et les autres) s'ils étaient dans les airs (et donc leur trajectoire est plus facile à prévoir) ou s'ils étaient proches du ballon. Pour les adversaires, la version finale utilisait une version simplifiée de ma propre stratégie de prise de décision, qui était lancée toutes les 5 ticks (le plus souvent elle ne permettait pas la vitesse).

Lors de la simulation de chaque personnage, j'ai calculé moi-même, la balle et les autres joueurs de football 40 ticks en avant (ma limite sur le nombre d'actions dans le génotype), puis j'ai simulé le même nombre de ticks sur une seule balle.

Nitro

Simple à indécent.

Dans la version finale, le nitro est toujours activé s'il l'est, si le joueur est en l'air et s'il n'a pas touché le ballon au cours des dernières tiques.

Au début, j'ai toujours dirigé la nitro directement vers le haut, mais j'ai ensuite essayé d'expérimenter et l'option d'aller exactement au centre de la balle fonctionnait le mieux. J'ai aussi essayé des options pour que la direction du nitro soit choisie par la génétique.

Cela a fonctionné bien pire. Peut-être en raison d'un manque de profondeur de recherche.

Fonction de notation

La somme des scores pour chaque tick avec l'atténuation de 2% par tick.

Le plus gros poids, bien sûr, avait un objectif. Plusieurs choses ont influencé son poids:

• La distance entre le ballon et le gardien ennemi au moment du but (le plus loin sera le mieux)
• Coordonnée Y du ballon (car en haut du but, il est beaucoup plus difficile de frapper)
• La vitesse du ballon le long de l'axe Z (qui est dirigée vers le but ennemi)

En m'attaquant, tout est exactement pareil, mais avec le signe opposé.

De plus, pour l'attaquant, le score global dépendait:

• Distances du joueur au ballon (pour qu'il court vers le ballon même s'il ne peut pas le frapper)
• Pénalité pour le saut (ne sauter que si cela rapporte tellement de points qu'ils dépasseront cette pénalité)
• Distances à la prochaine tic de la simulation du ballon aux adversaires
• Coordonnées de la balle Y (plus elle est élevée, moins l'ennemi a de chances de l'intercepter)
• Cosinus de l'angle entre la direction du ballon et le centre du but ennemi
• Signaler si j'ai touché le ballon
• Drapeau, si l'ennemi a touché le ballon
• Bonus pour la sélection de nitro

En outre, il y avait un petit bonus pour frapper un joueur ennemi. En fait, c'est arrivé, mais rarement.

Pour le gardien de but:

• Bonus pour la distance au ballon, la vitesse du ballon en Z, la position du ballon en Y
• Pénalité pour le saut
• Pénalité pour avoir trouvé le ballon dans la zone devant mon but
• La distance par rapport aux ennemis et à mes attaquants a été prise en compte (pour que la balle s'éloigne des ennemis, mais si possible, se rapproche de mes attaquants)
• Et encore quelques petites choses.

Apprentissage automatique

C'était juste un peu dans l'une des branches du git à titre d'expérience. Mais il me semble quand même utile de le mentionner. Je n'ai pas réussi à me le rappeler (et je ne sais pas ce qui avait du sens).

En général, j'ai essayé de prédire avec son aide si l'ennemi peut intercepter le ballon en fonction des positions et des vitesses de l'ennemi et du ballon. J'avais prévu de l'utiliser dans la fonction d'évaluation. Pénaliser les trajectoires qu'il est possible d'intercepter.

Mais j'ai tout de suite compris que je ne pouvais pas me permettre non seulement un réseau de neurones, mais rien de grave du tout, car cela devrait être fait 80 fois par trajectoire. Eh bien, même si c'est 40 ou 20, sinon chaque tick est compté, mais de toute façon, je n'avais aucune marge de temps du tout, donc je n'ai même pas envisagé ces options.

Voici ce que j'ai fait:

J'ai couru plusieurs jeux avec un bot modifié, dans lequel, lors de la recherche d'une trajectoire, j'ai enregistré des données sur moi-même et le ballon, ainsi qu'un drapeau, si une trajectoire a été trouvée dans laquelle j'intercepte le ballon.

J'ai considéré toutes les coordonnées relatives au joueur de football. C'est-à-dire Je l'avais toujours dans la coordonnée [0,0,0], donc je n'ai gardé que 10 champs: la position relative du ballon, le vecteur vitesse du ballon, le vecteur vitesse du footballeur, le drapeau d'interception binaire. J'ai enregistré l'ensemble de données uniquement pour la partie centrale du champ, car J'ai réalisé que les algorithmes simples ne tireraient pas encore et rendraient compte des conseils.

Ensuite, j'ai alimenté ce jeu de données DecisionTreeClassifier avec max_depth = 7. L'arbre formé a donné une précision, pour autant que je m'en souvienne, de l'ordre de 90%.

Ensuite, j'ai exporté l'arborescence vers un ensemble d'if (qui est essentiellement DecisionTree).

Cela ressemblait à ceci:

public static boolean predict(double dude_vel_x, double dude_vel_y, double dude_vel_z, double ball_rel_pos_x, double ball_rel_pos_y, double ball_rel_pos_z, double ball_vel_x, double ball_vel_y, double ball_vel_z) { if (ball_vel_z <= 6.4765448570251465) { if (dude_vel_y <= -6.087389945983887) { if (ball_vel_z <= -20.188323974609375) { if (dude_vel_x <= 13.032730102539062) { if (ball_rel_pos_y <= -1.1829500198364258) { return ball_vel_y <= 18.906089782714844; } else { return false; } } else { return true; } } else { // ............................ 

À ce stade, j'ai effectué les tests, je n'ai vu aucune amélioration et j'ai reporté le procès à plus tard, qui, en raison de mes aventures, n'est jamais arrivé.

Schroedinbag

Quelque part après le premier tour, j'ai attrapé cet animal rare dans ma maison.

Qui ne sait pas, c'est un tel bug qu'ils ne trouvent qu'en lisant le code, et l'ayant trouvé, le développeur se demande comment le programme pourrait fonctionner. Et dans mon cas, elle est également restée dans le top 10.

En général, le bug était qu'un constructeur était appelé dans la fonction de copie du gène, dans lequel un argument facultatif était omis contenant la valeur de ce gène. En l'absence de cet argument, la valeur a été choisie au hasard. Ainsi, en essayant de copier un gène, au lieu d'une copie, il a créé une nouvelle instance aléatoire.

En fait, au lieu de la génétique, j'ai eu une recherche aléatoire, car chaque tick a simplement généré plusieurs centaines de chemins aléatoires et sélectionné le meilleur.

Après la correction (consistant à ajouter 2 caractères au code), le jeu est devenu environ 3 fois meilleur.

Danse rituelle

À un moment donné, j'ai remarqué que les joueurs rebondissaient parfois sans raison, étant loin du ballon, malgré la pénalité.

L'explication s'est avérée être telle que j'ai compté le moment du saut avec une précision de 100 microtiques. Et parfois, il s'est avéré que juste au moment du saut il y avait une collision de la balle avec la barre. Et selon la précision du calcul précisément dans cette coche, la trajectoire proposée a conduit à un objectif ou non.

En gros, le ballon vole vers le but de l'adversaire et frappe le poteau. mon footballeur, courant à l'autre bout du terrain, simule une trajectoire sans saut (avec 1 mikrotik) et voit que le ballon ne touche pas le but.

Puis une autre trajectoire entre en jeu, avec un saut exactement au moment où la balle frappe la barre. Et puisque je compte une tique avec un saut de 100 Mikrotiks non seulement pour un joueur de football, mais aussi pour une balle, l'angle de rebond calculé de la balle diffère de l'angle obtenu sur le chemin avec 1 microtik, et il peut arriver que la balle dans cette trajectoire plus précise tombe dans la porte.

Et donc, c'est cette trajectoire qui sera sélectionnée et le bot sautera.

En général, en exécutant une danse rituelle avec rebond, les joueurs ont nommé un but :)

Fonction tueur

Elle n'est pas

Test

J'ai conduit des jeux sans fin dans 8 threads (4 sur chaque ordinateur et ordinateur portable). J'ai choisi le nombre de jeux pour qu'il soit statistiquement significatif.

Avec une amélioration significative de la stratégie pourrait être satisfait avec un demi-millier d'objectifs au total,
avec des corrections plus petites, parti pour la nuit, puis le projet de loi est allé par milliers.

Sélection génétique des constantes

Je l'ai essayé avant le premier tour. Cela ne donne rien parce que pour la génétique, vous devez jouer un tournoi à partir d'un grand nombre de jeux.

J'ai essayé de jouer à 100 000 ticks, mais ce n'était pas suffisant. Avec une petite différence de force (et généralement lors du choix des constantes, c'est exactement le cas), le gagnant par 100 000 ticks dépend trop du cas. Vous devez jouer beaucoup plus pour être sûr du gagnant. Et je ne pouvais pas me permettre de quitter la sélection pour un jour ou plus, alors j'ai refusé cette aventure.

En conclusion

Remerciements traditionnels aux organisateurs. La tâche était intéressante. Dommage que je sois juste obligé de rater près de la moitié du championnat et n'ai vraiment rien fait pour le nitro ou pour trois joueurs.

En conséquence, jusqu'à la toute fin, j'ai regardé dans le bac à sable comment ma stratégie gagne en mode 2x2 sans nitro avec un score de 13: 2 contre n'importe quel Mr.Smile, qui a pris la 3e place en finale, et après quelques matchs, il perd 12: 2 en mode 3x3 avec nitro :)

Et bien sûr, la vidéo de mon visualiseur propriétaire:

Vous seul devrez probablement dire adieu à ce visualiseur lors de futurs championnats.
Pour chaque fois, je suis de plus en plus convaincu que si vous postulez pour des places normales, la seule option est d'écrire ...

... eh bien, vous obtenez le point.

Fatigué à chaque fois de se reposer sur la lenteur de Java et de réduire la force de la stratégie pour respecter le temps imparti.

J'espère que quelqu'un a trouvé quelque chose d'intéressant ou d'utile dans cet opus à moi avec une note de caractère autobiographique :)