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

113 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.