game theory...

[sao123]

I was trying to do some analysis, (albeit im only in an infancy stage) on the game of tic tac toe...

I am curious if the game (mathematically speaking) is X's game to win, or O's game to lose... If both player play optimally, is it a guarantee stalemate, or a guarantee X win?

I started off analysisng X's first move, whereby it seems that in ranking order a corner would be the best choice, the center being second, and finally, a side choice being an absolute blunder. then I began anaylising O's responce... and the tree became very large after that...

Can someone offer some useful information or general suggestions?

 

[silverpig]

I spent a little time thinking about it a few weeks ago and came to the conclusion that if both players play perfectly the result will always be a draw.

 

[edcarman]

You could probably use symmetry to simplify your analysis. The response to X playing top-left first should be the same (relatively) to X playing any of the other corners.

 

[QuantumPion]

With optimal play it is a draw regardless of starting position.

 

[Peter]

Someone hasn't been watching their 1980's movies ... WOPR has figured that out for you already

TTT always results in a tie if no mistakes are made.

The complete game 'map' is fairly simple, only nine moves deep and branching through just a couple hundred 'valid' board states. Totally unlike chess.

Here's an important CS hint to all this: You need to realize it's NOT a tree.

 

[sao123]

Originally posted by: Peter
Someone hasn't been watching their 1980's movies ... WOPR has figured that out for you already

TTT always results in a tie if no mistakes are made.

The complete game 'map' is fairly simple, only nine moves deep and branching through just a couple hundred 'valid' board states. Totally unlike chess.

Here's an important CS hint to all this: You need to realize it's NOT a tree.

rotations & transpositions simplify the problem greatly?

 

[Peter]

Well sure. For each board state, there are flips, rotates and mirrors that look different but aren't.

But again: The key to these things is that the map of possible games (sorry, I'm lacking the correct name for this in English - my CS degree is in German ) is not a tree. Different openings can lead to the same intermediate board state.

 

[Cogman]

Solved game is what you are looking for. To date, Checkers is the most complicated solved game. If played perfectly, I believe that black always wins.

Edit: I was wrong, it ends in a draw.

 

[silverpig]

Originally posted by: sao123

Originally posted by: Peter
Someone hasn't been watching their 1980's movies ... WOPR has figured that out for you already

TTT always results in a tie if no mistakes are made.

The complete game 'map' is fairly simple, only nine moves deep and branching through just a couple hundred 'valid' board states. Totally unlike chess.

Here's an important CS hint to all this: You need to realize it's NOT a tree.

rotations & transpositions simplify the problem greatly?

There are only three different starting positions... corner, middle of an edge, and center of board.

 

[Steve]

Originally posted by: Peter
Here's an important CS hint to all this: You need to realize it's NOT a tree.

Nor is the internet a truck!

 

[Polish3d]

If you immediately know the candlelight is fire, the meal was cooked a long time ago

 

[MagnusTheBrewer]

Any moment may be your next.

 

[hypn0tik]

As others have stated, optimal play results in a draw.

 

[DrPizza]

If you don't count rotations and reflections as being different, there are only a few dozen possible outcomes...


x corner - O adjacent corner
x corner - O opposite corner
x corner - O adjacent edge
x corner - O opposite edge
x corner - O center

x edge - O adjacent corner
x edge - O opposite edge
x edge - O opposite corner
x edge - O center
x edge - O "kitty-corner" edge

x center - O corner
x center - O edge

These are all the possible first two moves. Number them 1 through 12.
Case #1
If x goes to an open corner, O is forced to block, X takes other corner, forces a win.
If x takes an edge next to his corner, O blocks, x blocks, game ends in stale mate
If x takes center, then

• O takes edge next to O's corner, x blocks & forces a win

• O takes edge next to x's corner, x takes corner and forces a win

• O takes corner, x blocks, game ends in stale mate

You can continue with the other 11 openings; you'll find that they lead to many overlapping positions (i.e x corner first move, center 2nd move leads to the same positions as center 1st move, corner 2nd move)

If you really want to have fun, you can do this as a combination/permutation problem and figure out exactly how many arrangements are possible.

Perfect strategy:
O always takes the center when available. If the center isn't available, O takes a corner. X cannot force a win under these circumstances.
I'm always willing to wager someone $1 vs. $100. They pay me $1. I'll play them 100 games of tic-tac-toe. If they win any of those 100 games, I'll pay them $100.

 

[TallBill]

As a very trivial example, the game of tic-tac-toe is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren).

LOL