Problema: Snakes and Ladder

A cada rodada um jogador joga uma moeda não viciada 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.

Diagrama de estados obtido para esse caso (Vale lembrar que alguns estados foram omitidos já que eles ou tem escada ou tem a cobra e na regra do jogo acabam nem ficando nesse estado):

* Todas as arestas desse grafo possuem peso 1/2

A matriz de transição de estados é mostrada na imagem abaixo (Nesta matriz os estados não foram omitidos como no diagrama de cima):

Agora para usarmos o power method foi feito este algoritmo em python:

Temos o vértice 1 como inicial, e isso pode ser observado na lista ini.
A partir disso fazemos uma multiplicação de matrizes na função calculoDist e para ter resultados em tempos diferentes foi usado a função tempoCalc.

Aqui um exemplo da saída nos primeiros passos:

Ao fim do passo 100 que foi considerado encontramos que a maior probabilidade é de estar no estado 30 (probabilidade de 0.011 aproximadamente) e a chance de ganhar o jogo, ou seja, estar no estado 36 é de 0.003 aproximadamente.