⏺️ 🥝 🕔 Cultivo da inteligência artificial como exemplo de um jogo simples 💇🏾 🆙 🤜🏿

Neste artigo, compartilharei a experiência de aumentar a inteligência artificial simples (IA) usando um algoritmo genético e também falarei sobre o conjunto mínimo de comandos necessários para formar qualquer comportamento.

O resultado do trabalho foi que a IA, sem conhecer as regras, dominou independentemente o jogo da velha e encontrou as fraquezas dos bots que jogavam contra ela. Mas comecei com uma tarefa ainda mais simples.

Conjunto de instruções

Tudo começou com a preparação de um conjunto de comandos que a IA poderia ter. Os idiomas de alto nível contêm centenas de operadores diferentes. Para destacar o mínimo necessário, decidi voltar para a linguagem Assembler. No entanto, descobriu-se que ele contém muitos comandos.

Eu precisava da IA para ler e gerar dados, trabalhar com memória, realizar cálculos e operações lógicas, fazer transições e loops. Me deparei com a linguagem Brainfuck, que contém apenas 8 comandos e pode executar qualquer cálculo (ou seja, Turing está completo). Em princípio, é adequado para programação genética, mas fui além.

Eu me perguntava: qual é o número mínimo de comandos necessários para implementar qualquer algoritmo? Como se viu - um!

O processador URISC contém apenas um comando: subtraia e pule a próxima instrução se a subtraída for maior que a decrementada. Isso é suficiente para criar qualquer algoritmo.

Oleg Mazonka foi ainda mais longe, ele desenvolveu a equipe BitBitJump e provou que está completa de acordo com Turing. O comando contém três endereços, copia um bit do primeiro para o segundo endereço de memória e transfere o controle para o terceiro endereço.

Tendo emprestado as idéias de Oleg, para simplificar o trabalho, desenvolvi a equipe SumIfJump. O comando contém quatro operandos: A, B, C, D e executa o seguinte: adiciona dados da célula ao endereço A ao endereço B, se o valor for maior que o especificado *, ele vai para o endereço C, caso contrário, ele vai para o endereço D.

Nota

* Nesse caso, 128 foram usados - metade do comprimento do genoma.

Quando o operando A acessa a célula de memória N0, os dados estão sendo inseridos e, quando vão para a célula N1, são enviados.

Abaixo está o código SumIfJump no FreePascal (um análogo gratuito do 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 implementa código auto-modificável. Pode executar qualquer algoritmo disponível na linguagem de programação usual. O código é fácil de modificar e suporta qualquer manipulação.

Tarefa simples

Portanto, nossa IA tem apenas uma equipe. Embora tic-tac-toe seja um jogo muito difícil para ele, comecei com um jogo mais simples.

O bot fornece um número aleatório e a IA deve ler os dados e dar uma resposta. Se o número for maior que a média (do intervalo de números aleatórios), a IA deve fornecer um número menor que a média e vice-versa.

O genoma da nossa IA consiste em 256 células com valores de 0 a 255. Cada valor é uma memória, um código e um endereço. O número de etapas de execução do código é limitado a 256. Os operandos são lidos um após o outro.

Inicialmente, o genoma é formado por um conjunto de números aleatórios, de modo que a IA não sabe o que precisa jogar. Além disso, ele não sabe que precisa digitar e enviar dados sequencialmente, respondendo ao bot.

População e seleção

A primeira população consiste em 256 AIs que começam a brincar com o bot. Se o AI executar as ações corretas, por exemplo, solicitar dados de entrada e depois exibir algo, o AI receberá pontos. Quanto mais ações corretas, mais pontos.

As 16 IAs que marcaram mais pontos dão 15 filhos e continuam a participar do jogo. Um descendente é um mutante. A mutação ocorre substituindo uma célula aleatória na cópia pai por um valor aleatório.

Se nenhuma IA marcou pontos na primeira população, a próxima população é formada. E assim por diante, até que parte da IA comece a executar as ações corretas e dar a prole "correta".

Evolução

N	Marcos
1	AI não faz nada. O programa leva 256 etapas e termina.
2	Começou a solicitar dados.
3	Ele começou a solicitar dados e produzir algo. A sequência de solicitações e respostas é caótica.
4	A entrada e saída de dados ocorre sequencialmente, às vezes ocorrem erros. Na metade dos casos, a IA fornece a resposta correta.
5	Dá respostas corretas regularmente, mas às vezes ocorrem erros.
6	Deu a resposta correta em 30 mil iterações. A seleção é carregada.

Entre eventos significativos, milhares de gerações se passaram. O programa foi lançado em vários threads no Core i7. Os cálculos levaram cerca de 15 minutos.

Pontos interessantes

Quando o “líder” da IA cometeu um erro aleatório e não obteve pontos suficientes, a população começou a se degradar, porque filhos formados de pais "secundários".
Aconteceu que no fluxo com pessoas de fora que estavam marcando o tempo, ocorreu uma mutação bem-sucedida, proporcionando um aumento explosivo nos pontos acumulados. Depois disso, esse fluxo se tornou o líder.
Às vezes, durante muito tempo, não ocorreram mutações bem-sucedidas, e mesmo 500 mil gerações não foram suficientes para concluir a seleção.

Conclusão

Em conclusão, eu fiz o mesmo com o jogo da velha. O tamanho do genoma foi utilizado como no primeiro caso. O número de etapas foi aumentado para 1024 e o tamanho da população para 64 (para um cálculo mais rápido). O cálculo demorou um pouco mais. Tudo aconteceu de acordo com o mesmo cenário.

A princípio, a IA jogou contra o "randomizador". Liguei para o bot que anda aleatoriamente. Muito rapidamente, a IA começou a vencê-lo, preenchendo uma linha. Além disso, compliquei a tarefa adicionando um pequeno motivo ao randomizador: ocupar a linha, se possível, ou defender. No entanto, neste caso, a IA encontrou as fraquezas do bot e começou a vencê-lo. Talvez a história sobre isso seja um tópico para um artigo separado.

O filho me pediu para escrever um programa para que as IAs brincassem entre si, e não com o bot. Havia idéias para fazer o mesmo para jogar damas ou ir, no entanto, para isso eu já não tinha tempo suficiente.

O único método que usei para obter novos indivíduos foi uma mutação. Você também pode usar crossover e inversão. Talvez esses métodos acelerem a obtenção do resultado desejado.

No final, nasceu a idéia: dar à IA a capacidade de gerenciar todos os processos em um PC e lutar por recursos do computador. Conecte um PC à Internet e use o pool de fazendas antigas de bitcoin como poder de computação ...

Como dito, conduzindo um experimento semelhante, o blogueiro Mikhail Tsarkov :

Talvez eles dominem o mundo, mas e se?

Cultivo da inteligência artificial como exemplo de um jogo simples