The Beautiful Math of Snakes and Ladders - Numberphile
Vložit
- čas přidán 31. 10. 2023
- Featuring Marcus du Sautoy. Book details below. The game is also widely known as Chutes & Ladders. More links & stuff in full description below ↓↓↓
Around the World in Eighty Games (Amazon): amzn.to/3snW2bD
More about the book: www.simonyi.ox.ac.uk/books/ar...
Marcus du Sautoy books: amzn.to/3QkSjnf
Marcus du Sautoy website: www.simonyi.ox.ac.uk
More videos with Marcus: bit.ly/Marcus_Numberphile
Dice videos on Numberphile: bit.ly/Dice_Videos
Patreon: / numberphile
Numberphile is supported by Jane Street. Learn more about them (and exciting career opportunities) at: bit.ly/numberphile-janestreet
We're also supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumberphile
Our thanks also to the Simons Foundation: www.simonsfoundation.org
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Video by Brady Haran and Pete McPartlan
Thanks Debbie Chakour for helping with error spotting!
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - Věda a technologie
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
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
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
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?
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.
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) ?
Love the “bong cloud” opening and the crashing eval bar.
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
18:40 Legendary bongcloud opening by Donny
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.
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!!
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
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_ .
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
Nice, cool spin on the classic game "Eels and Escalators"!
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.
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.
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).
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!!).
Found in a British museum? You don't say!
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. :)
Donny playing the bongcloud opening I found very humorous
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)
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!
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.
Marcus is such a legend. I watched his documentary The story of Mathematics and it completely changed how I look at Mathematics
The chess history was mind blowing. Excellent production all round, thank you!!
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.
That colorful rendition of “The Ambassadors” looks cool!
I loved playing the game in my childhood.
Thanks
❤
Absolutely wonderful!
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.
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!
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.
I love the bongcloud at the end there
I like the (unnamed) reference to the Brasess paradox. I always wondered where this could also apply, besides traffic networks.
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.
3:58 I love the snake and ladder cutouts! The snake is so cute!
A very nice use of linear algebra!
I loved his book "Music of the Primes"!
It's amazing that a video a bout solving a math problem about S&L is far more fun than actually "playing" S&L
Beautiful.
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!
Great Video Marcus!
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 love this channel!
the fact that they made Trump play the bongcloud is nuts
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 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.
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.
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 :)
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.
Fascinating.
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.
This guy is great!
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.
I had a lot of fun playing the Royal Game of Ur with a friend and my nieces.
Love it thanks
His other book The Music Of The Primes is absolutely amazing.
HAPPY BIRTHDAY NUMBERPHILE 🎉🎉🎉
The climax is awesome 😍
Please do something on squads packing. I think it’d be fun to watch.
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.
Love the bongcloud 😅
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.
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)
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!
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.
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.
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.
Brilliant
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.
We play with a D6 and a D8 - you are free to choose whichever die you want when it's your turn to roll.
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.
13:04 an absolutely awesome thing is that Ramanujan actually discovered this!
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?
Fun and profound
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.
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.
If you want to retain your sanity and actually have a career and friends, run away from Collatz.
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.
It's that nice snake that help you reach nirvana early, that made me hit like. 😁
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.
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?
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.
this somehow feels very VERY familiar. it's awesome!
I were actually wondering at the start why he didn't include the 9 there, but then I tealized that the missing numbers would have to sum to 1.
so bu just subtracting the total from 1 you would get the missing 9'th column;
of course in this situation you're working with matrices so 1 is I and numbers have various numbers but... it's working in the same way.
Couldn't you leave the last position there? it'll have 0 everywhere and 1 on the diagonal so the answer you're looking for would naturally accumulate at that position, which would be beautiful.
I guess for the computer it's better to leave it off.
AFAIK, it's more common to include the "terminal" or "absorbing" states in the transition matrix. But in this particular case, it's more useful to leave them out, because what you get at the end is a matrix that only represents "live" states.
I think there is room for more game maths on the channel 😊
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
0:15 Somebody made the conscious choice to edit the narration down to: "it's a beautiful board with these snakes, and ladders on." Movingly descriptive, you are a shining star
Yeeesss, I knew he’d say backgammon
Love This Game ❤
I'm wild for Whist! Wish it were more well-known in the states, but such wistfulness bids bagatelle, so go fish.
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.
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...
The bongcloud opening! 😂😂😂
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)
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.
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?
To make the game interesting one could alter the rules such that the player whose go it is may choose whether to move forwards or backwards. Generally forwards would be better, but, as was shown here, it might be wise to slip down a short snake in order to have the chance of subsequently climbing up a long (and steep) ladder.
You could even gamble your chances further by deciding which way you will be moving BEFORE casting the die. (Of course rules would need to be set for what happens when you go below zero.)
Considering the traffic, i wonder whether the public can use the markov chain to optimize the traffic by manipulating the waiting time at each crossing, such that it can reduce the total waiting time.