-
Notifications
You must be signed in to change notification settings - Fork 0
Approach adopted
Apresentar o jogo conforme a definição feita em Mundo do Wumpus, bem como adicionar a esta implementação um conjunto de aditivos.
Os seguintes aditivos foram apresentados como proposta de trabalho:
- Adicionar múltiplos jogadores colaborativos;
- Estes jogadores podem ser humanos ou agentes;
- Adicionar uma interface gráfica (Java);
- Adicionar uma comunicação por mensagens entre as bases de conhecimento dos agentes e dos jogadores;
- Adicionar uma comunicação entre a base de conhecimento de mensagens com a interface em java;
- Aumentar o tamanho da matriz do tabuleiro;
- Manter as características básicas principais do jogo proposto no livro.
Assim sendo, a seguir apresentamos detalhadamente as modificações feitas:
O jogador, também conhecido como agente, está dentro de uma caverna, na qual ele possui visão limitada ao seu redor. Dentro desta caverna há um ouro, buracos e um monstro, o Wumpus. O objetivo do jogo é matar o monstro, localizar o ouro e de posse do ouro, voltar até a entrada da caverna. Se cair num buraco o jogador morre, se for comido pelo Wumpus. Só há uma flecha para o jogador matar o monstro, não a desperdice.
Os personagens são:
- O Wumpus, o monstro horripilante;
- Vários jogadores humanos;
- Vários jogadores robos, também conhecidos como agentes.
O ambiente é disposto da seguinte maneira:
- Define-se uma matriz quadrada de tamanho variável;
- Os agentes e os jogadores iniciam o jogo na posição [1,1], e deverão terminar seu desafio neste mesmo lugar;
- Dentro desta matriz, define-se a posição do Wumpus (estática), que não se modifica no decorrer do jogo;
- Dentro desta matriz, também se encontram 3 buracos, que não se modificam no decorrer do jogo, aqui há uma variação pois o jogo original proposto pelo livro sugere um cálculo para determinação do número de buracos, mas por questões práticas utilizamos um número fixo de buracos;
- Por fim há dentro da matriz uma posição onde se encontra o ouro, que também é definida e não se modifica no decorrer do jogo;
- Nenhum objeto fixo (Wumpus, buracos e ouro) da matriz poderá ser definido no mesmo local de um outro objeto ao mesmo tempo;
- Todos os objetos fixos da matriz são dispostos randomicamente em suas posições.
Os agentes possuem 5 sensores (sentidos), são eles:
- Sente o mau cheiro exalado pelo Wumpus, nas posições da matriz (horizontais ou verticais) ao seu redor ;
- Percebe uma brisa ao redor dos buracos, nas posições da matriz (horizontais ou verticais) ao seu redor ;
- Visualiza um brilho ao redor do ouro, nas posições da matriz (horizontais ou verticais) ao seu redor ;
- Ouve um ruído de "bum", indicando que encostou em uma parede (horizontais ou verticais) ao seu redor;
- Ouve um grito quando o Wumpus é morto pela sua flecha, este grito no jogo proposto no livro pode ser ouvido em qualquer lugar da caverna, mas decidimos criar uma dificuldade a mais fazendo com que apenas o agente que atirou preste atenção e ouça o grito interpretando-o como a morte do monstro, assim os outros jogadores ou agentes só saberão da morte do monstro caso sejam informados via mensagem.
A pontuação do jogo originalmente era bastante simples, e foi alterada em nossa proposta para tornar as decisões tomadas pelos agentes ou jogadores mais ou menos importantes conforme suas percepções. A pontuação na realidade está mapeada como energia, de forma que todos os agentes ou jogadores iniciam o jogo com um valor de 1000, e vão tendo energia somada ou reduzida de acordo com suas ações.
Assim a pontuação (pontos de energia) é distribuída como a seguir:
+1000 pontos por escalar a caverna e sair com o ouro; -1000 pontos se cair em um buraco ou ser comido pelo Wumpus;
- -10 pontos ao usar a flecha;
- -10 pontos se estiver atuando em uma casa com fedor e com vento;
- -5 pontos se estiver atuando em uma casa apenas com fedor;
- -5 pontos se estiver atuando em uma casa apenas com vento;
- -2 pontos se estiver atuando em uma casa sem percepções de vento, fedor ou brilho;
- -1 se tentar atirar uma flecha sem tê-la;
- -1 se bater em uma parede;
- -1 se esbarrar no Wumpus morto;
- -1 se tentar sair antes de pegar o ouro;
- -1 por qualquer outra ação tomada;
- 0 pontos se acertar o Wumpus com um tiro;
- 0 pontos se estiver atuando em uma casa com brilho, prevalecendo as casas com fedor e/ou vento.
As ações propostas aos agentes ou jogadores são:
- Mover-se de posição em posição da matriz;
- A movimentação do agente ou jogador na matriz, deve ocorrer apenas na horizontal e na vertical, não sendo permitido movimentações na diagonal;
- A movimentação só ocorre de uma em uma iteração, não sendo permitido executar saltos;
- O agente pode encostar nas paredes, e repetirá a ação;
- O agente pode esbarrar no cadáver do Wumpus, e repetirá a ação;
- O agente pode atirar uma flecha em linha reta, na direção para a qual o agente está virado;
- A flecha se movimenta até encontrar uma parede ou até acertar o Wumpus;
- A flecha não acerta seus companheiros e passa por cima dos buracos e do ouro;
- O agente ou jogador só possui uma única flecha para cada um;
- O agente ou jogador morre se cair em um buraco, se for comido pelo Wumpus ou se sua energia acabar.
- O agente ou jogador, quando está na posição [1,1], pode escalar até a saída da caverna, se ele ou algum outro agente ou jogador já estiver de posse do ouro.
Abaixo uma figura da interface do jogo, resultante de nosso trabalho:
Fica claro na figura acima apresentada que a interface foi implementada em uma ferramenta mais apropriada para este fim do que o Prolog, que no nosso caso a escolha desta ferramenta foi baseada na existência de uma biblioteca nativa do próprio SwiProlog para interface com o Java (JPL.jar), e pela capacidade de interpretação da linguagem JSON por ambas as ferramentas.
Os detalhes desta interface estão apresentados no relatório da interface em: Interface gráfica
Para promover uma integração perfeita entre as ferramentas de interface em Java e do núcleo do jogo no SWIProlog, partimos do conceito de que toda navegação, inteligência e controle do jogo estão no núcleo Prolog, cabendo à interface apenas a função de representação gráfica das ações, percepções e resultados fornecidos pelo núcleo.
Neste sentido algumas estratégias foram adotadas dentro do código em Prolog para que tal comunicação fosse possível, conforme abaixo:
Criação de um conjunto de predicados para geração e transmissão das informações do núcleo em Prolog para a interface em Java:
- json_inic -> para inicialização da matriz e seus objetos;
- json_mat -> para retornar o tamanho da matriz;
- json_fdrs, json_blhs e json_vnts -> para posicionamento dos fedores, brilhos e ventos;
- json_inic_agt -> para inicializar cada agente e retornar suas percepções inicias;
- json_inic_hum -> para inicializar cada jogador humano e retornar suas percepções inicias;
- json_passo -> para retornar o resultado de cada ação de um dado jogador ou agente após um passo do jogo (após executar sua ação);
- json_msg -> para retornar o "pool" de mensagens de cada agente ou jogador para a interface após um passo do jogo (após executar sua ação);
- json_fim -> para retornar o fim do jogo.
Criação de um servidor web para envio das informações no formato JSON:
server(Port) :- http_server(http_dispatch, [port(Port)]).
Criação de uma série de predicados especiais para filtragem das informações a serem enviadas de modo que sempre ocorra um retorno no formato adequado, mesmo quando não há informação a ser enviada; Criação de um conjunto de predicados para execução especificamente pela interface Java, com a finalidade de simples execução do jogo:
- main4j(M,KB,KBH) -> execução principal e inicialização do jogo com uma matriz de tamanho 'M', 'KB' agentes (jogadores robôs) e 'KBH' jogadores humanos;
- passo4j(A,O,KB,T) -> execução de cada passo para executar a ação 'A', em uma orientação 'O' de um jogador ou agente do tipo 'T' identificado por 'KB';
Apesar do jogo ser executado em uma interface visual Java, o núcleo em Prolog permite sua execução de forma direta pelo console do SWIProlog, bastando executar os predicados abaixo:
A primeira tarefa para a solução do problema está na definição de símbolos para identificar cada proposição dentro do nosso domínio. Ou seja precisamos de um Vocabulário de Símbolos Proposicionais (VSP).
O livro utiliza-se das letras ('P', 'A', 'B', 'W', 'G','OK', 'S', 'V'), que são as iniciais das palavras em Inglês "pit, agent, breese, wumpus, gold/gliter, ok, stench, visited" respectivamente. Porém achei mais conveniente utilizar uma simbologia em Português e com três letras de abreviatura, ficando definido assim:
- WPS = Wumpus;
- AGT = Agente;
- AUR = Ouro;
- BLH = Brilho;
- PPA = Passei por aqui (posição visitada);
- BRC = Buraco;
- VNT = Vento ou brisa;
- FDR = Fedor;
- PLV = Posição livre;
- FCH = Flecha;
- BUM = Barulho da parede;
- GRT = Grito do Wumpus;
- PRD = Parede.
- e outras mais.
Além disso, definimos como valores usuais dentro de nossos fatos: sim e nao (não).
Também se faz necessário definir o conjunto de ações e orientações para o agente, então estamos definindo 4 atributos importantes de direção, são eles:
Ações:
- mover;
- atirar;
- pegar_ouro
- sair;
- impasse;
- esbarrão;
- parede.
Orientações:
- norte;
- sul;
- leste;
- oeste;
- aqui.
E algumas informações a mais a respeito dos jogadores:
- agente;
- humano.
A função principal destas abreviaturas é servir como base para a definição do VSP e de marcação para as movimentações do jogo.
Isso feito, definiremos também uma simbologia para a nossa matriz.
Seja então a matriz do jogo uma matriz 4x4, definida no livro, mas que para nossa implementação do jogo foi ampliada para uma função M(m), temos então:
Matriz original do jogo conforme o livro:
Matriz ampliada para um tamanho variável 'm':
Trabalharemos com coordenadas (linha, coluna) e os atributos posicionáveis possuem como ponto de referencia a posição [1,1] da matriz M,
Outro aspecto importante e que foi passado em sala de aula, diz respeito à separação das bases de conhecimento, uma para cada jogador ou agente, outra para o jogo () em si e uma para a comunicação por meio de mensagens.
Assim define-se então que as bases de conhecimento são:
- KB = 0 -> Base de conhecimento do jogo onde são armazenadas informações como: tamanho da matriz, disposição dos artefatos na matriz, e as suas regras;
- KB > 0 -> Base de conhecimento dos 'n' jogadores ou agentes, sendo primeiramente os 'KB' agentes e a seguir os 'KBH' jogadores humanos, por exemplo, para 2 agentes e 2 humanos teremos: KB = 1 para o primeiro agente, KB = 2 para o segundo agente, KB = 3 para o primeiro jogador e KB = 4 para o segundo jogador;
- KB = -1 -> Base de conhecimento para troca de mensagens e comunicação com a interface, onde são guardadas as mensagens enviadas e processadas as respostas de leitura destas mensagens.
É importante lembrar que para diferenciar cada KB, estas informações são armazenadas como uma das aridades (a primeira) das proposições e regras de cada KB.
Vale salientar que foram também definidos alguns proposições e regras gerais os quais são acessíveis por qualquer KB por não possuírem essa restrição em suas aridades.
Esta divisão é interessante na medida que o jogo pode evoluir para ações e reações de outros personagens, por exemplo se quisermos tornar o Wumpus reativo também.
Observamos que o ponto de vista das KBs dos jogadores ou agentes é inverso ao ponto de vista do KB do jogo, e essa constatação nos mostra que o jogo será mais inteligente tanto quanto for capaz de reconhecer as ações e reações entre a KB do jogo e as KBs dos jogadores ou agentes e vice-versa.
É interessante também definir um objetivo para que as ações sejam direcionadas conforme o que se quer. Assim sendo os objetivos levantados estão associados às ações anteriormente mostradas, são eles:
- WUMPUS = Matar o Wumpus;
- OURO = Pegar o ouro;
- IMPASSE = Quando não há mais opções;
- SAIR = Sair da caverna.
A abordagem utilizada para a troca de mensagens entre os agentes foi feita de forma colaborativa e por meio de "broadcast", assim cada agente ou jogador deve informar todas as suas descobertas, a cada jogada, para todas outras KBs exceto para a KB do jogo (KBs diferentes de zero).
Assim foi necessário criar uma estrutura de dados dinâmica, conforme abaixo, para armazenar as mensagens dentro da KB de mensagens:
msg(, <Identificador único da mensagem>, , , , <Conteúdo da mensagem>)
Assim foram definidos alguns predicados importantes, são eles:
- novo_id(NID) -> Cria um novo identificador para registrar cada mensagem;
- envia_msg(KB,broadcast,TMSG,LMSG) -> Função para o envio da mensagem;
- le_msg(KBD) -> Função para a leitura das mensagens;
- grava_msg(KBD,KBO,TMSG,LMSG) -> Função para gravação da mesnagem;
- msg_broadcast(KBO,KBD,TMSG,LMSG) -> Efetiva o broadcast da mensagem para todas as KBs <> 0, onde KBO é a KB origem, KBD é a KB destino, TMSG é o tipo de mensagem e LMSG é a mensagem em si;
O envio das mensagens ocorre sempre que uma ação é concluída e suas percepções de um agente ou jogador são processadas.
A leitura das mensagens recebidas é feita sempre antes do processamento de decisão parada executar uma ação por parte de um agente ou jogador.
A partir de agora temos um agente capaz de executar ações, porém sabe-se que os agentes podem se comportar de forma diversa, podemos então ter:
- AGENTE REATIVO PURO;
- AGENTE COM MODELO DE MUNDO;
- AGENTE BASEADO EM OBJETIVO.
Um agente reativo puro, não é capaz de avaliar situações passadas, isso significa dizer que ele não sabe o que ocorreu, se pegou o ouro ou não, e etc. Então, para que o agente possa guardar informações de um certo passado, é necessário que ele possua uma representação do mundo.
Então necessita-se ter sentenças sobre o estado atual do mundo, por exemplo indicando que o agente está com o ouro. Este modelo deve ser atualizado quando o agente receber novas percepções e quando realizar ações.
A solução para esta questão está no Cálculo Situacional.
Isto significa dizer que a cada situação (momento determinado), o agente executa uma ação e ao executar esta ação, ele percebe novos fatos, que são usados para avaliar a próxima ação e assim sucessivamente. Então há regras que ligam a sequencia de percepções às ações do jogo, estas regras assemelham-se a reações.
As ações a serem tomadas dependem das não somente das percepções de cada indivíduo mas também da integração deles entre si por meio do "pool" de mensagens adotado para o jogo gerado informações na KB de cada agente ou jogador para informar desde a sua localização e dos seus objetivo, até suas inferências, em um determinado momento do jogo.
Estas ações de inferência a partir da percepção do agente estão baseadas em um predicado especial definido para: no caso do agente decidir sobre qual a melhor ação a ser tomada; e para o caso do jogador determinar o risco de sua decisão. A partir desta sequencia estratégica os trajetos serão formados durante o jogo.
A seguir uma sequência básica das preferências dos agentes dentro da estratégia adotada:
- Prefere posições não visitadas,
- Prefere posições cujo risco de morte é menor,
- Prefere atirar se já inferiu o monstro, exceto se já atirou,
- Pode atirar a esmo se o risco de morte for grande,
- Prefere posições visitadas livres em caso de não haver outra possibilidade não visitada,
- Realiza inferências com base nas mensagens recebidas e no seu próprio comportamento,
- Dá prioridade ao pegar o ouro e só em caso eventual mata o monstro,
- Procura uma saída usando posições livres e já visitadas.
MANUAL:
O manual do jogo está disponível em: