In my previous post, I discussed Tic-Tac-Toe (TTT) and why it’s so easily solved. Today, you will learn about Meta Tic-Tac-Toe (M-TTT), and how its increased complexity can make the game much more fun to play.
The playing field of TTT consist of a 3 by 3 grid of 9 cells in total, and all M-TTT does is insert a new TTT grid in every cell. Thus, M-TTT is a TTT grid where every cell is a TTT grid in itself:
This concept is known to programmers as recursion: defining something by using its own definition. Of course there needs to be a base case to this recursive definition, such that the definition eventually resolves to a meaningful answer. A base case is an alternative definition that is not recursive, and eventually any recursive definition should resolve to that base case. For example, let’s take a look at the following piece of code:
In this little piece of C code, the
recursiveMethod adds 1 to the result
recursiveMethod, except when the passed
level argument dips below 1
(in other words, less or equal to 0). This
if (level < 1) is the base case
that prevents the method from recursively adding 1 to its own results until the
end of time (or until your call stack decides to overflow).
Similarly in M-TTT, not defining a base case will mean we have an infinite amount of TTT grids nested in TTT grids, and good luck finding somebody to play that game with you. The base case of M-TTT is the number of nested TTT grids that must exist until the cells are simply empty playing fields. Generating our M-TTT grid can thus be achieved like so:
The C++ code snippet omits a lot of details, but generally is should bring the point across.
When the recursion level is less or equal to 0 we simply return a grid with empty cells,
otherwise we fill each cell of the grid with a new recursively defined meta grid, but with
one level of recursion less (note the
level - 1).
generateMetaGrid(1) thus generates a meta grid where every cell has another
grid stored within, but those nested grids themselves only contain empty cells
(as their constructing method was called with a level of 0).
A conventional game of M-TTT (our recursive grid of level 1) follows a simple sequence of events:
Especially step 2 might seem somewhat confusing, so I encourage you to simply scroll down to the section below and simply play the game yourselves. It should become clear what is meant with ‘relative location’ once you see the effects of marking an empty cell.
Now, once you understand the core concepts behind M-TTT, you might begin to see how it will work for any arbitrary number of nested TTT grids. The player must always place their mark in a grid that has the same relative location as the the previously marked cell. Where, with ‘relative location’, we mean the location of the cell relative to its containing grid. Propagating this rule throughout all levels of the nested grid allows us to easily determine the allowed moves:
All this might seem a little complex at first sight, but trust me, the game is still trivially simple once you actually start to play it.
Of course, this post would not be complete without a neat little demonstration! The interactive window below allows you to generate a TTT game of any Meta level between 0 and 2 1. Go find a bored opponent, and play some M-TTT!
Now you know how the game works, the true place for any TTT game to be played is on a piece of paper (or in the dirt, whilst waiting for the hourly bus to arrive). Simply grab a pen, some paper, and then ask your friend: