Au début de l'automne, le concours pour écrire des bots Mini AI Cup # 3 (alias Mad Cars) s'est terminé, dans lequel les participants devaient se battre sur des voitures. Les participants ont beaucoup discuté de ce qui fonctionnera et de ce qui ne fonctionnera pas, des idées ont été exprimées et testées à partir de simples ifs pour former des réseaux de neurones, mais les premières places ont été prises par les gars avec la soi-disant «simulation». Essayons de comprendre de quoi il s'agit, comparons les solutions pour les 1ère, 3ème et 4ème places et discutons sur le sujet d'autres solutions possibles.

Clause de non-responsabilité

L'article a été écrit en collaboration avec Alexei Dichkovsky (Commandos) et Vladimir Kiselev (Valdemar) .

Pour ceux qui veulent simplement lire les décisions des gagnants, je vous conseille de commencer tout de suite avec le point «Simulation».

Énoncé du problème

Cette fois, la mécanique du monde ressemblait beaucoup au jeu mobile Drive Ahead: les joueurs ont reçu une voiture avec un bouton situé dessus; la tâche consiste à appuyer sur le bouton de l'ennemi plus rapidement que lui. Si personne ne gagne en 600 ticks de jeu, la carte commence à couler dans un tas d'ordures, qui peut également appuyer sur un bouton. En d'autres termes, vous devez protéger votre bouton contre les ennemis, le monde qui vous entoure et les tas d'ordures (vitalement, oui). Chaque joueur a eu 5 vies, le jeu est passé de 5 à 9 tours, tandis que quelqu'un n'a pas mis fin à sa vie. Chaque manche s'est déroulée sur une carte aléatoire et des voitures, les mêmes pour les deux participants. Au total, il y avait 6 cartes différentes et 3 types de voitures - un total de 18 combinaisons différentes.

Chaque tour est divisé en tiques. Une tique est un mouvement, comme aux échecs. La seule différence est que les deux joueurs vont en même temps. Il y a des compétitions où tout le monde se relaie, ou vous ne pouvez faire une action qu'une fois tous les quelques mouvements et sélectionner des unités comme cadre .
Chaque tick au bot vient un état de paix et a la possibilité d'effectuer 3 actions: , , . Ces actions font aller la voiture dans une des directions, et si en même temps elle ne touche pas les roues de la terre, alors elles donnent une petite rotation à tout le corps (un peu de physique d'arcade). Après que les deux adversaires ont choisi une action, une simulation du monde du jeu est lancée, un nouvel état est considéré et envoyé aux joueurs. Si quelqu'un a cliqué sur un bouton, le tour se termine et le suivant commence. Tout est simple, mais il y a des nuances.

Des règles plus complètes peuvent être trouvées ici . Et voyez les matchs de la finale ici .

Description générale de la solution

La plupart des compétitions d'écriture de bots sont très similaires: il y a un nombre fini de ticks (il y a environ 1500 maximum pour un tour), il y a un nombre fini d'actions possibles, vous devez choisir une séquence d'actions pour être meilleur que vos adversaires. Un peu plus tard, nous reviendrons sur ce que signifie être meilleur, mais pour l'instant, nous trouverons comment résoudre le problème principal - un grand nombre d'options: au début, nous avons un état initial, puis chaque machine peut se déplacer de trois manières différentes, ce qui nous donne 9 combinaisons différentes pour deux voitures, d'ici le 1500ème ce sera 9 ^ 1500 combinaisons différentes ... Ce qui est un peu plus que ce que nous aimerions si nous prévoyons de les trier pendant l'existence de l'Univers.

Nous arrivons ici à ce qu'est la simulation . Ce n'est pas une sorte d'algorithme, mais simplement une recréation des règles du jeu avec une précision suffisante ou complète pour qu'il soit possible de trier les solutions. Bien sûr, nous ne passerons pas en revue toutes les solutions, mais seulement une partie d'entre elles. Un algorithme de recherche sera utilisé à cet effet - dans l'arbre d'état du jeu, nous recherchons le meilleur pour nous. Il y a beaucoup d'algorithmes (de minimax aux SCTM), chacun a ses propres nuances. Il est préférable de vous familiariser avec les décisions écrites par les participants aux précédents concours d'IA. Cela fournira une compréhension de base de dans quelles conditions les algorithmes fonctionnent et dans quels cas pas. Il existe de nombreux liens pour cela dans un référentiel spécial .

Lors du choix d'un algorithme, vous devez considérer:

• limite de temps pour 1 tick (ici j'ai beaucoup mal calculé cette année, mais j'ai pu rester à la 3ème place);
• nombre de joueurs. Par exemple, s'il y a trois joueurs, il sera difficile d'utiliser minimax;
• précision de la simulation, cela peut permettre la réutilisation d'anciens calculs;
• «Ramification» de l'arbre d'état (est-il possible de calculer tous les états possibles au moins 10 mouvements en avant);
• bon sens - ne commencez pas à écrire des SCTM si la compétition dure 4 heures.

Dans cette compétition, 1 tick a donné environ 10-13 ms (2 minutes pour tout le match). Pendant ce temps, le bot a dû lire les données, prendre une décision et envoyer une commande pour se déplacer. C'était suffisant pour stimuler environ 500 à 1000 mouvements. Itérer sur tous les états. L'algorithme de recherche le plus simple peut ressembler à une comparaison de trois options de mouvement: "50 ticks vont à gauche", "50 ticks vont à droite", "50 ticks click stop". Et aussi simple que cela puisse paraître, ce n'est pas très loin de la décision du vainqueur.

Parce que nous ne comptons que 50 coups d'avance, ce qui dans la plupart des cas ne compte pas avant la fin du jeu, alors nous avons besoin d' une fonction d'évaluation qui dira à quel point l'état du monde est bon et mauvais pour nous. Le plus souvent, il repose sur l'heuristique et la compréhension de ce qui est important pour la victoire. Par exemple, dans la compétition de la Coupe AI russe de 2014, il y avait des courses, mais vous pourriez gagner si vous êtes arrivé le dernier, si vous obtenez plus de points bonus. Par conséquent, la fonction d'évaluation devrait stimuler la collecte de points en même temps qu'un mouvement rapide le long de l'autoroute. Le score ne peut être calculé que pour le dernier état de la simulation (après 50 ticks) ou comme la somme des estimations des états intermédiaires. Souvent, l'estimation «s'estompe» dans le temps afin que les états qui se produisent plus tôt soient plus influencés. Parce que nous ne pouvons pas à coup sûr prédire l'ennemi, alors les options futures sont moins susceptibles de se produire, nous ne compterons pas beaucoup sur eux. De plus, cette technique rend le bot plus rapide pour terminer ses tâches, et ne remet pas tout à plus tard. Mais il convient de noter que le bot prendra moins de risques pour le bien des avantages ultérieurs.

Puisque nous allons prédire l'état du monde en réponse à nos actions, nous devons en quelque sorte modéliser le comportement des ennemis. Il n'y a rien de compliqué et il y a quelques options courantes:

• Stub ou heuristique
  Une logique de comportement simple est écrite où l'ennemi ne fait rien, ou choisit des actions basées sur de simples heuristiques (par exemple, vous pouvez utiliser vos premières versions de la stratégie ou simplement répéter le mouvement précédent de l'adversaire).
• Utilisez le même algorithme que pour vous
  Nous essayons d'abord de trouver les meilleures actions pour l'ennemi (contre notre meilleure série d'actions du dernier coup, ou contre un talon), puis nous recherchons la meilleure action pour nous-mêmes, en utilisant le comportement que l'ennemi a trouvé. Ici, le bot tentera de résister à des ennemis difficiles. Cette logique ne fonctionne pas bien au début de la compétition, car de nombreux bots sont encore très faibles et votre décision sera trop prudente avec eux.
• Autre
  Le même minimax itère sur tous les mouvements des joueurs en même temps, et il n'aura tout simplement pas besoin d'heuristique.

Si vous implémentez toutes les étapes ci-dessus, vous obtiendrez très probablement un très bon bot, surtout si vous pouvez choisir une bonne fonction de notation. Mais, en regardant à travers ses combats, vous pouvez voir que dans certaines situations, il se comporte étrangement. Corriger la fonction d'évaluation de ces situations peut être difficile, ou il y a un grand risque de briser une autre logique. Ici, des béquilles et des ifs viennent à la rescousse. Oui, les derniers jours de la compétition se résument souvent à écrire des béquilles et des ifs afin de corriger les défauts dans des conditions spécifiques. Personnellement, je n'aime vraiment pas cette partie, mais j'ai remarqué plus d'une fois que ce sont les béquilles en finale qui peuvent affecter la disposition des places dans le top dix, ce qui signifie qu'un si non écrit peut vous coûter un prix (mon cœur me fait mal quand j'écris ces mots, je J'aime aussi les beaux algorithmes et solutions).

Q: Est-il possible de se passer du tout de simulation?
R: Oui, vous pouvez utiliser des solutions sur l'heuristique (arbres de décision, un tas d'if, etc.). Il y a un bon article avec les architectures IA sur l'heuristique.

Q: Dans quelle mesure l'utilisation de la simulation est-elle meilleure que les approches heuristiques?
R: Tout dépend de la tâche. Par exemple, ici, certaines combinaisons de cartes et de voitures peuvent être codées en dur avec des ifs et toujours gagner (ou tirer). Cependant, la simulation trouve souvent des solutions difficiles à penser par vous-même ou à mettre en œuvre une heuristique difficile. Dans ce concours, lorsque vous retournez une autre voiture, les solutions sur les simulations mettent leur roue sur la roue de l'ennemi, ce qui éteint le drapeau "en l'air", ce qui signifie que l'ennemi ne peut pas appliquer la rotation du corps et revenir sur les roues. Mais la décision n'a pas réfléchi à la signification de cela, elle a juste trouvé des options où l'ennemi tomberait plus vite sur le toit et presserait son bouton.

Q: Réseaux de neurones et RL?
R: Peu importe leur popularité, dans les compétitions de robots, ces solutions fonctionnent rarement bien. Bien que les réseaux de neurones n'aient pas besoin de simulation, car ils peuvent simplement émettre une action basée sur les paramètres d'entrée de l'état actuel, ils ont encore besoin d'apprendre quelque chose, et pour cela, ils doivent souvent écrire un simulateur pour piloter des milliers de jeux localement. Personnellement, je crois qu'ils ont du potentiel. Ils peuvent peut-être résoudre une partie du problème ou l'utiliser dans des conditions de temps de réponse très limité.

Remarque
En ce qui concerne le nombre fini d'actions possibles, il convient de préciser que parfois il est permis d'ajuster "en douceur" certains paramètres. Par exemple, non seulement avancer, mais avec un certain pourcentage de puissance. Dans ce cas, la «finitude» du nombre de conclusions peut être facilement obtenue simplement en utilisant plusieurs valeurs, par exemple 0%, 25%, 50%, 75% et 100%. Le plus souvent, deux seulement suffisent: "complètement allumé" et "complètement éteint".

La simulation

Dans ce concours, nous avons utilisé le moteur physique de tamia préparé. Les organisateurs s'attendaient à ce qu'il soit vieux, éprouvé et qu'il ait de nombreux emballages pour que tout le monde puisse l'inclure dans sa décision ...

Dans la dure réalité, le moteur produisait des valeurs différentes à chaque fois, ce qui rendait difficile le redémarrage pour calculer les options de déplacement. Le problème a été résolu «de front» - un allocateur de mémoire a été écrit en C et un morceau de mémoire avec l'état du monde a été complètement copié. Un tel allocateur a mis fin à la possibilité d'écrire des solutions dans des langages autres que C ++ (en fait, c'était possible, mais très laborieux et un allocateur devrait encore être écrit en C). De plus, la précision de la prédiction a été influencée par l'ordre d'ajout d'éléments au monde du jeu, qui nécessitait une copie très précise du code que les organisateurs utilisaient pour calculer les jeux. Mais il était déjà en Python. Le dernier point fort du cercueil des autres langages de programmation était que le moteur est ancien et contient de nombreuses optimisations qui ne peuvent pas être recréées avec précision pendant la compétition pour obtenir votre propre version découpée de la simulation physique.

En conséquence, le moteur, qui était censé offrir à tous les participants des conditions égales pour simuler les mouvements, est devenu l'obstacle le plus difficile à cela. Plus de 10 personnes ont pu le surmonter et les 7 premières places du classement ont été prises exclusivement par les gars qui ont fait une simulation précise, ce qui peut servir de preuve de son importance dans de telles compétitions.

À l'exception de quelques participants qui ont pu pénétrer à l'intérieur du tamia et optimiser la copie de son état, les autres ont eu une simulation d'environ les mêmes performances (ce qui a rendu la compétition un peu plus intéressante, car vous savez que la lutte concerne l'algorithme de décision, non "qui compte le plus de coups").

Algorithme pour rechercher et prédire un adversaire

À partir de ce point, une description séparée des solutions commence. Les algorithmes seront décrits au nom de son auteur.

Vladimir Kiselev (Valdemar) 4e place

Une recherche aléatoire (Monte Carlo) a été utilisée pour rechercher l'espace de la solution. L'algorithme est le suivant:

1. Nous initialisons le génome - une séquence d'actions (gauche, droite, arrêt) pour 60 tiques - des données aléatoires.
2. Prenez le meilleur génome trouvé
3. Modifier aléatoirement l'une des actions
4. En utilisant la fonction d'évaluation, nous obtenons un nombre - un indicateur de la qualité du nouveau génome
5. Si vous obtenez une meilleure solution, mettez à jour la meilleure solution.
6. Répétez à nouveau à partir de l'étape 2

Mon simulateur a produit ~ 100k simulations du monde en 1 seconde, considérant qu'il y a en moyenne ~ 12ms par tick, nous obtenons 1200 actions par tick. Autrement dit, en 1 tick, nous parvenons à parcourir le cycle complet environ 20 fois.

Pour trouver la solution optimale, ce nombre d'itérations n'était clairement pas suffisant. Par conséquent, l'idée d'actions «d'étirement» a été mise en œuvre: au lieu d'un génome de 60 mouvements, nous fonctionnerons avec une chaîne de 12 mouvements «étirés» - nous pensons que chaque action dure 5 ticks d'affilée.
Le plus: Amélioration de la qualité des mutations en réduisant la longueur du génome, la simulation peut également être exécutée toutes les 5 ticks et vérifier 100 génomes au lieu de 20 (pour éviter les chutes de temps, je me suis finalement arrêté à 70).
Moins: les actions d'étirement peuvent conduire à des solutions non optimales (par exemple, se balancer sur le pare-chocs, au lieu d'un rack stable)

Il convient de noter les techniques qui ont considérablement amélioré la qualité de l'algorithme:

• Nous n'effectuons une initialisation aléatoire que sur le premier tick, le reste du temps nous réutilisons la meilleure solution trouvée avec un décalage de 1 mouvement (l'action sur le 2ème tick est décalée sur le 1er, etc., une action aléatoire est ajoutée à la fin). Cela améliore considérablement la qualité de la recherche, car sinon l'algorithme "oublie" ce qu'il allait faire au dernier tick et fait des saccades insensées dans des directions différentes.
• Au début du cours, on fait des changements plus intensifs (on change le génome 2 ou 3 fois au lieu d'un) dans l'espoir de casser le maximum local (similitude de température dans la méthode de simulation du recuit).
  L'intensité a été sélectionnée manuellement: les 30 premières itérations font 3 mutations, les 10 suivantes par 2, puis par 1.
• La prévision des actions ennemies est très importante. Au détriment du temps pour rechercher notre propre solution, nous lançons une recherche aléatoire du côté de l'adversaire, à 20 itérations, puis 50 pour nous-mêmes, en utilisant des informations sur les mouvements optimaux de l'adversaire.
  La meilleure décision de l'adversaire est également réutilisée au coup suivant avec un décalage. Dans le même temps, lors de la recherche d'une solution à l'ennemi, le génome du dernier mouvement est utilisé comme mes actions prévues.

Pendant le concours, il a activement utilisé des outils de développement local, ce qui a permis de trouver rapidement des bugs et de se concentrer sur les points faibles de la stratégie:

• arène locale - lancement de nombreux matchs contre la version précédente;
• visualiseur pour le comportement de débogage;
• un script pour collecter des statistiques sur les matchs du site - vous permet de comprendre sur quelles cartes et machines la défaite se produit le plus souvent.

mortido:
Compter tous les 5 ticks semble risqué, surtout si l'ennemi s'éloigne des options que vous aviez prévues. En revanche, dans ce monde de jeu à 5 ticks, il ne s'est pas passé grand-chose.
De plus, dans ma décision, j'ai néanmoins ajouté des combinaisons aléatoires à chaque tick, mais je ne dirai certainement pas comment cela a affecté la décision.

Commandos:
Changer quelques actions avec un tel nombre de simulations ne semble pas très significatif, car très peu de changements se produisent en une seule action. Mais lorsque vous étirez une action à 5 ticks de sens, cela semble devenir plus.
Je n'aime pas non plus l'idée elle-même - nous prenons le meilleur ensemble et essayons de le modifier quelque part au début. Il semble illogique que le changement des premières tiques laisse les suivantes plus ou moins adéquates.

Alexander Kiselev (mortido) 3e place

Armé d'articles de lauréats d'autres concours, j'ai décidé d'utiliser l'algorithme génétique. Il s'est avéré, cependant, quelque chose de similaire à une recherche aléatoire ou même une imitation de recuit, mais plus à ce sujet plus tard.

Nous encodons la solution avec un tableau de 40 nombres, où -1, 0 et 1 correspondent aux mouvements , et .

Au début de chaque tour, j'ai calculé combien de temps j'avais déjà passé pour tout le jeu, compté une nouvelle limite de temps basée sur le nombre de tours restants, et chaque tour que je supposais était de 1200 ticks. T.O. Initialement, j'ai essayé de ne pas passer plus de 11 ms par tour, mais je pouvais "marcher" un peu à la fin si les tours précédents étaient plus rapides que 1200 ticks.

Valdemar:
Fait intéressant, cette puce a aggravé le jeu pour moi. Il s'est avéré qu'il est toujours préférable de passer 20 à 30 ms que 11 en premier et 60 à la fin

Un tiers de cette fois, je cherchais le meilleur coup de l'ennemi, le reste a été dans le calcul de ma propre décision. Lors de la recherche d'un mouvement pour l'ennemi, mon comportement a été modélisé comme le meilleur du dernier mouvement, décalé de 1 tick. C'est-à-dire comme si je continuais à agir selon le plan établi dans la dernière tique, et il essaie de me résister.

La recherche de la solution elle-même était la même pour lui-même que pour l'adversaire:

1. Nous prenons la décision du dernier coup et la décalons d'un coup (ce que nous avons déjà fait)
2. Nous prouvons à la population de solutions aléatoires jusqu'à ce que nous remplissions tout
3. Nous simulons toutes les décisions et définissons la forme physique à l'aide de la fonction d'évaluation. Nous nous souvenons du meilleur.
4. Bien qu'il y ait du temps pour les calculs
   
   1. Astuce, ajoutez toujours 1 mutation de la meilleure solution actuelle à la population, rappelez-vous si c'est mieux
   2. Tant qu'il y a une place dans la nouvelle population et que le temps de calcul n'a pas été dépassé (vous pouvez aller sur le parquet d'une population peuplée)
      
      1. Nous prenons deux personnes différentes et repartons avec la meilleure forme physique - maman
      2. Nous prenons deux personnes différentes et partons avec la meilleure forme physique - papa (ne devrait pas coïncider avec maman)
      3. Croisez-les
      4. Muter si RND <
      5. Nous simulons une solution et nous nous en souvenons, si elle est la meilleure

En conséquence, nous retournerons la séquence d'actions considérée comme optimale. Le premier mouvement est envoyé comme une action de bot. Malheureusement, il y avait un sérieux inconvénient dans mon plan, car le nombre de simulations pouvant être effectuées dans une tique était très faible (y compris en raison de la longue fonction d'évaluation), puis sur le serveur de compétition 4 points ont été effectués une seule fois, et pour l'ennemi, cela n'a pas été effectué du tout. Cela a rendu l'algorithme plus comme une recherche aléatoire ou un recuit simulé (puisque nous avons réussi à muter la solution 1 fois depuis le dernier mouvement). Il était déjà trop tard pour changer quelque chose et nous avons réussi à conserver la 3ème place.

Il est important de mettre en œuvre les algorithmes de croisement, de mutation et de génération de solutions aléatoires initiales, car cela dépend des décisions qui seront testées, et une décision aléatoire complète n'est pas aussi bonne qu'elle peut paraître à première vue (cela fonctionnera, mais beaucoup plus d'options seront nécessaires).

Dans la version finale, des décisions aléatoires ont été générées en segments, ce qui excluait les solutions «saccadées» en un seul endroit:

1. Équipe aléatoire sélectionnée
2. Pour toute la longueur de la solution (40 coups)
   
   1. On écrit la commande courante dans la cellule
   2. Avec une probabilité de 10%, nous modifions l'équipe actuelle au hasard

Selon une technologie similaire, une mutation s'est également produite - un segment aléatoire de la solution a été remplacé par une commande aléatoire. Le croisement a eu lieu en choisissant le point auquel la décision a été prise de 1 parent, et après du 2.

J'ai aimé que nous utilisions tout le temps dont nous disposions pour trouver la meilleure solution. Ce n'est pas grave si la solution n'est pas la meilleure - nous pouvons l'améliorer au prochain tick, car l'optimisation se révèle "floue" dans le temps. , . , - , . ,

Valdemar:
1 , , .

Commandos:
— - .
— , . , … , . " ”. -.

(Commandos) 1

( ), n m . 3^2=9 . m + n 40 .

:

 |----------- n  -----------|---------- m  --------| |   ...   |   ...   | 

: , , . ( ).

n m , . , .

:

1. , ( , ):
   
   • , , , .
   • , , . . . , , , .
   • . ; ( ).
2. n m . , .1, , . - ( ) , — , ;
3. . , — . , ( ).

Valdemar:
, 2 . . , .

mortido:
Ouah! , . . , 2 , 40-60 . , 3 .
n + m == const ?

. n + m != const , . , . - .

(Valdemar) 4

, . , ( , , ..) [0..1].
. : , .
, , : , .

, :

• — 70 180 ( : ).
  , .
• 0..500
• — [2pi, pi/4] [0, 1]
• — , ( ), ( , , )
• — , , , .
  , , .
• — . .
• Y — .

, 2 , .

.

:

• “” ,
• “ ” , , .

mortido:
, .. , .

Commandos:
, . -

(mortido) 3

, chipmunk. . , , , , . .

3 .

, ( , , ):

• . , , ( , );
• , — , ; , 1 ;
• ;
• ( , );
• ( “+”, “-”);
  - ( “+”, “-”); , , , ;
  30 , , ( );
• , .

, , (, , )

Valdemar:
. , “ , , ” , ( ..) .

, , . .

Commandos:
, , “”… ? , “” .

(Commandos) 1

SquaredWheelsBuggy , .. , . Buggy , , ( /).
:

1. ;
2. ; — , , 1 0; .. ;
3. . ; 10 ( );
4. ( , );
5. (, );
6. — - , ;
7. / ; , — ; .

1-5 , . 2 “ ”.

Valdemar:
, . , .

mortido:
, 10 .

IF'

(Valdemar) 4

, if'. 3 , , . , , -.
: , “” — , - , ( , ) — .

:

• . , .
• — , .
• . “ ” .
  , , .
  , , .

, : . , , if' .

mortido:
, . .

Commandos:
if'. , , … , , .

(mortido) 3

- .

3 . . . “”, . , , .

, “” . . , , , - . . , , .. .

, , , , , . … . - — , ( , ).

Valdemar:
, . . “” , if'. , — .

, + . , .

Commandos:
… , - — , , . , , .

(Commandos) 1

. (, , ). ( ) /.

pill carcass map , , ( ). island map, , .

island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .

(Pill map, Bus) , ( / 100% ).

pill hubble map. , ( ), . .

— , ...

, . , . ( ).

Valdemar:
, — . , .

mortido:
, “” .

Valdemar:
. , . ( ) .
. “”, , , , :)
, mailru , .

mortido:
: , … , , ( ). , 3 , , … .

Commandos:
- , . , , , . … . — , .
— ++. . , . 1 -.

, . , . , , .

Mail.Ru Group .

Valdemar
mortido