X’s and O’s

We all remember TicTacToe as the simplest game from our childhood.  But nothing is simple in computer science.  If you were assigned the task of designing a computer program that could beat a human at TicTacToe, how would you go about doing it?  Feel free to stop and think about it for a second.

My first choice was to build an algorithm that dealt step-by-step with each possible scenario: a sort of priority checklist.  If one priority is achieved, then the move is immediately made, and the rest of the priorities aren’t even considered.  Thus the order of the priority list is important; the most urgent ones must be at the top.  The list of priorities went something like this:

1. If victory is immediately possible, make the winning move.
2. If the enemy’s victory is immediately possible, block their winning move.
3. If a fork is possible, make the fork.  A fork is a move that creates two possible ways to win.  Thus the enemy will follow step 2 but will only be able to block one possibility; you will then follow step 1 to win.
4. If the enemy is in danger of making a fork, you must prevent this, with one of two options:
   1. Create a counterthreat.  The enemy will then have to obey step 2, preventing him from reaching step 3.  Note that this only works if the enemy’s response as per step 2 isn’t the same move he was about to make anyway as per step 3.  If the enemy’s answer to your counterthreat is the same as his original fork move, then you will be forked anyway.
   2. Block the enemy’s fork by moving in the location of his potential forking move.
5. General strategies for good play, such as playing the center and playing the corner opposite to one your opponent occupies.