LOL! I love that his takeaway was "it pays to behave badly" instead of something inspirational like "even a setback might be a blessing in disguise" 😂😂😂
If you look closely at the two statements, there is a difference: "Behaving badly" is something you choose to do, you have agency in its occurrence; whereas a "setback" is usually something that happens to you whether you want it to or no, you don't have agency in its occurrence.
I could care less about this, and I'm not trying to be a pre-Madonna, but for all intensive purposes, I think you are wrong. The saying is actually "blessing in the skies" 🤡
@Roccondil (no tags on mobile) you're right and that's what makes it even funnier! His whole thesis is that the game gives you no agency. But then the framing of a setback that's out of your control (rolling a number that takes you down a snake) is, "well, I might as well go use my agency to be bad" (Of course, I'm not trying to take his comment too seriously, as it's just an off-handed statement. Just trying to highlight one more layer to its perplexing nature)
@@bigpopakapthere is tags on mobile (this response is from my phone). You just have to tap the message you want to respond to and it will automatically have the tag
Years ago I was playing this game with my daughter who was five. She learned about counting and how being ahead in the game didn't necessarily mean she would win. Later that day, I showed my son who was 14 how to write a computer program to simulate the game. The computer played 1 million games and found that it took 42 moves to win on average. It's the answer to everything! It was crazy that this exact game provided two separate opportunities for two completely different aged kids to learn something
@@EumelHugo Yea, as a CS or math student re-visit it for the 3rd. I knew where he was going with the matrix: raising a connectivity matrix to a power to embody multiple turns is something that was covered in my first Algorithms class (high school AP CS) and such things were examined in more depth in Discrete Math courses in my degree program.
@@EumelHugo actually there are 4 levels. The 4th level is Generalisation. Snake and Ladders in 3 dimensions, or Snake and Ladders for n fields and how does the expected value of moves depend on n.
One way that you can add a bit of strategy to this game is to roll 2 dice at a time and choose one of them as your move. This adds quite a bit of strategy to the game without taking away too much of the randomness.
This actually sounds fun! I also conceived a version where all snakes and ladders are replaced by lifts. You can choose to go down the snake or ladder to earn a coin (you can only have one coin at a time). When you could take a lift up, you spend your coin and can't take another lift upward until you earn another coin. Also, if you roll a 6, you may choose to roll again or take a coin (or pass, if you already have one).
Another cool feature would be to add D&D dice. Each player has a full set up to d20. He can choose 1 die to roll. At the top, where we go back and forth, as opposed to reincarnate, a d4 might work best. After a few games this will get boring for adults, but it would probably give a few more hours of fun for kids. Also, you can add a speed element to it. Given a certain size of board with a specific placement of snakes and ladders, how fast can you get to the top?
I could also see this becoming part of a D&D map, where players are equipped with a widget or spell that allows them to advance, and are under attack by several enemies. Can the players layout the map to allow them to reach the end before a certain limit?
In this case yes, but matrix multiplication is not commutative, so one cannot simply take algebra and apply it to matrices. That is, matrices A, B and C: ABC is not equal to BAC, for example. If you want to go from ABC to BAC, and what you have are the product ABC, A and B (but not C on its own), you would need to do BA(B^-1)(A^-1)(ABC). You could interpret this as start from ABC, divide by A (get BC), divide by B (get C) then multiply by A again (get AC) then multiply by B (get BAC).
The requirement Q^n -> 0 is somewhat more tricky to check for general square matrices than it is for the special case of 1×1 matrices. But as long as you know that's true, then yes, it holds. That being said, that algebraic identity holds in a bunch of different contexts. It's really cool.
@@Mephisto707 There's a thing called the spectral radius of the matrix, which is the maximum absolute value eigenvalue: ρ(A) = max |r|, where r is an eigenvalue of A. Then, for a square matrix A, ρ(A) < 1 is a necessary and sufficient condition for 1 + A + A^2 + ... to converge to (I - A)^(-1). Notice that when A is 1x1, ρ(A) = |a|, where a is the lone entry of A.
I ran a simulation of Marcus' small board version of the game, and over 1,000,000 games, the average number of turns was about 8,59. Quite a bit less than 10.
I think the surprise realization at the end - that removing a snake can actually increase the expected number of turns to win - sets up a wonderful bit of advice for life: Don't get too upset or give up when you face an event in your life that seems to have set you back a lot - it might be just what you need to achieve your goals faster! ❤
Me and my son played this game so much when he was young. He learn to add numbers with it. And me I ended up analysing probabilities and expected values of the two players version. I wrote and publish a paper on this. I am now cited on the wikipedia page. My, now teen, son loves math. He compete in international math competitions and has a better intuition on probability than mine. And he loves Markov chains...
When I played this as a kid, it did have an element of agency: It had question cards. Whenever you landed on the bottom of a ladder, you'd have to get a question right in order to climb up; and when you hit the head of a snake, you'd only fall down if you got the question wrong.
The matrix sum shows the number of times you expect to be on each square over the course of the game, and when you add that up you get the (expected) total number of moves.
What the 0th row of the matrix Qⁿ shows is the probability that starting at position 0 and having done _n_ moves we are still in game (on the corresponding squares). So for each _n_ we add one more move multiplied by probability of still having moves after _n_ .
The implications are beautiful. Sometimes you need the risk of making mistakes to do better on your next go around. Or, the free will to sin is an opportunity to learn virtues in your next life
Here is a slightly easier way. Denote x_n = expected number of throws to win from square "n". So, x_0=1/6*(x_1+x_2+x_3+x_5+x_6+x_7)+1, x_1=1/6*(x_2+x_3+x_5+x_6+2*x_7)+1, etc. One gets a system of equations of of x_n that can be written as: X = Q*X + I, where Q is the transformation matrix as described in the video. Solve it, X = (I-Q)^(-1).
Marcus was the first person I can remember delivering the xmas lectures from the royal academy! A wonderful maths communicator, and a fascinating dive into a game I'm sure we've all played at one point or another.
This was very interesting, but I'm missing a crucial piece of explanation... WHY is the total of the top row of the matrix equal to the expected number of turns?
@@macronencer The final matrix has to be multiplied by a vector representing the initial state. That vector is (1, 0, 0, 0, ....), as you start on square zero. Multiplying by that vector picks out the first row of the matrix.
@@godfreypigott This makes a lot of sense. Almost too much sense. Like, is this not somehow represented in the equations or something, somewhere in this video? This just seems like crucial information.
So glad he mentioned backgammon! I got into it pretty deeply in the last 6 months, and the cool thing is I can play with my roommates (to whom I just explained the rules) and also with grandmasters. It's always going to be fun and often competitive with a little help from the dice. But it's also a very serious mathematical subject where neural networks can tell us the "right" moves statistically and you can measure how far away you were from making the perfect moves, win or lose. So you can play vs your opponent but also compare yourself vs the "perfect player" who had the same decisions you had. Snakes and ladders also kind of reminds me of backgammon since it's some sort of racing game. Or a better comparison could be "Mensch ärgere Dich nicht" also a kid's game which means "man don't get angry" (it makes you angry!!).
It would have been nice to see the graph representation for those not familiar with transition/adjacency matrices. That is, showing that the snakes and ladders connect vertices with edge weight 0 so they can be combined, and then result in the simplified transition/adjacency matrix.
If the dice's number is too big, you go up to the finish and then start going down until you "advanced" the right number of cases. At least that's what we did in my family.
@@remixtheidiot5771 While that has been historically true, it seems dice has been trending towards both the singular and plural form. So, while I'd certainly call die for a single, and dice for multiple correct, I wouldn't necessarily call dice for singular incorrect.
I always played by a different rule for overshooting the final square - you would move the number shown on the dice as normal, but "bounce off" the final square and go backwards for the remaining number of moves. I wonder how this rule would change the expected number of turns?
Based on the small board in this video, and 2× 1,000,000 simulated games, the average number of turns is about 8.59 (not 10!) when you don't move, and 9,69 when you bounce back. (It's higher because the odds of landing on the snake are higher.)
@@gabor6259 In that case (if you continue 8, 9, 1, 2, 3 ...) the average is about 10.5. So even worse. If you include 0 (so 8, 9, 0, 1, 2 ...), the average is about 11.4. And finally, if you always go to 0 (and no further) when you overshoot, the average is 12.3.
I've never liked matrices, but this video certainly shines a new light on them which change my mind a slight bit. I find them annoying to work with, but in a way they display information in a clear and beautiful manner which I just can't find anywhere else
I learned about Markov chains in my stochastic processes class, and it blew my mind when Hannah fry used it to determine the chances you land on a square in Monopoly. I was thinking about what other games I could apply this too, and I did think of snakes and ladders. Then I realized the ending matrix would just be a probability of 1 on square 100 since you stop the game there (aka square 100 only leads to itself)
Here's an idea for introducing some skill into snakes and ladders. Start with no snakes or ladders on the board. Each time someone lands on a square that hasn't been visited yet in that game, they get to add one snake or ladder wherever they want.
I have played this game with my sister in my childhood days and we finally realized that, it was based on pure chance and left it. Two and a half decades later, we have got a chance to get back to this game through this video. This time it's from the mathematical perspective rather than the game itself. It was interesting to know that, every snakes and ladders game will have a transition matrix and one could calculate the expectation value for the number of die rolls required to win. I never thought of this game in this way until now. Thanks to Marcus for the explanation.
Try throwing two dice, and your opponent throws one. Then your opponent can choose to make you use their roll as one of your two, or stick with your own. If you have to use theirs, you get to choose which of yours is paired with it. This gives the tactical element that the game seems to be missing for so many people.
I'm so glad he brought up the induced demand problem with more roads/lanes. Pretty fundamental economics theory we all just keep forgetting. Applicable to everything, not just roads.
From the 64th to the 69th row of the big matrix you made for the Indian Snakes and Ladders board there are only 5 positions filled out in the matrix, whilst it should be 6, right? If not, could you maybe explain why?
I used this game as an example in my Master's thesis but added agency by looking at an MDP version, which means before each throw of a dice you can choose what probability distribution the throw should have. You can think of it as loaded dice. The task is then to figure out which dice you should pick at which square. While for each dice you can calculate the probability of landing on each square it's not clear which dice is best because you do not necessarily now which squares are more preferable since again, you don't know which dice are optimal in the follow-up square.
@@antonmiserez934 Yes, that's the way I always think about these. Basically you just solve a system of linear equations which is also faster than matrix inversion in practice. And even solving the system is quite slow compared to other methods, mainly value iteration, which also handles MDPs nicely.
Nice. I've always played it in the Indian way. But you didn't mention the other element that we used: when another player lands on the square where you are, you start again at the bottom. And as to agency--that comes in to your ability to telekinetically influence your throw to make your man land on your brother's square!
Here's a way to add agency: Each player has 4 dice, with their last roll still showing. (Or, use number cards) Choose which of the four numbers to use on your turn, then re-roll that one.
It would be helpful to write a program which simply takes inputs of the board size, goal square, dice size, list of ordered pairs of squares which are connected by snakes or ladders (they are the same thing), and toggle for overshoot wrapping/reïncarnation and generates the transition matrix (Q in the video). That way, the whole entry-by-entry calculation need not be done by hand.
Because of the whole "rem,oving a snake is a bad thing" revalation, I wonder if you could make a version of this board that would allow you to change the rules so that you wouldn't HAVE to use a snake or a ladder, but it was a strategic choice, thus solving the "we are just dice-rolling machines with no agency" problem. Of course, that might not be very fun either, once the best snakes/ladders to take are found.
I once did a Monte Carlo simulation of Snakes and Ladders to determine the optimal number of dice to reach the end square as part of my PhD studies into applying Monte Carlo to a physics simulation. Using Markov Chains is a slightly different method to the one that I used to solve the problem :)
I would subscribe to an entire channel dedicated to the maths behind games (as long as there is actual math like in this episode). Having just taken linear algebra, this was interesting in a new way.
I don't think I ever played this; but here an idea to make it more interesting is that each player has 2 dice. you can sacrifice 1,or even save 1. so at the start of a turn you can decide whether you wish to save a dice for next roll. so next roll will have 3 dice. once you roll let say 2 and 5 you can sacrifice one let say 5 so you only move 2. there could be a cost to sacrificing like next round you can't use that dice. I could see saving being a different color dice so that if you sacrifice it there no cost to your next turn. adding the rule where if it loop back to the start can make it where there more control. this could make it where not all snakes are bad since some may lead you to a ladder. you could also add a rule that say if you land on a space with someone already on it you can either remove a dice or add a dice to both player. this also add a extra cost to sacrifice since you would only have 1 dice and even the add a extra dice could mess someone up if it near the end since you can only sacrifice 1 dice each turn. another change is to add points of good karma and have space that reward the player like 2 or 3 points and this could add a extra cost to sacrifice where it lower karma by 1. and have it where you need positive karma to win. and have it where snakes can lower your karma. to make it more random you can have 2 deck one for ladder(positive) and one for snake(negative) and the card give a random amount. this way it easy to know your karma but able to hide it from other player. this mean that you may not know if the other play can win so you may wish to slow them down by landing on them even at the cost of your own karma. I also think that rebirth should allow you to discard 2 cards lowering your bad karma. is this still consider snake and ladder? pieces(board, 2 deck of cards, x pieces, (2+1)x dice)x= players. there could be a problem if a play save a dice then another player lands on them and they decide to add a extra dice a simple fix could be that the max you can roll in one turn is 3 dice or just add a extra dice per player in the box.
You could add some player agency, by allowing each player to specify ONE snake (or ladder) to DISABLE for their game. With the example snake given in the video, the player who chooses to disable that snake would get a disadvantage! Each board would be a puzzle, which increases or decreases your chance of success.
since watching this video a few days ago, I have been contemplating which popular games are pure strategy, which ones are pure chance, and which are in between. pure chance: Candyland, Snakes and Ladders, War (which I've seen argued isn't a true game because the result is predetermined) pure strategy: Chess, Connect Four, Chinese Checkers, Checkers combination: Guess Who, Catan, Monopoly, Clue, Trouble, Battleship it also occurred to me there is another category: skill games. ones that rely on neither chance nor strategy but your level of competence at a particular task. examples: scattegories (tests the skill of thinking of words that fit certain categories), Trivial Pursuit (tests knowledge), Scene It (tests knowledge of movies), Jenga (tests physical skill of removing blocks without knocking the tower over), Operation (tests fine motor skills), Boggle (tests the skill of finding words in a jumble), Pictionary (tests drawing and interpreting drawings)
The fact that you have no agency in this game is absolutely the point. It's an allegory of life. I also think the rule where you get "reborn" and go back to start if you overshoot makes it even more poignant and catarthic.
4:05 Well there's this important, the transition matrix. This sounds so much like structural (or fluid, or any finite element) calculation. It's all about setting up a matrix that explains how each pixel (square, voxel) is related the other nearby or adjacent pixels, and then solving it for the equilibrium positions of all pixels. Usually involves a spare matrix inverse, and there are lots of interesting algorithms that programs try to chug through to do that.
The "value" of this game for kids is learning about the randomness itself, and dealing with the frustration it can induce. As with many games, these "secondary effects" are more important in S&L than the actual gameplay.
I watched Arthur Benjamin play backgammon and was amazed at how often he would say something like, "I have [blank] percent chance of getting the [blank] that I need," and then he would roll exactly what he needed.
I would love to see a video on the game cribbage! It’s one of my favourites because it involves luck with the cards you get but there are certain choices you can make to get more points, it’s also heavily math based with all the counting to 15 and 31. It’s super fun as well!
My favourite game with my adolescent children was "The Hare And Tortoise". Part chance (dice) plus strategy (go fast with smaller moves or go slow to pick up points and then do a really big move)
Snakes&Ladders is how I learned to count and add up, before I started at school. It meant numbers were fun toys to me, before the education system tried to beat the fun out of it.
I'm wondering how deep the esoteric symbolism of the original snakes and ladders goes. I wonder if even each square has a numerological correspondence. I must look into this.
I have recently thought about how the Collatz conjecture actually can be represented as an infinite board game of snakes and ladders. The goal is to reach to the number 1 where every step of dividing by two is a ladder and every step of multiplying by 3 and adding 1 is a snake. So maybe a sort of generalization of the ideas that were shown here can help to solve this problem...
Snakes (chutes) and ladders differs from Collatz in one important way. To turn a singles and ladders board into Collatz then the exit of any snake or ladder would have to be the entry point too the next one. It's that difference that underlies @mikealexander7017's observation that there's no dice roll. Start anywhere and you conjecturally go on forever. That makes the topology different. There's also the details that the board is infinite, and that the target is to get back to square one, bit both of those are less interesting.
The people mebtioning a bounceback rule gave me an idea: how much agency is added by letting the player choose which direction they go? Would rational play reduce down to only going back if you'd land on a ladder, taking you up higher?
in my local version of the game, we don't overshoot the last square but we go backwards for the amount we overshoot, which quite similar to the aeroplane game.
the way I was taught to play it is that if you over shoot, you have to cont back the extra spaces, i.e if you're on 7 and roll a 3: you go up to 9 and then 1 back to 8
If there are multiple flat irregular figures of different sizes and shapes (not convex polygons, they may even have curved sides), how can we make the gaps between them smaller or the total area (envelope area) smaller?
Wow didn't expect the philosophical life lesson of sometimes "its better to fall down and pick yourself back up than to never have fell down" from the board game snakes and ladders...
Fun fact: if you add an infinitely repeated grid to the snakes & ladders board, it becomes undecidable, because the system becomes Turing Complete (equivalent to a 2 counter Misky machine).
It also gives them a chance to win- my dad used to thrash me at chess for years until I finally beat him at which point he refused to ever play me again. Well I never actually beat him- I trapped his queen he refused to move for hours until I had to go to bed 🤔
@@glxxyz 😀 Yep, usually they don't have to! Reminds me of someone I played backgammon with (just once) who wouldn't forfeit the round if he didn't accept a double, and an elderly grandfather who would only play chess if "we don't play taking queens". 🤪
Interesting to learn that others played this game to where if you overshot the winning square you just didn't move. We played it either that overshooting was still a win, or if you overshot then you took steps backwards based on how much you had to spare. So if you were on square 8, and needed square 9, but rolled a 3, you'd move forward one square to and back two so that you landed back on square 7. Never heard of this version where you just don't move unless you have the right roll. But it's fascinating that this all has its origins in an Indian religious-themed game where overshooting the target equals being reincarnated. That's just epic.
Just in time for Cities: Skylines II. I thought I was making my city more efficient with that new road. I caused a terrible traffic jam, and now I know why.
This made me think about simplest ways to modify the game to add the player agency and strategy. First thought: player throws 2 dice and can pick one of them. But this doesn't seem to offer much strategy - randomness keeps the effect of the choice local, doesn't affect future choices for anyone.
That's a beautiful result. Is there a way to think about that so that it makes sense immediately? Like, how would you explain the answer to be the inverse matrix of I - Q?
Based on the video, I am interested in trying a version of Snakes and Ladders where after each roll you get to decide whether to go forward or backward that many spaces. For example, if you roll a 7, you could go forward 7 like normal or backwards 7 if you thought that would position you to win better. That may add a little bit of intellect, strategy, or individual expression without being completely open-ended like he enjoys, and I'd love to see how you'd approach the strategy of making that decision mathematically.
What I love but also hate about this is that it opens up so many followup questions. What do all the matrices that produce 59 have in common? Is there a structure they share? How strong is the deviation from this expected value? Can you easily tell which addition of a snake would make the value go up or down? What happens if you build a loop in your board? And many more. Markov chains are really a funny thing.
There's a young age where agency is unhelpful. Games of complete chance are best if your brain can't really do strategy yet. The original game of snakes and ladders was (like monopoly) a philosophical game intended to teach us humility, that we have no agency in real life. I can't say I agree, but it wasn't accidental.
I wonder if creating the ability to change the snakes/ladders during the game would suffice to make it stategic enough. My thought was: Whenever a player lands on the "passive end" of one by rolling - not taking the forced path from the "active end" - they were allowed to move the respective active end by N (like 2-5) squares horizontally/vertically - but not invert or level the up/down direction. (Read: Not change snake to ladder and vice versa. That could be too powerful. But maybe not!) That could enable you to create better opportunities for yourself, or worse for your opponent on the go. Would ofc need some fine tuning for the actual freedom to move the ends, but as a concept I could see it make it much more interesting.
Around the World in Eighty Games (Amazon): amzn.to/3snW2bD
More videos with Marcus: bit.ly/Marcus_Numberphile
301 views?
Talking about puzzles, the puzzle in my latest video is practically impossible to solve.
301
What can be more British than assuming something from India is yours?
Nice one
Beat me to it
Ouch
Don't be racist.😊😊
making fun of some word americans say or use that actually originated from britain
LOL! I love that his takeaway was "it pays to behave badly" instead of something inspirational like "even a setback might be a blessing in disguise" 😂😂😂
Those who are behind in life have the greatest opportunities for growth
If you look closely at the two statements, there is a difference: "Behaving badly" is something you choose to do, you have agency in its occurrence; whereas a "setback" is usually something that happens to you whether you want it to or no, you don't have agency in its occurrence.
I could care less about this, and I'm not trying to be a pre-Madonna, but for all intensive purposes, I think you are wrong. The saying is actually "blessing in the skies"
🤡
@Roccondil (no tags on mobile) you're right and that's what makes it even funnier! His whole thesis is that the game gives you no agency. But then the framing of a setback that's out of your control (rolling a number that takes you down a snake) is, "well, I might as well go use my agency to be bad"
(Of course, I'm not trying to take his comment too seriously, as it's just an off-handed statement. Just trying to highlight one more layer to its perplexing nature)
@@bigpopakapthere is tags on mobile (this response is from my phone). You just have to tap the message you want to respond to and it will automatically have the tag
Love the “bong cloud” opening and the crashing eval bar.
Years ago I was playing this game with my daughter who was five. She learned about counting and how being ahead in the game didn't necessarily mean she would win. Later that day, I showed my son who was 14 how to write a computer program to simulate the game. The computer played 1 million games and found that it took 42 moves to win on average. It's the answer to everything! It was crazy that this exact game provided two separate opportunities for two completely different aged kids to learn something
Actually after this video there are three levels of approaching this game:
1. Playing the game
2. Simulating the game
3. Mathematically analysing it
@@EumelHugo Yea, as a CS or math student re-visit it for the 3rd.
I knew where he was going with the matrix: raising a connectivity matrix to a power to embody multiple turns is something that was covered in my first Algorithms class (high school AP CS) and such things were examined in more depth in Discrete Math courses in my degree program.
@@EumelHugo actually there are 4 levels. The 4th level is Generalisation. Snake and Ladders in 3 dimensions, or Snake and Ladders for n fields and how does the expected value of moves depend on n.
The space of snake and ladders functions and matrices
Yeah, that definitely happened.
One way that you can add a bit of strategy to this game is to roll 2 dice at a time and choose one of them as your move. This adds quite a bit of strategy to the game without taking away too much of the randomness.
Ooo, I love this idea!
This actually sounds fun! I also conceived a version where all snakes and ladders are replaced by lifts. You can choose to go down the snake or ladder to earn a coin (you can only have one coin at a time). When you could take a lift up, you spend your coin and can't take another lift upward until you earn another coin. Also, if you roll a 6, you may choose to roll again or take a coin (or pass, if you already have one).
Another cool feature would be to add D&D dice. Each player has a full set up to d20. He can choose 1 die to roll. At the top, where we go back and forth, as opposed to reincarnate, a d4 might work best. After a few games this will get boring for adults, but it would probably give a few more hours of fun for kids.
Also, you can add a speed element to it. Given a certain size of board with a specific placement of snakes and ladders, how fast can you get to the top?
I could also see this becoming part of a D&D map, where players are equipped with a widget or spell that allows them to advance, and are under attack by several enemies. Can the players layout the map to allow them to reach the end before a certain limit?
It's really neat that the algebraic identity 1 + q + q^2 + q^3 + ... = 1/(1-q) also holds for matrices!
In this case yes, but matrix multiplication is not commutative, so one cannot simply take algebra and apply it to matrices. That is, matrices A, B and C: ABC is not equal to BAC, for example. If you want to go from ABC to BAC, and what you have are the product ABC, A and B (but not C on its own), you would need to do BA(B^-1)(A^-1)(ABC). You could interpret this as start from ABC, divide by A (get BC), divide by B (get C) then multiply by A again (get AC) then multiply by B (get BAC).
The requirement Q^n -> 0 is somewhat more tricky to check for general square matrices than it is for the special case of 1×1 matrices. But as long as you know that's true, then yes, it holds.
That being said, that algebraic identity holds in a bunch of different contexts. It's really cool.
With numbers, for that formula to hold, |q| must be less than 1. What is the equivalent for matrices?
@@Mephisto707 There's a thing called the spectral radius of the matrix, which is the maximum absolute value eigenvalue: ρ(A) = max |r|, where r is an eigenvalue of A. Then, for a square matrix A, ρ(A) < 1 is a necessary and sufficient condition for 1 + A + A^2 + ... to converge to (I - A)^(-1). Notice that when A is 1x1, ρ(A) = |a|, where a is the lone entry of A.
Why the expectation is the sum of the first row of inv(I -Q) ?
I ran a simulation of Marcus' small board version of the game, and over 1,000,000 games, the average number of turns was about 8,59. Quite a bit less than 10.
His inverse must have been incorrect because I redid the calculate and the sum of the first row was 43/5 = 8.6.
Same.
Ditto.
Here I was wondering why it seemed to always magically be a whole number. I guess it's not haha
damn, we have peer reviewer in the comment section
I think the surprise realization at the end - that removing a snake can actually increase the expected number of turns to win - sets up a wonderful bit of advice for life: Don't get too upset or give up when you face an event in your life that seems to have set you back a lot - it might be just what you need to achieve your goals faster! ❤
Me and my son played this game so much when he was young. He learn to add numbers with it. And me I ended up analysing probabilities and expected values of the two players version. I wrote and publish a paper on this. I am now cited on the wikipedia page. My, now teen, son loves math. He compete in international math competitions and has a better intuition on probability than mine. And he loves Markov chains...
When I played this as a kid, it did have an element of agency: It had question cards. Whenever you landed on the bottom of a ladder, you'd have to get a question right in order to climb up; and when you hit the head of a snake, you'd only fall down if you got the question wrong.
Beautiful. I do not comprehend how this sum of probability matrices shows the number of moves.
it's like taking the average over an infinite number of games
The matrix sum shows the number of times you expect to be on each square over the course of the game, and when you add that up you get the (expected) total number of moves.
What the 0th row of the matrix Qⁿ shows is the probability that starting at position 0 and having done _n_ moves we are still in game (on the corresponding squares). So for each _n_ we add one more move multiplied by probability of still having moves after _n_ .
18:40 Legendary bongcloud opening by Donny
The implications are beautiful. Sometimes you need the risk of making mistakes to do better on your next go around. Or, the free will to sin is an opportunity to learn virtues in your next life
Here is a slightly easier way. Denote x_n = expected number of throws to win from square "n". So, x_0=1/6*(x_1+x_2+x_3+x_5+x_6+x_7)+1, x_1=1/6*(x_2+x_3+x_5+x_6+2*x_7)+1, etc. One gets a system of equations of of x_n that can be written as: X = Q*X + I, where Q is the transformation matrix as described in the video. Solve it, X = (I-Q)^(-1).
Nice, cool spin on the classic game "Eels and Escalators"!
Marcus was the first person I can remember delivering the xmas lectures from the royal academy! A wonderful maths communicator, and a fascinating dive into a game I'm sure we've all played at one point or another.
That chess game at 18:34 lol 😂 ❤
As always, brilliant attention to details in the animation by Numberphile!
Kudos to animator Pete.
@@numberphile Thank you Pete for giving us the PresidentDonny Bongcloud!
Bongcloud reference!!
I've heard the actual value of this game is to teach children how to take turns graciously. This was a fun video, thank you!
This was very interesting, but I'm missing a crucial piece of explanation... WHY is the total of the top row of the matrix equal to the expected number of turns?
I was wondering too, I think it's because the first row is what happens when you start from 0.
He could have explained that more clearly. He's calculating the total number of turns by adding up the total number of times you were on each square.
@@martinepstein9826 Ah, I think perhaps that's beginning to make sense, yes. I must go away and do the calculations myself, I think :)
@@macronencer The final matrix has to be multiplied by a vector representing the initial state. That vector is (1, 0, 0, 0, ....), as you start on square zero. Multiplying by that vector picks out the first row of the matrix.
@@godfreypigott This makes a lot of sense. Almost too much sense. Like, is this not somehow represented in the equations or something, somewhere in this video? This just seems like crucial information.
So glad he mentioned backgammon! I got into it pretty deeply in the last 6 months, and the cool thing is I can play with my roommates (to whom I just explained the rules) and also with grandmasters. It's always going to be fun and often competitive with a little help from the dice. But it's also a very serious mathematical subject where neural networks can tell us the "right" moves statistically and you can measure how far away you were from making the perfect moves, win or lose. So you can play vs your opponent but also compare yourself vs the "perfect player" who had the same decisions you had. Snakes and ladders also kind of reminds me of backgammon since it's some sort of racing game. Or a better comparison could be "Mensch ärgere Dich nicht" also a kid's game which means "man don't get angry" (it makes you angry!!).
It would have been nice to see the graph representation for those not familiar with transition/adjacency matrices. That is, showing that the snakes and ladders connect vertices with edge weight 0 so they can be combined, and then result in the simplified transition/adjacency matrix.
If the dice's number is too big, you go up to the finish and then start going down until you "advanced" the right number of cases. At least that's what we did in my family.
Indeed. The goal "reflects" you if you get too high a throw. That's how I played this, and Ludo, and the Nordic classic African Tähti.
The goal doesn’t reflect you, unless you’re making up your own rules.
the singular for dice is die.
@@remixtheidiot5771 While that has been historically true, it seems dice has been trending towards both the singular and plural form. So, while I'd certainly call die for a single, and dice for multiple correct, I wouldn't necessarily call dice for singular incorrect.
@@X22GJPthat is the way I had always played it too, and the set I just bought to play with my son has that rule explicitly explained in the rules
Found in a British museum? You don't say!
It's amazing that a video a bout solving a math problem about S&L is far more fun than actually "playing" S&L
I always played by a different rule for overshooting the final square - you would move the number shown on the dice as normal, but "bounce off" the final square and go backwards for the remaining number of moves. I wonder how this rule would change the expected number of turns?
Based on the small board in this video, and 2× 1,000,000 simulated games, the average number of turns is about 8.59 (not 10!) when you don't move, and 9,69 when you bounce back. (It's higher because the odds of landing on the snake are higher.)
@@mscha What if you overshoot, you start at the beginning, so it's a circle?
@@gabor6259 In that case (if you continue 8, 9, 1, 2, 3 ...) the average is about 10.5. So even worse. If you include 0 (so 8, 9, 0, 1, 2 ...), the average is about 11.4. And finally, if you always go to 0 (and no further) when you overshoot, the average is 12.3.
@@mscha came here to see this comment. :)
I've never liked matrices, but this video certainly shines a new light on them which change my mind a slight bit. I find them annoying to work with, but in a way they display information in a clear and beautiful manner which I just can't find anywhere else
A pity it didn't explain matrix squaring/inverting for those of us in a country that didn't have it in HS curriculum.
The chess history was mind blowing. Excellent production all round, thank you!!
I learned about Markov chains in my stochastic processes class, and it blew my mind when Hannah fry used it to determine the chances you land on a square in Monopoly. I was thinking about what other games I could apply this too, and I did think of snakes and ladders. Then I realized the ending matrix would just be a probability of 1 on square 100 since you stop the game there (aka square 100 only leads to itself)
Marcus is such a legend. I watched his documentary The story of Mathematics and it completely changed how I look at Mathematics
We teach our children that the fun of the games like this is spending time together playing, and that if you have fun, you’ve won.
Here's an idea for introducing some skill into snakes and ladders. Start with no snakes or ladders on the board. Each time someone lands on a square that hasn't been visited yet in that game, they get to add one snake or ladder wherever they want.
Sounds fun
I have played this game with my sister in my childhood days and we finally realized that, it was based on pure chance and left it. Two and a half decades later, we have got a chance to get back to this game through this video. This time it's from the mathematical perspective rather than the game itself. It was interesting to know that, every snakes and ladders game will have a transition matrix and one could calculate the expectation value for the number of die rolls required to win. I never thought of this game in this way until now. Thanks to Marcus for the explanation.
Try throwing two dice, and your opponent throws one. Then your opponent can choose to make you use their roll as one of your two, or stick with your own. If you have to use theirs, you get to choose which of yours is paired with it.
This gives the tactical element that the game seems to be missing for so many people.
Please do something on squads packing. I think it’d be fun to watch.
I'm so glad he brought up the induced demand problem with more roads/lanes. Pretty fundamental economics theory we all just keep forgetting. Applicable to everything, not just roads.
As some one who played Saap-shidi(marathi name for Snakes and ladders) it was interesting to learn more about the game and will be getting the book.
From the 64th to the 69th row of the big matrix you made for the Indian Snakes and Ladders board there are only 5 positions filled out in the matrix, whilst it should be 6, right? If not, could you maybe explain why?
Donny playing the bongcloud opening I found very humorous
I used this game as an example in my Master's thesis but added agency by looking at an MDP version, which means before each throw of a dice you can choose what probability distribution the throw should have. You can think of it as loaded dice. The task is then to figure out which dice you should pick at which square. While for each dice you can calculate the probability of landing on each square it's not clear which dice is best because you do not necessarily now which squares are more preferable since again, you don't know which dice are optimal in the follow-up square.
Thinking about this, could some sort of Bellman equation be used?
@@antonmiserez934 Yes, that's the way I always think about these. Basically you just solve a system of linear equations which is also faster than matrix inversion in practice. And even solving the system is quite slow compared to other methods, mainly value iteration, which also handles MDPs nicely.
Nice. I've always played it in the Indian way. But you didn't mention the other element that we used: when another player lands on the square where you are, you start again at the bottom. And as to agency--that comes in to your ability to telekinetically influence your throw to make your man land on your brother's square!
This is Chutes and Ladders in the US.
Here's a way to add agency:
Each player has 4 dice, with their last roll still showing. (Or, use number cards)
Choose which of the four numbers to use on your turn, then re-roll that one.
Me and my class are literally doing a libear algebra project on thist topic 😂 this is so great to have a vodeo to go along with it!
That colorful rendition of “The Ambassadors” looks cool!
It would be helpful to write a program which simply takes inputs of the board size, goal square, dice size, list of ordered pairs of squares which are connected by snakes or ladders (they are the same thing), and toggle for overshoot wrapping/reïncarnation and generates the transition matrix (Q in the video). That way, the whole entry-by-entry calculation need not be done by hand.
Because of the whole "rem,oving a snake is a bad thing" revalation, I wonder if you could make a version of this board that would allow you to change the rules so that you wouldn't HAVE to use a snake or a ladder, but it was a strategic choice, thus solving the "we are just dice-rolling machines with no agency" problem. Of course, that might not be very fun either, once the best snakes/ladders to take are found.
the fact that they made Trump play the bongcloud is nuts
I once did a Monte Carlo simulation of Snakes and Ladders to determine the optimal number of dice to reach the end square as part of my PhD studies into applying Monte Carlo to a physics simulation. Using Markov Chains is a slightly different method to the one that I used to solve the problem :)
I would subscribe to an entire channel dedicated to the maths behind games (as long as there is actual math like in this episode). Having just taken linear algebra, this was interesting in a new way.
I don't think I ever played this; but here an idea to make it more interesting is that each player has 2 dice. you can sacrifice 1,or even save 1.
so at the start of a turn you can decide whether you wish to save a dice for next roll. so next roll will have 3 dice.
once you roll let say 2 and 5 you can sacrifice one let say 5 so you only move 2.
there could be a cost to sacrificing like next round you can't use that dice.
I could see saving being a different color dice so that if you sacrifice it there no cost to your next turn.
adding the rule where if it loop back to the start can make it where there more control. this could make it where not all snakes are bad since some may lead you to a ladder.
you could also add a rule that say if you land on a space with someone already on it you can either remove a dice or add a dice to both player. this also add a extra cost to sacrifice since you would only have 1 dice and even the add a extra dice could mess someone up if it near the end since you can only sacrifice 1 dice each turn.
another change is to add points of good karma and have space that reward the player like 2 or 3 points and this could add a extra cost to sacrifice where it lower karma by 1.
and have it where you need positive karma to win. and have it where snakes can lower your karma.
to make it more random you can have 2 deck one for ladder(positive) and one for snake(negative) and the card give a random amount. this way it easy to know your karma but able to hide it from other player. this mean that you may not know if the other play can win so you may wish to slow them down by landing on them even at the cost of your own karma. I also think that rebirth should allow you to discard 2 cards lowering your bad karma.
is this still consider snake and ladder?
pieces(board, 2 deck of cards, x pieces, (2+1)x dice)x= players. there could be a problem if a play save a dice then another player lands on them and they decide to add a extra dice a simple fix could be that the max you can roll in one turn is 3 dice or just add a extra dice per player in the box.
You could add some player agency, by allowing each player to specify ONE snake (or ladder) to DISABLE for their game. With the example snake given in the video, the player who chooses to disable that snake would get a disadvantage! Each board would be a puzzle, which increases or decreases your chance of success.
We play with a D6 and a D8 - you are free to choose whichever die you want when it's your turn to roll.
since watching this video a few days ago, I have been contemplating which popular games are pure strategy, which ones are pure chance, and which are in between.
pure chance: Candyland, Snakes and Ladders, War (which I've seen argued isn't a true game because the result is predetermined)
pure strategy: Chess, Connect Four, Chinese Checkers, Checkers
combination: Guess Who, Catan, Monopoly, Clue, Trouble, Battleship
it also occurred to me there is another category: skill games. ones that rely on neither chance nor strategy but your level of competence at a particular task. examples: scattegories (tests the skill of thinking of words that fit certain categories), Trivial Pursuit (tests knowledge), Scene It (tests knowledge of movies), Jenga (tests physical skill of removing blocks without knocking the tower over), Operation (tests fine motor skills), Boggle (tests the skill of finding words in a jumble), Pictionary (tests drawing and interpreting drawings)
The fact that you have no agency in this game is absolutely the point. It's an allegory of life. I also think the rule where you get "reborn" and go back to start if you overshoot makes it even more poignant and catarthic.
I agree 100%. The best games are ones where you have some agency but also involve luck.
This is why the game of marriage is so popular.
4:05 Well there's this important, the transition matrix.
This sounds so much like structural (or fluid, or any finite element) calculation. It's all about setting up a matrix that explains how each pixel (square, voxel) is related the other nearby or adjacent pixels, and then solving it for the equilibrium positions of all pixels. Usually involves a spare matrix inverse, and there are lots of interesting algorithms that programs try to chug through to do that.
The "value" of this game for kids is learning about the randomness itself, and dealing with the frustration it can induce. As with many games, these "secondary effects" are more important in S&L than the actual gameplay.
I watched Arthur Benjamin play backgammon and was amazed at how often he would say something like, "I have [blank] percent chance of getting the [blank] that I need," and then he would roll exactly what he needed.
It'd be fun to do this with nonstandard dice too. Be it a D20 etc or a weighted D6
That could be a way to add agency if on each turn, the player chose between D4, D6, D8. I also like to go back around version better.
I would love to see a video on the game cribbage! It’s one of my favourites because it involves luck with the cards you get but there are certain choices you can make to get more points, it’s also heavily math based with all the counting to 15 and 31. It’s super fun as well!
I like the (unnamed) reference to the Brasess paradox. I always wondered where this could also apply, besides traffic networks.
I love the bongcloud at the end there
HAPPY BIRTHDAY NUMBERPHILE 🎉🎉🎉
13:04 an absolutely awesome thing is that Ramanujan actually discovered this!
His other book The Music Of The Primes is absolutely amazing.
I loved his book "Music of the Primes"!
My favourite game with my adolescent children was "The Hare And Tortoise". Part chance (dice) plus strategy (go fast with smaller moves or go slow to pick up points and then do a really big move)
Snakes&Ladders is how I learned to count and add up, before I started at school. It meant numbers were fun toys to me, before the education system tried to beat the fun out of it.
I'm wondering how deep the esoteric symbolism of the original snakes and ladders goes. I wonder if even each square has a numerological correspondence. I must look into this.
I have recently thought about how the Collatz conjecture actually can be represented as an infinite board game of snakes and ladders. The goal is to reach to the number 1 where every step of dividing by two is a ladder and every step of multiplying by 3 and adding 1 is a snake. So maybe a sort of generalization of the ideas that were shown here can help to solve this problem...
I like to think of Collatz as infinite snakes and ladders too. But it's entirely deterministic; there's no dice roll.
Snakes (chutes) and ladders differs from Collatz in one important way. To turn a singles and ladders board into Collatz then the exit of any snake or ladder would have to be the entry point too the next one.
It's that difference that underlies @mikealexander7017's observation that there's no dice roll. Start anywhere and you conjecturally go on forever.
That makes the topology different.
There's also the details that the board is infinite, and that the target is to get back to square one, bit both of those are less interesting.
3:58 I love the snake and ladder cutouts! The snake is so cute!
The people mebtioning a bounceback rule gave me an idea: how much agency is added by letting the player choose which direction they go? Would rational play reduce down to only going back if you'd land on a ladder, taking you up higher?
Could you calculate the standard deviation? What's the 95% confidence interval?
Someone in the other comments did a simulation, you could try asking them.
in my local version of the game, we don't overshoot the last square but we go backwards for the amount we overshoot, which quite similar to the aeroplane game.
Lovely video! I would have loved to see some explanations for why this infinite sum of matrices gives us the expected number of turns to win.
The climax is awesome 😍
Absolutely wonderful!
the way I was taught to play it is that if you over shoot, you have to cont back the extra spaces, i.e if you're on 7 and roll a 3: you go up to 9 and then 1 back to 8
If there are multiple flat irregular figures of different sizes and shapes (not convex polygons, they may even have curved sides), how can we make the gaps between them smaller or the total area (envelope area) smaller?
Wow didn't expect the philosophical life lesson of sometimes "its better to fall down and pick yourself back up than to never have fell down" from the board game snakes and ladders...
Fun fact: if you add an infinitely repeated grid to the snakes & ladders board, it becomes undecidable, because the system becomes Turing Complete (equivalent to a 2 counter Misky machine).
I also have a snobby view of Snakes and Ladders. It does have its place though, and that is to teach children how to lose without being a sore loser.
It also gives them a chance to win- my dad used to thrash me at chess for years until I finally beat him at which point he refused to ever play me again. Well I never actually beat him- I trapped his queen he refused to move for hours until I had to go to bed 🤔
The idea of connecting the snakes and ladders with behaviors is also a fairly painless way to teach small children to behave well.
@@glxxyz Ha! I think that might be a bit too competitive to be a top role model! And this is why serious games have a move timer.
@@jonathanrichards593 yes but a 7 year old playing with his dad doesn’t usually demand a game clock 😂
@@glxxyz 😀 Yep, usually they don't have to! Reminds me of someone I played backgammon with (just once) who wouldn't forfeit the round if he didn't accept a double, and an elderly grandfather who would only play chess if "we don't play taking queens". 🤪
I had a lot of fun playing the Royal Game of Ur with a friend and my nieces.
Interesting to learn that others played this game to where if you overshot the winning square you just didn't move. We played it either that overshooting was still a win, or if you overshot then you took steps backwards based on how much you had to spare. So if you were on square 8, and needed square 9, but rolled a 3, you'd move forward one square to and back two so that you landed back on square 7. Never heard of this version where you just don't move unless you have the right roll. But it's fascinating that this all has its origins in an Indian religious-themed game where overshooting the target equals being reincarnated. That's just epic.
Just in time for Cities: Skylines II. I thought I was making my city more efficient with that new road. I caused a terrible traffic jam, and now I know why.
Public transit is always the better option in the long run, for efficiency, for climate, and for pedestrians.
This made me think about simplest ways to modify the game to add the player agency and strategy.
First thought: player throws 2 dice and can pick one of them. But this doesn't seem to offer much strategy - randomness keeps the effect of the choice local, doesn't affect future choices for anyone.
I like the idea of playing snakes and ladders and selectively going down snakes that you would normally pass
I think there is room for more game maths on the channel 😊
I'm wild for Whist! Wish it were more well-known in the states, but such wistfulness bids bagatelle, so go fish.
That's a beautiful result. Is there a way to think about that so that it makes sense immediately? Like, how would you explain the answer to be the inverse matrix of I - Q?
what a co-incidence, i also got to know that this game was made in india just few hours ago
damn, game made just few hours ago and is already known around the world?
:)
@@NoNameAtAll2 yeah, but i didn't know about its origin
Perfectionism is a Snakes and Ladders game where there's one ladder skipping one tile to the end point and 8 snakes all taking you back to the start.
Based on the video, I am interested in trying a version of Snakes and Ladders where after each roll you get to decide whether to go forward or backward that many spaces. For example, if you roll a 7, you could go forward 7 like normal or backwards 7 if you thought that would position you to win better. That may add a little bit of intellect, strategy, or individual expression without being completely open-ended like he enjoys, and I'd love to see how you'd approach the strategy of making that decision mathematically.
who else came from the 301 video
Me
Dude really changed a lot.
What I love but also hate about this is that it opens up so many followup questions. What do all the matrices that produce 59 have in common? Is there a structure they share? How strong is the deviation from this expected value? Can you easily tell which addition of a snake would make the value go up or down? What happens if you build a loop in your board? And many more. Markov chains are really a funny thing.
It's that nice snake that help you reach nirvana early, that made me hit like. 😁
There's a young age where agency is unhelpful. Games of complete chance are best if your brain can't really do strategy yet.
The original game of snakes and ladders was (like monopoly) a philosophical game intended to teach us humility, that we have no agency in real life. I can't say I agree, but it wasn't accidental.
Very true
I loved playing the game in my childhood.
Thanks
❤
I wonder if creating the ability to change the snakes/ladders during the game would suffice to make it stategic enough.
My thought was: Whenever a player lands on the "passive end" of one by rolling - not taking the forced path from the "active end" - they were allowed to move the respective active end by N (like 2-5) squares horizontally/vertically - but not invert or level the up/down direction. (Read: Not change snake to ladder and vice versa. That could be too powerful. But maybe not!)
That could enable you to create better opportunities for yourself, or worse for your opponent on the go. Would ofc need some fine tuning for the actual freedom to move the ends, but as a concept I could see it make it much more interesting.
If you want agency in your game of snakes/chutes and ladders, play with two dice and on your turn you get to choose whether you roll one or both.