Butter, Cheese and Depth-first search

Tic-Tac-Toe (or as we call it in the Netherlands, “Boter Kaas en Eieren”) is a game you probably have played at least once, and if you did, you most assuredly finished with a draw (leaving you and your opponent equally bored as when you started the darned game). In contrast to games like Chess, the noble sport of Tic-Tac-Toe is simple enough for our feeble minds to plan to its inevitable end:

Why you draw

When you are mentally preparing your moves, your brain is performing an algorithm known to Computer Scientists as Depth-first search.

Depth-first search is an algorithm that works on trees. A tree is a graph that contains a collection of nodes that are connected in a parent-child relationship. Imagine a hereditary tree where one parent can have multiple children (without loops, this family cannot travel through time):

Depth-first search is a searching algorithm that traverses down a branch of the tree and checks for every node in the branch if a particular condition has been met. If it reaches a leaf, it moves back up the tree and starts traversing the next alternative branch. For example, imagine the algorithm looking for Jessy, it would find him like so:

One can see how this simple search can help you solve Tic-Tac-Toe: you mentally imagine what will happen if you place a marker on the board and envision the end-game state that will occur as a result of that choice. If this end-game state does not appeal to you, you imagine another sequence of events that will most likely make you win. Don’t believe me? Try to beat the algorithm yourselves below!

Stepping up the game

In an effort to increase the complexity of this game, bored scientist have invented Meta Tic-Tac-Toe. A game that cannot be trivially solved, and is much more fun to play as a result. In part 2, we will discuss this game and how it can be constructed using recursion.