# 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.

The process of building this program was quite painstaking.  It wasn’t too difficult at first, but the complexity began to explode by step 3 and especially by step 4.  Nevertheless, about 300 lines of code later, I finished it.  The computer was able to draw or beat me consistently.  Now, it was time to put it to the true test: setting the computer against itself.  Here, I was greeted by an unexpected surprise.  One computer player had happened upon an instance I had not taken into account in my priority list above: that of a fork of forks.  Player 1 discovered a move that simultaneously threatened two forks; player 2 recognized the fork danger and blocked it, but player 2 simply forked his opponent in the other location.  I was dumbfounded.

I considered going back into my already unwieldy program and adding capability to detect double forks, but at this time I realized it was time to change my tack.  I was building far too complex a program to tackle too simple a problem.  It was time to embark on the next stage of my quest: building a recursive TicTacToe program.

Recursion is a strange “black magic” in computer science, where a procedure invokes itself in order to solve a problem.  To help grasp this, consider a classically simple example of recursion: calculation of factorials. We might, of course, iterate i from 1 to n, multiplying a running total by i each time and returning the final total. More elegant is the recursive method. Namely, n factorial might be expressed as simply n multiplied by (n – 1) factorial. But what’s (n – 1) factorial? It’s (n – 1) times (n – 2) factorial. Are we endlessly digging deeper into recursion, with no solid ground to land on? We must include a base case. A solid answer is returned when the procedure reaches 1; then the calculation speeds back up the chain. (Note that, of course, the same calculation is being made either way – this is a subtle point).

Our procedure may be written with just one line of functional code and one recursive call. In pseudocode:

• procedure factorial(int n)
• if  n is 1 return 1
• else return n × factorial(n – 1)
• end procedure

How could recursion be used to solve TicTacToe?  The answer lies in our approach to the problem.  What’s the best move for player 1?  Player 1 assumes that, no matter where he moves, player 2 will play his best move.  Thus player 1 picks the move for which, given player 1’s move, player 2’s best move is worst.  But how is player 2’s best move calculated? By determining which of player 2’s moves makes next move worst for player 1.  And so on; the recursive cycle continues inward until the entire board is full and the game has ended.  Every single time a move is decided, the computer recursively plays out every possible move for both players, searching for possible wins given perfect play. When it hits a win, the news is carried back up the chain.

But how is goodness evaluated? Here we’ll see the recursive function call.

• procedure goodness (boolean player, array position)
• if check_victory(position, notplayer) return -128
• maximum <– -100
• for each i from 1 to 9:
• if position[ i ] is empty then
• position[ i ] <– player
• value <– (-1)×goodness (position, notplayer)
• if value > maximum then maximum  <– value
• position[ i ] <– empty
• end if
• end for
• return maximum
• end procedure

Once again, we’re tracking the maximum value of notplayer’s negative goodness, given player’s move. Goodness for player depends on the evaluation of goodness for notplayer, which in turn depends on the goodness for player, and so on.  The program recurses deeper and deeper until position contains no empty fields.

Thus the program is done, written in about ¼ the length of the non-recursive program.  The beauty is that the computer now figures out on its own what I once had to explicitly teach it. How does it all work? It’s almost magical.  Also, in contrast to my earlier program, this code could be easily altered to support 3×3, 4×4, and nxn grids, or the replacement of pieces (for example, only 3 or 4 pieces are allowed per player at a time).  The possibilities are endless, and all would be relatively easy with my recursive algorithm.

One thing’s for sure: however easy it would be to program these games, it’s much, much easier to just to play them.  It goes to show the power of the human brain.  I can make all the calculations required to play TicTacToe without even knowing I’m making them.  Even much more complex games like Chess are easy to think through, but would be very difficult to program.  When games become easier to program than they are to play, computers will have come a long way indeed.