Mathematical Game Theory (Drawing gametree for Tic-Tac-Toe

[ctownballer03]

Homework Statement

Draw out the game tree for tic-tac-toe

Homework Equations

The Attempt at a Solution

I'm just thinking about it and I don't know how to start. To draw out the entire gametree, we'd have thousands and thousands of branches. So based on symmetry there is only 3 starting points we need to reference I think. From there I'm just trying to see which plays would be symmetric, but I'm still lost

The key is to use symmetry somehow to make the game tree more reasonable, but I'm really struggling and just looking for advice/hints.

 

[jedishrfu]

Welcome to PF!

Try staring with the center move. Nearly everyone who plays chooses that move. From there you have two moves corner or side...

 

[ctownballer03]

Welcome to PF!

Try staring with the center move. Nearly everyone who plays chooses that move. From there you have two moves corner or side...

Thanks!

So my understanding is that due to symmetry the only three starting positions I'd have to show in the game tree is a corner, a side, and the middle, since rotating the game would result in every starting point being taken. So symmetrically speaking, I believe these three starting points should cover every starting point.

 

[haruspex]

Thanks!

So my understanding is that due to symmetry the only three starting positions I'd have to show in the game tree is a corner, a side, and the middle, since rotating the game would result in every starting point being taken. So symmetrically speaking, I believe these three starting points should cover every starting point.

Yes. How many positions are there after one move each?
Do you have to cover every position, or are you allowed to assume a player will always take an obvious win? Or perhaps you only need to create a game tree which provides the first player with a winning strategy?

 

[ctownballer03]

Yes. How many positions are there after one move each?
Do you have to cover every position, or are you allowed to assume a player will always take an obvious win? Or perhaps you only need to create a game tree which provides the first player with a winning strategy?

I'm pretty sure I have to cover every position but I'm not 100%, I was wondering the same thing earlier today so I e-mailed my professor about it but I haven't heard back.

No, I'm supposed to be making a game tree for a tic-tac-toe, ie every situation. The only hint he gives is to utilize symmetry to make it more doable without taking up 200 sheets of paper.

 

[jedishrfu]

Found this amusing tictactoe game map on XKCD comics using Google which is not the solution you're looking for:

http://xkcd.com/832/

 

[haruspex]

I'm pretty sure I have to cover every position but I'm not 100%, I was wondering the same thing earlier today so I e-mailed my professor about it but I haven't heard back.

No, I'm supposed to be making a game tree for a tic-tac-toe, ie every situation. The only hint he gives is to utilize symmetry to make it more doable without taking up 200 sheets of paper.

I have a nasty feeling your prof has not realized how messy this is going to get. After two moves each, I calculate there are over 80 positions.

 

[jedishrfu]

I have a nasty feeling your prof has not realized how messy this is going to get. After two moves each, I calculate there are over 80 positions.

That sounds right I remember seeing the solution in an old book on Basic game programming published by Radio Shack in the heyday of first personal computers.

 

[ctownballer03]

I have a nasty feeling your prof has not realized how messy this is going to get. After two moves each, I calculate there are over 80 positions.

Oh he knows lol.. He's the chair of the math department and specializes in Game Theory. He teaches the two class sequence once every two years and every person I've talked to who has taken it in the past said that he simply gives more work than any human can complete in a term. I've also heard he grades relatively leniently though and doesn't expect anyone to finish all his assignments.