Watching a video about snakes and ladders (https://www.youtube.com/watch?v=k2ixp5VozIs) inspired me to dust off my markov-chain-memories and calculate the probability of winning the game after N rounds for normal and hardcore (ladders are snakes too) version.
Here’s my code: https://gist.github.com/SimonLammer/5f7c5fd4f9e60bba9fd13db0930ff83b

Normal: 61% after 55 rounds; 95% after 144 rounds; 99% after 233 rounds.
Hardcore: 4.5% after 55 rounds; 19% after 144 rounds; 32% after 233 rounds; 66% after 610 rounds; 95% after 1597 rounds; 99% after 2584 rounds.

I expected the hardcore version to be harder, but didn’t foresee a difference this big.

How could the number of expected snakes that were taken to win be calculated (aside from computer simulation)?

  • @chumbalumber@lemmy.blahaj.zone
    link
    fedilink
    English
    2
    edit-2
    1 year ago

    And in case you don’t know how to calculate the hitting probability, there’s some notes on it here: http://www.statslab.cam.ac.uk/~rrw1/markov/M.pdf. More generally, Dexter’s notes (should come up if you Google it) are great for a number of topics in maths.

    For an example of how you’d go about calculating it for your specific problem, consider the following: squares 1, 2, 3 and 4, a snake from 3 to 1, a dice that rolls 1 or 2, and finishing at 4. Then, letting hi be the probability of hitting 3 from square i,

    h3 = 1

    h4 = 0

    h2 = 1/2h3 = 1/2

    h1 = 1/2h3 1/2h2 = 3/4

    More generally, for any Markov chain, for set A to be hit, the hitting probabilities are the minimal solution to

    hi = 1, I in A

    hi = Σj pij hj, for transition probabilities pij

    Hopefully that makes sense, and feel free to DM about any stats questions, as it was the focus of my undergrad :)