• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

game theory...

sao123

sao123

Lifer
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?
 
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.
 
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.
 
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.
 
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.
Click to expand...

rotations & transpositions simplify the problem greatly?
 
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.
 
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.
 
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.
Click to expand...

rotations & transpositions simplify the problem greatly?
Click to expand...

There are only three different starting positions... corner, middle of an edge, and center of board.
 
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.
 
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 😀
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top