1. Máquina de Estados Finitos Não Determinísticas

Imagine, por exemplo, o jogo de futebol que você está desenvolvendo e que dois times controlados pelo computador vão disputar uma partida. Hum… imaginou? Ou seja, é uma simulação, e não um jogo. Se você usar a Máquina de Estados Finitos tal qual foi descrita na aula anterior, a posição inicial dos jogadores no campo irá determinar o resultado. Isso ocorrerá porque para um determinado evento apenas uma transição de estado é possível, fazendo com que essa “simulação” seja determinística. Assim, ao ser dado um conjunto de parâmetros de entrada para a simulação (posição inicial dos jogadores), uma única saída (resultado) será produzida.

Muitas vezes, não é possível perceber essa limitação, mesmo usando a MEF Determinística, porque a produção de aleatoriedade, que quebra o aspecto determinístico, fica a cargo do jogador. Ele movimenta seu personagem de um lado para o outro, atira, pula, faz combinações de golpes e hadoukens inesperados que criam a ilusão de que os personagens controlados pela IA não seguem padrões.

No filme Pixels (2015), os seres intergalácticos usam os jogos de arcade clássicos contra a Terra, até que Sam Brenner (Adam Sandler), campeão de competições de videogames dos anos 80, ajuda a salvá-la. A técnica dele era “identificar os padrões”.

Os seres intergalácticos, tão inteligentes, criaram seus jogos com Máquina de Estados Finitos Determinística! Ainda bem que eles não viram essa aula que você está vendo!

Uma alternativa às MEFs clássicas é a introdução de incertezas não através de aleatoriedade sobre as transições, mas através da dúvida sobre os eventos.

Você deve estar em “dúvida sobre essa dúvida”. Como um personagem controlado pela IA pode ter dúvida? Quando um evento ocorre em um cenário, por exemplo, e o personagem se encontra a menos de 50 m do inimigo, não há dúvida sobre isso. O computador pode, muito bem, calcular a distância do personagem ao seu inimigo e, se essa distância for menor que 50 m, é porque o evento ocorreu, caso contrário, não. É ou não é? Não há discussão sobre isso. É preto no branco!

Suponha que você tenha vários eventos concorrendo e um personagem que precisa defender uma base. Ele pode ir atrás do um inimigo que começou a atacá-la, mas se afastou para não morrer. O personagem, então, persegue o inimigo para não deixar que ele recupere sua saúde (health). Porém, outros inimigos estão também atacando a base. O que fazer, então? Voltar para protegê-la ou continuar e acabar com os últimos suspiros do inimigo inicial?

Essa dúvida é cruel… mesmo para nós quando estamos jogando. Imagine, então, para personagens controlados pelo computador. Bom, na verdade, não é tão cruel assim para eles. Eles vão apenas seguir um algoritmo. É cruel para o desenvolvedor dos algoritmos: você!

Mas, o que seria então uma MEF Não Determinística?

Antes que eu responda essa pergunta, pense um pouco e recapitule o que foi visto na aula 04. Nela, você viu o conceito de probabilidade sendo usado para “modelar incertezas”. Foi demonstrado que um chute ao gol pode gerar vários resultados. Pode ser um chute a la Roberto Baggio ou um chute a la Zico. Esse mesmo conceito pode ser usado para criar Máquina de Estados Finitos Não Determinística. Assim como uma ação pode gerar diferentes resultados, um evento pode também gerar diferentes transições de estados. Simples, não é?

Os mesmos elementos e mecanismos apresentados na aula 4 (Probabilidade) podem ser usados sobre os elementos e mecanismos apresentados na aula 05 (Máquina de Estados Finitos). A diferença das MEFs anteriores é que pode-se ter, para o mesmo evento, mais de uma transição de um estado para o outro.

Por exemplo, a Figura 02 representa uma MEF similar à da aula 04, porém introduz uma transição de um estado para ele mesmo. Isso significa dizer que, caso o personagem tenha o inimigo à vista, ele pode continuar no mesmo estado, ou seja, patrulhando.

Como você deve ter percebido, há uma duplicidade de transição quando o inimigo estiver à vista durante o estado de patrulha. Como, então, resolver qual transição executar? Uma solução é definir uma probabilidade para cada transição de cada uma das possíveis opções. Lembra da fórmula que define a probabilidade de um evento específico ocorrer?

$$ p=\frac{evento \space específico }{todas \space opções \space de \space eventos \space possíveis } $$

Com essa fórmula, é possível estabelecer uma regra que determine a frequência possível de cada transição. Suponha que um estado possua 10 possíveis transições a partir do mesmo evento. Nesse caso, se todas as transições tiverem a mesma chance de serem a escolhida para serem executadas, a probabilidade de cada uma seria dada por:

$$ p=\frac{evento \space específico }{todas \space opções \space de \space eventos \space possíveis } = \frac{1}{10} = \frac{1}{100} = 10 $$

Ou seja, cada uma teria uma chance de 10% de ser executada.

Mas esse é o caso de todas as transições terem chances iguais. E se você fosse tendencioso? Poderia dar uma chance maior àquelas transições nas quais queira que aconteça com mais frequência. Por exemplo, no comportamento modelado na Figura 02, podem ser introduzidas probabilidades associadas às transições, como representado na Figura 03.

Observe que quando o personagem perceber o inimigo ele continuará patrulhando em 20% das vezes, mas passará a perseguir o inimigo em 80% das vezes.

Talvez pareça estranho para você modelar um comportamento de, por exemplo, um personagem soldado que às vezes não persegue o inimigo, mesmo o tendo visto. De fato, não faz muito sentido se você pensar em um jogo com um único soldado para perseguir o jogador. E se for um cenário com vários desses soldados e que eles sejam controlados por uma MEF Determinística como a da Figura 02? Quando o jogador (inimigo, para os soldados) entrar nesse cenário, todos os personagens vão sair correndo atrás dele, de uma vez só. Nesse caso, vai parecer estranho também, pois mostra que eles não possuem coordenação alguma entre eles. A princípio, espera-se que uma tropa de soldados possua um mínimo de coordenação. O uso de probabilidade nas transições, como a MEF da Figura 03, fará com que você possa reduzir o ritmo em que os soldados irão em direção ao jogador, simulando um pouco de coordenação sem precisar elaborar algoritmos complexos para isso.