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