Solving the Tic-Tac-Toe game, finally...

The simple game that has been always after me laughing at my programming incompetence.

The very first time I tried to make a program that could play perfectly the game was in the university, after taking my very first course in Programming Languages (I learned Pascal). It was holidays and I was visiting my cousin and got the nice surprise of him getting a personal computer. It was a powerful 286 with a monochrome amber monitor. I couldn't find anything similar but for you to get the idea, games were played like this in those computers:

My cousin was the first lucky one in getting a computer in our family and he was learning Turbo Pascal by himself. We decided to celebrate our reunion programing the ultimate and invincible "Michi" (that is how the TicTacToe game is called over here). It was the morning and I had to return to my city at the afternoon, so we had only some hours to get it working. He was going to do the main menu and the game board, and I was going to implement the game logic. He started programming while I was writing on paper my part. This is just a bunch of ifs and a 3x3 matrix, How difficult can it be?. I thought. I recall he did a beautiful work, our graphics looked great (all in black and amber of course) but after typing my part the game really bombed, it played awfully, losing idiotically. Without more time to debug my program I had to leave with the bitter taste of defeat on my mouth.

The second time I tried to solve the game was after getting my programmable calculator Casio FX-7700, a powerful beast of 4K of memory. This calculator only accepted some kind of primitive BASIC but it gave me some moments of solace programming it. In every sense it was my first "computer", because before that I only could test my programs after getting laboratory time on my university laboratory, and that place was always full of people waiting, I had to awake early to sign-in the notebook for reserving a place. I remember using all the 4K of my calculator for my TicTacToe game, it draw the board not only with "X" and "O" but also with different icons that I had diligently drawn pixel by pixel. This time the game logic worked fine. Or that I thought. One of the reasons my first attempt failed so miserably was that I didn't want a "boring" adversary. I know this is ridiculous when the game is boring for starters, but it was very very boring if the computer always played in the center first, or in some corner first. I knew that the computer could play in any place if it was first and indeed had high chances of confusing the casual adversary playing that way, so my game logic must choose randomly from a valid set of possible movements. I have see some TicTacToe game solvers cutting corners starting always in the center or in some corner. My game seemed to play randomly and even so never to lose. Some day I needed the memory of my calculator for useful stuff, and I had to delete my TicTacToe program so I decided to play the little thing for the last time... and I found a bug I have never seen before! even worse, due to the randomness I couldn't reproduce it later. No time to debug, like the first time, TicTacToe laughing again at me.

This year I saw again the little monster thanks to a friend, and I decided to settle things once for all with it. This time I didn't want to use a greedy approach to the problem, like before. This time I would generate all the game tree once for all and decide the best move using the MiniMax algorithm. You can see the result below (flash):

Left click for doing a move, and clicking while pressing [shift] or [control] undo the last move. The valid moves for the next player are show in black. About the statistics printed on every cell: the first 3 numbers (from top to bottom) are the number of possible games that are won by any part or are drawn (in ascending order). Next is the total of games and finally comes the MiniMax score of that cell. That score is used by the program to show the best moves for the next player. Positive scores are a secure win for the "X" player, negative scores are a secure win for the "O" player, a zero score means a draw.
So TicTacToe in resume looks like this:

The area in blue is proportional to the possible games than "X" can win, the red area is proportional to the number of wins for "O" and the area in yellow are the draws. You can see that there are 255168 games with "X" wining 51% of them, "O" wins only 30% and the rest is a draw. Clearly "X" has an advantage. This is the distribution for the first move:

You can play in any cell (and like everybody knows) the best you can get is a draw (all the cells have zero for MiniMax score). Playing in the center gives you 60% chances of winning, in any corner a 52% percent of winning and playing in the side 48%. If you play in the corner, you'll get this:

Now the interesting bit is that for the "O" player there is only one valid possible answer for drawing (playing in the center) playing in any other place is a secure win for the "X" player. If "X" plays in the center first:

the only valid answers for "O" is playing in some corner, and if "X" plays in the side:

there are only 4 cells that are valid for the "O" player now (I really liked that opening).

Play with the flash thing and convince yourself that it's unbeatable. I hope I didn't do a mistake again! :D. Source code here.