Trabalho 2: Ghostbusters


Introdução

O objetivo deste trabalho é projetar agentes que encontram fantasmas invisíveis num grid usando sensores, e depois tentam adivinhar a sua localização (os fantasmas não se movem).

O código base para este trabalho é formado pelos seguintes módulos, que podem ser baixados neste arquivo zip.

Ghostbusters
ghostbusters.py O código principal do jogo Ghostbusters.
tutorial.py Um script tutorial -- comece por aqui!
sensorDistributions.py Plug-in para a interface gráfica. Este arquivo pode ser ignorado.
gui.py Interface gráfica do Ghostbusters. Este arquivo pode ser ignorado.
graphicsUtils.py Utilidades gráficas. Este arquivo pode ser ignorado.
util.py Ferramentas para programar o Ghostbusters. Devem ser usadas para facilitar o seu trabalho.
Agentes
ghostbusterAgent.py Você irá implementar o método getAction() nesse arquivo.
staticInferenceModule.py Você irá implementar os métodos getGhostTupleDistributionGivenObservations() e getReadingDistributionGivenObservations() nesse arquivo.
dynamicInferenceModule.py (Este arquivo não deve ser modificado.)

 

O que entregar: Você irá preencher partes dos arquivos ghostbusterAgent.py e staticInferenceModule.py. Cada grupo deve enviar por e-mail esses dois arquivos. O e-mail deve conter o nome dos integrantes do grupo (até três).

Ghostbusters e Redes Bayesianas

O objetivo do agente no Ghostbusters é localizar e atirar nos fantasmas que estão escondidos no grid.  O agente pode obter informações sobre a localização dos fantasmas colocando sensores em posições do grid. Esses sensores retornam valores que estão correlacionados com a distância ao fantasma mais próximo.  O agente só pode tentar atirar uma vez para cada fantasma, e depois que ele acaba de atirar, os fantasmas tendo sido atingidos ou não, o jogo acaba.  Há duas tarefas de interesse nesse jogo.  Primeiro, o agente deve calcular distribuições de probabilidade para as posições dos fantasmas dadas as leituras dos sensores.  Este é um problema de inferência probabilística.  Segundo, o agente deve decidir, dadas suas crenças atuais sobre as posições dos fantasmas, se ele deve acrescentar um sensor ou atirar, e onde atirar.  Este é um problema de tomada de decisão. 

As regras do jogo (modo interativo) são:

A qualquer momento, o jogador pode fazer uma medição ou atirar.  Se ele quer fazer uma medição, deve clicar com o botão esquerdo na posição do grid em que ele quer colocar o sensor. Imediatamente, uma cor indicando a leitura do sensor será mostrada naquela posição.  O jogador não pode fazer outra medição na mesma posição.  Nem faria sentido porque nesse jogo os fantasmas não mudam de posição.  O valor retornado pelo sensor será VERMELHO (o mais perto), LARANJA, AMARELO, or VERDE (o mais longe), que indicam a grosso modo o quão perto o fantasma mais próximo está do sensor.  O modelo exato é dado em sensorDistributions.py.  O jogador perde um ponto por cada sensor colocado.

Quando o jogador decide atirar, deve clicar o botão BUST. Ele ficará vermelho para indicar que o jogo está no modo BUST.  O jogador pode então atirar um número de vezes igual ao número de fantasmas no grid.  Quando os tiros acabam, o jogador vê quais ele acertou e quais errou, e o jogo acaba.  Se o jogador atirar em um quadrado que tem mais de um fantasma todos eles são atingidos.  O jogador ganha 50 pontos para cada fantasma atingido.

Para se familiarizar com o Ghostbusters, você pode jogar alguns jogos.  Para iniciar o jogo, digite na linha de comando:

  python ghostbusters.py -w -q

Há muitas opções possíveis na linha de comando, que você pode ver usando a opção -h.  O flag -w mostra as posições verdadeiras dos fantasmas, e o flag -q desabilita o display de crenças do agente (já que você ainda não tem agente).

Clique com o botão esquerdo para colocar um sensor em um quadrado ou clique o botão BUST para começar a atirar.  Lembre que depois que você parar de atirar o jogo acaba, independente de você ter acertado ou não.  Você pode jogar em um grid maior usando a opção (-l medium).  Usando a opção (-l test), um grid de 3 por 3, tente colocar sensores nos 9 quadrados. Note que não há ruído na leitura dos sensores -- isto é, a informação dada pelo código RED, ORANGE, YELLOW, e GREEN é determinística dada a posição dos fantasmas.  Você pode mudar para sensores com ruído usando a opção (-s noisy). Olhe o arquivo sensorDistributions.py para ver como são as distribuições determínisticas e com ruído.  Deve ser mais difícil encontrar um fantasma usando a distribuição com ruído.  Jogue alguns jogos com grids de tamanho médio e sensores com ruído, sem ver a posição verdadeira dos fantasmas para ter uma ideia do que estamos pedindo para os agentes fazerem!

Passo 0 (0 pontos)  Siga o tutorial (tutorial.py), que dá uma introdução às classes e funções principais do programa.

Vamos formalizar o domínio do jogo através de uma rede bayesiana.  A estrutura da rede é mostrada abaixo (para um grid 2x3):

O nó G representa a tupla de posições dos fantasamas.  Você pode imaginar que existe uma variável aleatória para a posição de cada fantasma; esta formulação é equivalente.  Você pode pegar a distribuição a priori de tuplas de fantasmas usando o método Game.getInitialDistribution().  Em geral, há vários métodos do tipo Game.getX(), e os seus agentes e módulos de inferência terão objetos self.game.   Note que se houver somente um fantasma no jogo, a posição dele será representada através de uma tupla de uma posição, e não através de uma posição simples.  Há uma variável aleatória Ri,j para cada posição possível para o sensor (linha, coluna) = (i, j).  Cada leitura do sensor depende somente dessa posição.  A distribuição condicional de Ri,j dado um valor de G pode ser obtida através do método Game.getReadingDistributionGivenGhostTuple().

Passo 1 (4 pontos)  Tente rodar o código sem o flag -q. 

  python ghostbusters.py -w
  A GUI vai mostrar agora as crenças posteriores do agente sobre as posições dos fantasmas (G) dados os sensores revelados ({Ri,j=ri,j}).  Porém, como o agente ainda não foi programado, a função vai sempre retornar a probabilidade a priori pra cada posição.  Você pode controlar a probabilidade a priori chamando o código com o flag --prior priorstring, onde priorstring pode ser ou uniform (default) ou border. No seu código você pode usar essa informação chamando o método getInitialDistribution(). Olhe para o código do agente StaticKeyboardAgent, que é quem está jogando o jogo: ele delega a escolha de ação dele para um humano, e usa o código ExactStaticInferenceModule para calcular distribuições para a posição de cada fantasma.
Você vai implementar a função getGhostTupleDistributionGivenObservations() localizada na classe ExactStaticInferenceModule no arquivo staticInferenceModule.py.  Ela recebe um dicionário de pares posição/leitura e deve calcular a distribuição posterior da posição de um fantasma dadas as leituras dos sensores.  O objeto retornado deve ser um dicionário que tenha todas as tuplas (de uma posição) de todas as posições do grid como chaves e as probabilidades posteriores (de que que o fantasma esteja nessa posição) como valores.  Você pode tentar imprimir as observações enquanto você joga pra ver se elas parecem razoáveis.  Teste seu agente jogando com sensores sem ruído (-s deterministic, que é o default): 

  python ghostbusters.py -s deterministic
Você também pode usar o flag -w para mostrar a posição verdadeira do fantasma para depurar o código:  

  python ghostbusters.py -w -s deterministic
Quando você estiver convencido que o código está funcionando, tente usar sensores com ruído(-s noisy): 

  python ghostbusters.py -w -s noisy
Note que você pode ignorar os valores das variáveis não observados quando você for calcular a probabilidade posterior de G. Isto é, você pode lidar com a rede da esquerda como se ela fosse igual à rede da direita:
              
Dicas:

Passo 2 (3 pontos) Você pode colocar múltiplos fantasmas no grid com a opção -k.  Jogue um jogo com as opções -k 2 -q:  

  python ghostbusters.py -w -q -k 2
Agora você deve verificar se a sua inferência funciona corretamente para o caso de múltiplos fantasmas; ela pode já estar correta, dependendo de como você programou o passo 1 (você deve entregar apenas a versão mais geral, que funcione para o passo 2).  Antes G era essencialmente a posição de um fantasma, mas agora é uma tupla de posições, então temos que calcular a distribuição posterior das tuplas.  Por exemplo, se temos 2 fantasmas, podemos calcular a probabilidade posterior de (fantasma1, fantasma2) estarem nas posições ((0,0), (0,0)), ((0,0), (0,1)), e assim por diante.  Como os fantasmas são equivalentes, não saberemos que fantasma está em que posição, mas saberemos quais k posições estão ocupadas.  Quando há múltiplos fantasmas, a GUI vai mostrar o número esperado de fantasmas em cada posição.  Há um método na classe StaticGhostbustersAgent (quase toda abstrata) chamado getExpectedGhostCounts() que calcula contagens esperadas de fantasmas a partir da distribuição posterior de G; tente entender esse método.  No caso de um único fantasma, as contagens esperadas de fantasmas são as crenças que calculamos em getGhostTupleDistributionGivenObservations().  No caso de k fantasmas, porém, a soma do número esperado de fantasmas pra todas as posições será k.  Por exemplo, você pode ter que a probabilidade de ((0,0), (0,1)) é 0.5 e a probabilidade de ((0,1), (0,0)) é 0.5, nesse caso (0,0) e (0,1) terão 1.0 como contagens esperadas.  Rode o seu código com 2 ou 3 fantasmas. Tente entender porque a inferência fica mais lenta quando aumentamos o valor de k rodando: 

  python ghostbusters.py -w -k 2

  python ghostbusters.py -w -k 3

Passo 3 (3 pontos)

Agora você vai programar um novo agente, que toma decisões usando os resultados da inferência.  A decisão mais simples a ser tomada é pra onde atirar dadas as crenças atuais do agente sobre as posições do fantasma (G).  Este cálculo é basicamente um expectimax, mostrado no diagrama abaixo.  No nó MAX raiz, você pode selecionar qualquer uma das opções de atirar (tupla de k quadrados), e a utilidade esperada (score) é o máximo das utilidades esperadas de cada ação possível.  Cada ação irá produzir uma utilidade esperada que é o número esperado de fantasmas naqueles quadrados vezes o score por fantasma, GHOST_SCORE.

Porém, o agente não precisa necessariamente atirar.  Ao invés disso, ele pode colocar um novo sensor, revelando uma nova leitura, e aí atirar.  Nesse caso, o agente teria várias ações possíveis disponíveis, correspondendo a colocar um sensor em cada posição vazia.   Cada ação leva a um nó de chance com a distribuição P(Ri,j | {r}), que descreve as crenças do agente sobre que leitura aparecerá naquela posição, dadas as leituras anteriores. Para cada nova leitura, teremos uma opção ótima para atirar e uma nova utilidade esperada.   O seu agente deve normalmente escolher a ação que revela a leitura que tem o maior ganho esperado em utilidade máxima esperada.  Quando esse ganho for menor do que 1 ponto, ele deve parar de colocar sensores e atirar.   Quando decide ações, o agente não avalia cenários em que ele coloca múltiplos sensores (mas ele pode acabar colocando múltiplos sensores).  Logo, o processo de decisão não é ótimo; o agente ótimo consideraria explicitamente a possibilidade de colocar mais de um sensor antes de atirar.  Em outras palavras, o agente construirá árvores de profundidade 2 para selecionar uma ação, mesmo quando o caminho ótimo tiver profundidade maior.

A árvore de busca para esse processo é representada no diagrama a seguir:

Você deve construir um agente que não apenas calcula crenças posteriores, mas também toma decisões, usando árvores de profundidade 2 (uma ação de colocar sensor + uma ação de atirar).  Você precisará implementar StaticVPIAgent.getAction() em ghostbusterAgent.py e ExactStaticInferenceModule.getReadingDistributionGivenObservations() em staticInferenceModule.py .  Talvez seja mais fácil pensar no caso de um fantasma primeiro pra depois generalizar pra vários fantasmas, mas o código no final terá que ser o mesmo.  Teste o seu agente VPI com a opção (-p vpi), primeiro usando sensores determinísticos (-s deterministic): 

  python ghostbusters.py -w -p vpi -s deterministic
e depois usando sensores com ruído (-s noisy):  

  python ghostbusters.py -w -p vpi -s noisy
Ele deve funcionar bem (melhor que 90%) no caso determinístico, mas pode às vezes tomar decisões não-ótimas no caso com ruído, por causa da limitação na altura da árvore. Teste também com mais de um fantasma (NOTA: deve ficar mais lento): 

  python ghostbusters.py -w -p vpi -k 2
Dicas: