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).
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 -wA 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.
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 deterministicVocê 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 deterministicQuando você estiver convencido que o código está funcionando, tente usar sensores com ruído(
-s noisy
):
python ghostbusters.py -w -s noisyNote 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:
Counter
em util.py
extende a classe built-in dictionary. Isso significa que você pode retornar um Counter
sempre que um dicionário for esperado.
Essa classe tem muitas funções que são úteis e farão você economizar tempo.self.game.getInitialDistribution()
self.game.getGhostTuples()
python ghostbusters.py -s deterministic --fixrandomseed --prior bordere clicar nos botões do canto esquerdo superior e canto esquerdo inferior, as contagens esperadas para os outros dois cantos devem ser
0.22
.
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 2Agora 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 deterministice depois usando sensores com ruído (
-s noisy
):
python ghostbusters.py -w -p vpi -s noisyEle 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 2Dicas:
self.observations
self.getExpectedGhostCounts()
na classe StaticGhostbusterAgent
em ghostbusterAgent.py
, que opcionalmente recebe um conjunto de observações (o default é self.obervations
)
e retorna o número esperado de fantasmas em cada quadrado baseado nessas observações. Porém a correção do código será baseada no funcionamento correto e não na eficiência.python ghostbusters.py -p vpi -s deterministic --fixrandomseed --prior bordero seu agente deve ser capaz de acertar o fantasma depois de colocar três sensores.