“Dormammu, cheguei a um acordo”: um algoritmo para cooperação mutuamente benéfica com uma pessoa

Reflexões sobre o tema da inteligência artificial têm visitado a mente de grandes pessoas há muitos séculos. Com o passar do tempo e o desenvolvimento da tecnologia, pensamentos se transformaram em implementação, teorias em prática e ficção científica no futuro real da humanidade. A principal essência da IA ​​é ajudar as pessoas. Em outras palavras, as máquinas inteligentes devem servir uma pessoa em plena medida, sem violar as leis básicas da robótica, que foram expressas pelo notório Isaac Asimov. Mas essa interação, se você a considerar realista, tem apenas um vetor: a pessoa disse - a IA foi executada. Ou seja, o trabalho da inteligência artificial visa o benefício apenas do homem. Mas e se a AI pensar em consonância com o bem dos dois lados da interação? Como ensinar um carro a comprometer, negociar e até negociar com uma pessoa? Bem, é precisamente a essas perguntas que o estudo de hoje dá respostas, nas quais um algoritmo foi criado que permite que a máquina chegue a um acordo mutuamente benéfico com uma pessoa. Vamos dar uma olhada mais de perto nessas questões. Vamos lá

Ideia de pesquisa

Os pesquisadores observaram que desde que Turing começou a falar sobre inteligência artificial, o homem tenta criar uma máquina que possa superá-la em algo. De uma forma ou de outra, todos conhecemos numerosos concursos, competições e experimentos quando uma pessoa compete com uma máquina (xadrez, pôquer e até artes marciais). No entanto, até agora extremamente pouca atenção foi dada a um tipo diferente de interação entre homem e máquina. Afinal, nem sempre na vida é apenas vitória ou derrota. Às vezes, o próprio consenso é necessário quando as necessidades e / ou desejos de duas partes são satisfeitas.

Considerar o trabalho da IA ​​exclusivamente a partir da posição de "sim ou não" está errado, porque sempre existe uma opção "provavelmente".

Os cientistas conseguiram criar um algoritmo que pode avaliar a situação, pesar os prós e contras, priorizar e alcançar um compromisso. Para verificar o funcionamento do algoritmo, foram utilizados jogos estocásticos * repetidos.

Um jogo estocástico * é um jogo repetido com um ou mais jogadores, quando seu estado muda constantemente em uma ordem aleatória.

Criar um algoritmo que possa funcionar em condições "flutuantes" não é uma tarefa fácil. Para funcionar com eficiência, o algoritmo deve ter alguns recursos. Mais sobre eles em mais detalhes.

Em primeiro lugar, o algoritmo não deve ser orientado ao assunto, ou seja, deve funcionar em um número ilimitado de cenários (neste caso, o jogo). Esse recurso é chamado pelos cientistas de "universalidade".

Em segundo lugar, o algoritmo deve aprender a construir relacionamentos bem-sucedidos com qualquer pessoa / algoritmo sem antes se familiarizar com seu comportamento. Isso é "flexibilidade". Para conseguir isso, o algoritmo deve levar em consideração que quase sempre seu parceiro-oponente adere ao comportamento operacional, ou seja, deseja usar o algoritmo exclusivamente para seu próprio benefício. Como resultado, ele deve determinar quando e como atrair para a cooperação aquele que provavelmente não pretende cooperar.

E finalmente, em terceiro lugar, o algoritmo deve agir rapidamente, principalmente quando se brinca com uma pessoa. Esse recurso é chamado de "velocidade de aprendizado".

Em palavras, tudo é muito bonito, claro e simples. Mas, de fato, a conquista de tais características está repleta de dificuldades. Sem mencionar o fato de que a capacidade de se adaptar ao oponente pode ser complicada pelo fato de o próprio oponente saber como se adaptar. Isso é um problema, porque dois algoritmos adaptativos, apesar de todas as suas tentativas de adaptação um ao outro, não conseguem chegar a um compromisso.

Os cientistas também observam que durante a interação entre duas pessoas, uma das ferramentas importantes para alcançar resultados mutuamente benéficos são coisas difíceis de associar a uma máquina, como intuição, emoções, instintos e muito mais. Está provado que "conversa fiada" acompanha fortemente um resultado mutuamente benéfico.

Conversa fiada * - na teoria dos jogos, é uma interação entre jogadores que não afeta diretamente o resultado do jogo. Em outras palavras, "conversa fora do tópico".

Os pesquisadores decidiram implementar isso em seu algoritmo, o que o ajuda a lidar melhor com os cálculos de situações complexas e a desenvolver uma idéia comum da situação com uma pessoa. Embora até agora não esteja claro como o algoritmo implementará essas “habilidades” em conjunto com suas principais características (flexibilidade, universalidade, velocidade de aprendizado).

O principal objetivo do estudo é estudar o maior número possível de algoritmos, desenvolver um algoritmo baseado em aprendizado de máquina com um mecanismo para responder a sinais e gerá-los em um nível compreensível para os seres humanos, e realizar muitos jogos experimentais para demonstrar a capacidade de aprendizagem do algoritmo e sua capacidade de se adaptar a diferentes oponentes (pessoas ou outros algoritmos).

A condução e os resultados do estudo

Algoritmos de comportamento estratégico em jogos repetidos estão presentes em muitos aspectos da sociedade: economia, biologia evolutiva, IA, etc. No momento, muitos desses algoritmos foram criados, cada um com seu próprio conjunto de vantagens. Naturalmente, os cientistas decidiram usá-los para desenvolver seu algoritmo. Assim, foram selecionados 25 algoritmos.

Seis indicadores de desempenho foram identificados com base em três opções de jogo: 100, 1000 e 50.000 rodadas.

Indicadores de desempenho:

• o valor médio de Round-Robin * ;
• melhor resultado de pontuação;
• pior resultado da pontuação;
• dinâmica do replicador * ;
• torneio do grupo 1;
• torneio do grupo 2.

Round-Robin * - um tipo de interação no jogo, quando durante a rodada cada um dos participantes joga alternadamente com todos os outros participantes.

A equação do replicador * é uma dinâmica de jogo não linear monótona determinística usada na teoria evolutiva dos jogos.

O primeiro indicador (o valor médio de Round-Robin) nos permite entender o quão bem o algoritmo é capaz de estabelecer relacionamentos benéficos com uma variedade de parceiros de jogos.

O segundo indicador (a melhor pontuação) é o número de algoritmos parceiros no jogo com os quais o algoritmo investigado obteve o maior número de pontos. É expresso como uma porcentagem. Este indicador reflete com que frequência o algoritmo será uma escolha bem-vinda, dadas as informações sobre o algoritmo do parceiro do jogo.

O terceiro indicador (o pior resultado por pontos) é uma avaliação da capacidade do algoritmo de vincular suas perdas (erros, erros).

Os três indicadores restantes visam determinar a estabilidade do algoritmo para diferentes grupos populacionais.

Por exemplo, um torneio (grupo 1) é uma série de jogos em que os algoritmos são divididos em 4 grupos. Líderes de cada grupo avançam para as finais, onde o único vencedor é determinado. Mas no torneio do grupo 2, dois melhores algoritmos são selecionados de cada grupo, que vão para as semifinais e os vencedores vão para a final, onde o único melhor algoritmo é determinado.

Segundo os cientistas, nenhum dos algoritmos selecionados (25 peças) participou anteriormente de uma verificação em larga escala (muitos parceiros e indicadores medidos). Essa verificação mostra quão bem cada um dos algoritmos funciona em um jogo normal com 2 participantes e não é "programado" para um cenário específico.


Tabela 1: Resultados experimentais envolvendo 25 algoritmos de comportamento estratégico diferentes.

Os resultados obtidos são apenas uma ferramenta que permite entender melhor os prós e contras de um algoritmo específico. Por exemplo, os algoritmos gTFT, WSLS, Mem-1 e Mem-2 mostraram excelentes resultados no "dilema do prisioneiro" * .

O dilema do prisioneiro * - na teoria dos jogos, um estado em que os jogadores nem sempre estão prontos para cooperar, mesmo que isso lhes seja benéfico. Nesse caso, o jogador (“prisioneiro”) tem seus próprios interesses em prioridade e não pensa nos benefícios dos outros.

No entanto, esses mesmos algoritmos mostraram resultados ruins em todos os jogos 2x2, o que indica sua ineficiência em interações mais longas. Portanto, eles não podem se adaptar ao comportamento de um parceiro (outro jogador).

Uma observação engraçada foi o fato de que os algoritmos Exp3, GIGA-WoLF e WMA, que são a base dos algoritmos do World Poker Championship, também apresentaram um resultado ruim. O que é bastante óbvio, porque o algoritmo do poker não deve cooperar com outros jogadores, mas superá-los e derrotá-los.

Se considerarmos todos os indicadores como um todo, então um algoritmo se destaca - S ++, que se mostrou perfeitamente em todos os tipos de jogos com todas as combinações possíveis marcadas. Além disso, vale ressaltar que, para a maioria dos algoritmos, o desenvolvimento do comportamento de cooperação ocorreu somente após milhares de rodadas. Para o S ++, esse processo levou apenas algumas rodadas, o que o torna uma ótima opção, dada a importância desse indicador em um jogo que envolve não um algoritmo, mas uma pessoa viva. Quanto mais rápido o algoritmo testado "perceber" a necessidade e a rentabilidade da cooperação e do compromisso, mais fácil e rápido será capaz de alcançá-lo.


Os resultados do experimento "S ++ contra seres humanos".

A interação do S ++ com outros algoritmos mostrou um bom resultado, portanto, foi necessário verificar como o S ++ se comportará no trabalho com pessoas vivas.

O experimento (4 jogos repetidos de 50 ou mais rodadas) envolveu algoritmos S ++ e MBRL-1, além de um grupo de pessoas. Os resultados desta experiência são visíveis nos gráficos acima. Vemos que o estabelecimento da cooperação S ++ com sua cópia é excelente, mas esse processo não é consistente com as pessoas. Além disso, o S ++ conseguiu alcançar cooperação de longo prazo com uma pessoa em apenas <30% das rodadas. Não é o resultado mais encorajador, mas as pessoas que brincam com as pessoas também não conseguiram estabelecer uma cooperação a longo prazo.

Embora o S ++ tenha se destacado entre outros algoritmos, isso não permitiu que ele se tornasse um vencedor claro neste estudo. Nenhum dos 25 algoritmos conseguiu demonstrar a capacidade de criar laços cooperativos de longo prazo com um jogador humano.

S #: cooperativa humana e algoritmo

Como mencionado anteriormente, um aspecto como "ligações baratas" desempenha um papel importante na obtenção de cooperação a longo prazo entre as partes; no entanto, essa técnica não foi implementada anteriormente em nenhum dos jogos acima. Portanto, os cientistas decidiram criar sua própria versão, o que permitirá que os jogadores usem essa técnica, mas de maneira limitada - 1 mensagem no início de cada rodada.

Para uma pessoa, essas conversas são naturais. No entanto, para uma máquina que visa solucionar um problema e fará isso, o que é lógico, essas formas de interação são estranhas. A idéia de introduzir esse comportamento leva diretamente os cientistas a um conceito como "IA explicável" ("IA explicável"), quando as ações da máquina são facilmente compreendidas pelos seres humanos. O problema é que a maioria dos algoritmos baseados em aprendizado de máquina tem uma representação interna de baixo nível, difícil de expressar em um nível compreensível para os seres humanos.

Felizmente, a estrutura interna do S ++ possui um nível muito alto, o que permite que ele seja usado como base para a implementação da técnica de "conversa barata". O S ++ introduziu uma estrutura de comunicação que permite gerar e responder a "chamadas baratas".


Uma nova forma do algoritmo S ++ foi chamada S #.

A imagem (a) mostra o esquema do algoritmo e (b ) mostra o esquema de interação com um parceiro no jogo usando a técnica de “conversa fiada”. Também em b, podemos nos familiarizar com as frases que o algoritmo S # pode gerar e que tipo de resposta ele espera para uma frase específica.

Assim, o S # é capaz de responder aos “sinais” (frases e ações) do jogador parceiro, o que lhe permite decidir quais táticas serão aplicadas a seguir. Juntamente com um alto grau de autoaprendizagem do algoritmo S ++ original, o algoritmo resultante pode criar relacionamentos mutuamente benéficos a longo prazo com um jogador, pessoa ou outro algoritmo.

Para verificar esta afirmação, os cientistas organizaram um experimento com 220 pessoas. Um total de 472 jogos repetidos foram jogados. A técnica de "conversa fiada" também foi incluída no experimento, mas nem sempre. E as identidades dos jogadores estavam ocultas, então ninguém (nem o algoritmo nem as pessoas) sabia com quem eles estavam jogando.


Os resultados do experimento envolvendo 220 pessoas.

Quando a “conversa barata” não foi incluída no processo do jogo, a interação homem-pessoa ou pessoa-S # não levou à cooperação a longo prazo. Quando essa técnica foi incluída no jogo, os indicadores de cooperação dobraram.



O gráfico (a) mostra que tipo de frases foram usadas durante o jogo de uma pessoa e o algoritmo S # (ódio, ameaça, controle, elogios ou planejamento).

Após o experimento, todos os participantes foram convidados a avaliar o grau de inteligência de seus parceiros no jogo, quão claras eram suas intenções e a utilidade de interagir com eles. Resultados da pesquisa no gráfico (b) . Ainda mais divertido é o (s) horário (s) . Mostra a porcentagem do número de vezes que uma pessoa ou algoritmo considerou seu parceiro no jogo humano. Como você pode ver, a maioria dos participantes humanos sentiu que S # é uma pessoa.

Os cientistas também observam que os resultados do S # são ainda melhores quando comparados com a forma como os pares pessoa-pessoa e S # -S # interagem. O grau de ocorrência de relações cooperativas de longo prazo entre uma pessoa e S # é aproximadamente no mesmo nível de um par pessoa-pessoa. E o par S # -S # sem o uso da técnica de “conversa fiada” tem um resultado muito melhor do que o par pessoa-pessoa, que teve a oportunidade de usá-lo.

Resumindo todas as opções acima, o algoritmo S # mostrou resultados que podem ser comparados aos resultados da interação entre pessoas.

Jogos estocásticos recorrentes

Jogos de tipo normal tornaram possível entender que o algoritmo S # é um vetor promissor de pesquisa. No entanto, esses jogos são limitados, são mais abstratos. Portanto, os cientistas decidiram usar um jogo estocástico repetitivo no qual os participantes devem separar blocos de diferentes formas e cores. Para o algoritmo S #, foram adicionadas as frases "Vamos colaborar" e "Eu recebo mais pontos". Além disso, o S # era limitado no uso da técnica de "conversa fiada" - ele podia usar frases, mas não conseguia responder às frases de um jogador humano.


O esquema do jogo com blocos multicoloridos (quadrado, círculo e triângulo).

A essência do jogo é a seguinte. Cada jogador tem um conjunto de 9 blocos (diferentes, é claro). A cada turno, o jogador remove 1 bloco do seu set até ter apenas 3. Esses três blocos devem atender aos requisitos (a mesma forma / cor ou forma e cor diferentes ao mesmo tempo). Cada bloco custa uma certa quantidade de pontos (pontos). Se o bloco não for adequado, esse número se tornará negativo. O diagrama acima mostra 5 opções para o resultado do jogo.


O uso e o não uso de "chamadas baratas".

Ao jogar entre pessoas, o uso de "conversa fiada" não afetou muito o resultado. No entanto, essa técnica aumentou muito o resultado do algoritmo S # em um jogo com uma pessoa.

Diferenças de S # de outros algoritmos

O algoritmo S # superou todos os outros assuntos, mas por quê? Quais propriedades desse algoritmo o distinguiram de vários concorrentes? Os cientistas contam até três.

Em primeiro lugar, é a capacidade de gerar e responder a sinais apropriados (frases e ações) que podem ser entendidos pelos seres humanos. Isso torna esse algoritmo muito flexível, capaz de evoluir dependendo da situação. E, é claro, permite que você crie laços mutuamente benéficos a longo prazo com outros jogadores.

Em segundo lugar, o S # usa um conjunto diversificado de estratégias, o que permite que você se adapte a diferentes jogadores parceiros e a diferentes tipos de jogos. Ao mesmo tempo, algoritmos projetados para funcionar eficientemente em apenas um cenário específico não podem funcionar efetivamente fora de sua “zona de conforto”.

Em terceiro lugar, o algoritmo S # mantém um estado de benefício mútuo, enquanto outros, tendo recebido o que desejam, mudam para uma estratégia diferente.


Gráficos da duração do estado de cooperação mutuamente benéfica.

Como pode ser visto no gráfico acima (a) , o S # estabelece uma conexão mutuamente benéfica com o player mais cedo do que outros algoritmos. Ele também mantém um estado de cooperação mutuamente benéfica com um número significativamente maior de rodadas que os algoritmos concorrentes (gráfico (b) ).

A flexibilidade do S # é claramente visível no gráfico (c) , onde vemos que ele atinge a meta com mais frequência do que outros, independentemente do tipo de jogo ou parceiro.

Bastante incomum é a afirmação dos cientistas de que seu algoritmo S # aprendeu fidelidade. O fato é que, tendo estabelecido a cooperação no par S # -S #, o algoritmo não tem pressa em quebrá-lo, mesmo quando não há muito benefício nisso. Ao mesmo tempo, em casais homem-a-homem, a cooperação freqüentemente se interrompeu imediatamente após a obtenção dos benefícios de curto prazo necessários. Esse comportamento naturalmente levou a maus resultados no final do jogo para os dois lados.

Aqueles que desejam se familiarizar com o relatório dos cientistas podem encontrá-lo aqui .

Materiais de pesquisa adicionais estão disponíveis aqui .

Epílogo

Este estudo é muito diferente dos outros, pois não visa criar uma IA capaz de derrotar uma pessoa em algo, mas criar uma AI capaz e disposta a alcançar consenso. Isso significa que as máquinas inteligentes se tornarão mais humanas graças a esse algoritmo? Possivelmente. , , , , .

, S# «». , . , .

Obrigado por ficar conosco. Você gosta dos nossos artigos? Deseja ver materiais mais interessantes? Ajude-nos fazendo um pedido ou recomendando a seus amigos, um desconto de 30% para os usuários da Habr em um análogo exclusivo de servidores básicos que inventamos para você: Toda a verdade sobre o VPS (KVM) E5-2650 v4 (6 núcleos) 10GB DDR4 240GB SSD 1Gbps de US $ 20 ou como dividir o servidor? (as opções estão disponíveis com RAID1 e RAID10, até 24 núcleos e até 40GB 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 vezes mais barato? Somente nós temos 2 TVs Intel Dodeca-Core Xeon E5-2650v4 128GB DDR4 6x480GB SSD 1Gbps 100 a partir de US $ 249 na Holanda e nos EUA! Leia sobre Como criar um prédio de infraestrutura. classe usando servidores Dell R730xd E5-2650 v4 custando 9.000 euros por um centavo?