Tic Tac Toe (noughts and crosses) is always such a nice example.
I was thinking about strategies and decided to implement a program that plays Tic Tac Toe according to John von Neumann’s minimax. This is a kind of meta-strategy that can be used for playing any game: Always chose the move that will minimize the maximum damage that your opponent can do to you.
The algorithm works recursively by looking for the move that will let an optimally playing opponent inflict the least damage. The opponent’s strategy is calculated by way of the same algorithm, and so on. This means that on the first move, the computer investigates the entire game tree – it considers every single possible Tic Tac Toe game and then choses randomly among the best (least dangerous) moves.
Have a go at http://www.half-real.net/tictactoe/
- Here’s a document with every single game of Tic Tac Toe. It gives the following numbers.
- 255,168 unique games of Tic Tac Toe to be played. Of these, 131,184 are won by the first player, 77,904 are won by the second player, and 46,080 are drawn.
- This supports the intuition that it is an advantage to begin the game.
- These numbers do not take similar board positions into account – rotating the board, mirroring it and so on. It does not matter which corner you place the first piece in, but this is not taken into account here.
- If neither player makes a mistake, the game is drawn (but we knew that already).
- This is an exercise in examining the objective properties of a game. There are two interesting sides to this:
- 1) The objective properties of Tic Tac Toe really matter for our enjoyment of it: It is a boring game because there are so relatively few combinations.
- 2) On the other hand, humans clearly play the game in a different way than the computer. The computer’s playing style lets us make some observations about how humans play games.
- To the computer, the first move is the most complicated (takes around a second on my 2ghz machine). This is unlike human players who seldomly have any problem deciding what to do on the first move.
- The program assumes that the opponent does not make any mistakes. Humans do make mistakes, of course, so adding some amount of randomness in algorithm would probably make it a better player against human opponents.
- The number of possible unique games is larger than I would have guessed, but this indicates how we humans are very good at identifying patterns. Faced with the huge number of variations in a game like this, we simply identify some general properties of Tic Tac Toe: Beginning in the middle is a good thing; if your opponent begins in the middle, you must pick the corner; a good way of winning is to threaten two squares simultaneously.
- We think about games like this in fuzzy and chaotic ways – this gives us a lot of flexibility.
- It is the same fuzziness that leads us into making stupid mistakes.
- On some level, it is our fuzzy way of playing games that allows us to have fun. If we simply played with the unimaginative brute force strategy that the computer uses, it would definitely be work rather than play – and nobody would have any fun playing against us, for that matter.
So I really can’t win? Damn. I guess I’ve just wasted 2 hours trying, then ;-)
Anyway, I really like the ‘hint’ option, it would make a nice guide when exploring remote areas of the possible game-space… (Some level of randomness would ofcourse also be required, since the computer currently picks the same response to a given scenario, even though multiple ‘draw’ tactics coexist.)
OK, it now choses randomly among equivalent moves – this makes it a lot more interesting opponent.
I’m curious (or perhaps mathematically challenged!) but how did you calculate your possible number of games and win/loss ratios? I just happned to be reading about Tic Tac Toe and computers in Danny Hillis; book “The Pattern on the Stone” where he points out that there are 19,683 possible games states (9 to the third power–9 square, three possible states X, O or blanks.) That number includes lots of impossible states (like all nine spaces taken up with Xs).
Just trying to put this all together!
Thanks.
OK, I goofed that up. It’s 3 to the 9th power=19.683
The number of total games was calculated by brute force: For every possible move, I found every possible subsequent move until there was a winner, a draw, or the board was full. To document, I made this file with every single game in it.
255,168 is larger than the theoretical number of positions because many positions can be reached in several different ways (i.e. the pieces can be placed in different order).
The 3 to the power of 9 number is misleading in that many of the positions will not be actually reachable – many of these boards will have both noughts and crosses having three in a row.
The theoretical number of games that can be played without considering games that end is 9! = 362,880.
Googling a bit, it turns out that a few people have reached the 255,168 number mathematically.
3D Tic Tac Toe seems to make a much more interesting game than 1D. This is a game in which the board is replicated twice, yielding a 3x3x3 grid (there are varieites, such as this 4x4x3 Atari 2600 game.
Anyway, in practical, human terms, 3D tic tac toe seems to force the human mind beyond its ability to (easily) mentally map the game space. I didn’t try to do the calculations, but I’d be curious to know. Can you modify your applet to accomodate a 3x3x3 grid?
It’s technically easy to modify the applet to a 3x3x3 grid – but I suspect it may suddenly take several years to calculate the initial move, so you need to start doing all kinds of clever things to make it work practically.
That’s the whole problem – it is also technically easy to write an unbeatable chess program using the minimax algorithm, but the sun will burn out many times over before it’s finished with the first move …
i was just wondering what it means if i beat that program?
If you beat the program, I’ve made a mistake somewhere. In case, please post your seqence of moves.
Did you take into account the fast pace at which computers improve when you said that it would take a long time for the computer to figure out its first move in the 3d tic-tac-toe game? I mean, if it was a 100ghz machine, would it be really quick at it?
A really rough and completely untrustworthy estimate for the time it would take to calculate the first move on 3d Tic Tac Toe:
Tic Tac Toe has 9!=362,880 possible games if we don’t take into account that the game stops when someone wins. (The actual figure is the 255,168 mentioned above.) This takes 1 second to calculate on a modern PC.
3d Tic Tac Toe has 27!=10,888,869,450,418,352,160,768,000,000 possible games (again without taking into account that the game stops when someone wins).
In other words, 3d Tic Tac Toe is (27!/9!)=30,006,805,143,348,633,600,000 times more complex on the first move. (This is really imprecise since we are ignoring the fact that the games are considered not one by one but by branching, and also ignoring that 3d games can be 3 times longer than 2d games).
30,006,805,143,348,633,600,000 seconds corresponds to 422,893,132,974,641. That is, it would take 422 trillion years for the program to calculate the first move of 3d Tic Tac Toe. A 100ghz machine would be able to do it in only 8,44 trillion years.
So the question is: If we assume that Moore’s law guarantees a doubling of the computational speed of a the computer every 18 months, when will a computer be able to calculate the first move of 3d Tic Tac Toe in one second? Which is to say, when will computers be 30,006,805,143,348,633,600,000 times more powerful than they are today?
A quick calculation reveals that their speed has to be doubled 75 times, which will take 112 years with the current rate of progress.
So computers will be fast enough to play 3d Tic Tac Toe using this algorithm around the year 2116.
This estimate comes without any guarantees …
Because the tic tac toe board is symmetrical about two axes (for 2 times two equals quadruple symmetry), the number of interesting states is much smaller than 19683. Here is a slightly less naive estimate:
Total spaces on board: 9
Possible states for each space: three (empty, X, O)
Symmetric spaces: 4 mutually symmetric corners + 4 mutually symmetric sides
3 states per square, 8 (outer) squares, quadruple symmetry (excluding “all squares empty” state): (3^8-1)/4 + 1 = 1641 states
outer states times centre square states: 1641 x 3 = 4923
In fact, because at all times half of the occupied squares must be filled with X’s and the other half (+/- 1) must be filled with O’s, the number of states is far fewer. I don’t personally have the knowledge of combinatorial theory to work it out, however. It’s less than half, at any rate, and probably less than five hundred.
Did you seriously work out all 255,168 games by brute force ie. Going thru each possible game manually?
Have you been committed since doing that? I can’t imagine what type of character has the patience and
desire to do such a thing. Surely it must have crossed your mind that using combinatorics would be the
far more intelligent thing to do.
By the way does your mini-max algorithm use some sort of alpha-beta pruning to trim fruitless paths
in the search tree?
The program went through all 255,168 games by brute force – not me …
It was just a small experiment – the program is pretty dumb and doesn’t use any sort of pruning either. A lot of the 255,168 combinations include one player overlooking an obvious win for 6 consecutive moves and so on.
Why is it that 3d Tic Tac Toe has 27! (10,888,869,450,418,352,160,768,000,000) possible games (again without taking
into account that the game stops when someone wins)? i know that it is pretty obvious that there are 27 squares but
what is the logic behind this 27!?
It’s combinatorics: The first piece can be placed in any of 27 squares, the second piece can be placed in any of 26 squares, the third in any of 25 and so on.
Hence the number is 27x26x25x24x23 … x3x2x1.
Quote: Beginning in the middle is a good thing.
Wrong that means that 1/2 of the squares lead to draw.
Start as corner means only 1/8 squares leads to a draw.
Interesting website ;)
However, my version of the Impossible Tic Tac Toe “AI” needs only 200 milliseconds for the first move, on a 2.2 GHZ Machine! I used my own recursive solution, which is comparable to the Minimum-Maximum solution!
You might be interested in another tic tac toe implementation in javascript:
http://ostermiller.org/calc/tictactoe.html
3D Tic-Tac-Toe is quite nice for a human vs. human game. I’ve tried it on paper even with a 4x4x4 space.
But with 4D it gets really tricky. The 3D view can be accomplished by drawing three 3×3 surfaces on top of each other using some perspective in the drawing. Now if you put three stacks of these 3x3x3 “towers” beside each other, you get 3x3x3x3.
Hmm, maybe I’ll have to try to make a computer game out of it…
Altho, in no means impossible and not using the same ideas you’ve used here, I have made a version of 3D Tic-Tac-Toe (where the person with the most lines at the end of the game wins).
My version has simple AI, basically;
IF Computer can do a move that will make a line it will
ELSE IF It can do a move to block the oppositon making a line it will
ELSE IF its the first move, it will place in a corner (leads to most possibles)
ELSE do a random move
Intreasting piece of trivia: There are 76 possible lines to be made on a (4x4x4 board)
Take a look at;
http://www.ryan-barlow.com/connect4.htm
hi there,
im from singapore, currently doing this mini project on tic tac toe programming on VB.net. i happened to find your project by chance and found it quite complete as supposed to others and i was wondering if you could be as kind to send me the source code for reference purposes as im totally new to programming of any sorts.
Thanks
Cheers
Hi ,
i am a biginner at programming in VB. Net but am grasping it fairly fast. I have tried to create the exact game and have made the computer randomise where to put the next move. Now i have reached the part where strategy comes into play and am stuck as i have no clue about puttin the minimax algorithm into code.
i have told the program to look for patterns of X’s(user symbol)
all the patterns i had to put in as in if the top left and middle are x then top right should be o
it works fine but there is no offence i cant make it do moves and check for a defence at the same time. it is going to drive me mad
would it be possible to get help on this or if possible the code for the minimax algorithm or how to put it into code. any thing will be appriciated
thanks a lot
Zo$o
Interesting. I programmed my own minimax 3D tic tac toe game late last year, though I implemented a strict ply of 6 moves ahead so that it would make a move sometime this century. I am curious though as to why you are using minimax over the equally capable alpha-beta method. The difference is only 2-4 lines of code and the search space is cut in approximately half.
Yes, it is rather simple.
One explanation is that I was interested in trying to do a minimax algorithm because I was reading Neumann and Morgenstern. The other is that I can’t claim to be an AI programmer, I was simply trying to think about when a game is too simple to work (like ttt is for adults). I will have a look at the alpha-beta thing.
I’m wondering how could fuzzy be implemented in tic tac toe?
Im a first year computer science student and have been learning about 2 player perfect information games, minimax algoristims and pratically everything that you have discussed in this blog. i was wondering if i could also have a copy of anything that you have used to do this, source code, algoritims etc the more the better. it would be a great help to understand a real implementation of the above algoritims. Thanks
My daughter did a Science Fair experiment on Tic Tac Toe in 2000. Her conclusions assume niether player makes a “dumb” move. “X” has only three opening moves; side, middle or corner. Her conclusions were:
When “X’s” first move is in the MIDDLE:
It’s very good even my maths teacher could’nt crak it!!!!
I am very much benefited by seeing your observation that the first person who begin the tic-tac-toe game is more advantageous. I also got how we got the total possible number of game as 3 pover 9 in this game by seeing the observation of MR DAVID Thomus,Dec30,2003. to your thesis on tic-tac-toe.
Thanks,
U.Annadurai,m.sc;m.phil;m.phil;
Lecturer in Maths,
Dept. of Maths.
Gandhigram Rural University,
Gandhigram,Tamilnadu,
India. Pin code 624302
i beat it
nice game
very very difficult game but still very nicely implemented
i won the game
interesting work…
do you know where i can get the game tree for the possible games of tic tac toe??
I have the file here, but no actual tree:
http://www.jesperjuul.net/tictactoe/allgamesoftictactoe.zip
thank you I loved your information and I win all the time now! I have looked everywhere except here yo find tic-tac-toe Information that isn’t a bunch of shit! Bye bye now tak care!
I recently posted this on a web forum and some one on the site claimed they beat it by randomly clicking on the squares. I don’t think that’s possible, is it?
Bruce, I am pretty sure it is impossible to beat the program (famous last words).
thakns
You mentioned the symmetry of the game (at least eight-fold due to reflections and rotations of the board), and paring the decision tree such that neither player makes an obvious mistake. If you do both of these, then there are 1145 meaningful games.
Specifically:
* Two games are the same if the sequence of moves as seen by the players is the same at every step, to within symmetric configurations of the board.
* A game is over when the outcome is determined, even if the three-in-a-row has not been completed or the board has not been filled in.
* Players never make the following two “obvious” mistakes: 1) Failure to complete a three-in-a-row, or (when that’s not possible) 2) Failure to block an opponent’s three-in-a-row.
Those conditions give 1145 different games with a total of 230 different positions, 138 of which are game-ending positions. When players never make these obvious mistakes, then a game can be “over” (meaning that the outcome is determined) in as few as three moves—and either player can establish a win in three moves.
Also, I agree with the 255,168 number for the case where you ignore all symmetry. If you want the number of games that are symmetrically equivalent from the players’ perspectives, where the game ends with three-in-a-row or a full board, and the players can be as stupid as they wish, then there are 26,830 possible games. It’s less than one eighth of 255,168 because some games have symmetry beyond the reflections and rotations of the board.
Mathrec, thanks for a detailed analysis.
In actuality, don’t you think there are certain kinds of symmetries that people tend to overlook?
It could be interesting to analyze a large number of Tic Tac Toe games to see if there are any patterns there.
Hey,
I’m jani and i know how to play games but this is some serous shit , cause it is unbeatable game. :( this make me and petsku sad…..
Hi
i was taught at school that the right way to play the game was that the last person gets the middle if no one gets the sides. My teacher also had a book about the history behind it,it was real interesting about the person who came up wit it.
hey,
My friend had an interview at Cambridge the other day and in the TSA test they had to do they had a question about noughts and crosses. it was something along the lines of:
If crosses went first and the first nought and cross were played, how many possible combinations are there, without any reflections or rotations allowed, and assuming the game goes to completion? (the first nought and cross are fixed)
We know that you would have to do 7!/(3!4!) to get the possible combinations but thats including all of the rotations, but we (including both maths teachers) didn’t know how to get the number of rotations and reflections in order to subtract it from 7!/(3!4!)… so do you have any idea how to solve this?? Please help – its been driving us all mad!! :S
thanks
Sophie,
I don’t personally have the math/combinatorial skills to calculate the number (I only know how to write the brute force program), but here are a few links to people who do:
http://www.math.mcgill.ca/ndo/documents/Mathellaneous-05.pdf
http://www.btinternet.com/~se16/hgb/tictactoe.htm
sorry made but the program isn’t perfect yet iv’e been trying to beat it for 10 minutes (i got lucky) and i did it im trying to find the combination again and i will tell you. something to spend the rest on my day with =D
@Mark I can’t rule out that there might be a mistake in the code, but nobody has found it in the seven years since I wrote the program.
Hi! to tell you frankly this is the best tic tac toe strategy. I learned a lot. More power to you. Thanks.
a very interesting idea. Thanks.