Vsauce!
Kevin here, with a game you can’t possibly comprehend.
Really, it’s too hard for you.
Your brain can’t take it.
Look, I’ll show you:
That’s it.
Are you sweating yet?
You should be.
Alright, as you stare into these dots your brain starts to short circuit, doesn’t it?
No.
Why would it?
I mean… it’s just two dots!
I can draw out all the possible moves for a game this simple.
Look, I'll show you.
Okay, my award-winning handwriting aside, this was a lot more complicated than I thought
it was gonna be.
And the thing is… as it scales, analyzing what appears to be the simplest game in the
world doesn’t just break your brain, computers can’t even crunch the possibilities.
Here’s how it works.
The game of Sprouts starts with any number of dots placed… anywhere.
The boundaries of the game board are limitless, so put the dots wherever you want.
We’ll play with two dots.
But ya can’t just play with yourself, you need an opponent.
Yes, yes.
A worthy adversary, you need.
Let’s go over the three rules of Sprouts.
First, a player draws a line from one dot to another, or from one dot back to itself.
Lines can be curved or they can be straight… they just can’t cross another line or themselves.
When you draw a line, you get to place a new dot anywhere on that new line.
And in Sprouts, no dot can have more than 3 lines coming from it or going to it.
Once a dot has 3 lines -- it’s an unplayable, dead dot.
The winner of Sprouts is the last person to draw a line.
Or to put it another way, the player who can’t draw another line loses.
Okay, now my friend and I will play a two-dot game of Sprouts.
Go first, I will!
Alright, Yoda.
Dude.
Okay Hang on!
Alright fine.
Just go.
Alright, alright.
Great job.
You gotta make sure you draw a new dot on the line.
Yes, yes, yes.
Invented this game, I did!
Sprouts trained many Jedi minds, hundreds of years!
Hundreds of years?
No, No, No.
Sprouts was created in 1967 by Cambridge mathematicians John Conway and Michael Paterson.
My turn it is!
Dots lead to lines.
Lines lead to dots.
Sprouts is the path to the light side of the...
And I just won.
Alive this dot still is!
Yeah but you can’t connect it to anything.
Look.
Dead, dead, dead, dead and you can't draw a line to get to this one.
*angry noises*
Explain why I lost you must!
Alright, the first player can always lose a two dot game against a perfect opponent
because, even though it’s complex -- your brain can analyze two dot Sprouts.
I mean, you could literally just memorize this whole game tree chart to make exactly
the right moves as player two, rendering player one helpless.
Player 2 can engineer the two-dot game so that it ends on a 4th move win for them -- but
Conway and Paterson figured out when the game has to end.
Check it out.
They discovered that a game of Sprouts must be completed by 3n - 1 moves, where n = the
number of starting dots.
So that means a two-dot game is concluded in no more than 5 moves because (3*2) - 1
= 5.
So problem solved, right?
No.
Why?
Because the game can play out in many different ways.
What’s interesting is that player 1 actually has 11 ways of winning compared to player
2 having only 6.
It’s just that if player 2 knows exactly what they’re doing they can always facilitate
one of their 6 winning outcomes.
What’s amazing to me about Sprouts is… this is all with just two dots!
As soon as we add a third dot to the game…
Become more difficult to analyze than Tic-Tac-Toe it does!
Adding a third dot at the beginning means that we could have up to 8 moves to determine
a winner since (3*3) - 1 = 8, but we have more possible moves to start.
It isn’t hard to figure out how many possibilities we begin with -- it’s just [n(n + 1)] / 2.
So here we have our number of dots at start and number of initial possible moves.
[n(n + 1)] / 2.
And number of moves to determine a winner that's 3n -1.
So if we have 2 dots to start the game, the initial possible moves would be 3.
With 3 dots to start that jumps to 6.
For 4, it’s 10.
For 5 it's 15.
And so on.
Now that we know this, what’s the guaranteed strategy for winning every time?
There isn’t one.
Because since the game can develop in so many different ways, especially once you start
playing with 4 or 5 dots, players will have to constantly re-analyze and adapt their moves
to force their opponent into a loss.
You need to factor in which dots are still live and which ones are dead.
You need to force your opponent into bad moves -- and eventually no moves at all.
There’s just no formula for this.
Adapt and overcome, you must!
What we do know -- kind of -- is who can win.
The first real glimpse into dominant Sproutology came from Denis Mollison, a Professor of Applied
Probability at Heriot-Watt University.
Conway bet Mollison 10 shillings -- before the 1971 decimalization of the British monetary
system and equivalent to a little under $10 today -- that he couldn’t complete a full
analysis of a 6-dot Sprouts game within a month.
Well, he did.
And it only took 47 pages.
I'm not looking forward to picking those up.
Mollison’s analysis led to the conclusion that Sprouts games with 0, 1, or 2 dots could
always be won by the second player.
Games with 3, 4, and 5 dots could always be won by the first player.
The second player can always win with 6 dots, but that’s where the computational power
of the human mind started to strain under the weight of the Sprout.
There were just too many scenarios to compute.
WAIT -- how can you have a game with 0 dots?
Well, if there are zero dots, the first player wouldn't be able to draw a line, so the second
player wins.
One thing that’s really weird about Sprouts is… you’d think that playing the game
would visually result in nothing but near-random lines and patterns but Conway and Mollison
unearthed something: bugs.
They call this..
FTOZOM!
The Fundamental Theorem of Zeroth Order Moribundity, which states that any Sprouts game of n dots
must last at least 2n moves, and if it lasts exactly 2n moves, the final board will consist
of one of five insect patterns: louse, beetle, cockroach, earwig, and scorpion, surrounded
by any number of lice.
Scorpions are arachnids, not insects, but these guys don’t have time for biology.
And that’s the FTOZOM for you.
But this was all 50 years ago.
How has Sproutology progressed since?
Well, it lay dormant for decades until Carnegie Mellon University fired up its computers in
1990.
Using some of the most advanced processors of the era, computer scientists David Applegate,
Guy Jacobson, and Daniel Sleator were able to map Sprouts conclusively up to 11 dots.
They found the same pattern: 6, 7 and 8 favored the second player.
9, 10 and 11 favored the first player.
There appears to be an endless 3-loss-3-win pattern with a cycle length of 6 dots.
In 2001, Focardi and Luccio published “A New Analysis Technique for the Sprouts Game”
that showed a simpler proof of Sprouts to 7 dots by hand.
Now we’re up to 11.
So, we’re making progress on the pencil and paper front.
But what about…1,272 dots?
Or a billion dots?
We’re not even close.
Like really… not close.
Julien Lemoine and Simon Viennot created a computer program called GLOP that could calculate
Sprouts results more efficiently, and in 2011 they were only able to process up to 44 dots
consecutively.
Their results were in line with Carnegie Mellon’s cycle of 6, but the computational power -- and
time -- required to get us to proving results with, say, a million dots, is way beyond our
reach.
It’s been over half a century since Conway and Paterson were drinking tea in the Cambridge
math department’s common room and playing around with inventing a simple pencil and
paper-based game.
They noticed that the game was spreading throughout the department and then the campus, seeing
students hunched over tables and spotting the discarded remnants of epic Sprouts battles.
They stumbled on something so big and so complex that the human mind can’t fully fathom it
beyond a very limited point -- and it all started by just connecting a couple of dots.
And as always -- thanks for watching.