You are here

Aula 03 - 15/03/2013 - Agente para jogo EATERS

 

CONTEÚDO DO RELATÓRIO:

 

 


ATIVIDADE 1:


1.1. Como o estado atual da criatura é considerado nas regras?

O arquivo "move-to-food.soar" tem apenas 3 regras, representadas abaixo:
 


A primeira propõe o operador "move-to-food" caso receba do "input-link" um conteúdo que indique uma direção onde existe ou uma "normalfood" ou uma "bonusfood"; para essa direção ele cria um operador "move-to-food" que possui uma EXTENSÃO "direction" que é a direção onde está a comida.

Em outras palavras, o agente irá se mover para uma das posições ao seu redor onde houver comida.

A entrada recebida pelo programa é um objeto "my-location" que possui extensões para cada direção; cada uma delas, por sua vez, possui uma extensão "content" que indica o que existe nessa posição. O tutorial apresenta ao final a relação completa dessas extensões, reproduzida a seguir:
 
 
 
1.2. Como a decisão de ação escolhida é aplicada de fato ao jogo?

A ação definda - no caso, o movimento do agente - é aplicado ao jogo com a criação de uma extensão "move" a partir do "output-link"; o formato final é:
 
 

(<id-output-link> ^move <id-move)
(<id-move> ^direction north)
 
 
 
* Exemplo com movimento para o norte.


Quando a ação é completada pelo programa, é adicionado ao estado <id-move> a extensão "status", ficando da seguinte forma:
 

(<id-move> ^direction north ^status complete)
 
 

1.3. Como esse conjunto de regras escolhe a direção para a qual a criatura deve se mover?

A proposição do operador "move-to-food" busca uma direção na qual existe uma posição com uma "normalfood" ou "bonusfood"; para todas elas são propostos operadores. Como existe a indicação de preferência indiferente (=) o Soar seleciona randomicamente entre todas as regras propostas.


1.4. Para que serve a regra "apply*move-to-food*remove-move"? O que aconteceria se ela não existisse?
 
Sem a remoção do comando executado do "output-link".
Sem a remoção do comando executado do "output-link".

Essa regra remove o operador "move-to-food" depois que o programa completa a execução do comando "move", o que é sinalizado com a criação da extensão "status complete".

Sem essa regra de remoção do comando executado, extensões no "output-link" para a execução do comando de "move" serão continuamente criadas o que, no mínimo, ocupará espaço na memória de trabalho.


1.5 Quais são as limitações desse programa? O que seria necessário fazer para que ele não ficasse paralizado depois de um tempo?
 
Sem alternativa de movimento.
Sem alternativa de movimento.
 
A primeira limitação importante é que o programa não sabe para onde mover o agente caso não tenha nenhuma comida ao seu redor; nessa situação ele não consegue concluir e termina por não ter como modificar o estado atual.

Uma maneira simplista de evitar que o agente fique paralizado é, no caso de não haver comida ao seu redor, o programa poderia sugerir que o agente se mova para qualquer um dos espaços vazios ao seu redor.

 

ATIVIDADE 2:

As seções 2 a 5 deste segundo tutorial refazem, em detalhes, todo o processo de criação de regras básicas para movimentação dos agentes, terminando com a mesma versão da atividade 1.

Essas seções também revisitam vários conceitos do tutorial 1, provendo maiores detalhes, como por exemplo a respeito de métodos de depuração e monitoramento da execução de programas Soar. Para a depuração, em especial, estas seções do tutorial (seção 5) fornecem maiores detalhes a respeito dos vários comandos que o "Soar debugger" aceita para visualizar quais regras propostas e quais estão a ponto de disparar (comando "match") ou ainda como visualizar quais as regras de preferência para os operadores propostos.
 
Uso de debug via comando "write".
Uso de debug via comando "write".

Algumas informações novas que surgiram nessas seções foram:
  1. A possibilidade de utilizar variáveis nas regras Soar para fazer o "match" de um atributo - como no caso da análise das informações do "input-link" para determinação de qual direção seguir;
  2. O uso de conjuntos (com "<<" e ">>) para testar valores de variáveis.
  3. O uso de uma forma condensada para testar vários sub-atributos numa condição de regra:

sp {apply*move-to-food
   (state <s> ^io.output-link <out>
              ^operator (^name move-to-food
                         ^direction <dir>))

 


Nesta atividade são desenvolvidas versões incrementais de um agente que resolve o jogo Eaters cada vez de forma mais eficiente.
 
Primeira versão com passos para todas as direções, independentemente de ter ou não comida.
Primeira versão com passos para todas as direções, independentemente de ter ou não comida.
 
 
Versão final dessa atividade, com passos e pulos e verificação genérica de melhor movimento através de sistema de pontuação.
Versão final dessa atividade, com passos e pulos e verificação genérica de melhor movimento através de sistema de pontuação.
 
Uma informação interessante apresentada nesta atividade: todas as preferências de operadores que não são as "preferências de aceitação" - definidas na proposição do operador - não são armazenadas na memória de trabalho, mas sim na memória de preferências, que existe enquanto as regras de instanciação que as criaram são válidas.

Um outro ponto interessante é que para o uso do operador de conjunto - "<<" e ">>" - é preciso ter um espaço entre eles e as constantes definidas.

Um ponto importante é que as regras de preferência não são transitivas:
  • Se temos 4 proposições feitas A, B, C e D
  • Se a princípio todas elas estão aceitáveis (+) e indiferentes (=)
  • Se a proposição A é a melhor de todas (>)
  • Se a proposição B é melhor que A (A > B)


As probabilidades de seleção das proposições são:

  • A = 33.3%
  • C = 33.3%
  • D = 33.3%

 

Isso porque não existe nada explícito que diga que B é melhor que C e D.

 


Veja o código fonte do programa desenvolvido aqui.
 
Uma primeira abordagem é guardar o caminho por onde o agente já passou e, quando a decisão da direção tiver que ser tomada com todas as células possíveis vazias, o agente vai para a posição onde passou há mais tempo ou para uma posição que ainda não passou (no caso de haver mais de um agente no jogo).
 
Para implementar essa abordagem, inicialmente foi criada uma extensão "step" no estado principal para armazenar qual o passo atual do jogo: essa é a referência para indicar quando passou por uma determinada posição - maiores números indicam posições passadas mais recentemente:
 
Caminho percorrido pelo agente, iniciando na posição (5, 11) e terminando na posição (2, 15).
 
 
Foi criada também uma extensão "visited-position" para armazenar todas as posições visitadas - identificadas pelas coordenadas (x, y) - e o respectivo "step" da visita. No momento em que não havia posição com comida diretamente ao redor do agente - ou acessível a partir de um pulo - as extensões "visited-position" eram consultadas para escolher a posição de menor "step", ou seja, visitada a mais tempo, conforme as regras abaixo indicam:
 
 
Regras para definir qual posição vazia ir, escolhendo posição ainda não visitada ou visitada há mais tempo.
 
A regra "select*best*among-empty-already-visited" escolhe dentre duas, a posição vazia que foi visitada a mais tempo, ou seja, que tem o atributo "step" com menor valor, dentro da extensão "visited-position" correspondente. Já a regra "select*best*among-empty-just-one-visited" escolhe, dentre duas, a posição vazia que ainda não foi visitada - isso só ocorrerá se no jogo houver outro agente.
 
A principal dificuldade dessa abordagem foi determinar corretamente os pontos para atualizar a lista de posições já visitadas, bem como atualizar o contador de passos - para indicar quando passou por cada posição: dependendo das condições colocadas para essas regras, o programa entrava em loop, pois a cada execução eram alteradas as condições que elas mesmo testavam e, por conta disso, as mesmas regras eram novamente avaliadas.

O ponto determinado para atualizar a lista de posições visitadas foi o momento da aplicação do movimento definido, como apresentado nas regras abaixo:
 

Regras para atualização da extensão "step".
 

Algumas regras adicionais foram criadas para garantir que um pulo para uma posição com comida fosse sempre preferido a um passo para uma posição vazia: embora ambas tenham a mesma pontuação, o pulo privilegiaria situações em que o agente mais rapidamente pudesse atingir uma comida. Também foi acrescentada uma regra para permitir que fosse dado um pulo para uma posição com comida, mesmo que ele fosse no sentido oposto ao do último movimento. Essas regras estão a seguir:
 
 
Regras para performance no número de movimentos.
 

Com essas modificações em 20 execuções o número de passos médio foi de 325,15 com a pontuação média de 1143,75; o melhor tempo foi de 232 passos (1090 pontos) e o pior foi de 414 passos (1130 pontos). A maior pontuação foi de 1195 (301 passos) e a pior foi de 1090 pontos (232 passos).
 
Execução da variante que armazena o caminho percorrido pelo agente.
Execução da variante que armazena o caminho percorrido pelo agente.
 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer