Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

+1 voto
186 visitas
perguntada Jan 29, 2020 em Ciência da Computação por Stuart Mill (1,424 pontos)  
editado Fev 1, 2020 por Stuart Mill

A imagem será apresentada aqui.

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?

Compartilhe
comentou Jan 31, 2020 por danielcajueiro (5,581 pontos)  
Como é esse jogo exatamente? Você fala em simulações Monte Carlo?
comentou Fev 1, 2020 por Stuart Mill (1,424 pontos)  
Sim, simulações de Monte Carlo. Editei a pergunta para explicar melhor.
comentou Fev 3, 2020 por danielcajueiro (5,581 pontos)  
Achei legal essa pergunta. Um exemplo bem simples de monte carlo.... Vou incluir no meu curso de métodos computacionais.
comentou Fev 3, 2020 por Stuart Mill (1,424 pontos)  
Bacana! Achei interessante também a aplicação. Geralmente é legal implementar esses jogos no Python.

2 Respostas

+1 voto
respondida Fev 4, 2020 por Stuart Mill (1,424 pontos)  
selecionada Fev 5, 2020 por danielcajueiro
 
Melhor resposta

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.

+1 voto
respondida Fev 1, 2020 por danielcajueiro (5,581 pontos)  

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
...