Snake and Ladders é um famoso jogo de tabuleiro em que a cada rodada um jogador joga uma moeda não viciada e avança 1 casa se obtiver cara ou avança 2 casas se obtiver coroa. Se o jogador para no pé da escada, então ele imediatamente sobe para o topo da escada. Se o jogador cai na boca de um cobra então ele imediatamente escorrega para o rabo. O jogador sempre inicia no quadrado de número 1. O jogo termina quando ele atinge o quadrado de número 36.

snakeandladders.PNG

Figura 1: Tabuleiro de Snake and Ladders com 36 casas

Uma aplicação da Teoria dos Grafos consiste em modelar o jogo utilizando uma Cadeia de Markov, especificando seu diagrama de estados. Além disso, é possível calcular as probabilidades de vitória de um jogador, aplicando a Lei da Caminhada Aleatória (Power Method) e também definir quais casas do tabuleiro (estados) são mais prováveis de serem acessados.

I) O GRAFO
Em nosso jogo, o grafo pode ser definido considerando cada casa do tabuleiro como um vértice, totalizando 36 vértices e cada jogada possível definindo uma aresta. Por exemplo, a partir da casa 1, correspondente a CodeCogsEqn (1).gif temos:

a) Se sair cara, o jogador vai para a casa 15, correspondente a CodeCogsEqn (2).gif
b) Se sair coroa, o jogador vai para a casa 3, correspondente a CodeCogsEqn (3).gif

Fazendo isso para todos os vértices atingíveis, temos o grafo CodeCogsEqn (4).gif, que está no código em Python abaixo:


import networkx as nx

def SnakeAndLadders():

 g = nx.Graph()
 for i in range(0, 36):
 g.add_node(i) #cria os 36 vértices do grafo

 #Criação das arestas
 g.add_edges_from([(0, 14), (0, 2)])
 g.add_edges_from([(2, 3), (2, 6)])
 g.add_edges_from([(3, 6), (3, 5)])
 g.add_edges_from([(5, 6), (5, 7)])
 g.add_edges_from([(6, 7), (6, 26)])
 g.add_edges_from([(7, 26), (7, 9)])
 g.add_edges_from([(9, 10), (9, 11)])
 g.add_edges_from([(10, 11), (10, 12)])
 g.add_edges_from([(11, 12), (11, 13)])
 g.add_edges_from([(12, 13), (12, 14)])
 g.add_edges_from([(13, 14), (13, 15)])
 g.add_edges_from([(14, 15), (14, 3)])
 g.add_edges_from([(15, 3), (15, 28)])
 g.add_edges_from([(28, 29), (28, 30)])
 g.add_edges_from([(29, 30), (29, 29)])
 g.add_edges_from([(30, 29), (30, 32)])
 g.add_edges_from([(32, 11), (32, 34)])
 g.add_edges_from([(34, 35)])

 return (g)

O grafo gerado:Graph.png

Figura 2: Grafo do jogo Snake and Ladders

II) MATRIZ DE ADJACÊNCIAS
Com o grafo definido, é possível determinar a matriz CodeCogsEqn (5).gif, tal que:

CodeCogsEqn (8).gif, se CodeCogsEqn (9).gif é adjacente a CodeCogsEqn (10).gif | CodeCogsEqn (11).gif, caso contrário

Em Python, utilizando a biblioteca NetworkX , a função:

nx.adjacency_matrix(G)

retorna a matriz CodeCogsEqn (12).gif, facilitando a programação.

III) GRAU DOS VÉRTICES
Computar a matriz  CodeCogsEqn (13).gif depende apenas da determinação do grau de cada vértice CodeCogsEqn (14).gifdefinido como o número de vezes em que um vértice CodeCogsEqn (15).gif é extremidade de uma aresta. Em Python, outra função da biblioteca NetworkX pode ser usada :  

G.degree(v)

retorna o grau do vértice CodeCogsEqn (15).gif.

Conhecendo o grafo CodeCogsEqn (16).gif, sua matriz de adjacências CodeCogsEqn (12).gif e sua lista de graus CodeCogsEqn (17).gif , a matriz  CodeCogsEqn (18).gif é facilmente computada, como mostra o código abaixo:

import numpy as np
import networkx as nx
from Graph import SnakeAndLadders

G = SnakeAndLadders() #carrega o grafo que descreve o jogo

def MatrizTransicao(G):
 MatrizA = nx.adjacency_matrix(G) #retorna a matriz de adjacencia A
 Delta = np.zeros((36,36)) #cria matriz 36 x 36 preenchida com zeros

 for i in range(0,36):
 if (G.degree(i)==0): #evita divisão por zero
 j = 0
 else:
 j = 1 / float (G.degree(i)) # 1/ grau do vértice
 Delta [i][i] = j # preenche a diagonal da matriz Delta

 MatrizP = MatrizA * Delta #cria matriz de transição P
 return (MatrizP)

IV) DÍGRAFO: DIAGRAMA DE ESTADOS

A matriz CodeCogsEqn (18).gif especifica um diagrama de estados (grafo direcionado) com pesos nas arestas, em que, cada peso, corresponde à probabilidade CodeCogsEqn (21).gif de, numa caminhada aleatória, ao sair de determinado vértice CodeCogsEqn (19).gif chegar a outro vértice CodeCogsEqn (20).gif.

V) POWER METHOD

Numa CMH é possível determinar como sua distribuição de probabilidades se comporta ao longo do tempo,

CodeCogsEqn.gif
CodeCogsEqn (22).gif:probabilidade de, num passo CodeCogsEqn (23).gif, estar num estado CodeCogsEqn (24).gif

A Lei da Caminhada aleatória define que, para uma CMH homogênea, uma distribuição estacionária inicial CodeCogsEqn (25).gif, o comportamento das probabilidades é:

CodeCogsEqn (26).gif

No caso do nosso jogo, a distribuição estacionária inicial é:

CodeCogsEqn (27).gif
Isso porque o jogo sempre inicia na casa 1, ou seja, no estado CodeCogsEqn (28).gif. Considerando esta distribuição e a matriz de transição já conhecida CodeCogsEqn (29).gif, o código em Python abaixo utiliza o Power Method para CodeCogsEqn (30).gif:

from MatrizP import MatrizTransicao
from Graph import SnakeAndLadders
import numpy as np

G = SnakeAndLadders() #carrega o grafo que descreve o jogo
P = MatrizTransicao(G) #carrega a matriz de transição P

#Distribuição estacionária inicial
w = np.zeros(36)
w[0] = 1

k = 100 #100 passos
Pn = P

# P ^ k
for i in range (0, k):
Pn = np.dot(Pn,P)
w = w * Pn #w0 x P^n

Desta forma, considerando 100 passos, a probabilidade de um jogador vencer o jogo, ou seja, atingir o estado CodeCogsEqn (31).gif é CodeCogsEqn (32).gif. Além disso, através do método

np.argmax( )

conseguimos determinar o vértice com maior probabilidade de acesso, que, no caso do nosso jogo é CodeCogsEqn (33).gif, ou seja, a casa 7 do tabuleiro.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s