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.

Advertisements

2 comments on “X’s and O’s

  1. Richard says:

    Recursion is an immensely interesting area of study and raises all sorts of interesting philosophical questions. If you are looking for a good philosophical discussion of how higher level recursive instructions relate to lower level non-recursive explicit instructions/actions then you should read chapter 6 (or maybe it’s 7) of ‘The Philosophy of Generative Linguistics’ by Peter Ludlow, a professor at the City University of New York. Philosophical questions about recursion connect, in interesting ways, the philosophy of mathematics to the philosophy of language. The later work of the philosopher Ludwig Wittgenstein did a lot to undermine the certainties associated with recursion and recursive specifications for behavior. His work undermined the idea that a definition can securely and uniquely specify how a word or phrase is to be correctly used in all possible instances and similarly how a procedure description, i.e. a program, which is sort of like a definition, can fail to uniquely specify the intended range of behaviors. Recursion certainly is mysterious because it relies upon the notion of intensional definition (which you can also find in set theory), which is at the heart of various puzzles in the philosophy of mind and language. The expression “black magic” may well capture the frustrated sentiments associated with philosophical attempts to understand how intensions work. One view is that recursion is the mind or brain’s way of dealing with a potential infinity of individual applications of a definition or procedure description.

    • Ben says:

      I should definitely take a look at that chapter, and the points you raise here seem very interesting. I do know that mathematicians sometimes refer to “recursive definition”, whereby each member of a sequence of objects (except the first) is defined through some relation to its preceding member. In the so-called “principle of recursive definition”, this can be formalized, and, as I understand, shown to be well-defined. I haven’t read deeply into this, and I’m only primitively aware of it. I wasn’t aware that there were philosophical considerations. Maybe I’ll read a mathematical exposition of the idea in addition to the philosophical investigations.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s