Por que um carro pode jogar desumanamente bem em Mario, mas não em Pokemon?

Antecipando nosso torneio no jogo da velha escola Game Overnight, decidimos conversar sobre bots em jogos de computador.

Você provavelmente já ouviu falar que os recursos dos bots modernos para jogos de computador excedem os humanos. Esses bots podem ser codificados, sempre reagindo igualmente aos mesmos conjuntos de dados de entrada. Outra abordagem para o seu desenvolvimento é que eles podem aprender e evoluir . Eles se comportam de maneira diferente nas mesmas situações, tentando encontrar soluções ideais para os problemas que enfrentam.



Aqui estão alguns exemplos conhecidos de tais bots:

• AlphaZero é um robô de xadrez que, após 24 horas de treinamento, se tornou o melhor jogador do mundo.
• AlphaGo é o programa que venceu Lee Sedola e Ke Jie em Go.
• MarI / O é um bot para Super Mario que aprende por conta própria, tentando completar os níveis do jogo o mais rápido possível.

Xadrez, vá, Super Mario - jogos difíceis, bots são combinações razoavelmente selecionadas de algoritmos, leva muito tempo para treiná-los.

Este material é dedicado à análise do bot MarI / O e à história de por que a abordagem usada para criar esse bot não ajudará a escrever um programa que possa jogar bem Pokemon.

Qual é a diferença entre Mario e Pokemon?

Existem três diferenças principais entre os jogos Mario e Pokemon que determinam o potencial sucesso dos bots:

1. O número de objetivos.
2. Coeficiente de ramificação.
3. A contradição entre otimização global e local

Compare jogos com esses fatores em mente.

Número de objetivos

As máquinas aprendem otimizando uma certa função objetiva. Pode ser a maximização da função de recompensa ou aptidão (ao aprender com reforço e ao usar algoritmos genéticos ), pode minimizar a função de perda (ao aprender com um professor ). De qualquer forma, se falamos sobre o aplicativo no jogo, estamos falando sobre o conjunto do número máximo possível de pontos.

Mario tem um objetivo: chegar ao fim do nível. Simplificando, quanto mais você avançar no jogo, melhor. Este indicador expressa uma única função objetivo, e as capacidades do modelo podem ser estimadas, de maneira simples e clara, por um único indicador.

Objetivo do jogo Mario

Pokemon tem muitos objetivos. Vamos tentar descobrir. Talvez o objetivo do jogo seja derrotar a elite quatro? Talvez esta seja a captura de todos os Pokémon? Ou talvez você precise treinar o time mais forte? É possível que o objetivo do jogo seja uma combinação de todos os objetivos anteriores ou mesmo algo completamente diferente. É provável que, na realidade, se você perguntar a um jogador específico sobre isso, o objetivo dele seja apresentado na forma de uma combinação complexa das muitas conquistas disponíveis no jogo.


Objetivos do Jogo Pokemon

Ao analisar um jogo, é necessário não apenas determinar seu objetivo final, mas também decidir como o jogo progride, como determinadas ações afetam a função do objetivo, piorando ou melhorando dependendo da enorme variedade de opções disponíveis para o jogador em um determinado momento.

De fato, a escolha de uma variante de ação em uma determinada situação nos leva ao segundo indicador de comparação de jogos.

Proporção de ramificação

O coeficiente de ramificação é, em termos simples, um indicador que indica o número de opções de ação disponíveis em cada etapa do processo do jogo. No xadrez, o coeficiente médio de ramificação é 35. Em movimento - 250. Se um bot tenta "olhar para o futuro", tendo contado todos os movimentos que pode fazer no momento e depois todos os movimentos que pode fazer após concluir o movimento atual e assim por diante, cada um desses níveis significa um aumento sério na complexidade da tarefa. Nomeadamente, o número de opções com essa abordagem cresce exponencialmente, expresso como uma fórmula da forma (coeficiente de ramificação) ^ (número de níveis).

Em Mario, um personagem pode se mover para a esquerda ou direita, pode pular e simplesmente não pode fazer nada. O número de opções que o bot precisa avaliar é pequeno. Quanto menor o coeficiente de ramificação, mais longe o bot pode olhar para o futuro, gastando recursos computacionais aceitáveis ​​nisso.

Mario Opções

Pokemon tem um mundo de jogo aberto. Isso significa que, em cada momento específico, o jogador tem muitas opções de ação. Além disso, neste caso, uma simples enumeração das direções do possível movimento de um personagem não é adequada para o cálculo do coeficiente de ramificação. Em vez disso, um papel é desempenhado por certas ações que fazem sentido no mundo do jogo. A próxima ação será uma luta, uma conversa com um personagem do jogo, uma transição para outra área do mapa? Além disso, o número de opções, à medida que avança no jogo, está aumentando.


Apresentação simplificada das ações dos personagens em Pokemon

Para criar um bot que possa descobrir qual sequência de decisões deve ser tomada em tal situação, esse bot precisa levar em conta seus objetivos de curto e longo prazo, o que nos leva à próxima dimensão da comparação de jogos de Mario e Pokemon.

A contradição entre otimização global e local

A otimização local e global pode ser considerada espacial e temporalmente. Objetivos de curto prazo e uma pequena área em torno do personagem do jogo estão relacionados à otimização local. Objetivos de longo prazo e fragmentos relativamente grandes do espaço do jogo (algo como uma “cidade” ou o mundo inteiro do jogo) estão relacionados à otimização global.

Se, em Pokemon, você dividir cada movimento em suas partes constituintes - isso ajudará a apresentar o problema que o bot, que consiste em fragmentos muito pequenos, precisa resolver. A otimização local, permitindo, digamos, ir do ponto A ao ponto B, não causará dificuldades. Um problema muito mais complicado é a escolha do ponto B, a direção do movimento. Os algoritmos gananciosos não nos ajudarão aqui, pois as soluções localmente ótimas não necessariamente levam a resultados ótimos globalmente.


O problema de escolher o próximo passo

Os mapas no Mario são pequenos e lineares. Os mapas em Pokemon são grandes, complexos e não lineares. Antes do jogador, conforme você avança no jogo e ele busca objetivos cada vez mais importantes, novas tarefas surgem constantemente. E a tarefa de organizar a conexão de otimizações locais com objetivos globais não é fácil. Pelo menos os modelos existentes ainda não estão prontos para resolvê-lo.

Sumário

Do ponto de vista dos bots, Pokemon não é um jogo. Os bots são notáveis ​​por sua estreita especialização, e um bot que ajuda o jogador a se mover pelo mapa será inútil se o jogador encontrar um personagem do jogo que precise entrar na batalha. Do ponto de vista dos bots, mover-se pelo mapa e batalhar são tarefas completamente diferentes.


Bots são sistemas altamente especializados

Durante a batalha em cada etapa, você deve escolher entre dezenas de opções. Você precisa decidir qual ação executar, qual Pokemon executar, você precisa entender quando usar vários itens. Tudo isso, por si só, apresenta desafios complexos de otimização. Aqui está o material que explora o desafio de desenvolver um simulador de batalha em Pokemon. Este artigo é bem desenvolvido, bastante complicado, mas mesmo aí o problema dos objetos, o fator mais importante que afeta o resultado da batalha, não é considerado.

No final, podemos dizer que precisamos nos alegrar pelo fato de podermos criar bots que jogam nossos jogos melhor do que nós. Esses jogos são complexos do ponto de vista matemático, mas seus objetivos são facilmente determinados. Com o desenvolvimento de tecnologias de inteligência artificial, a humanidade será capaz de criar máquinas que podem resolver os problemas cada vez mais importantes do mundo real. Eles farão isso estudando esses problemas, que são tarefas complexas de otimização. Mas, por enquanto, posso garantir, há tarefas que resolvemos melhor do que máquinas, incluindo jogos que muitos de nós jogamos na infância. Pelo menos este é o caso agora.

Caros leitores! Convidamos você a participar do primeiro torneio da Rússia nos videogames da velha escola Game Overnight . O torneio tem uma parte de qualificação e uma verdadeira batalha dos melhores dos melhores, que será realizada em 30 de novembro no Museu das máquinas caça-níqueis soviéticas. Aguardamos o torneio de 20 a 3 horas, bebidas de espuma Smart Admin, Dj Ogurets (Sergey Mezentsev) e o DJ Unpushible do RUVDS Admin o ajudarão e também experimentaremos novos hambúrgueres de neve Sub Zero de nossos administradores. Então, como eles dizem, seja bem-vindo!