1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 11, 2014 #1
    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. jcsd
  3. Oct 11, 2014 #2

    jedishrfu

    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...
     
  4. Oct 11, 2014 #3
    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.
     
  5. Oct 12, 2014 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  6. Oct 12, 2014 #5
    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.
     
  7. Oct 12, 2014 #6

    jedishrfu

    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/
     
  8. Oct 12, 2014 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  9. Oct 12, 2014 #8

    jedishrfu

    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.
     
  10. Oct 12, 2014 #9
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Mathematical Game Theory (Drawing gametree for Tic-Tac-Toe
  1. Game Theory (Replies: 4)

  2. Game theory (Replies: 2)

Loading...