La dernière partie.
Dans les chapitres précédents ( partie 1 , partie 2 , partie sur le GPU ), nous avons abordé les conditions du concours, le réseau neuronal, l'algorithme génétique, alors continuons.
Mais avant de continuer, il existe un lien vers GitHub avec le code source du programme en c ++ et pour prendre en charge le titre de l'article - un fichier exécutable sous Windows dans le dossier bin , qui est assez similaire à l'économiseur d'écran. Au sous-sol de l'article, il a organisé le «Hall of Fame» des championnats passés.
Nous avons donc opté pour l'architecture du programme, qui se compose de deux parties distinctes (programmes), la partie contenant uniquement le réseau de neurones et le protocole de communication avec le serveur de jeu des organisateurs de la compétition (le bot de jeu lui-même) et la partie principale, constituée des blocs suivants:
Brièvement sur chacune des parties.
Moteur physique. Basé sur le module de calculs physiques des sources officielles, refait pour le GPU et ajouté des calculs de capteurs de bot, des fonctions de fitness, des collisions de bots. Le code source a supprimé les virus et les tentatives de partage de bots, divisant la partie instable du programme. Par conséquent, je n'ai pas partagé mes erreurs.
Réseau de neurones. Nous en avons parlé suffisamment en détail la dernière fois, y compris sur l'implémentation dans le code, donc je suppose que beaucoup de choses sont également claires ici, d'autant plus qu'il n'y a pas eu de questions particulières de la part des lecteurs.
Algorithme génétique. Il y avait des lacunes dans la couverture de sa mise en œuvre. Maintenant, je suis plus susceptible de le répéter, mais il est plus facile de le répéter encore une fois.
Je me souviens beaucoup de la diapositive de présentation. Par conséquent, la question principale restait: comment faire évoluer l'évolution? Pour cela, la fonction Fitness a été inventée. L'objectif principal de la fonction fitness est la sélection de génotypes à transmettre de la population actuelle de bots à la suivante.
Comment le choix de la fonction de fitness est-il devenu très clair? La question du franchissement restait.
Il existe plusieurs méthodes de base de croisement, plus sur le lien . Mais le principe de base est l'échange aléatoire de gènes entre les génotypes parentaux. Deux parents sont généralement sélectionnés, il existe également plusieurs méthodes pour choisir les parents dans une population, le lien peut être lu plus en détail. Bien que le choix des parents se fasse au hasard, la probabilité de choisir un parent spécifique augmente proportionnellement à sa fonction de fitness.
Ensuite, la fonction de mutation est appliquée au génotype fini.
Dans notre cas, de temps en temps, l'algorithme change un gène sélectionné arbitrairement en un gène aléatoire, en d'autres termes, l'un des poids du réseau neuronal change en un aléatoire.
Nous avons obtenu une nouvelle population et l'évolution continue vers le résultat souhaité. Il y a plusieurs points, le premier: plus il y a de robots dans la population, plus l'algorithme génétique trouvera rapidement la solution optimale ou convergera vers la solution (le rapport optimal de poids dans le réseau neuronal). Par exemple, si un bot possède 1 000 gènes, l'espace de recherche s'étend considérablement avec une population de 3 000 bots, contre une population de 300 bots. Mais un autre problème se pose, si vous libérez les 3000 bots dans l'arène conçue pour 4-8 bots, alors les robots seront probablement bondés physiquement et s'ils apprennent quelque chose, alors ce n'est certainement pas un jeu dans Agario. Par conséquent, il existe deux façons principales d'éviter la surpopulation de l'arène: la première pour sélectionner plusieurs bots dans la population et participer à l'arène, et tant de fois, jusqu'à ce que nous accumulions des statistiques de jeu pour chaque bot. La seconde que l'auteur est allée est le lancement de plusieurs arènes en parallèle, disons 50-300, tout dépend de la puissance d'un ordinateur particulier, et en parallèle toute la population de bots participe à des compétitions. La population peut être divisée en sous-populations avec ses fonctions de fitness et ses identifiants (correspond au nombre d'arènes), puis échanger des génotypes entre sous-populations. Ou imaginez tout comme une grande population de robots jouant dans différentes arènes. L'auteur a essayé les deux options, mais dans la version source avec une seule population de bots. Le paramètre du programme Depth est le numéro de l'arène.
Il a donc expliqué les principes de base de l'élaboration d'un programme. Qui veut voir en direct, bienvenue sur le lien vers le github .
si vous ne pouvez pas le démarrer, alors une courte vidéo égayera ce moment:
Annonce: En août, mail.ru organisera une autre mini-coupe AI, l'annonce officielle n'a pas encore été vue comme une vérité. Mais selon les informations des télégrammes du groupe, la base de la compétition est à nouveau le moteur physique, quelque chose sur les voitures. Par conséquent, brièvement sur les principes de création d'un bot, ceux qui seront intéressés bien sûr:
Ici, comme notre équipe de football, il est conseillé de quitter le groupe, la finale est une chanson à part. Laissez les finalistes écrire sur les victoires, mais sur notre principale participation.
Le plus clair et le plus simple:
Écrivez des conditions plus différentes dans le corps du code du bot, par exemple, si (trou) -> saut, etc. Des conditions simples sont efficaces au début du championnat, puis la complexité des bots va augmenter et l'avantage des solutions conditionnelles disparaîtra.
Et donc la méthode la plus prometteuse dans de nombreux jeux stratégiques:
Méthode PP ( ou champs potentiels ). L'idée est belle, la recherche du maximum ou du minimum dans un environnement dynamique. Une grille de la dimension sélectionnée est construite sur l'ensemble du terrain de jeu ou uniquement sur la zone autour du bot, tout dépend de la portée du bot. De plus, à chaque point nodal de cette grille, nous considérons les distances aux objets qui nous intéressent ou, en option, les potentiels tout de suite, ils peuvent être positifs (attraction, c'est ce qui est intéressant pour le bot) et négatifs (danger pour le bot). En conséquence, les potentiels au point sont additionnés et nous obtenons les potentiels totaux à chaque point de la grille. Champ de potentiels. Le robot ne peut choisir que le plus petit ou le plus grand potentiel, en fonction de la tâche du moment. Fondamentalement, les champs potentiels sont des implémentations 2D, bien que la 3D ait l'air cool, mais il y aura beaucoup de ressources pour les calculs.
Le plus difficile:
Les deux principales implémentations sont la méthode Brute Force ou la méthode Monte Carlo . Chacun d'eux fait l'objet d'un article séparé, mais selon la sensation, ce sont ces méthodes qui vous mèneront à la finale. S'il s'agit d'une thèse, le bot peut non seulement regarder l'heure actuelle ou le passé, mais s'il le souhaite, il peut regarder vers l'avenir, ici un entonnoir (cône) de résultats possibles se pose et plus le bot veut regarder, plus d'options apparaîtront. Par exemple, au point de temps Tick Zero, le bot décide d'aller dans l'une des huit directions, à l'étape Tick + 1 dans chacune des huit nouvelles coordonnées, il a la possibilité de repartir dans huit directions, etc. il est nécessaire de prendre en compte les éventuels mouvements ennemis pendant cette période. Chaque résultat possible des calculs s'accompagne d'un avantage ou d'un préjudice possible. Sur la base de laquelle le bot se déplace dans l'une des directions. Et plus loin, un tel calcul dans la profondeur du futur va à chaque tick. La profondeur des vues de mouvements est déterminée par les ressources possibles de l'ordinateur. Par conséquent, pour les petites ressources informatiques, le problème se pose d'optimiser ces calculs.
Concernant la source, s'il y a un intérêt, je vais éditer les commentaires sur le code, pendant que je le présente tel quel.
A la source, les signaux du Tick actuel et du Tick précédent sont envoyés à l'entrée du neurone, c'est devenu plus intéressant, grâce au lecteur: tongohiti pour l'idée.
Pour ceux qui se souviennent de la thèse sur la distribution initiale des poids dans le réseau neuronal, un sujet intéressant est l'initialisation Xavire.
Merci de votre attention. Retrouvez-moi lors des compétitions d'IA.
Articles connexes des participants, mais première digression :
Elle était assise par terre
Et trié la pile de lettres
Et comme la cendre refroidie
Je les ai pris dans mes mains et je les ai jetés.
A pris des feuilles familières
Et c'était merveilleux qu'elle les regarde,
Comment les âmes regardent d'en haut
Sur eux un corps abandonné ...
Oh combien de vie était ici
Irréversiblement expérimenté!
Oh combien de minutes lamentables
L'amour et la joie tués! ..
Ma stratégie à la Russian AI Cup 2017
Historique de la participation (et presque de la victoire) à la compétition annuelle Russian AI Cup 2016
L'histoire de la victoire à la Coupe d'AI russe 2015
Russian AI Cup 2014: stratégie gagnante
Médaille d'or à la Russian AI Cup 2013 - comment tout cela s'est passé
Le chemin vers la médaille d'argent à la Coupe AI russe 2012