Au départ, je n'avais aucun plan pour un article, surtout pour parler lors d'une conférence. Mais il y a eu une conférence. Et après en avoir parlé, les téléspectateurs m'ont posé des questions concernant la mise en œuvre de certains problèmes techniques. Et il s'est avéré mot pour mot - un article.
Enregistrement en direct sous le lien .
Avertissement: Cet article est une tentative de répondre à certaines de ces questions. Je serai heureux si de nouvelles questions surgissent, répondant à cela il y aura une opportunité d'apprendre quelque chose de nouveau moi-même. Et oui, cet article n'est en aucun cas une tentative de sentir le tintement des tuyaux en cuivre.
Et donc commençons par le tout début de cette histoire. Au printemps 2018, mail.ru a annoncé un concours de programmation basé sur le jeu Agairo . L'essence de la compétition est la création d'un bot de jeu.
Règles de compétition sur ce lien . Mais pour être bref et décrire les règles dans vos propres mots, vous devez créer un bot pour jouer à Agairo. À un moment donné, un jeu Internet populaire (dans le sens où il est lancé à partir du navigateur), dont l'essence est de manger vos jeunes frères et de fuir les plus grands. Vous contrôlez une roue chromatique dans un espace bidimensionnel limité. Pour créer le gameplay dans cet espace, en plus de votre cercle, il existe d'autres cercles contrôlés en conséquence par d'autres joueurs. Il y a de la nourriture (points colorés) pour la croissance, des obstacles supplémentaires sont introduits sous la forme de «virus», une collision avec laquelle crée une division de votre cercle en plus petits, ce qui complique partiellement le processus de jeu, car les petits mangent les plus grands et les plus grands sont plus sûrs.
Je vais donner une image d'une variante du jeu pour les compétitions
De plus, par joueur, nous entendons non pas le développeur du bot, mais le bot lui-même.
Les organisateurs de la compétition dans leur ensemble ont conservé le concept original du jeu, mais ont ajouté un certain nombre d'innovations. Le principal étant la restriction de l'examen du bot et l'introduction d'une simple loi physique appelée inertie. La physique traverse la physique depuis longtemps, donc l'inertie est associée non seulement à nous, mais aussi à des quantités telles que la masse, la vitesse et l'accélération. Nous n'avons besoin de rien d'autre du monde de la physique.
J'espère que la partie littéraire a fait assez attention et qu'il est temps de passer à la composante technique du concours et d'y participer.
Avertissement 2: Je suis presque sûr que ce qui a été décrit ci-dessous pourrait être rendu plus mince, plus élégant et plus intelligent, mais comment cela s'est produit.
Notez donc la recette et les principaux ingrédients, ils ne sont pas tous nouveaux, mais vous pouvez ajouter les vôtres à votre goût.
Tâche: créer un bot capable de jouer seul à Agairo.
L'idée principale: utiliser les réseaux de neurones (ci-après dénommés réseau de neurones, réseau de neurones (NN)) comme élément de contrôle du bot.
Principaux outils de production: Microsoft Visual Studio et c # avec une transition en douceur vers c ++.
Ensuite, la chose la plus importante pour l'auteur est de choisir ou de comprendre son lecteur, pour qui j'écris, sait-il ce que sont les réseaux de neurones, les algorithmes génétiques et comment décrire tout cela en détail.
C'est tout, j'ai choisi mon lecteur, mon lecteur sait tout cela, mais pas si bien de l'utiliser en pratique.
Par conséquent, en écrivant cet article, je rappellerai des formes simples telles qu'un neurone et une fonction d'activation.
Pour la visualisation, j'utiliserai des images dessinées à la main, qui devraient être lues comme: si vous voyez des erreurs, écrivez, redessinez vers les bonnes.
Ainsi, tout est prêt à être envoyé sur le chemin de la construction logicielle du bot. Commençons:
Nous prenons le cycle, ou plutôt, les organisateurs du concours nous l'ont préparé comme exemple d'un simple bot. Allons plus loin, téléchargez l'archive du participant au concours à partir du référentiel en utilisant ce lien . Les organisateurs ont promis que le serveur du concours serait en vie, et après son achèvement, nous serons en mesure de vérifier ces mots. Nous ouvrons l'archive et choisissons un langage de programmation qui nous soit compréhensible.
La documentation du concours décrit également la technologie de communication du client (lire notre bot) et du serveur d'un centre de données vivant quelque part dans les profondeurs. En bref, la communication passe par la ligne de console, en y écrivant et en lisant des commandes.
Le mot magique Sérialisation doit être mentionné ici: il s'agit de compresser vos données dans un format que le sérialiseur comprend et de pouvoir lire ces données dans le programme à l'aide du sérialiseur. Il existe de nombreux sérialiseurs, le format séquentiel le plus simple pour écrire dans le fichier txt est également un sérialiseur, mais simple. Ce que nous devons savoir sur les sérialiseurs, c'est qu'ils existent et sont presque transparents en termes d'API. Les organisateurs l'ont très probablement compris et donc l'exemple de leur bot contient toutes les instructions nécessaires pour travailler avec le sérialiseur. Dans notre cas, c'était JSON .
Pour le bot après le sérialiseur, le monde du jeu ressemble à un tableau de données reçues au début du cycle mentionné. Les données sur le monde du jeu sont limitées par le serveur en fonction du rayon de vue égal aux 4 rayons du bot, rappelez-vous que le bot est un cercle. Et le cercle autour du cercle est la bordure externe de l'examen, bien que le cercle extérieur soit légèrement biaisé vers le mouvement du bot par rapport au centre du bot, mais cela peut être négligé dans notre cas.
Et nous avons donc un cycle, la mesure du cycle est Tick, combien de cycles ont passé, tant de ticks ont fonctionné. Très probablement, nous ne nous souviendrons plus de ce Tick, mais cela introduira un certain nombre de limitations et de simplifications importantes: le temps de calcul est limité non seulement par un seul Tick, le temps d'une itération du cycle, mais aussi par le temps de calcul total, après lequel le serveur de jeu déconnectera votre bot de la gestion. Cochez-le et il est temps de donner des commandes au bot. Nous le considérerons comme un quantum de temps de jeu, Tick est un temps indivisible dans le monde du jeu. Des avantages en découlent. Étant donné que le tick est égal à 1 par défaut, il est plus facile de calculer les vitesses, les accélérations et d'autres valeurs. Dans toutes les formules, nous multiplions par 1, au lieu d'utiliser une sorte de temps de courbe t = 0,0015 seconde. Les erreurs dans ces opérations sont également minimes.
Tout ce qui précède est quelque peu similaire à un film, il semble que l'image à l'écran soit animée et en mouvement, mais en fait, nous voyons 25 images différentes par seconde, et notre cerveau considère simplement cela comme une fréquence suffisante pour une perception complète de la dynamique de la vidéo. Ainsi, le bot voit le monde à intervalles de temps. Tick est un cadre du monde du jeu.
Le réseau neuronal fonctionnera également en fonction des tiques.
L'image commence à s'effacer du côté du bot:
Le serveur envoie les données traitées sur le monde au bot-> Tick Start-> le bot reçoit les données -> les traite-> envoie les commandes de gestion du bot au serveur-> Le serveur lit les données-> End of the Tick puis presque sans fin dans un cercle ou une boucle, 45000 ticks au final le jeu est assez important.
Remarque importante: vous pouvez ignorer Tick et vous n’obtiendrez rien. Il y a des cas de serveurs où chaque Tick doit dire quelque chose au serveur, afin que le serveur ne suspecte pas le bot dans un blocage du programme de contrôle.
L'auteur a décidé de ne pas trop toucher au serveur, mais je dois en dire quelques mots. Il existe un modèle du monde du jeu sur le serveur, et conformément à celui-ci, il effectue des calculs et des actions. Le programme serveur comprend les blocs suivants:
- calcul des collisions de bots (traitement des collisions avec les limites du monde du jeu, qui a mangé qui, bot bot ou bot food, ou collision avec un virus, etc.)
- calcul de la physique du bot (mouvement du bot, changements de vitesse du bot en fonction des commandes du bot ou des collisions qui se sont produites)
- calculs liés à la division des bots ou à leur combinaison, si possible, à l'ajout de nourriture et d'autres fonctions pour maintenir le monde du jeu.
- et bien sûr envoyer et recevoir des données aux bots sur les ticks de jeu.
Un tel serveur est appelé une "commande". Autrement dit, toutes les actions se produisent du côté serveur, ce qui supprime les problèmes de synchronisation des données. Le client (lire le bot) ne reçoit qu'une image toute faite du monde, comme ses autres rivaux, ici l'égalité des positions des bots est atteinte, il n'y a pas de priorités et de files d'attente. Encore une fois, un changement dans les coordonnées du bot se produit sur le serveur, par exemple, le bot donne une commande de décalage et seulement au Tick suivant reconnaît ses nouvelles coordonnées, qui ne coïncident pas toujours avec l'équipe, en option un obstacle sous la forme d'un mur du monde du jeu.
photo du site des organisateurs
Nous avons compris la lecture des données avec le bot et le serveur de gestion, maintenant regardons les profondeurs du périphérique bot.
Comme le lecteur l'a probablement déjà compris, il y aura peu de mots et beaucoup de travail, ou vice versa.
Le bot est contrôlé par un réseau de neurones. Court et volumineux, mais pas tout à fait clair comment.
Le choix d'un réseau neuronal et la technique de sa mise en œuvre.
Pour le moment, nous décidons que le réseau neuronal pour nous est une boîte noire qui a une entrée et une sortie.
L'entrée et la sortie pour nous seront des tableaux unidimensionnels avec une dimension de N = 16 pour l'entrée et une dimension de M = 4 pour la sortie.
Puisque la nature du réseau neuronal artificiel est grossièrement copiée du réseau neuronal naturel, il serait bon pour nous de rapprocher la structure des données d'entrée des données naturelles. Dans la nature, divers capteurs en sont responsables. Tenez-vous donc aux capteurs du bot.
L'option suivante a été sélectionnée expérimentalement (l'image est simplifiée à 8 capteurs et un réseau neuronal 4x3, mais cela ne fait que confondre mon lecteur):
Le champ de vision du bot est divisé en secteurs égaux (voire même inégaux). Chaque secteur fournit un signal à l'une des entrées du réseau neuronal. Par conséquent, si nous divisons la zone autour du bot en 16 secteurs (360/12 = vue d'ensemble du secteur à 22,5 degrés), nous obtenons 16 entrées du réseau neuronal. Typiquement, un signal allant de -1 à 1 est appliqué à l'entrée d'un réseau neuronal, il est donc nécessaire de normaliser les signaux d'entrée.
Le rationnement consiste, en simplifiant, à diviser le signal total par sa valeur maximale possible. Il est bien sûr possible de faire une normalisation dynamique, c'est-à-dire de rechercher le maximum à chaque fois et de ramener la valeur du signal à sa norme, mais nous fixerons la valeur maximale sous la forme d'une constante égale au nombre maximum d'objets dans un secteur et ne la changerons pas dans le processus de travail sur le bot.
Les signaux peuvent être positifs ou négatifs, nous convenons que la valeur du signal de 0 à 1 est un motif positif pour notre bot (nourriture, nourriture sous la forme d'un bot plus petit), une valeur de signal négative de -1 à 0 est un motif négatif pour le bot (mur monde du jeu, un autre plus gros bot).
dessin
Un signal provenant d'un secteur est une quantité normalisée constituée de la somme des signaux individuels. Comme cela a été dit, chaque signal individuel a un signe et une amplitude. L'amplitude du signal est définie comme une fonction proportionnelle de la distance. La distance minimale est la limite du cercle du bot de définition; la distance maximale est la frontière de la visibilité du bot. Par conséquent, si nous recevons un signal positif, par exemple, de la nourriture entrant uniquement dans le secteur à une distance maximale, alors le signal sera faible et augmentera si le bot s'approche de la nourriture.
Les capteurs sous forme de secteurs étaient les plus adaptés à ce cas, mais il peut tout simplement y avoir des antennes sondes, ici le fantasme est de votre côté. Bien sûr, l'auteur a essayé diverses options pour se diviser en secteurs de 4 secteurs à 72, mais la pratique a montré que le réseau neuronal est formé avec succès dans 16 secteurs et est prêt à contrôler le bot même avec quatre secteurs. Ici se manifeste la flexibilité de la nature même du réseau neuronal.
Enfin, le mot entraînement au réseau neuronal a été prononcé. Mais pour l'instant, nous avons décidé que le réseau neuronal est une boîte noire avec entrée et sortie, et puisque nous avons trié les données d'entrée, il reste à dire quelques mots sur les données ou signaux de sortie de cette boîte, que faire avec et comment les traiter.
Nous fixons la dimension du signal de sortie à 4. Ce nombre est une manifestation du dualisme des coordonnées cartésiennes et polaires. L'auteur n'a pas oublié la nature des connaissances de son lecteur et lui rappelle donc avec son dessin des connaissances autrefois bien acquises.
Ainsi, les développeurs du serveur ont logiquement utilisé les coordonnées polaires pour simuler le monde du jeu, et pour les robots et leurs développeurs, ils ont poliment fourni des coordonnées cartésiennes. Par conséquent, l'auteur a dû choisir un côté dans ce système de coordonnées. Pour un réseau neuronal, un système de coordonnées polaires ne contenant que la magnitude (longueur de lecture) du vecteur et l'angle de son écart est plus compréhensible. Après tout, vous comprenez également les mots «tourner à droite» plutôt que de faire deux pas le long des ordonnées et trois pas le long des abscisses.
Par conséquent, 4 signaux de sortie sont 2 signaux sur l'augmentation ou la diminution de l'angle du vecteur vitesse du bot, et 2 autres augmentent ou diminuent l'amplitude du vecteur vitesse.
Mais puisque le serveur de jeu a demandé de donner des commandes pour contrôler le bot en coordonnées cartésiennes, alors quelques formules de traduction des coordonnées polaires en coordonnées cartésiennes et toute cette honte se sont levées à leur place (il s'agit d'un pseudo-code similaire à c #).
float rotate1 = outputs[0]; float rotate2 = outputs[1]; float speed1 = outputs[2]; float speed2 = outputs[3]; if (rotate1 > 0.65 && rotate2 < 0.65) angle = angle + 35 * PI / 180; if (rotate1 < 0.65f && rotate2 > 0.65) angle = angle - 35 * PI / 180; if (speed1 > 0.65 && speed2 < 0.65) speed = speed + 2; if (speed1 < 0.65 && speed2 > 0.65) speed = speed - 2; dx = speed * Cos(angle); dy = speed * Sin(angle);
Les signaux sont en place, tout comme un bot. Il semble qu'ils lui aient donné des signaux d'entrée, mais à la sortie, quelque chose ne vaut rien: il se tient ou se déplace au hasard.
Il est donc venu ouvrir la boîte noire et regarder à l'intérieur.
À suivre.
Mais avant la nouvelle série teaser:
Le bot violet du réseau de neurones joue dans Local Runner contre les bots standard que les organisateurs lui ont cousus par défaut.