Snake and Ladders, usando Markov Chain para entender um jogo.

Snake and Ladders, ou Cobras e Escadas em português, é um jogo de tabuleiro originário da índia. Acho que é parecido com a maioria dos jogos de tabuleiros de hoje em dia que so se anda para frente, só mudando a temática, enquanto no Snake and Ladders, você usa uma escada para avançar casas e uma cobra te engole e, bem, você sai pela outra extremidade casa atras, no jogo da vida você pega carona para frente, ou volta no tabuleiro como punição. No wikipedia tem um tabuleiro dele nas antigas.

02

Mas qual o interesse nisso? Olha como o mundo científico é um lugar pequeno. Lembra do senhor John Conway, do jogo da vida que discutimos aqui? Esse mesmo cara escreveu um livro chamado Winning Ways for your Mathematical Plays, e nesse livro ele usa um tipo de cadeia de Markov chamado Absorbing Markov chain para modelar esse joguinho, e aqui vamos olhar esse exemplo.

Bem o jogo é simples, temos esse tabuleiro, mas na nossa simulação vamos usar um tabuleiro um pouco modificado, um com 100 casinhas. Bem para facilitar uma representação no R, vamos usar setinhas ao invés de Escadas e cobras, ou seja se você cair uma no início da seta(lado contrário a ponta) da seta, você vai para onde ela ta apontando, se você cair na ponta da seta, continue sua vida.

Então aqui está nossa representação.

01

Então todo mundo começa com o peão fora do tabuleiro, então joga um dado de 6 faces e vê onde vai parar. Acontece que podemos ver isso como um processo markoviano, em que cada posição no tabuleiro é um estado do sistema, e temos, a cada jogada, as respectivas chances de mudar de estado. So que a gente não vai para qualquer estado, a gente tem uma chance em seis de mover de estado do quadradinho atual para o próximo, uma chance em seis de andar 2 casas, 1 chance em seis de andar 3 casas, até seis.

Isso pode ser representado por uma matriz de estados, com 100 linhas e 100 colunas, uma para cada posição do jogo. 101 na verdade, poque vamos supor que o estado 0 é quando o jogo não começou, o peão não esta ainda no tabuleiro, mas ele tem que começar de algum lugar, que é a posição zero. Assim, a primeira linha vai ser a seguinte.

> M[1,] 0 1 2 3 4 5 6 7 8 9 0.0000000 0.1666667 0.1666667 0.1666667 0.0000000 0.1666667 0.1666667 0.0000000 0.0000000 0.0000000 . . . 90 91 92 93 94 95 96 97 98 99 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 100 0.0000000

Vou suprimir um pouco dos resultado para ficar mais fácil de entender.
Mas veja que essa é a primeira linha da matriz, e ela ta dizendo que uma vez que estamos na posição zero, temos uma chance em seis, 1 divido por 6 que da 0.1666667 arredondando, podemos ir para na casa 1, 2 ,3, 5 ,6. Opa, porque o 4 está com zero de chance? Porque, se você olhar no tabuleiro ali em cima, temos que quando a gente cai no 4, a gente pega a escadinha e vai parar na casa 14.

Podemos colocar esse números na nossa representação gráfica do jogo.

02

Certo, mas a primeira jogada é fácil, mas daqui pra frente que vem a parte bolada.
Se você está na casa 3, e jogar o dado de 6 faces denovo, existem 6 possibilidades ainda.

02

Mas na verdade se a gente jogar o dado duas vezes, podemos saber qual a chance de parar em qualquer lugar ainda, simplesmente multiplicando as chances de cada valor de cada um dos dois dados jogados.

01

Ja vimos isso aqui, em probabilidade condicional. So que a matriz de estados aqui vai respeitar essa propriedade também.

Então podemos fazer uma função para multiplicar linhas dessa matriz.

powermat=function(P,h) {
    Ph=P
    if(h>1) {
        for(k in 2:h) {
            Ph=Ph%*%P
        }
    }
    return(Ph)
}

Essa função multiplica linhas da nossa matriz de transição, e multiplicando as duas primeiras linhas vemos o seguinte.

03

Veja que estamos representando a intensidade das probabilidades com cores, quanto mais vermelho, maior a chance, quanto mais clarinho, menor a chance. Aqui a chance maior é de estarmos na posição sete, já que podemos chegar no sete tirando 1 e 6, 2 e 5, 3 e 4, 4 e 3, opaaaaaa, lembre-se que quando a gente cai no 4, a gente pega a escada para o 14, então com 4 e 3, vamos para o catorze, e depois andamos 3, só que no 17 a gente é engolido pela cobra e volta pro 7, eu diria que isso é uma ironia, já que era para estarmos no 7 mesmo. Mas veja que como temos a matriz, estamos levando em conta as escadas e cobras, o que ignoraríamos, ou teríamos bem mais dificuldade se formos no braços, simulando cada acontecido.

É fácil se perder, se a gente andar 10 vezes, podemos andar de 6 em 6 casas, com muita sorte, você esperaria que ninguém tenha ganho o jogo não? Afinal andando direto, isso da 60 casas, se você começa no zero, so tirando 6 estaria na casa 60, mas lembre-se que quem tem sorte, não vai tirar só 6, vai é pegar as escadas certas, e andar muito mais rápido que isso, veja a distribuição depois de 10 jogadas como fica.

04

As vezes da a impressão que tem algo de especial nessa matriz, mas confira, a gente tem que cada casa só tem chance de ir para 6 outras casas, só voltando em casos de quando encontramos a boca de uma cobra.

> sum(M[2,]>0) [1] 6 > sum(M[10,]>0) [1] 6 > sum(M[50,]>0) [1] 6

Agora vamos supor que depois dessas 10 jogadas, um cara que não sabe perder da um chute na mesa e derruba todos os peões, agora a gente não lembra onde estava, mas podemos pegar a figura acima e podemos então tentar olhar onde você estava, primeiro que sabemos exatamente onde você não pode estar, só ver os lugares com probabilidade zero.

Mais do que isso, se você afirma que estava em algum lugar entre 59, 60 ou 61, podemos ver a probabilidade de estar em cada um desses lugares.

> h=10 > posição<-(initial%*%powermat(M,h))[59:61]/sum((initial%*%powermat(M,h))[59:61]) > posição [1] 0.1597003 0.5168209 0.3234788 > h=10 > posição<-(initial%*%powermat(M,h))[59:61]/sum((initial%*%powermat(M,h))[59:61]) > sum(posição) [1] 1 > posição [1] 0.1597003 0.5168209 0.3234788

Veja que a gente multiplica onde podemos estar depois de 10 jogadas, olhas a probabilidade de cada uma dessas 3 posições, divido pela soma dessas 3 posições, e temos nossa distribuição para a sua afirmação de estar nas casas 59, 60 ou 61.

Veja que podemos seguir a mesma linha, e perguntar quando ainda estaremos jogando, se a gente olhar a distribuição para cada jogada, é só ver que a chance da gente estar jogando ainda, é a chance de não estarmos na posição 100. Veja que uma vez que caímos no estado “posição 100”, ele é estacionário, e todo o jogo tende pra ele, se a gente chegar la, a gente não sai mais, isso é o jogo acabou, então podemos olhar a chance de não estarmos no 100 jogada por jogada e construir uma curva de probabilidade para isso.

05

Após 50 jogadas, é praticamente certeza que o jogo acabou. Veja a distribuição de chances depois de 50 jogadas.

06

Tem que ser muito pé frio para não ter terminado o jogo depois de 50 jogadas, mas veja que isso é uma situação pouco provável, mas não impossível.

Mas em média, vão levar 32 jogadas para finalizar o jogo.

> sum(1-game) [1] 32.16499

Veja que 1 é 100% de chance do jogo ter terminado, quando estamos diminuindo 100% de chance, o que está sobrando é a chance de ainda estarmos jogando. Quando o jogo acabou com certeza, temos 1, ou 100% de chance do jogo ter acabado, então 100% – 100% da zero, a chance da zerada, então estamos somando ai em cima todas as chances de estarmos jogando, para a distribuição ali em cima. Assim talvez seja mais difícil pensar.

Para ficar mais simples, podemos perguntar, quando na distribuição, temos menos de 50% de chance de estar jogando, 50% de chance do jogo ter acabado.

> max(which(1-game>.5)) [1] 29

São vinte e nove jogadas, e já temos 50% de chance do jogo ter acabado.

07

Agora tudo isso que estamos falando, é tendo em mente apenas um jogador. E com dois jogadores, mudaria muito?

Bem, é intuitivo pensar que, quanto mais gente jogando, mais rápido o jogo deve acabar. Se temos dois jogadores, é mais difícil exatamente termos dois jogadores azarados.

08

É só fazer a potência da distribuição anterior, elevar ela pelo número de jogadores, no caso dois, que temos a nova distribuição de quando o jogo deve acabar, podemos calcular também qualquer uma das estatísticas anteriores.

Mais do que isso, podemos usar isso para qualquer quantidade de jogadores.

09

Bem, para quem não pegou ainda a ideia das cadeias de markov, esse foi mais um exemplinho bem legal.
Esse não é o primeiro exemplo de Markov Chain que a gente olha, ja vimos aqui como prever a chuva usando Markov Chain, ou ainda como podemos prever a chuva, sem ver a chuva, apenas pelo comportamento de alguém, nesse exemplo está aqui. Isso pode parecer todo, mas o crescimento populacional pode ser pensado dessa forma, o que a gente ve pode ser apenas uma parte do processo que realmente esta acontecendo, como vimos no crescimento de passarinhos aqui.

Outro processo que temos muito interesse e que é assim é a evolução, a gente viu como simular cadeias de DNA com cadeias de markok aqui. E a evolução é mais ou menos isso, é uma passagem quase sempre, so de ida, não tem volta, a gente dificilmente volta para um estado anterior.

Bem, acho que é isso ai por hoje. Ficamos por aqui. Os scripts sempre no repositório recologia e é isso, até o próximo post. A, e se você curtir esse post, de uma olhada num blog chamado Freakonometrics, foi la que eu vi pela primeira vez essa ideia do Snake and Ladders

#Codigo original
#http://freakonometrics.blog.free.fr/index.php?post/2011/12/20/Basic-on-Markov-Chain-(for-parents)
 
#Matrix de transição
n=100
M=matrix(0,n+1,n+1+6)
rownames(M)=0:n
colnames(M)=0:(n+6)
 
for(i in 1:6) {
    diag(M[,(i+1):(i+1+n)])=1/6
}
 
M[,n+1]=apply(M[,(n+1):(n+1+6)],1,sum)
M=M[,1:(n+1)]
starting=c(4,9,17,20,28,40,51,54,62,64,63,71,93,95,92)
ending  =c(14,31,7,38,84,59,67,34,19,60,81,91,73,75,78)
 
for(i in 1:length(starting)) {
    v=M[,starting[i]+1]
    ind=which(v>0)
    M[ind,starting[i]+1]=0
    M[ind,ending[i]+1]=M[ind,ending[i]+1]+v[ind]
}
 
#Olhando o que criamos
nrow(M)
M[1,]
M[2,]
 
sum(M[2,]>0)
sum(M[10,]>0)
sum(M[50,]>0)
 
#Função para multiplicar a matriz de transição
powermat=function(P,h) {
    Ph=P
    if(h>1) {
        for(k in 2:h) {
            Ph=Ph%*%P
        }
    }
    return(Ph)
}
 
#Função para plotar o calculo das posições
initial=c(1,rep(0,n))
COLOR=rev(heat.colors(101))
u=1:sqrt(n)
boxes=data.frame(index=1:n,ord=rep(u,each=sqrt(n)),abs=rep(c(u,rev(u)),sqrt(n)/2))
 
#
position=function(h){
    D=initial%*%powermat(M,h)
    plot(0:10,0:10,col="white",axes=FALSE,xlab="",ylab="",main=paste("Posição após",h,"jogadas"))
 
    for(i in 1:n) {
        polygon(boxes$abs[i]-c(0,0,1,1),boxes$ord[i]-c(0,1,1,0),col=COLOR[min(1+trunc(500*D[i+1]),101)],border=NA)
    }
 
    segments(c(0,10),rep(0,2),c(0,10),rep(10,2))
    segments(rep(0,2),c(0,10),rep(10,2),c(0,10))
    segments(0:10,rep(0,11),0:10,rep(10,11))
    segments(rep(0,11),0:10,rep(10,11),0:10)
 
    for(i in 1:length(starting)) {
        arrows(x0=boxes$abs[starting[i]]-0.5,
               y0=boxes$ord[starting[i]]-0.5,
               x1=boxes$abs[ending[i]]-0.5,
               y1 =boxes$ord[ending[i]]-0.5,
               lty=3,length=0.10,col="darkgray",lwd=2)
    }
    text(boxes$abs-.5,boxes$ord-.5,boxes$index,cex=.7)
}
 
#figuras
 
position(1)
position(2)
position(10)
 
#Se quiser ver uma animação olhe esse codigo, no Sys.sleep da para configurar
#uma pausa entre os plots, deixei em 1/4 de segundo por jogada.
#for (i in 1:100) {
#                  position(i)
#                  Sys.sleep(0.25)
#                  }
 
 
#Probabilidade parcial
h=10
posição<-(initial%*%powermat(M,h))[59:61]/sum((initial%*%powermat(M,h))[59:61])
sum(posição)
posição
 
#Distribuição de jogadas
distrib<-initial%*%M
game<-rep(NA,1000)
 
for(h in 1:length(game)){
    game[h]<-distrib[n+1]
    distrib<-distrib%*%M
}
 
#Figuras de distribuição
plot(1-game[1:200],type="l",lwd=2,col="red",ylab="Probabilidade de ainda estar jogando",xlab="Jogadas")
position(50)

4 thoughts on “Snake and Ladders, usando Markov Chain para entender um jogo.

  1. Outro excelente post!! Sua forma de passar conteúdo é realmente muito didática e prende muito minha atenção, parabéns pelo excelente trabalho!
    Por curiosidade, teria algum exemplo ligando Markov (principalmente modelos ocultos) ao Poker? Andei procurando, mas não encontrei nada interessante…

  2. Opa, rapaz livro sobre poker com Markov Chain eu não sei. Até porque no poker, tecnicamente da para contar cartas, essas coisas, eu pelo menos não teria nem ideia como modelar usando Markov Chain. Mesmo no ludo, aquele jogo de tabuleiro, acho que ja é mais complicado, porque tem a possibilidade de escolher o peão pra jogar. Eu imagino que no Poker, a gente vai querer algo mais como otimizar ações para maximizar a chance de maior pontuação ponderando pra essa chance não ser muito pífia, você não pode sempre contar com a sorte.

    Mas eu acho que nunca li especificamente sobre isso, mas valeu pelo comentário, fico feliz que os textos sirvam a mais gente além de mim, eu escrevo o blog mais para me forçar a estudar mesmo, mas é legal saber que mais gente le 🙂

  3. Eu imaginei que você não investe em divulgar seu blog, mas deveria! É de alta qualidade! Recomendo que procure o pessoal do http://scienceblogs.com.br , com certeza você se encaixa no que eles fazem. Aguardo novos posts.

  4. Boa noite! Parabéns pela iniciativa!!
    Viu, seria possível plotar um gráfico da probabilidade (sem ser acumulada) de um jogador vencer o jogo??? Tipo, qual matriz eu tenho que levar em consideração pra fazer isso??
    Obrigado!!!

Leave a Reply

Your email address will not be published. Required fields are marked *