Desenvolvimento de IA usando o exemplo do jogo Dicey Dungeons

Por cerca de um mês, eu estava resolvendo um dos problemas técnicos mais difíceis do meu novo jogo, o Dicey Dungeons - uma IA aprimorada para o lançamento final do jogo. Foi um trabalho bastante interessante, e grande parte dele era novo para mim, então decidi escrever um pouco sobre isso.

Para começar, explicarei: não sou especialista em teoria dos computadores, mas apenas um daqueles que estudaram programação o suficiente para criar videogames, após o qual me formei em treinamento, pegando apenas o que precisava. Normalmente, posso resolver meus problemas por conta própria, mas um programador real provavelmente não aprovaria minhas decisões.

Tentei escrever um artigo com um nível de abstração alto o suficiente para que as idéias básicas fossem claras, mesmo para não programadores. Mas eu não sou especialista em tais coisas, portanto minhas explicações da teoria podem estar erradas. Escreva-me sobre isso nos comentários ao original, terei prazer em fazer alterações!

Bem, vamos começar explicando a tarefa!

Desafio

Caso você não tenha jogado Dicey Dungeons, falarei brevemente sobre o jogo: este é um RPG com construção de baralho, no qual cada inimigo tem um conjunto de mapas de armas que executam várias ações. Além disso, eles jogam dados! Então eles colocam esses dados em armamento para causar dano, ou criar vários efeitos de status, ou curar, ou se defender de danos e coisas do gênero. Aqui está um exemplo simples de como um sapinho usa uma espada grande e um escudo pequeno:


Um exemplo mais complexo: esse Valete de todos os comércios tem uma chave inglesa, que permite que você coloque dois dados juntos (ou seja, 3 + 2 dará 5 e 4 + 5 dará 6 e 3). Ele também tem um martelo (Hammer), que impõe um efeito de "choque" ao jogador, se você aplicar seis a ele, e um atirador de ervilhas (Pea Shooter), que causa pouco dano, mas tem uma "contagem regressiva". lá é válido para vários movimentos.


Outra complicação importante: o jogo tem efeitos de status que alteram as capacidades dos oponentes. O mais importante deles é o Shock, que desativa aleatoriamente as armas; o choque pode ser removido usando um cubo adicional e "Burn", que atira fogo nos cubos. Enquanto os cubos estão queimando, eles podem ser usados, mas cada uso custará 2 pontos de vida. É isso que um faz-tudo inteligente faz quando choca e queima todas as suas armas e cubos:


Claro, há muito mais no jogo, mas para se ter uma idéia geral, isso é suficiente.

Então, nossa tarefa: como fazer com que a IA escolha a melhor ação para sua jogada? Como ele pode descobrir qual dos cubos ardentes deve ser lançado, qual cubo usar para aliviar o choque e qual guardar para armas importantes?

Como ele fez antes

Por um longo tempo, a IA nas Dicey Dungeons tinha apenas uma regra: ele olhou para todas as armas da esquerda para a direita, determinou o melhor cubo que poderia ser usado nele e depois a usou. Isso funcionou muito bem, mas havia exceções. Então eu adicionei novas regras.

Por exemplo, lidei com um choque olhando todas as armas que não estavam sujeitas a choques e escolhendo quais dados eu usaria quando o choque fosse removido e, então, marquei esses dados como "reservados" para o futuro. Trabalhei com cubos em chamas assim: verifiquei se tinha saúde suficiente para apagá-los e escolhi aleatoriamente se deveria fazer isso.

Adicionei regra por regra para tudo o que eu poderia imaginar e, como resultado, recebi uma IA que parecia funcionar! De fato, é incrível o quão bem esse entrelaçamento de regras diferentes se mostrou - a IA nas Dicey Dungeons nem sempre pode tomar a decisão certa, mas sempre foi pelo menos aceitável. Pelo menos para um jogo ainda em desenvolvimento.

Mas, com o tempo, o sistema de adicionar constantemente novas regras começou a quebrar nas costuras. As pessoas descobriram façanhas que fizeram a IA se comportar estupidamente. Por exemplo, com a abordagem correta, você pode superar um dos chefes para que ele nunca ataque o jogador. Quanto mais regras adicionei para corrigir a situação, mais coisas estranhas começaram a acontecer - algumas regras entraram em conflito com outras, casos de fronteira começaram a aparecer.

Obviamente, uma das soluções era adicionar novas regras, considerar cada tarefa uma por uma e criar novas construções if para processá-las. Mas acho que dessa maneira simplesmente deixei de lado a verdadeira solução para o problema. A limitação do sistema era que ele preocupava apenas uma pergunta: "Qual será o meu próximo passo?" Ela nunca olhou para frente e não tentou sugerir o que poderia resultar de uma combinação inteligente específica.

Então eu decidi começar de novo.

Solução clássica

Tente procurar informações sobre IA para jogos e, provavelmente, a primeira coisa que você encontrará em uma solução clássica - criando um algoritmo minimax . Aqui está um vídeo sobre como é usado no desenvolvimento de IA para xadrez:


A implementação do minimax é a seguinte:

Primeiro, criamos a versão mais simples e abstrata do nosso jogo, na qual há todas as informações necessárias para um momento específico do jogo. Vamos chamar de quadro . No caso do xadrez, essas são as posições atuais de todas as peças. No caso de Dicey Dungeons, esta é uma lista de dados, armas e efeitos de status.

Em seguida, criamos uma função de valor que mede o desempenho do jogo para uma configuração específica do jogo, ou seja, para um tabuleiro específico. Por exemplo, no xadrez, um tabuleiro no qual as peças estão localizadas em suas posições originais é avaliado em 0 pontos. O tabuleiro no qual você comeu o peão do seu oponente tem um valor de 1 ponto, e o tabuleiro no qual você perdeu o seu próprio peão tem um valor de -1 pontos. E o tabuleiro no qual colocamos o oponente em xeque será avaliado em um número infinito de pontos, ou algo assim!

Então, neste quadro abstrato, simulamos todos os movimentos possíveis que podemos fazer, o que nos dá novos quadros abstratos. Em seguida, simulamos a conclusão de todos os movimentos possíveis nessas placas, e assim por diante, quantas etapas você desejar. Aqui está uma excelente ilustração de uma solução semelhante do freecodecamp.org :


Criamos um gráfico de todos os movimentos possíveis que ambos os jogadores podem fazer e aplicamos uma função de valor para avaliar o andamento do jogo.


E nisso, o Dicey Dungeons difere do minimax: o minimax veio da teoria matemática dos jogos, é projetado para encontrar a melhor série de movimentos do mundo em que o oponente procura maximizar sua pontuação. O algoritmo é chamado assim porque minimiza as perdas do jogador quando o oponente joga para maximizar seus ganhos.

Mas o que acontece nas Masmorras Dicey? Na verdade, eu não ligo para o que meu oponente faz. Para que o jogo seja emocionante, basta que a inteligência artificial faça movimentos lógicos - para determinar a melhor maneira de aplicar os dados às armas, para que a batalha seja justa. Em outras palavras, apenas "max" é importante para mim, sem "mini".

Ou seja, para que as AI Dicey Dungeons façam uma boa jogada, é suficiente para eu criar esse gráfico de movimentos possíveis e encontrar o tabuleiro com a maior pontuação e depois fazer os movimentos que levam a esse ponto.

A jogada fácil do inimigo

Bem, vamos aos exemplos! Vamos olhar para o sapo novamente. Como ela pode decidir o que fazer a seguir? Como ela sabe que a ação escolhida é a melhor?


Na verdade, ela tem apenas duas opções. Coloque 1 na espada larga e 3 no escudo, ou faça o oposto. Ela obviamente decide que é melhor colocar 3 em vez de 1. Mas por quê? Porque ela estudou todos os resultados possíveis:


Se você colocar 1 na espada, obteremos 438 pontos. Se você colocar 3, obtemos 558 pontos. Ótimo! Então, eu ganho mais pontos colocando a espada 3, o problema está resolvido.

De onde vêm esses óculos? Atualmente, o sistema de avaliação em Dicey Dungeons leva em consideração os seguintes aspectos:

• Dano: O fator mais importante é 100 pontos para cada ponto de dano causado.
• Veneno: Um importante efeito de status que a IA considera quase tão importante quanto o dano - 90 para cada veneno.
• Criando outros efeitos de status: por exemplo, choque, queima, enfraquecimento etc. Cada um deles custa 50 pontos.
• Efeitos de status de bônus: adicionar ao próprio jogador efeitos positivos de status, como defesa e similares, custa 40 pontos cada.
• Uso de armas: o uso de qualquer tipo de arma custa 10 pontos, porque se nada mais der certo, a IA precisa apenas tentar usar tudo.
• Redução da contagem regressiva: para ativar alguns tipos de armas (por exemplo, para o Pea Shooter), o valor total dos dados é suficiente. Portanto, a IA recebe 10 pontos para cada ponto de contagem regressiva que reduz.
• Pontos nos Dados: A IA recebe 5 pontos por cada ponto não utilizado nos dados, ou seja, 1 custa 5 pontos e 6 custa 30 pontos. Isso é feito para que a IA prefira não usar cubos que você não precisa, para que seus movimentos se tornem muito semelhantes aos humanos.
• Duração: A IA perde 1 ponto por turno, portanto, movimentos longos têm um valor ligeiramente menor que os curtos. Isso é feito para que, na presença de dois movimentos que tenham valor igual, a AI escolha o menor.
• Tratamento: custa apenas 1 ponto para um ponto de saúde restaurado, porque, embora eu queira que a IA considere isso importante, eu realmente não monitorei minha saúde. Sempre há coisas para fazer e mais importante!
• Pontos de bônus: eles podem ser adicionados a qualquer movimento para forçar a IA a fazer algo que ele nunca faria de outra maneira. Usado muito moderadamente.

E, finalmente, existem dois casos especiais - se o alvo atacado ficar sem saúde, custará um milhão de pontos. Se a saúde termina com a IA, custa menos um milhão de pontos. Isso significa que a IA nunca se matará acidentalmente (por exemplo, pagando um dado com muito pouca vida) ou nunca perca um movimento em que possa matar um jogador.

Esses números não são ideais - considere, por exemplo, as questões em aberto atuais: 640 , 642 , 649 , mas isso não é muito importante. Mesmo números aproximadamente precisos são suficientes para estimular a IA a fazer mais ou menos corretamente.

Movimentos mais difíceis do inimigo

O caso do sapo é tão simples que até meu código terrível pode descobrir todas as opções em apenas 0,017 segundos. Mas então a situação se torna mais complicada. Vejamos novamente o exemplo de Jack of All Trades.


Sua árvore de decisão é "um pouco" mais complicada:


Infelizmente, mesmo em casos relativamente simples, uma explosão de complexidade ocorre rapidamente. Nesse caso, em nosso gráfico, temos 2.670 nós que precisam ser examinados, e isso leva muito mais tempo do que no caso de um sapo - talvez um ou dois segundos.

Isso se deve em grande parte à complexidade combinatória - por exemplo, não importa qual dos dois usamos inicialmente para aliviar o choque, o algoritmo considera isso como duas soluções separadas e cria uma árvore completa de soluções de ramificação para cada uma. Como resultado, obtemos um ramo cuja duplicação é completamente desnecessária. Também existem problemas combinatórios semelhantes ao escolher blocos para resgate, para remover choques de armas e o procedimento para seu uso.

Mas, mesmo que encontremos e otimizemos esses ramos desnecessários (o que eu faço até certo ponto), sempre haverá um ponto em que a complexidade de todas as permutações possíveis de soluções leva a enormes e lentas árvores de decisão, cuja avaliação levará um tempo infinito. Portanto, este é o primeiro problema sério dessa abordagem. Aqui está outro:


Chave mestra. Divide o cubo em dois.

Esse tipo importante de armamento (e similares) causa problemas de IA porque o resultado de seu uso é incerto . Se eu colocar um seis, posso obter cinco e um, ou quatro e dois, ou talvez dois triplos. Eu não sei disso até saber, por isso é muito difícil criar um plano que leve isso em consideração.

Felizmente, Dicey Dungeons tem uma ótima solução para esses dois problemas!

Solução moderna

O método Monte Carlo Tree Search (MCTS) é um algoritmo probabilístico de tomada de decisão. Abaixo está um vídeo um pouco estranho, que, no entanto, explica muito bem o princípio da tomada de decisão com base no método de Monte Carlo:


De fato, em vez de adicionar todos os movimentos possíveis ao gráfico, o MCTS verifica as seqüências de movimentos aleatórios e depois rastreia aqueles que se mostraram melhores. Graças a uma fórmula chamada Upper Confidence Bound, ele pode determinar magicamente quais ramos da árvore de decisão são os "mais promissores":


A propósito, peguei essa fórmula em um artigo muito útil sobre a pesquisa de árvores usando o método Monte Carlo . Não me pergunte como funciona!

O incrível do MCTS é que, para encontrar a melhor solução, geralmente não precisamos fazer uma pesquisa idiota de tudo, e podemos usar o mesmo sistema de simulação de quadro / movimento abstrato do minimax. Ou seja, usamos os dois algoritmos. Esse é exatamente o esquema que usei nas Dicey Dungeons. Primeiro, ela tenta concluir uma implantação completa da árvore de decisão, que geralmente não leva muito tempo e leva ao melhor resultado. Mas se a árvore parecer muito grande, estamos voltando ao uso do MCTS.

O MCTS tem dois recursos muito legais que são perfeitos para os Dicey Dungeons:

Primeiro, o método funciona idealmente com incerteza. Como ele é executado repetidamente, coletando dados de cada execução, eu apenas permiti que ele simule movimentos indefinidos, por exemplo, usando uma chave mestra, de maneira natural, e depois de muitas execuções, o método cria um intervalo bastante correto de pontos obtidos como resultado dessa movimentação.

Em segundo lugar, ele pode me dar uma solução parcial. De fato, ao trabalhar com o MCTS, você pode executar quantas simulações desejar. Teoricamente, se for executado indefinidamente, convergirá para exatamente os mesmos resultados que o minimax. No entanto, o mais importante para mim é que posso usar o MCTS para obter uma boa solução em um período limitado de tempo. Quanto mais pesquisas fizermos, melhor será a "solução", mas no caso de Dicey Dungeons, muitas vezes apenas algumas centenas de pesquisas são suficientes, o que leva uma pequena fração de segundo.

Tópicos relacionados interessantes

Então, é assim que os inimigos nas Dicey Dungeons decidem como matá-lo! Quero adicionar este sistema à próxima versão do jogo v0.15!

De onde vieram os gráficos que mostrei, inclusive no twitter:


Eu os criei escrevendo um exportador para o GraphML , um formato de arquivo gráfico de código aberto que pode ser lido por muitas ferramentas diferentes. (Eu usei o excelente ano , que eu recomendo.)

Parte da solução para esse problema foi permitir que a IA simulasse movimentos, o que por si só é um quebra-cabeça interessante. Como resultado, implementei um sistema de script de ação. Agora que os oponentes estão usando diferentes tipos de armas. eles executam esses pequenos scripts:


Esses pequenos scripts são executados pelo analisador hscript e pelo interpretador de expressões com base no haxe. Essa parte foi difícil de implementar, mas o esforço valeu a pena: tornou o jogo super conveniente para a criação de mods. Espero que, após o lançamento do jogo, as pessoas possam usar esse sistema para desenvolver suas próprias armas, ou seja, possam adicionar ao jogo quase tudo o que possam imaginar. Além disso, como a IA é inteligente o suficiente para avaliar qualquer ação transferida para ela, os inimigos poderão descobrir como usar as armas modificadas que os jogadores criarão!