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

Tags:
1. Oct 11, 2014

### ctownballer03

1. The problem statement, all variables and given/known data

Draw out the game tree for tic-tac-toe
2. Relevant equations

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

Last edited: Oct 11, 2014
2. Oct 11, 2014

### Staff: Mentor

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

3. Oct 11, 2014

### ctownballer03

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.

4. Oct 12, 2014

### haruspex

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?

5. Oct 12, 2014

### ctownballer03

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.

6. Oct 12, 2014

### Staff: Mentor

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

http://xkcd.com/832/

7. Oct 12, 2014

### haruspex

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

8. Oct 12, 2014

### Staff: Mentor

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.

9. Oct 12, 2014

### ctownballer03

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.