Como modelar o jogo de tabuleiro "Serpentes e escadas" usando cadeias de Markov?

Question

O jogo "Serpentes e Escadas", ou "Snakes and Ladders" é um jogo de tabuleiro inspirado em um jogo indiano muito antigo chamado Moksha Patam. A mecânica do jogo é muito simples, e na verdade não tem estratégia, é puramente baseada em rolagem de dados. O jogo pode ser jogado entre 2 ou mais jogadores. No turno de cada jogador, o jogador rola um dado de 6 faces e anda o número de casas igual ao número que tirou no dado. Se cair em uma casa da parte de baixo de uma escada, o jogador sobe até a casa no topo dessa escada. Se cair em uma casa que tem a cabeça de uma cobra, o jogador desce até a casa onde está a cauda da cobra. Todos os jogadores começam na casa número 1, e quem chegar primeiro na casa 100, vence.

Como interpretar o jogo como uma cadeia de Markov? E como seria uma implementação simples do jogo para simular a duração média?

Comments

Como é esse jogo exatamente? Você fala em simulações Monte Carlo?

---

Sim, simulações de Monte Carlo. Editei a pergunta para explicar melhor.

---

Achei legal essa pergunta. Um exemplo bem simples de monte carlo.... Vou incluir no meu curso de métodos computacionais.

---

Bacana! Achei interessante também a aplicação. Geralmente é legal implementar esses jogos no Python.

Answer 1

Uma implementação possível que eu fiz baseado na ideia do prof. Cajueiro:

# Definindo os quadrados especiais
snakes = [(32,6),(74,22),(86,41),(99,39)]
ladders = [(9,31),(16,45),(18,64),(48,66),(50,93),(63,81)]
sl = snakes + ladders

#Mapeando os quadrados do jogo
mapState = {}       
for state in range(1,101):
    print(state)
    result = list(filter(lambda x: x[0] == state, sl))
    if len(result) != 0:
        mapState[state] = result[0][1]
    else:
        mapState[state] = state

# Simulando:
import random as rd

def snakes_ladders_mc(simulacoes, dado,step=1):
    durations = []
    for i in range(simulacoes):
        #print(i)
        state = 1
        game_duration = 0
        while(state != 100):
            state = state + rd.randrange(1,dado+1,step)
            game_duration += 1
            if state<100: # Se cai em algum quadrado sem finalizar o jogo
                state = mapState[state] # Toma o quadrado final onde ele cai de acordo com o mpapa
            else:
                durations.append(game_duration)
                break # sai do while, passa pra próxima iteração do for
    return (sum(durations)/simulacoes,durations)

result1 = snakes_ladders_mc(1000,6) # Testando com um dado de 6 faces
result2 = snakes_ladders_mc(1000,7) # Testando com um dado de 7 faces
result3 = snakes_ladders_mc(1000,6,2) # Testando só com resultados ímpares de um dado de 6 faces

Com o dado de 6 faces, a duração média foi de 32 aproximadamente. Com o de 7 faces, foi de 27 aproximadamente. Restringindo o dado de 6 faces a apenas número ímpares, o resultado foi de 37 aproximadamente.

Answer 2

Esse é um exercício bem simples.
1) Crie uma variável chamada "state". Essa variável dará a posição do jogador no jogo.
Ela será iniciada com a posição 1.

2) Crie um mapa de cada posição na posição final. Use um dicionário.

mapState={}

Na maioria dos casos o dicionário será assim:

mapState[state]=state

Mas isso será diferente para os casos que tem uma escada ou uma cobra.
Por exemplo:

Primeira escada:

 mapState[9]=31 

Primeira cobra:

mapState[32]=6

Agora é a parte legal.

A simulação monte carlo será assim:

numberRepetitions=100
averageDuration=0 #Numero de lances de dados

for i in range(numberRepetitions):
      while(state!=100):
            Resultado do Lançamento do dado
            state=state+resultadoDoLancamentoDeDado
            averageDuration=averageDuration+1
            if (state<100):
                 state=mapState[state]
            else:
                 break

averageDuration=averageDuration/numberRepetitions