This course will cover the mathematical theory and analysis of simple games without chance moves.

Loading...

From the course by Georgia Institute of Technology

Games without Chance: Combinatorial Game Theory

115 ratings

This course will cover the mathematical theory and analysis of simple games without chance moves.

From the lesson

Week 7: What You Can Do From Here

The topic for this seventh and final week is Where to go from here.

- Dr. Tom MorleyProfessor

School of Mathematics

Hello again. Games Without Chance, Tom Morley.

Let's look at atomic weights. [SOUND] Now.

Let's look at our, one of our favorite games.

A nin heap of size one. Not terribly exciting.

No one's really, oh let's go play in them heaps of size one.

Nobody's really that excited about it. But, this is a new symbol.

That's the integral sign, but this is the way the sign is used in theory.

And has nothing to do really with integrals.

This is the heating of star by three. So instead of zero.

You say zero plus three over here. Instead of zero over here, you say zero

minus three. And this is a heated game, and this is a

hot game, because left is, wants to play this, because then left gets three

points, or three, and right wants to play this because then right gets three

points, or minus three, to the left. So this is a hot game.

So we started off with a really kind of boring game and created a hot game.

Okay, now I resolve to Simon-Norton that any game is actually a number plus the

sum of the heated version of infetesimal. Okay.

Infinitesimal would be a game that, that's less than one over two to the add

for every add and greater than minus one over two to the add for any add.

So, so you can't know anything, you can't know all about games unless you know all

about infinitesimals. And infinitesimals can be really

complicated. So here's one way of analyzing at least a

very large class of infinitesimals. the game is called all small.

If whenever left has a move so does right, and whenever right has a move so

does left and this is true for both the game itself for any position possible in

play. So for instance the game, hmm, zero this

is the game one I believe. this right, left has a move but right

doesn't have a move so this not all small.

So an all small is your, you can prove are infinitesimal.

Now hmm, here's the result and this is computable and this is probably actually

the most complicated. Most intricate or long proof in winning

weights by one. If g is all small then then there is

again capital G, computable from g in the various ways and they go, go through the

ways its computable such that g times, capital G times up, so this is a multiple

of up. we have to eventually say what that means

so that g minus this multiple of up is pretty close to zero.

It's caught between up plus star plus an unspecified nim heap and greater than or

equal to down plus star plus an unspecified nim heap and from this.

this another approximation result that an all small game is very nearly subject to

this error a multiple of up. And this is, this is, this can be used

to, to analyze the play of all small games.

But enough of this theory, let's look again at divided fair shares and varied

pairs. If you remember what we have for fair

shares and varied pairs is that you can, it's here somewhere.

you can take, take, take a coin, take a take a stack of coins and, and divide it

into any number of equal stacks. Or you can take two stacks that are not

equal and combine them. So this is, this is a fun party game.

Let's start with a stack of three over here, a stack of three over here.

A stack of two and a stack of two. And let me remind you, you can take any

stack, divide it into any number of equal stacks.

You can take any two unequal stacks and combine them.

So[SOUND] here we have a stack of three, stack of three, stack of two, stack of

two. Ten coins in total.

Go ahead, it's your first move.

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.