Uma série de artigos sobre como escrever IA para um jogo online multiplayer do gênero roguelike.
Parte 1
Parte 3
Nesta parte do artigo, consideraremos abordagens para a criação de lógica para a IA, falaremos um pouco sobre o estabelecimento de metas de cada bot cumpridor da lei e também determinaremos a escolha de uma linguagem de programação e escreveremos algum código.
Vindinium Game World
Para criar AI, você precisa entender a estrutura do mundo do jogo.
Tradução gratuita da documentação do jogoDescrição do produto
Vindinium é um bagel multijogador baseado em turnos. Cada um dos quatro jogadores tem um herói que pode se mover pelo mapa. O objetivo é que os jogadores colecionem a quantidade máxima de ouro em um determinado número de jogadas (cada jogador faz 300 jogadas por jogo, de modo que o jogo inteiro consiste em 1200 jogadas). Os jogadores devem assumir o controle das minas de ouro para produzir ouro; no entanto, as minas são protegidas por duendes. Quando um jogador derrota um duende, ele se torna o dono da mina e recebe um ouro por turno. Além disso, o goblin agora protege a mina de outros jogadores.
Heróis podem lutar entre si. Um sobrevivente em batalha ganha o controle de todas as minas de ouro de seu oponente. O herói morto renasce imediatamente com todo o seu ouro, no entanto, todas as minas passam para as mãos do assassino.
Indo para a taberna, os heróis podem comprar cerveja por 2 unidades de ouro, restaurando seus pontos de vida.
O objetivo é criar um programa de computador (bot) que jogue o jogo Vindinium o mais razoavelmente possível. É recomendável usar um dos kits iniciais para um grande número de linguagens de programação como ponto de partida.
Mapa
Os mapas são criados aleatoriamente. Cada objeto do jogo no mapa é codificado usando dois caracteres. Exemplo de mapa:
+----------------------------------------+ |######$- $-############$- $-######| |###### ## ## ######| |####[] #### #### []####| |## #### ## ## #### ##| |#### $- $- ####| |########## @1 @4 ##########| |############ #### #### ############| |$-##$- ############ $-##$-| | $- $-################$- $- | | ######################## | | ######################## | | $- $-################$- $- | |$-##$- ############ $-##$-| |############ #### #### ############| |########## @2 @3 ##########| |#### $- $- ####| |## #### ## ## #### ##| |####[] #### #### []####| |###### ## ## ######| |######$- $-############$- $-######| +----------------------------------------+
Legend
## - Floresta irresistível
@1 - O primeiro herói
[] - Tabernas
$- - Mina de Ouro (Desenhada)
$1 - Mina de Ouro (de propriedade do primeiro herói)
Os mapas gerados são simétricos e sempre contêm 4 tabernas e 4 heróis.
Hero
Os heróis podem mover uma célula para cada turno e ter os seguintes indicadores:
- Pontos de Vida (HP): Cada jogador "novo" começa com um valor máximo = 100. Se o HP cair a zero, o herói morre (veja a seção "Morte do Herói").
- Ouro: a partir do zero, este é um indicador do sucesso do herói. No final do jogo, os heróis serão avaliados com base na quantidade de ouro.
- O número de minas de ouro.
Direção da viagem
O bot deve emitir um pedido por turno. Pedidos possíveis: Stay ), North ), South ), East ) ou West ). Assim que a ordem é executada, o herói permanece em seu lugar ou move uma célula em uma determinada direção.
Movimento do herói
Se o herói:
- Tentando ir além do mapa ou atravessar árvores, nada acontece.
- Entra na mina de ouro, permanece no local e:
- Se a mina já pertence ao herói, nada acontece.
- Se a mina não é terra de ninguém ou pertence a outro herói, há uma batalha com o guarda goblin, vigiando a mina. O herói perde 20 pontos de vida. Se ele sobreviver, o meu.
- Ele pisa em outro herói, permanece no lugar e nada acontece. Lutas de heróis são decididas no final do turno.
- Ele entra na taberna, permanece no lugar e ordena que coma. O herói paga 2 de ouro e restaura 50 de vida. Observe que a quantidade de saúde não pode exceder 100 unidades.
- Ele não envia um pedido no tempo que lhe foi concedido para tomar uma decisão (1 segundo), ele permanece no local até o final do jogo, torna-se impossível enviar novos pedidos. Observe que ele ainda pode ganhar se tiver mais ouro no final do jogo do que outros jogadores.
Fim do turno
Depois que o herói se mudar (ou decidir ficar parado), as seguintes coisas acontecerão:
Batalhas
Os heróis estão um pouco nervosos e nunca perdem a oportunidade de se baterem com grandes espadas. No final do turno do herói, se houver um inimigo a uma distância de um quadrado em qualquer direção, o herói o ataca. Por exemplo, nesta situação, no final do turno do primeiro herói ( @1 ):
######## ##@1@2## ## @3## ########
O jogador 1 ataca o segundo jogador, mas não toca o terceiro, porque o terceiro está a uma distância de dois quadrados dele.
O atacante não perde unidades de saúde, o defensor perde 20 unidades.
Se o defensor morrer (veja: Morte de um herói), o atacante ganha o controle de todas as minas de ouro do perdedor.
Mineração de ouro
Após o seu turno e batalhas com outros heróis (se houver), o jogador recebe uma unidade de ouro para cada mina controlada.
Sede
Então o herói perde uma unidade de saúde, pois qualquer ação o deixa com sede.
Observe que os heróis não podem morrer de sede. Na pior das hipóteses, o valor de sua saúde cai para a unidade.
Morte do herói
Quando a saúde do herói cai para zero, ele morre. O herói aparece imediatamente no mapa em seu ponto de renascimento, com uma reserva de saúde completa (100 unidades). O herói perde o controle de todas as suas minas de ouro, mas retém todo o ouro acumulado. Tenha cuidado quando o herói retornar ao ponto de renascimento, qualquer oponente que esteja nesta célula morrerá automaticamente. Portanto, você deve evitar ficar na célula de desova de um dos heróis ...
Um herói não pode morrer de sede. A sede pode deixar um herói com uma unidade de saúde, mas não matá-lo.
O fim do jogo
O jogo termina quando o número máximo de jogadas (geralmente 300) é atingido. O vencedor é o herói com mais ouro. Se dois jogadores tiverem a mesma quantidade de ouro, não haverá vencedor.
Classificação
O sistema de classificação de força relativa do jogador usa a classificação Elo . A ideia é: é melhor ser o primeiro que o segundo, é melhor ser o segundo que o terceiro, e assim por diante. Espero que o princípio seja claro.
Usando vários bots de uma só vez
Você pode iniciar simultaneamente várias instâncias de seus bots e, em geral, usar quaisquer medidas que, na sua opinião, sejam adequadas para alcançar a liderança dominante. Luta!
Link para o original
Vale ressaltar mais alguns aspectos que não foram descritos nas regras, mas identificados empiricamente:
- Se tivermos menos de 21 unidades de saúde, mas você atacar uma mina que não lhe pertence, você morre. Sim, sim, não há proteção contra o tolo, tudo é sério aqui, como em batalhas reais. Se você atacar a mina de ninguém, todas as suas minas se tornam terras de ninguém, e se você atacar um de seus inimigos, suas minas passam para as mãos do jogador que é dono dessa mina.
- O jogo descreve o seguinte procedimento:
1 . E o que acontece se morrermos durante a execução da ordem (no jogo você pode fazer isso apenas morrendo na batalha com o goblin)? Nós renascemos (e instantaneamente matamos o jogador que está agora em nosso ponto de desova), mas perdemos a capacidade de atingir inimigos próximos e também não perdemos 1 pontos de vida devido à sede. - Tendo matado o inimigo que estava em nosso ponto de desova durante nosso renascimento, capturamos suas minas, hehe.
- O mapa tem uma aparência quadrada, o comprimento do mapa leva valores pares no segmento [8, 28].
"Aprenda com seus inimigos e você entenderá os pontos fortes deles"
Vindinium é um jogo público, seu lado útil é que podemos olhar para o perfil de qualquer jogador e ver as últimas cem lutas com sua participação. "Excelente! É hora de usar redes neurais, porque temos 50 jogadores de ponta, vamos pegar os 10 melhores, cada uma das últimas 100 lutas contém ~ 300 momentos em que o jogador teve que tomar uma decisão, totalizando entre 200 e 300 mil unidades material para treinamento! E você pode girar cada situação no sentido horário, espelho, etc., para obter ainda mais material para treinamento e consolidar o resultado, isso nos dará de 4,8 a 7,2 milhões de unidades de material "- a voz da razão saiu. Sim, de fato, essa ideia tem o direito de existir. Além disso, as redes neurais têm muitas vantagens.
- Todo o material de treinamento é facilmente analisado a partir de um código aberto.
- É aberto um amplo escopo para reflexão sobre a visão computacional:
- Você pode deixar tudo como está, haverá 28 * 28 neurônios de entrada (se o mapa for menor, preencha-o com árvores);
- Você pode centralizar cada vez de acordo com a posição do herói (talvez traga algum resultado surpreendente);
- Você pode apresentar o mapa na forma de um gráfico, facilitando bastante o trabalho da rede neural na localização de padrões; Essa opção permitirá que o neurônio encontre rapidamente padrões de comportamento complexo e entenda rapidamente por que, se tivermos pouca saúde, vamos a uma taberna distante, se houver apenas outra taberna em algumas células, mesmo que o inimigo esteja bem próximo a ela;
- Uma rede neural já treinada, dada a tarefa de consumir recursos antecipadamente, pode ser compactada em 512 megabytes de RAM alocados para nós (na verdade, são cerca de 480 megabytes), tanto que o poder de um computador de placa única é suficiente para cálculos.
No entanto, o maximalismo adolescente em mim quer seguir o caminho mais difícil - não colocar a busca por padrões na rede neural, mas fazer esse trabalho por conta própria, na testa, contando com a plasticidade intuitiva e mais alta dessa solução.
Então Árvores de decisão, recorte alfa beta, minimaxes ... tarefas muito exigentes! No subreddit Vindinium, vários desenvolvedores, revelando o véu dos segredos de seus bots, já usaram essa solução, e provavelmente não nessas condições espartanas. Infelizmente, nesta área, é improvável que qualquer coisa possa ser feita melhor que o resto.
Depois de ler artigos sobre algoritmos evolutivos, genéticos, resolver árvores, descobri o conhecimento secreto - campos em potencial. Você pode ler mais sobre eles aqui e aqui . Essa ideia parecia muito funcional, porque o campo potencial é um gráfico planar, uma função é colocada em cada link, que depende dos dados de entrada (em particular, a distância do objeto, mas ninguém se preocupa em criar mais condições). Tudo isso se encaixa perfeitamente na realidade do Vindinium - você não precisa procurar o caminho para o objeto, se ele já estiver no algoritmo.
"Sabores bastante específicos"
Vamos assistir as lutas dos personagens principais. Antes de começar, vamos escolher um favorito, vamos segui-lo, torcer por ele, castigar as decisões erradas no estilo de "mas eu teria agido neste lugar ...". Após uma dúzia de lutas, você já pode fazer o primeiro esboço do que é uma IA cumpridora da lei (as condições são verificadas em ordem):
- Você não deve chegar perto do ponto de desova do inimigo se ele tiver chance de morrer (ou seja, se podemos esperar uma morte inglória enquanto estiver no ponto de desova do inimigo);
- É tolice lutar contra seu inimigo perto do ponto de desova, pois ele ainda será como uma fênix clara com saúde total e tentará novamente capturar nossas minas saqueadas honestamente;
- Se o inimigo está perto de nós, e nós estamos perto da taverna - hora de ficar bêbado. A julgar pelas numerosas batalhas sangrentas perto dos meios de subsistência e relaxamento, essa regra é muito relevante;
- Se não podemos derrotar o inimigo / inimigos, mas conseguimos correr para a taverna, corremos;
- Se não podemos derrotar o inimigo / inimigos e não temos tempo para chegar à taverna, então:
- Se podemos nos matar na fazenda de ninguém, nos matamos por causa disso. Dê uma mordida!
- Se pudermos morrer sobre a placa de mina de uma pessoa com a menor quantidade de ouro, nós mesmos nos vimos;
- Se um final triste nos espera, precisamos tirar o máximo de saúde possível deste réptil, que ele se lembre do seu erro por um longo tempo!
- Se houver um inimigo que possamos matar dentro de dois de nossos movimentos e ele tiver Linhas de Mina, atacamos;
- Se existe um inimigo que está mais distante de todos os minilocks do que nós, e ele tem 33% de minilock sob controle. E podemos derrotá-lo - vamos ganhar, senão vamos beber cerveja;
- Capturamos fazendas se nada mais restar.
Perguntas e Respostas:
- Quais são as vantagens sobre as redes neurais que podem executar essa tarefa cem vezes melhor, ou sobre as árvores que todos os seus próximos n passos à frente conhecem e já desenvolveram contramedidas, tudo o que resta é usar uma boa função de avaliação?
(1) Multifuncionalidade. É mais fácil alterar parâmetros, adicionar novas funções. Você segue esse personagem, se alegra e depois bam - e vê que, em um determinado momento, poderia ter agido de maneira completamente diferente e com mais prudência - estamos escrevendo uma nova regra ou mudando a antiga. (2) Também sabemos exatamente qual decisão guiou o programa ao escolher um movimento específico. (3) Campos potenciais mostraram-se bem nos bagels como base para a inteligência artificial dos bots.
- Prove que sua abordagem é válida, que suas intenções valem alguma coisa.
Na tabela de classificação, o Zaraza 0.1 fica em 27º lugar - a IA em campos potenciais, guiada por apenas três instintos - pega sem pensar em tudo que fica no seu caminho, não se seca em bares e se comporta cuidadosamente com os inimigos. Se você seguir os movimentos dele, verá como ele luta, embora isso seja inacreditável para a IA, que é baseada em três regras simples e ele nem sonha com um comportamento complicado. Além disso, agora estou trabalhando no Zonko 0.11 , que é uma versão bastante aprimorada da bebida de Zaraz, e você pode integrar um comportamento muito mais complexo a ele devido à interação aprimorada com os campos - como em um GPS novo. Mas, como se viu, é voraz em relação aos recursos, então o processo de otimização está acontecendo agora ... Mas discordo, agora estamos falando de restrições estritas, regras estritas estritas (...).
- Suas crenças são ridículas, sua fé é muito fraca! Eu posso criar uma IA em method_name e isso vai te rasgar!
- Será muito agradável ouvir os pensamentos de outras pessoas sobre esse assunto. Além disso, para você, eu já reuni todas as lutas dos 10 melhores jogadores, apenas 1000 lutas e cerca de 1.000.000 de movimentos - link (.zip - 33MB, RAW - 1.68GB). Eu ofereço as condições do jogo:
- Registre bots com seus apelidos em tempos de geek.
- Aos cinco jogadores que marcaram mais pontos antes de 30 de setembro do que eu ou qualquer outra pessoa que tenha indicado jogar, enviarei um cartão postal de Moscou).
Então, agora a linguagem de programação ... Pessoalmente, agora estou correndo entre o Python3 (desenvolvimento rápido, fácil de ler, familiarizado com ele há muito tempo, existem pypy3 (intérprete otimizado rapidamente), jupyter ("notebooks" nos quais você pode escrever com segurança partes de código e otimizá-las para infinito); mas pypy / pypy3 não funciona no ARM de 64 bits e, de fato, o ARM não é mais suportado, e a linguagem em si é inferior aos compilados por sua natureza) e Golang (também de desenvolvimento rápido, fácil de entender, um grande viés para o back-end, multithreading e multiprocessing, roda mais rápido que python, mas com etsya para se acostumar com a ausência de um ambiente interativo para tipagem estática).
A principal função que se comunica com o servidor pode ser representada da seguinte maneira:
Mas é recomendável usar desenvolvimentos prontos para uso, cujos links podem ser encontrados no site oficial do Vindinium.
Extra 1: Eu realmente quero ler sobre o desenvolvimento da inteligência artificial baseada no Vindinium de outras pessoas, porque dessa maneira você pode entender a natureza multifacetada da solução desse problema. Para obter o resumo da batalha no formato json (isso pode ser útil para lutas de depuração), é necessário converter o link na batalha do formulário http://vindinium.org/fd96vc2z no link do formulário http://vindinium.org/events/fd96vc2z . Mas eu não aconselho atormentar o servidor do jogo, tentando obter centenas de brigas dos melhores jogadores, use o link acima.
Extra 2: se alguém quiser tentar executar o tempo de operação no Vindinium dentro das limitações do NanoPi Neo2 ou Orange Pi Zero, posso oferecer a oportunidade de trabalhar com esses computadores de placa única.
→ Link para Vindinium
→ O link para o subreddit Vindinium é uma coisa muito útil, você pode acompanhar meus movimentos no Vindinium
→ Link para o meu github com uma pequena quantidade de trabalho no Vindinium
Na próxima parte, configuraremos campos em potencial, trabalharemos com mapas em potencial, escreveremos condições e imporemos tudo isso às realidades modernas.