Trabalho 1
Contexto
Snakes and Ladders é um antigo jogo de tabuleiro indiano, que hoje faz sucesso no mundo todo. Ele é jogado por dois ou mais jogadores em um mapa quadriculado onde cada um dos quadrados possui um número. Uma certa quantidade de "escadas" (ladders) e "cobras" (snakes) é desenhada no tabuleiro, conectando dois quadrados específicos do mapa.
O objetivo do jogo é ir até o final do mapa de acordo com o número tirado na moeda (um ou dois), e assim, avançando as casas. Caso caia em alguma casa onde está a base de uma escada, o jogador a sobe até a próxima posição - o semelhente acontece com as cobras, com a diferença de que o jogador desce para uma posição anterior caso caia numa casa onde está desenhada a cabeça da cobra.
Objetivos
Para este projeto há três objetivos especificados:
1. Apresentar o diagrama de estados da Cadeia de Markov que representa o jogo, computando, para isso, a matriz de transição de estados P.
2. Desenvolver um script em Python para calcular a distribuição estacionária da Cadeia de Markov homogênea em questão e responder: Qual a probabilidade de um jogador vencer o jogo no longo prazo? Considerando, para esse cálculo, k = 100 um número suficiente de iterações no Power Method. Além disso, quais estados são os mais prováveis de serem acessados?
3. Especificar a matris P (P_barra) referente ao modelo Pagerank considerando alpha = 0.1. Considerando também k = 100, aplicar o Power Method e comparar os resultados obtidos com os do item 2, e checar se as distribuições estacionárias são diferentes.
Uma Cadeia de Markov é um caso particular de processo estocástico com estados discretos, com a propriedade de que a distribuição de probabilidade do próximo estado depende apenas do estado atual e não da sequência de eventos que se procedem.
O Power Method é um modo iterativo para obter a distribuição de probabilidades dos estados num tempo k.
PageRank é o algoritmo utilizado pela ferramenta de busca Google para posicionar websites entre os resultados de suas buscas.
Para este projeto há três objetivos especificados:
1. Apresentar o diagrama de estados da Cadeia de Markov que representa o jogo, computando, para isso, a matriz de transição de estados P.
2. Desenvolver um script em Python para calcular a distribuição estacionária da Cadeia de Markov homogênea em questão e responder: Qual a probabilidade de um jogador vencer o jogo no longo prazo? Considerando, para esse cálculo, k = 100 um número suficiente de iterações no Power Method. Além disso, quais estados são os mais prováveis de serem acessados?
3. Especificar a matris P (P_barra) referente ao modelo Pagerank considerando alpha = 0.1. Considerando também k = 100, aplicar o Power Method e comparar os resultados obtidos com os do item 2, e checar se as distribuições estacionárias são diferentes.
Uma Cadeia de Markov é um caso particular de processo estocástico com estados discretos, com a propriedade de que a distribuição de probabilidade do próximo estado depende apenas do estado atual e não da sequência de eventos que se procedem.
O Power Method é um modo iterativo para obter a distribuição de probabilidades dos estados num tempo k.
PageRank é o algoritmo utilizado pela ferramenta de busca Google para posicionar websites entre os resultados de suas buscas.
Execução
Para o desenvolvimento do trabalho, foi utilizada a linguagem Python, a biblioteca NumPy e a IDE Spyder. O código foi escrito primeiramente utilizando a ferramenta Notepad++.
 |
| Código para cálculo do Power Method |
 |
| Matriz de Adjacências ixj contendo a probabilidade de se avançar da casa i para a j |
 |
| Tabela de Probabilidades já ordenada por casa. |
Analisando então a Tabela de Probabilidades, podemos concluir que a probabilidade de se ganhar o jogo a longo prazo é de 4,5%, e a casa mais provável de ser acessada é a de número 30, seguida das casas 32 e 32.
Comentários
Postar um comentário