Inteligencia Artificial #2 - Máquina de Estados Finitos (FSM)

[Raizen]

[box class=windowbg1]

Índice das aulas básicas

• Aula 1 - Introdução
  
• Aula 2 - Objetos
  
• Aula 3 - Operações
  
• Aula 4 - Condições
  
• Aula 5 - Repetição
  
• Aula 6 - Arrays
  
• Aula 7 - Hashes
  [/box]
  [box class=windowbg1]
  Índice das aulas avançadas
• Aula 8 - Superclasses e instâncias
  [/box]
  [box class=windowbg1]
  Índice das aulas de algoritmos
• Aula 1 - Sort
  
• Aula 2 - Busca
  
• Aula 3 - Recursividade
  [/box]
  
  
  Conhecimento necessário : médio
  [box class=windowbg]
  FSM (Finite State Machine)
  [/box]
  [box class=windowbg2]
  Para a segunda aula vamos explicar sobre um algoritmo que é muito utilizado nos jogos que contém I.A. Esse seria o FSM (Finite State Machine), ou Máquina de Estados Finitos. Como definição do método ele depende apenas de uma coisa, que a máquina tenha um estado único a cada momento. Um exemplo prático em jogos, que o NPC tenha apenas uma estado, correndo, voando, atacando etc.
  Qual é a maior diferença em relação a aula anterior de Árvore de decisão, a maior diferença é que na realidade não há o dito "tomada de decisão", isso é um estado da máquina e não uma decisão que ele toma a cada X segundos. A máquina sempre irá verificar o estado para saber como agir em tempo real.
  Vamos as condições necessárias para o FSM:
  
  
  • Um número finito de estados possíveis para a máquina (Ex: correr, pular e andar)
    
  • A máquina pode assumir apenas um estado simultaneamente.
    
  • É realizado uma série de verificações para as transições de estado
    
    
    Explicando com códigos:
    
    

    classe Personagem
    	  metodo Personagem
    	    correndo = Correndo(personagem)
    		pulando = Pulando(personagem)
    		andando = Andando(personagem)
    	  fim metodo
    	  metodo estado_inicial()
    	    estado = andando
    	  fim metodo
    	  metodo transicao_estado(estado_novo)
    	    estado = estado_novo
    	  fim metodo 
          metodo estado_atual()
    	    retorna estado
          fim metodo	  
    	  fim classe
    	    
    	classe Correndo(personagem)
    		//metodos que demonstram o personagem correndo, imagens, sons etc
    	fim classe
    	classe Pulando(personagem)
    		//metodos que demonstram o personagem pulando, imagens, sons etc
    	fim classe
    	classe Andando(personagem)
    		//metodos que demonstram o personagem andando, imagens, sons etc
    	fim classe
    

       
    Como ele funciona, a máquina tem um estado inicial, no caso parado, sempre que eu quiser mudar o estado dele existe o chamado, transição de estado, essa transição de estado pode ter N condições, usando a mesma lógica do tomada de decisão da aula anterior, você pode sempre verificar se é necessário mudar o estado da máquina. Essa A.I é muito utilizada em jogos de estratégia como Age of Empires, ela permite que sempre seja verificado se cada máquina precisa mudar o estado.
    
    Você pode imaginar as possibiidades assim:
    
    
    [/box]
    
    [box class=windowbg]
    FSM com pilha
    [/box]
    
    [box class=windowbg2]
      Agora que sabem como funciona o FSM, vamos adicionar um pouco de tempero ao algoritmo. Para uma ação mais natural do NPC vamos supor uma certa situação. o FSM verifica que o NPC tem que atacar uma casa, ai ele termina de destruir a casa logo o estado se desliga... E depois? o que aconteceria se usar apenas o método acima ele vai ficar parado até atingir alguma nova condição para mudar a sua ação. Para resolver esse "delay" de estado, podemos usar a pilha.
      Mais especificamente LIFO, qual é o plano aqui, LIFO significa o último que entrou sai, então ao invés de simplesmente mudarmos o estado, vamos empurrando os novos estados e ai caso um estado cumpra a função retiramos ele e seguimos para o estado seguinte. Exemplo prático:
      Adicionar ao NPC "correr em direção a uma edificação"
      Adicionar ao NPC "atacar edificação"
      Edificação destruida, retiro o estado atacar a edificação, o estado anterior seria "correr em direção a uma edificação" , que ele ira realizar.
     
      no nosso código ficaria:
     
     

      	  metodo transicao_estado(estado_novo)
    	    estado.empurrar(estado_novo)
    	  fim metodo 
          metodo estado_atual()
    	    retorna estado.ultimo
          fim metodo	
          metodo remover_estado()
    	    retorna estado.remover_ultimo
          fim metodo
     
    

    
    
      Claro que isso pode ser aprimorado com todo o restante da lógica de programação como condições.
    [/box]
    
    [box class=windowbg]
    Finalizando
    [/box]
    [box class=windowbg2]
    Agora começou a ficar interessante :)! Espero que tenham gostado dessa aulinha e fiquem a vontade para qualquer ponto de melhoria!
    [/box]
    

[Corvo]

Não sei porque, mas essa aula me lembrou o Evolution. Para quem não conhece, é um simulador que usa I.A. para gerar modelos com um corpo criado pelo usuário. A ideia é criar uma coisa(?) que se movimente pela maior distância possível. A I.A. vai testando as hipóteses (estados) de movimento até encontrar a combinação mais útil para seguir em frente.

Interessante, eu não sabia que isso tinha nome e muito menos que era um algorítimo. Muito legal entender estas minúcias, mande mais. 

[Raizen]

Não sei porque, mas essa aula me lembrou o Evolution. Para quem não conhece, é um simulador que usa I.A. para gerar modelos com um corpo criado pelo usuário. A ideia é criar uma coisa(?) que se movimente pela maior distância possível. A I.A. vai testando as hipóteses (estados) de movimento até encontrar a combinação mais útil para seguir em frente.

Interessante, eu não sabia que isso tinha nome e muito menos que era um algorítimo. Muito legal entender estas minúcias, mande mais. 

Opa da hora esse que você mandou hahaha 

Apesar que esse certamente está usando "aprendizagem de máquina", esse seria a 4ª aula provavelmente, tem um pouco de FSM, mas acho que o "Machine Learning" é aonde chega mesmo nesse resultado. Droga agora que me mostrou to brincando nesse jogo hahaha

Edit: aliás agradeço muito por me mostrar isso, isso vai ser um exemplo sensacional quando eu chegar lá XD.

[Gabriel]

Postou a segunda parte mais rápido do que eu esperava, aí sim! Gostei muito da explicação.

De bônus, muito legal esse link que o Corvo postou acima. Interessante analisá-lo e entender como os processos para funcionar foram criados.