Dans cet article, je partagerai l'expérience de la croissance de l'intelligence artificielle (IA) simple à l'aide d'un algorithme génétique, et parlerai également de l'ensemble minimal de commandes nécessaires pour former tout comportement.
Le résultat du travail était que l'IA, ne connaissant pas les règles, maîtrisait indépendamment le jeu du tic-tac-toe et découvrait les faiblesses des bots qui jouaient contre. Mais j'ai commencé par une tâche encore plus simple.
Jeu d'instructions
Tout a commencé avec la préparation d'un ensemble de commandes que l'IA pourrait avoir. Les langages de haut niveau contiennent des centaines d'opérateurs différents. Pour mettre en avant le minimum nécessaire, j'ai décidé de me tourner vers le langage Assembleur. Cependant, il s'est avéré qu'il contient de nombreuses commandes.
J'avais besoin de l'IA pour lire et sortir des données, travailler avec la mémoire, effectuer des calculs et des opérations logiques, faire des transitions et des boucles. Je suis tombé sur le langage Brainfuck, qui ne contient que 8 commandes et peut effectuer tous les calculs (c'est-à-dire que Turing est complet). En principe, il convient à la programmation génétique, mais je suis allé plus loin.
Je me suis demandé: quel est le nombre minimum de commandes nécessaires pour implémenter un algorithme? Il s'est avéré - un!
Le processeur URISC ne contient qu'une seule commande: soustraire et ignorer l'instruction suivante si la soustraite était supérieure à celle décrémentée. Cela suffit pour construire n'importe quel algorithme.
Oleg Mazonka est allé encore plus loin, il a développé l'équipe
BitBitJump et a prouvé qu'elle est complète selon Turing. La commande contient trois adresses, copie un bit de la première à la deuxième adresse mémoire et transfère le contrôle à la troisième adresse.
Après avoir emprunté les idées d'Oleg, pour simplifier le travail, j'ai développé l'équipe SumIfJump. La commande contient quatre opérandes: A, B, C, D et effectue les opérations suivantes: ajoute des données de la cellule à l'adresse A à l'adresse B, si la valeur est supérieure à la valeur spécifiée *, elle va à l'adresse C, sinon elle va à l'adresse D.
Remarque* Dans ce cas, 128 ont été utilisés - la moitié de la longueur du génome.
Lorsque l'opérande A accède à la cellule de mémoire N0, des données sont entrées et lorsqu'elles vont à la cellule N1, elles sont ensuite sorties.
Ci-dessous se trouve le code SumIfJump sur FreePascal (un analogue gratuit de Delphi).
procedure RunProg(s: TData); var a, b, c, d: TData; begin Inc(NStep); if NStep > MaxStep then begin ProgResult := 'MaxStep'; Exit; end; a := s; b := s + 1; c := s + 2; d := s + 3; a := Prog[a]; b := Prog[b]; c := Prog[c]; d := Prog[d]; if a = 0 then begin ProgResult := 'Input'; Exit; end; if a = 1 then begin ProgResult := 'Output'; Exit; end; Prog[b] := Prog[b] + Prog[a]; if Prog[b] < ProgLength div 2 then RunProg(c) else RunProg(d); end;
SumIfJump implémente du code auto-modifiable. Il peut exécuter tous les algorithmes disponibles dans le langage de programmation habituel. Le code est facile à modifier et résiste à toute manipulation.
Tâche simple
Donc, notre IA n'a qu'une seule équipe. Bien que le tic-tac-toe soit un jeu très difficile pour lui, j'ai commencé par un jeu plus simple.
Le bot donne un nombre aléatoire, et l'IA devrait lire les données et donner une réponse. Si le nombre est supérieur à la moyenne (parmi la gamme de nombres aléatoires), l'IA doit donner un nombre inférieur à la moyenne et vice versa.
Le génome de notre IA se compose de 256 cellules avec des valeurs de 0 à 255. Chaque valeur est une mémoire, un code et une adresse. Le nombre d'étapes d'exécution de code est limité à 256. Les opérandes sont lus les uns après les autres.
Initialement, le génome est formé par un ensemble de nombres aléatoires, donc l'IA ne sait pas ce dont elle a besoin pour jouer. De plus, il ne sait pas qu'il doit entrer et sortir des données séquentiellement, répondant au bot.
Population et sélection
La première population se compose de 256 IA qui commencent à jouer avec le bot. Si l'IA effectue les actions correctes, par exemple, demande des données d'entrée, puis affiche quelque chose, l'IA reçoit des points. Plus les actions sont correctes, plus il y a de points.
Les 16 IA qui ont marqué le plus de points donnent 15 descendants et continuent de participer au jeu. Un descendant est un mutant. La mutation se produit en remplaçant une cellule aléatoire dans la copie parent par une valeur aléatoire.
Si aucune IA n'a marqué de points dans la première population, la population suivante est formée. Et ainsi de suite jusqu'à ce qu'une partie de l'IA commence à effectuer les actions correctes et à donner la progéniture «correcte».
Évolution
| N | Jalons |
|---|
| 1 | L'IA ne fait rien. Le programme prend 256 étapes et se termine. |
| 2 | A commencé à demander des données. |
| 3 | Il a commencé à demander des données et à produire quelque chose. La séquence des demandes et des réponses est chaotique. |
| 4 | L'entrée et la sortie des données se produisent séquentiellement, parfois des erreurs se produisent. Dans la moitié des cas, l'IA donne la bonne réponse. |
| 5 | Donne régulièrement des réponses correctes, mais parfois des erreurs se produisent. |
| 6 | A donné la bonne réponse en 30 mille itérations. La sélection est téléchargée. |
Entre des événements importants, des milliers de générations sont passées. Le programme a été lancé dans plusieurs threads sur Core i7. Les calculs ont pris environ 15 minutes.
Points intéressants
- Lorsque le «chef» de l'IA a commis une erreur aléatoire et n'a pas marqué suffisamment de points, la population a commencé à se dégrader, car progéniture formée de parents «secondaires».
- Il se trouve que dans le flux avec des étrangers qui marquaient le temps, une mutation réussie s'est produite, entraînant une augmentation explosive des points accumulés. Après cela, ce flux est devenu le leader.
- Parfois, pendant longtemps, aucune mutation réussie ne s'est produite et même 500 000 générations n'ont pas été suffisantes pour terminer la sélection.
Conclusion
En conclusion, j'ai fait de même avec le jeu tic-tac-toe. La taille du génome a été utilisée comme dans le premier cas. Le nombre d'étapes a été augmenté à 1024 et la taille de la population à 64 (pour un calcul plus rapide). Le calcul a pris un peu plus de temps. Tout s'est passé selon le même scénario.
Au début, l'IA a joué contre le "randomiseur". J'ai appelé le bot qui marche au hasard. Assez rapidement, AI a commencé à le battre, remplissant une ligne. De plus, j'ai compliqué la tâche en ajoutant une petite raison au randomiseur: occuper la ligne, si possible, ou défendre. Cependant, dans ce cas, AI a trouvé les faiblesses du bot et a commencé à le battre. Peut-être que l'histoire à ce sujet est un sujet pour un article séparé.
Le fils m'a demandé d'écrire un programme pour que les IA jouent entre eux, et non avec le bot. Il y avait des idées pour faire la même chose pour jouer aux dames ou y aller, cependant, pour cela, je n'avais déjà pas assez de temps.
La seule méthode que j'ai utilisée pour obtenir de nouveaux individus était une mutation. Vous pouvez également utiliser le croisement et l'inversion. Peut-être que ces méthodes accéléreront l'obtention du résultat souhaité.
En fin de compte, l'idée est née: donner à l'IA la capacité de gérer tous les processus sur un PC et de lutter pour les ressources informatiques. Connectez un PC à Internet et utilisez le pool d'anciennes fermes de bitcoins comme puissance de calcul ...
Comme dit, conduisant une expérience similaire, le blogueur
Mikhail Tsarkov :
Peut-être qu'ils vont conquérir le monde, mais si?
Les références
- Algorithmes génétiques
- Copier Bit - La machine informatique la plus simple / Oleg Mazonka
- URISC - Wikipedia
- Complétude de Turing - Wikipedia