«Dormammu, je suis tombé d'accord»: un algorithme de coopération mutuellement bénéfique avec une personne

Des réflexions sur le sujet de l'intelligence artificielle ont traversé les esprits de grandes personnes pendant de nombreux siècles. Avec le passage du temps et le développement de la technologie, les pensées se sont transformées en mise en œuvre, les théories en pratique et la science-fiction en un avenir très réel pour l'humanité. L'essence principale de l'IA est d'aider les gens. En d'autres termes, les machines intelligentes devraient servir une personne dans sa pleine mesure, sans violer les lois fondamentales de la robotique, qui ont été exprimées par le célèbre Isaac Asimov. Mais une telle interaction, si vous la raisonnez sur terre, n'a qu'un seul vecteur: la personne a dit - l'IA a joué. C'est-à-dire que le travail de l'intelligence artificielle vise uniquement l'homme. Mais que se passe-t-il si l'IA pense en fonction du bien des deux côtés de l'interaction? Comment apprendre à une voiture à faire des compromis, à négocier et même à négocier avec une personne? Eh bien, c'est précisément à ces questions que l'étude d'aujourd'hui donne des réponses, dans lesquelles un algorithme a été créé qui permet à la machine de parvenir à un accord mutuellement bénéfique avec une personne. Examinons de plus près ces problèmes. Allons-y.

Idée de recherche

Les chercheurs ont noté que depuis que Turing a commencé à parler d'intelligence artificielle, l'homme a essayé de créer une machine qui peut la dépasser en quelque chose. D'une manière ou d'une autre, nous connaissons tous de nombreux concours, compétitions et expériences lorsqu'une personne rivalise avec une machine (échecs, poker et même arts martiaux). Cependant, jusqu'à présent, très peu d'attention a été accordée à un autre type d'interaction entre l'homme et la machine. Après tout, ce n'est pas toujours dans la vie que la victoire ou la défaite. Parfois, le consensus même est nécessaire lorsque les besoins et / ou les désirs de deux parties sont satisfaits.

Considérer le travail de l'IA exclusivement à partir de la position «oui ou non» est faux, car il y a toujours une option «probablement».

Les scientifiques ont réussi à créer un algorithme qui peut évaluer la situation, peser le pour et le contre, hiérarchiser et parvenir à un compromis. Pour vérifier le fonctionnement de l'algorithme, des jeux stochastiques * répétés ont été utilisés .

Un jeu stochastique * est un jeu répétitif avec un ou plusieurs joueurs, lorsque son état change constamment dans un ordre aléatoire.

Créer un algorithme qui peut fonctionner dans de telles conditions «flottantes» n'est pas une tâche facile. Pour fonctionner efficacement, l'algorithme doit avoir certaines fonctionnalités. Plus à leur sujet plus en détail.

Premièrement, l'algorithme ne doit pas être orienté sujet, c'est-à-dire qu'il doit fonctionner dans un nombre illimité de scénarios (dans ce cas, le jeu). Cette caractéristique est appelée par les scientifiques «universalité».

Deuxièmement, l'algorithme doit apprendre à établir des relations fructueuses avec n'importe quelle personne / algorithme sans d'abord se familiariser avec son comportement. C'est la «flexibilité». Pour y parvenir, l'algorithme doit tenir compte du fait que presque toujours son partenaire-adversaire adhère à un comportement opérationnel, c'est-à-dire qu'il veut utiliser l'algorithme exclusivement pour son propre bénéfice. En conséquence, il doit déterminer quand et comment attirer à la coopération celui qui n'a probablement pas l'intention de coopérer.

Et enfin, troisièmement, l'algorithme doit agir rapidement, surtout lorsque vous jouez avec une personne. Cette fonctionnalité est appelée «vitesse d'apprentissage».

En mots, tout est très beau, clair et simple. Mais en fait, la réalisation de ces caractéristiques est semée d'embûches. Sans parler du fait que la capacité d'adaptation à l'adversaire peut être compliquée par le fait que l'adversaire lui-même sait s'adapter. C'est un problème, car deux algorithmes adaptatifs, malgré toutes leurs tentatives d'adaptation, ne parviennent pas à un compromis.

Les scientifiques notent également que lors de l'interaction entre deux personnes, l'un des outils importants pour obtenir des résultats mutuellement bénéfiques sont des choses difficiles à associer à une machine, telles que l'intuition, les émotions, les instincts, etc. Il a été prouvé que le «discours bon marché» accompagne fortement un résultat mutuellement bénéfique.

Discussion bon marché * - dans la théorie des jeux, il s'agit d'une interaction entre les joueurs qui n'affecte pas directement le résultat du jeu. En d'autres termes, "conversation hors sujet".

Les chercheurs ont décidé de mettre en œuvre cela dans leur algorithme, ce qui l'aide à mieux gérer les calculs de situations complexes et à développer une idée commune de la situation avec une personne. Bien que jusqu'à présent, on ne sait pas encore comment l'algorithme mettra en œuvre ces «compétences» en conjonction avec ses principales caractéristiques (flexibilité, universalité, vitesse d'apprentissage).

L'objectif principal de l'étude est d'étudier autant d'algorithmes existants que possible, de développer un algorithme basé sur l'apprentissage automatique avec un mécanisme pour répondre aux signaux et de les générer à un niveau compréhensible pour l'homme, et de mener de nombreux jeux expérimentaux pour démontrer la capacité d'apprentissage de l'algorithme et sa capacité à s'adapter à différents adversaires (personnes ou d'autres algorithmes).

La conduite et les résultats de l'étude

Les algorithmes de comportement stratégique dans les jeux répétés sont présents dans de nombreux aspects de la société: économie, biologie évolutive, IA, etc. À l'heure actuelle, de nombreux algorithmes de ce type ont été créés, chacun ayant ses propres avantages. Naturellement, les scientifiques ont décidé de les utiliser pour développer leur algorithme. Ainsi, 25 algorithmes ont été sélectionnés.

Six indicateurs de performance ont été identifiés sur la base de trois options de jeu: 100, 1000 et 50 000 tours.

Indicateurs de performance:

• la valeur moyenne du Round-Robin * ;
• meilleur résultat;
• pire résultat de score;
• dynamique du réplicateur * ;
• tournoi du groupe 1;
• tournoi du groupe 2.

Round-Robin * - un type d'interaction de jeu, lorsque pendant le tour chacun des participants joue alternativement avec tous les autres participants.

L'équation du réplicateur * est une dynamique de jeu non linéaire déterministe monotone utilisée dans la théorie des jeux évolutionnaires.

Le premier indicateur (la valeur moyenne de Round-Robin) nous permet de comprendre dans quelle mesure l'algorithme est capable d'établir des relations bénéfiques avec une variété de partenaires de jeu.

Le deuxième indicateur (le meilleur score) est le nombre d'algorithmes partenaires dans le jeu avec lesquels l'algorithme étudié a gagné le plus grand nombre de points. Il est exprimé en pourcentage. Cet indicateur reflète la fréquence à laquelle l'algorithme sera un choix bienvenu, compte tenu des informations sur l'algorithme du partenaire de jeu.

Le troisième indicateur (le pire résultat par points) est une évaluation de la capacité de l'algorithme à lier ses pertes (ratés, erreurs).

Les trois autres indicateurs visent à déterminer la stabilité de l'algorithme pour différents groupes de population.

Par exemple, un tournoi (groupe-1) est une série de jeux dans lesquels les algorithmes sont divisés en 4 groupes. Les chefs de chaque groupe se qualifient pour la finale, où le seul gagnant est déterminé. Mais dans le tournoi du groupe 2, deux meilleurs algorithmes sont sélectionnés dans chaque groupe, qui vont en demi-finale, puis les gagnants se rendent en finale, où le seul meilleur algorithme est déterminé.

Selon les scientifiques, aucun des algorithmes sélectionnés (25 pièces) n'a précédemment participé à une telle vérification à grande échelle (nombreux partenaires et indicateurs mesurés). Une telle vérification montre à quel point chacun des algorithmes fonctionne bien dans un jeu normal avec 2 participants et n'est pas «programmé» pour un scénario spécifique.


Tableau 1: Résultats expérimentaux impliquant 25 algorithmes de comportement stratégique différents.

Les résultats obtenus ne sont qu'un outil qui vous permet de mieux comprendre les avantages et les inconvénients d'un algorithme particulier. Par exemple, les algorithmes gTFT, WSLS, Mem-1 et Mem-2 ont montré d'excellents résultats dans le "dilemme du prisonnier" * .

Le dilemme du prisonnier * - dans la théorie des jeux, un état où les joueurs ne sont pas toujours prêts à coopérer, même si cela leur sera bénéfique. Dans ce cas, le joueur («prisonnier») a ses propres intérêts en priorité, et il ne pense pas aux bénéfices des autres.

Cependant, ces mêmes algorithmes ont montré de mauvais résultats dans tous les jeux 2x2, ce qui indique leur inefficacité dans les interactions plus longues. Par conséquent, ils ne peuvent pas s'adapter au comportement d'un partenaire (un autre joueur).

Une observation amusante a été le fait que les algorithmes Exp3, GIGA-WoLF et WMA, qui sont la base des algorithmes du World Poker Championship, ont également montré un mauvais résultat. Ce qui est assez évident, car l'algorithme de poker ne doit pas coopérer avec les autres joueurs, mais les dépasser et les vaincre.

Si nous considérons tous les indicateurs dans leur ensemble, alors un algorithme se démarque - S ++, qui s'est montré parfaitement dans tous les types de jeux avec toutes les combinaisons possibles vérifiées. De plus, il convient de noter que pour la plupart des algorithmes, le développement du comportement de coopération ne s'est produit qu'après des milliers de tours. Pour S ++, ce processus n'a pris que quelques tours, ce qui en fait une excellente option, compte tenu de l'importance de cet indicateur dans un jeu impliquant non pas un algorithme, mais une personne vivante. Plus l'algorithme testé «réalise» rapidement la nécessité et la rentabilité de la coopération et du compromis, plus il sera facile et rapide à y parvenir.


Les résultats de l'expérience "S ++ contre l'homme".

L'interaction de S ++ avec d'autres algorithmes a montré un bon résultat, il a donc été nécessaire de vérifier comment S ++ se comportera en travaillant avec des personnes vivantes.

L'expérience (4 jeux répétitifs de 50 tours ou plus) a impliqué des algorithmes S ++ et MBRL-1, ainsi qu'un groupe de personnes. Les résultats de cette expérience sont visibles dans les graphiques ci-dessus. Nous voyons que l'établissement de la coopération S ++ avec sa copie est excellent, mais ce processus n'est pas cohérent avec les gens. De plus, S ++ a réussi à réaliser une coopération à long terme avec une personne dans <30% des tournées seulement. Ce n'est pas le résultat le plus encourageant, mais les gens qui jouent avec les gens n'ont pas réussi non plus à établir une coopération à long terme.

Bien que S ++ se démarque parmi d'autres algorithmes, cela ne lui a pas permis de devenir un gagnant clair dans cette étude. Aucun des 25 algorithmes n'a pu démontrer la capacité de nouer des liens de coopération à long terme avec un joueur humain.

S #: coopérative humaine et algorithme

Comme mentionné précédemment, un aspect tel que les «appels bon marché» joue un rôle important dans la réalisation d'une coopération à long terme entre les parties, cependant, une telle technique n'a été mise en œuvre auparavant dans aucun des jeux ci-dessus. Par conséquent, les scientifiques ont décidé de créer leur propre version, qui permettra aux joueurs d'utiliser cette technique, mais dans une mesure limitée - 1 message au début de chaque tour.

Pour une personne, de telles conversations sont naturelles. Cependant, pour une machine qui vise à résoudre un problème et fera pour cela, ce qui est logique, de telles formes d'interaction sont étrangères. L'idée d'introduire un tel comportement conduit directement les scientifiques à un concept tel que «l'IA explicable» («AI explicable»), lorsque les actions de la machine sont facilement compréhensibles pour l'homme. Le problème est que la plupart des algorithmes basés sur l'apprentissage automatique ont une représentation interne de bas niveau, qui est difficile à exprimer à un niveau compréhensible pour les humains.

Heureusement, la structure interne de S ++ a un niveau très élevé, ce qui lui permet d'être utilisé comme base pour la mise en œuvre de la technique du «bon marché». S ++ a introduit un cadre de communication qui vous permet de générer et de répondre à des «appels bon marché».


Une nouvelle forme de l'algorithme S ++ a été appelée S #.

L'image (a) montre le schéma de l'algorithme, et (b ) montre le schéma d'interaction avec un partenaire dans le jeu en utilisant la technique de «conversation bon marché». Également sur b, nous pouvons nous familiariser avec les phrases que l'algorithme S # peut générer et le type de réponse qu'il attend pour une phrase particulière.

Ainsi, S # est capable de répondre aux «signaux» (phrases et actions) du joueur partenaire, ce qui lui permet de décider quelle tactique appliquer ensuite. Associé à un degré élevé d'auto-apprentissage de l'algorithme S ++ d'origine, l'algorithme résultant peut créer des relations mutuellement bénéfiques à long terme avec un joueur, une personne ou un autre algorithme.

Afin de vérifier cette affirmation, les scientifiques ont organisé une expérience avec 220 personnes. Un total de 472 matchs répétés ont été joués. La technique du «discours bon marché» a également été incluse dans l'expérience, mais pas toujours. Et les identités des joueurs étaient cachées, donc personne (ni l'algorithme ni les gens) ne savait avec qui ils jouaient.


Les résultats de l'expérience impliquant 220 personnes.

Lorsque la «conversation bon marché» n'était pas incluse dans le processus de jeu, l'interaction homme-personne ou personne-S # n'a pas conduit à une coopération à long terme. Lorsque cette technique a été intégrée au jeu, les indicateurs de coopération ont doublé.



Le graphique (a) montre le type de phrases utilisées pendant le jeu d'une personne et l'algorithme S # (haine, menace, contrôle, éloge ou planification).

Après l'expérience, tous les participants ont été invités à évaluer le degré d'intelligence de leurs partenaires dans le jeu, la clarté de leurs intentions et l'utilité d'interagir avec eux. Résultats de l'enquête sur le graphique (b) . Les horaires sont encore plus divertissants. Il montre le pourcentage du nombre de fois qu'une personne ou un algorithme a considéré son partenaire dans le jeu comme humain. Comme vous pouvez le voir, la plupart des participants humains ont estimé que S # est une personne.

Les scientifiques notent également que les résultats de S # sont encore meilleurs par rapport à la façon dont les paires personnes-personnes et S # -S # interagissent. Le degré d'occurrence de relations de coopération à long terme entre une personne et S # est approximativement au même niveau qu'un couple personne-personne. Et la paire S # -S # sans l'utilisation de la technique de «conversation bon marché» a un bien meilleur résultat que la paire personne-personne, qui a eu l'occasion de l'utiliser.

En résumant tout ce qui précède, l'algorithme S # a montré des résultats qui peuvent être mis sur un pied d'égalité avec les résultats de l'interaction entre les personnes.

Jeux stochastiques récurrents

Des jeux de type normal ont permis de comprendre que l'algorithme S # est un vecteur de recherche prometteur. Cependant, ces jeux sont limités, ils sont plus abstraits. Par conséquent, les scientifiques ont décidé d'utiliser un jeu stochastique répétitif dans lequel les participants doivent séparer des blocs de formes et de couleurs différentes. Pour l'algorithme S #, les phrases «collaborons» et «j'obtiens plus de points» ont été ajoutées. De plus, S # était limité dans son utilisation de la technique du «discours bon marché» - il pouvait utiliser des phrases, mais ne pouvait pas répondre aux phrases d'un joueur humain.


Le schéma du jeu avec des blocs multicolores (carré, cercle et triangle).

L'essence du jeu est la suivante. Chaque joueur a un ensemble de 9 blocs (différents, bien sûr). A chaque mouvement, le joueur retire 1 bloc de son set jusqu'à n'en avoir que 3. Ces trois blocs doivent répondre aux exigences (même forme / couleur ou forme et couleur différentes en même temps). Chaque bloc coûte un certain nombre de points (points). Si le bloc ne convient pas, ce nombre devient négatif. Le diagramme ci-dessus montre 5 options pour le résultat du jeu.


L'utilisation et la non-utilisation des «appels bon marché».

Lorsque vous jouez entre des personnes, l'utilisation de «conversations bon marché» n'a pas beaucoup affecté son résultat. Cependant, cette technique a considérablement augmenté le résultat de l'algorithme S # dans un jeu avec une personne.

Différences de S # par rapport aux autres algorithmes

L'algorithme S # a dépassé tous les autres sujets, mais pourquoi? Quelles propriétés de cet algorithme le distinguent d'un certain nombre de concurrents? Les scientifiques en ont compté jusqu'à trois.

Premièrement, c'est la capacité de générer et de répondre à des signaux appropriés (phrases et actions) qui peuvent être compris par les humains. Cela rend cet algorithme très flexible, capable d'évoluer en fonction de la situation. Et, bien sûr, cela vous permet de former des liens mutuellement bénéfiques à long terme avec d'autres joueurs.

Deuxièmement, S # utilise un ensemble diversifié de stratégies, ce qui vous permet de vous adapter aux différents joueurs partenaires et aux différents types de jeux. Dans le même temps, les algorithmes conçus pour fonctionner efficacement dans un seul scénario spécifique ne peuvent pas fonctionner efficacement en dehors de leur «zone de confort».

Troisièmement, l'algorithme S # maintient un état de bénéfice mutuel, tandis que d'autres algorithmes, ayant reçu ce qu'ils veulent, passent à une stratégie différente.


Graphiques de la durée de l'état de coopération mutuellement bénéfique.

Comme le montre le graphique ci-dessus (a) , S # établit une connexion mutuellement avantageuse avec le joueur plus tôt que les autres algorithmes. Il détient également un état de coopération mutuellement bénéfique avec un nombre de tours significativement plus important que les algorithmes concurrents (graphique (b) ).

La flexibilité de S # est clairement visible sur le graphique (c) , où l'on voit qu'il atteint l'objectif plus souvent que les autres, quel que soit le type de jeu ou de partenaire.

Assez inhabituel est l'affirmation des scientifiques que leur algorithme S # a appris la fidélité. Le fait est qu'ayant établi une coopération dans la paire S # -S #, l'algorithme n'est pas pressé de la casser, même s'il n'y a pas beaucoup d'avantages à cela. Dans le même temps, dans les couples d'homme à homme, la coopération s'est souvent interrompue immédiatement après avoir obtenu les avantages nécessaires à court terme. Ce comportement a naturellement conduit à de mauvais résultats en fin de match pour les deux camps.

Ceux qui souhaitent se familiariser avec le rapport des scientifiques peuvent le trouver ici .

Des documents de recherche supplémentaires sont disponibles ici .

Épilogue

Cette étude est très différente des autres en ce qu'elle ne vise pas à créer une IA capable de vaincre une personne dans quelque chose, mais à créer une IA capable et désireuse de parvenir à un consensus. Est-ce à dire que les machines intelligentes deviendront plus humaines grâce à cet algorithme? C'est possible. , , , , .

, S# «». , . , .

Merci de rester avec nous. Aimez-vous nos articles? Vous voulez voir des matériaux plus intéressants? Soutenez-nous en passant une commande ou en le recommandant à vos amis, une réduction de 30% pour les utilisateurs Habr sur un analogue unique de serveurs d'entrée de gamme que nous avons inventés pour vous: Toute la vérité sur VPS (KVM) E5-2650 v4 (6 cœurs) 10 Go DDR4 240 Go SSD 1 Gbps à partir de 20 $ ou comment diviser le serveur? (les options sont disponibles avec RAID1 et RAID10, jusqu'à 24 cœurs et jusqu'à 40 Go de DDR4).

3 Dell R630 — 2 Intel Deca-Core Xeon E5-2630 v4 / 128GB DDR4 / 41TB HDD 2240GB SSD / 1Gbps 10 TB — $99,33 , , .

Dell R730xd 2 fois moins cher? Nous avons seulement 2 x Intel Dodeca-Core Xeon E5-2650v4 128 Go DDR4 6x480 Go SSD 1 Gbps 100 TV à partir de 249 $ aux Pays-Bas et aux États-Unis! Pour en savoir plus sur la création d'un bâtiment d'infrastructure. classe utilisant des serveurs Dell R730xd E5-2650 v4 coûtant 9 000 euros pour un sou?