A BRQ está com algumas oportunidade para Programadores e Analistas Java

Divulgado:

A BRQ está com algumas oportunidade para Programadores e Analistas Java para atuar em Curitiba.

Enviar CV com pretensão salarial para: Fernanda Perencin (fperencin@brq.com).

Posted in Oportunidades at julho 25th, 2012. No Comments.

Construção de um Agente Inteligente que Jogue Mario

Com esse post você vai obter o resultado abaixo:


Nas últimas semanas eu veio estudando a fundo a técnica de inteligência artificial de redes neurais. Não é toa que praticamente os meus dois últimos posts foram sobre esse assunto.

Tudo começou com a ideia de criar um agente inteligente que conseguisse jogar Mario sozinho, a minha pretensão nunca foi muito grande, eu apenas tinha a ideia de fazer algo simples que funcionasse, mas não tinha a grande pretensão de fazer um super agente inteligente capaz de passar por vários níveis diferentes de dificuldade do jogo Mario. Partindo disso, com o único objetivo de aprendizado, eu decidi usar a técnica de redes neurais e fazer o Mario passar pela primeira fase.

Para simplificar mais ainda, eu fiz por padrão o Mario andar para a direita e a única ação que é aplicada inteligência artificial é a decisão se o Mario deve ou não pular.

O código do jogo Mario eu obtive do site: http://www.marioai.org/gameplay-track/getting-started, esse é o site da competição que tem o foco na criação de agentes inteligentes e criação de fases para o Mario, usando inteligência artificial. Eles não disponibilizam o código da parte de inteligência artificial, cabe a cada participante implementar o seu algoritmo e enviar para a competição, o melhor agente inteligente vence. Eu também não tinha a ideia de vencer essa competição, não tenho nível e conhecimento suficiente para isso ainda.

Antes de entrarmos em código e implementação, é importante entender do que consiste a técnica de redes neurais.

De forma resumida, uma rede neural é constituída por um neurônio (perceptron), que possui a seguinte estrutra:

  • Dendritos;
  • Corpo celular;
  • Axônio.

O dendrito(s) corresponde(m) as entradas (inputs) do neurônio, o corpo celular é responsável pelo processamento e o axônio representa a saída (output).

O algoritmo de uma rede neural se resume em:

  • Os dendritos recebem um valor de entrada cada um, esse valor é multiplicado por um peso, uma soma ponderada na verdade;
  • O neurônio, corpo celular, recebe a soma ponderada e através de uma verificação matemática, decide o valor de saída para o neurônio. Isso é conhecido por função de ativação, que em muitas vezes se resume em um if que testa se a soma é maior ou menor que zero;
  • O axônio transmite essa saída

Você pode pensar “Hum muito bem, onde está a inteligência artificial nisso?”, a inteligência artificial está no próximo passo do algoritmo, o neurônio deve ser treinado, ele deve receber um conjunto de valores de entrada para os dendritos e a saída válida, saída conhecida para esse conjunto de entradas. Com posse disso o neurônio é treinado, e o grande segredo de uma rede neural é o ajuste dos pesos que são multiplicados pelas entradas no dendritos, nessa parte que consta a inteligência artificial. O grande foco e obter os pesos ideias para que a rede neural se comporte da melhor forma, depois de encontrar esses pesos basta em usá-los sempre.

Na verdade tudo é matemática.

Agora que está claro como tudo acontece vamos ver a implementação. Vamos começar pelas estruturas de dados mais básicas e avançamos para as mais complexas.

Dendrito

Dendrite.java

package br.pucpr.neuralnetwork;
 
// Classe que representa um dendrito
public class Dendrite {
	// Valor para o dendrito
	private int value;
 
	// Método construtor
	// aceita como parâmetro:
	// * value = valor para o dendrito
	public Dendrite(int value) {
		this.value = value;
	}
 
	// Obtém o valor atual do dendrito
	public int getValue() {
		return value;
	}
}

Axônio

Axon.java

package br.pucpr.neuralnetwork;
 
// Classe que representa um axônio
public class Axon {
	// Sinal de saída
	private int sign;
 
	// Obtém o sinal do axônio
	public int getSign() {
		return sign;
	}
 
	// Define o sinal para o axônio
	public void setSign(int sign) {
		this.sign = sign;
	}
 
	// Transforma o sinal em um valor booleano
	public boolean signToBoolean() {
		if (sign == -1) {
			return false;
		}
		return true;
	}
}

Neurônio

Neuron.java

package br.pucpr.neuralnetwork;
 
// Classe que representa um neurônio
public class Neuron {
	// Dendritos
	private Dendrite[] dendrites;
	// Axônio
	private Axon axon;
	// Pesos
	private float[] weights;
	// Pesos padrões
	private float[] defaultWeights;
	// Tipo da função de ativação
	private String activationType;
	// Constante de aprendizado
	private float constantLearning;
 
	// Método construtor
	// aceita como pârametros:
	// * numberDendrites = Número de dendritos
	// * defaultWeights = Pesos padrão
	// * activationType = tipo da função de ativação
	public Neuron(int numberDendrites, float[] defaultWeights, String activationType) {
		// Define os pesos padrões
		this.defaultWeights = defaultWeights;
 
		// Se não for definida o tipo da função de ativação,
		// então define como sign
		if (activationType == null) {
			this.activationType = "sign";
		}
 
		// Pesos
		weights = new float[numberDendrites];
		// Dendritos
		dendrites = new Dendrite[numberDendrites];
 
		// Cria valores iniciais randômicos para os pesos
		for (int i = 0; i < weights.length; i++) {
			weights[i] = Util.random(-1, 1);
		}
 
		// Constante de aprendizado
		constantLearning = (float)0.0001;
		// Axônio
		axon = new Axon();
	}
 
	// Soma os dendritos com os seus pesos
	// média ponderada
	public float sumDendrites() {
		float sum = 0;
 
		if (defaultWeights != null && defaultWeights.length > 0) {
			for (int j = 0; j < defaultWeights.length; j++) {
				weights[j] = defaultWeights[j];
			}
		}
 
		for (int i = 0; i < weights.length; i++) {
			sum += dendrites[i].getValue() * weights[i];
		}
		return sum;
	}
 
	// Método de ativação
	// dependendo da soma e do tipo de ativação
	// envia o sinal -1 ou 1 para o axônio
	public void activation() {
		float sum = sumDendrites();
 
		axon.setSign(1);
		if (sum < 0) {
			axon.setSign(-1);
		}
	}
 
	// Treina o neurônio, afim de obter os melhores pesos para os dendritos
	// aceita como parâmetros:
	// * numberTimes = número de épocas
	// * percentageCorrect = percentual correto para o treinamento ser considerado bem sucedido
	// * examplesTraining = exemplos para o treinamento
	public void train(int numberTimes, int percentageCorrect, Point[] examplesTraining) {
		System.out.println("Treinamento iniciado...");
 
		// Quantidade de treinamento verificado
		int totalVerified = 0;
		// Quantidade de treinamento verificado errado
		int totalVerifiedWrong = 0;
		// Quantidade de treinamento verificado correto
		int totalVerifiedCorrect = 0;
 
		// Repete até o número de épocas ser satisfeito
		for (int i = 0; i < numberTimes; i++) {
			// Percorre todos os exemplos de treinamento
			for (int j = 0; j < examplesTraining.length; j++) {
				// Obtém a saída adivinhada pelo neurônio
				int result = guess(examplesTraining[j]);
				// Calcula o fator de mudança do peso baseado no erro
				// erro = saída desejada - saída adivinhada
				// multiplica pela constante de aprendizado
				float weightChange = constantLearning * (examplesTraining[j].getOutput() - result);
				// Ajusta os pesos baseado no fator de mudança * a entrada
				for (int k = 0; k < weights.length; k++) {
					weights[k] += weightChange * examplesTraining[j].getVals()[k];
				}
 
				// Contabiliza se o valor adivinhado foi correto ou não
				if (result == examplesTraining[j].getOutput()) {
					totalVerifiedCorrect++;
				} else {
					totalVerifiedWrong++;
				}
			}
		}
 
		// Quantidade de treinamentos verificados
		totalVerified = totalVerifiedWrong + totalVerifiedCorrect;
		float totalPercentageCorrect = ((100 * totalVerifiedCorrect ) / totalVerified);
 
		System.out.println("Treinamento terminado...");
		System.out.println("Resultados obtidos:");
		System.out.println(" - Número de épocas executadas: " + numberTimes);
 
		String indicativeSuccess = "bem sucedido";
 
		if (totalPercentageCorrect < percentageCorrect) {
			indicativeSuccess = "mal sucedido";
		}
 
		System.out.println(" - Indicativo de sucesso: Treinamento " + indicativeSuccess);
		System.out.println(" - Porcentagem correto: " + totalPercentageCorrect);
		System.out.println(" - Pesos:");
 
		if (defaultWeights != null && defaultWeights.length > 0) {
			for (int j = 0; j < defaultWeights.length; j++) {
				weights[j] = defaultWeights[j];
			}
		}
 
		for (int i = 0; i < weights.length; i++) {
			System.out.println("   - Peso " + i + ": " + weights[i]);	
		}
	}
 
	// Método que adivinha a saída esperada
	// baseada nas entradas, de acordo com os pesos
	// calculados
	public int guess(Point point) {
		// Define os valores para os dendritos
		setDendrites(point.getVals());
		// Faz a ativação
		activation();
		// Sinal de ativação
		return axon.getSign();
	}
 
	// Define os valores para os dendritos
	// de acordo com um array de valores
	public void setDendrites(int[] vals) {
		for (int i = 0; i < vals.length; i++) {
			dendrites[i] = new Dendrite(vals[i]);
		}
	}
 
	// Obtém a constante de aprendizado
	public float getConstantLearning() {
		return constantLearning;
	}
 
	// Define uma nova constante de aprendizado
	public void setConstantLearning(float constantLearning) {
		this.constantLearning = constantLearning;
	}
 
	// Obtém o axônio
	public Axon getAxon() {
		return axon;
	}
 
	// Obtém o tipo da função de ativação usada
	public String getActivationType() {
		return activationType;
	}
}

Ponto

Point.java

package br.pucpr.neuralnetwork;
 
// Classe que representa um ponto de treinamento
public class Point {
	// Valores de entrada
	private int[] vals;
	// Saída esperada
	private int output;
 
	// Método construtor
	// aceita os parâmetros:
	// * obs1 = tipo de obstáculo na posição 1
	// * obs2 = tipo de obstáculo na posição 2
	// * output = saída esperada
	public Point(int obs1, int obs2, int output) {
		vals = new int[3];
		vals[0] = obs1;
		vals[1] = obs2;
		// Bias para quando as entradas forem zero
		vals[2] = 1;
		this.output = output;
	}
 
	// Valores de entrada
	public int[] getVals() {
		return vals;
	}
 
	// Saída esperada
	public int getOutput() {
		return output;
	}	
}

Agente Inteligente

NeuralNetworkAgent.java

package ch.idsia.ai.agents.controllers;
 
import br.pucpr.neuralnetwork.Neuron;
import br.pucpr.neuralnetwork.Point;
import ch.idsia.ai.agents.Agent;
import ch.idsia.mario.engine.sprites.Mario;
import ch.idsia.mario.environments.Environment;
 
// Classe que representa um agente inteligente que utiliza rede neural
public class NeuralNetworkAgent extends BasicAIAgent implements Agent {
 
	// Neurônio
	private Neuron neuron;
	// Pontos para treinamento
	private Point[] examplesTraining;
 
	public NeuralNetworkAgent() {
		super("NeuralNetworkAgent");
 
		// Instância um neurônio
		// Com 3 dendritos, obstáculo 1, obstáculo 2 e 
		// bias para quando as primeiras entradas forem zero
		neuron = new Neuron(3, null, "sign");
 
		// Com pesos padrões
		// float[] defaultWeights = new float[3];
		// defaultWeights[0] = (float)0.12533271;
		// defaultWeights[1] = (float)-0.15752053;
		// defaultWeights[2] = (float)-0.22475332;
		// neuron = new Neuron(3, defaultWeights, "sign");
 
		// Cria os pontos para o treinamento
		setExamplesTraining();
 
		// Realiza o treinamento
		neuron.train(300, 43, examplesTraining);
 
		reset();
	}
 
	public void reset() {
		action = new boolean[Environment.numberOfButtons];
		action[Mario.KEY_RIGHT] = true;
	}
 
	public boolean[] getAction() {
		// Através dos pesos calculados no treinamento
		// tenta jogar Mario sozinho
		// Define o valor para os dendritos baseado nos obstáculos do jogo
		int[] vals = new int[2];
		vals[0] = mergedObservation[11][13];
		vals[1] = mergedObservation[11][12];
		neuron.setDendrites(vals);
 
		// Realiza ativação do neurônio, afim de obter o sinal de saída
		neuron.activation();
 
		// De acordo com o neurônio faz o Mario pular ou não
		if (neuron.getAxon().signToBoolean()) {
			if (isMarioAbleToJump) {
				action[Mario.KEY_JUMP] = true;	
			}
		} else {
			action[Mario.KEY_JUMP] = false;
		}
 
		return action;
	}
 
	// Cria os pontos para o treinamento
	public void setExamplesTraining() {
		examplesTraining = new Point[6];
		examplesTraining[0] = new Point(0, 0, -1);
		examplesTraining[1] = new Point(-10, 0, 1);
		examplesTraining[2] = new Point(20, 0, 1);
		examplesTraining[3] = new Point(-10, -10, 1);
		examplesTraining[4] = new Point(2, 0, 1);
		examplesTraining[5] = new Point(-11, 0, 1);
	}
}

Main

Main.java

package ch.idsia.scenarios;
 
import ch.idsia.ai.agents.Agent;
import ch.idsia.ai.agents.controllers.NeuralNetworkAgent;
import ch.idsia.maibe.tasks.BasicTask;
import ch.idsia.mario.environments.Environment;
import ch.idsia.mario.environments.MarioEnvironment;
import ch.idsia.tools.CmdLineOptions;
 
/**
 * Created by IntelliJ IDEA. User: Sergey Karakovskiy, sergey at idsia dot ch Date: Mar 17, 2010 Time: 8:28:00 AM
 * Package: ch.idsia.scenarios
 */
public class Main
{
    public static void main(String[] args)
    {
    	// final String argsString = "-vis on";
    	// args = argsString.split("\\s");
        final CmdLineOptions cmdLineOptions = new CmdLineOptions(args);
        final Environment environment = new MarioEnvironment();
        // final Agent agent = new ForwardAgent();
        // final Agent agent = cmdLineOptions.getAgent();
        final Agent agent = new NeuralNetworkAgent();
        // final Agent a = AgentsPool.load("ch.idsia.controllers.agents.controllers.ForwardJumpingAgent");
        final BasicTask basicTask = new BasicTask(environment, agent);
        basicTask.reset(cmdLineOptions);
        basicTask.runOneEpisode();
 
        System.out.println("cmdLineOptions.getLevelLength() = " + cmdLineOptions.getLevelLength());
        System.out.println(environment.getEvaluationInfoAsString());
        System.exit(0);
    }
}

Vamos entender como as classes acima se juntam para implementar a rede neural, a classe NeuralNetworkAgent.java possui os exemplos de treinamento, esses exemplos foram captados quando eu estava realmente jogando, por isso que a saída é conhecida, é o que se espera que o Mario faça quando ele tiver obstáculos pela frente. Além dos exemplos essa classe define o comportamento inicial do Mario que é andar para direita, a classe também realiza o treinamento, e com posse dos pesos ela abre a tela do jogo e coloca o Mario para jogar sozinho com inteligência. No código incluído está para toda vez os pesos serem calculados, é possível passar pesos padrões para o neurônio, essa parte do código está comentada, se você descomentar já irá ver o Mario jogando com os melhores pesos que eu encontrei.

A classe Point.java descreve os pontos ou ponto de entrada, ela recebe a informação se existem obstáculos na posição 1 e na posição 2 e a saída que deve existir.

A classe Dendrite.java descreve um dendrito e o seu valor de entrada.

A classe Axon.java descreve o axônio do neurônio, o sinal de saída, que também é transformado em um valor booleano.

A classe Neuron.java por sua vez que realiza todo o trabalho, cálculo dos melhores pesos e o emprego da inteligência artificial. Poder conter vários dendritos (várias entradas), uma única saída, os pesos para cada entrada e a constante de aprendizado. Inicialmente os pesos são valores randômicos, ao entrar no treinamento, os melhores pesos tentam ser encontrados, não sempre isso acontece, vai depender da quantidade de exemplos de treinamento e a quantidade de épocas. As épocas são quantas vezes o algoritmo vai ser repetido para tentar encontrar os melhores pesos para a rede neural. A constante de aprendizado é usada para alterar os pesos e tentar achar o melhor peso, as referências bibliográficas afirmam que quanto menor a constante de aprendizado, mais vai demorar para encontrar os pesos, mas os pesos encontrados são melhores e mais úteis para o funcionamento da rede.

A classe Main.java que executa o jogo e coloca todas as classes para trabalhar afim de obter a rede neural.

É claro que para o Mario rodar, é necessário ter toda o código fonte do Mario, disponibilizado no endereço que eu mencionei no começo do texto. Os códigos apresentados são apenas um agente inteligente que foi embutido no jogo do Mario.

Eu não vou entrar em mais detalhes do algoritmo, com posse dessas informações e comentários você já deve ser capaz de entender tudo que está acontecendo.

O que eu escrevi nesse texto não representa a verdade absoluta, eu ainda estou estudando o assunto, por isso algumas coisas podem estar erradas ou podem ser feitas de uma forma muito melhor. Apenas quero ajudar e propagar o conhecimento.

O código fonte está disponível em: http://github.com/patrickespake/Mario-Neural-Network-Agent

Posted in Algoritmo, Java, Rede Neural at maio 10th, 2010. 2 Comments.

 Assinar RSS Feed