| |
| Acadêmico(a): Andre Luis Galastri |
| Título: O Uso de Programação Genética na Tomada de Decisão de Jogos |
| |
| Introdução: |
Programação genética é um mecanismo de busca onde o universo é o conjunto de todos os programas de computador e o resultado final da busca é um único programa. Pode-se procurar, por exemplo, por um programa que tome como entrada dois números e retorne o resultado da soma de ambos, ou um programa que receba uma seqüência de números e retorne a mesma seqüência ordenada. A procura pelo programa alvo é realizada através de sucessivas seleções de indivíduos que representam, ou geram, os resultados mais próximos do esperado. Segundo Koza (1992), o universo dos programas de computadores possui uma quantidade praticamente ilimitada de elementos, e a programação genética é uma forma de encontrar elementos neste universo.
Os programas encontrados através da programação genética são “empíricos”, ou seja, os resultados que geram não são o fruto de uma teoria ou estudo que foi transformado em algoritmo, mas sim um simples programa que retornou resultados corretos para os valores com os quais foi testado (Koza, 1992). De acordo com Koza (1992) é exatamente a natureza “inexata” de tais programas que fizeram com que o seu desenvolvimento e utilização fossem, de certa forma, relegados a um segundo plano em diversas áreas de Inteligência Artificial (IA). A tomada de decisão em jogos é uma destas áreas, embora seja uma aplicação clássica de IA, é, paradoxalmente, muito pouco explorada através de programação genética (Koza, 1992).
Uma forma possível de explorar a programação genética em jogos é através do simulador Robocode (IBM, 2001). Robocode é um simulador de batalhas entre tanques de guerra (IBM, 2001). Cada tanque é controlado por um programa de computador escrito na linguagem Java, informações sobre tal linguagem podem ser obtidas em Flanagam (2000), Haggar (2000) e Newman(1997). Este programa recebe eventos e realiza operações no tanque. Os eventos são a forma que o programa recebe informações sobre o que está ocorrendo na simulação. Eles indicam, por exemplo, se o tanque que o programa está controlando foi atingido pelo inimigo, ou se um disparo que o tanque realizou foi bem sucedido. As operações são a forma como o programa controla as ações do tanque interagindo assim com a simulação. O programa pode, por exemplo, realizar uma operação de “andar para frente” e, na simulação, o tanque irá se mover para frente. Quando dois tanques estão lutando, o confronto, é na verdade, entre dois programas, onde cada programa é executado em uma thread diferente, ambas controladas pelo simulador. O simulador garante que ambos os programas terão uma quantidade de tempo máximo de processamento, garantindo assim um confronto justo. O simulador Robocode é acompanhado de diversos exemplos de programas controladores de tanques.
Como cada tanque no simulador Robocode é controlado por um programa em Java, pode-se utilizar a programação genética para encontrar tais programas. Como o simulador oferece operações e eventos basta procurar no universo de programas de computador por programas que utilizem tais operações e respondam a tais eventos.
Para realizar busca por programas é necessário desenvolver uma ferramenta capaz de realizar as operações de programação genética. A ferramenta deve testar cada programa controlador de tanques na plataforma de simulação Robocode. A eficiência de cada programa é medida através da pontuação dada a ela pelo simulador. A forma como a ferramenta procura pelos programas é se restringindo somente a programas na linguagem de programação Java que utilizem certas construções da linguagem. Essas construções podem ser operadores condicionais (“if”), operadores de repetição (“while”), valores constantes, variáveis e a chamada de métodos que representam as operações realizáveis no tanque.
|
| |
|
