Another article about Tic Tac Toe? Why? Well, I was discussing with a friend the inappropriateness of typical software teaching projects, given how they tended to not relate to the real workplace. Good old Tic Tac Toe got mentioned. It made me remember how the simple question "has the game been won" leads to pretty clumsy looking code just by the nature of the game. Sadly, that got me thinking that there may be a simpler way!

The problem is that one sees a grid and so one presumes that one has to analyse a grid. So I tried to reduce the question to it's bare essentials. What do we mean by a game being won? A win is simply when a set of cells that lie on the same line have been filled by one player. Hmm. Hang on, did I just say "set"? Being a Pascal fan, and given that Pascal has support for sets, this seemed promising!

So, if we number the cells as

1 2 3
4 5 6
7 8 9

then basically, the question becomes, "are the cell numbers of the line being tested a subset of the moves the current player has made?".

Clearly we will need a number of sets, one for the first player's moves, one for the second and one to take a copy of one of those as needed for testing by common code. It will also be useful to have a constant array of sets (let's call it Lines) to represent the winning lines, i.e. ([1,2,3], [4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]). As it only makes sense to test the lines that pass through the last selected cell, a further constant array of sets, one for each cell, is useful (let's call it Possibles). For that, we need to number the lines as per the elements of Lines, and use those numbers as the set members for each cell. That all makes sense if you look at the source code, see links to the right.

So, to check the last move for being winning, we need to...

for each line passing throught the last used cell,
check if the line is a subset of the player's moves

Now compare that to the actual Lazarus/Free Pascal code, (Line is a number, Choice is the last cell used, Choices is the test copy of the set of moves made by the current player) ...

for Line in Possibles [Choice] do
   if Lines [Line] <= Choices then
      Status := Win;

Did you notice how the code is almost identical to the English specification? If we differentiate between code and data, then that really is all the code that is needed. Compare that to more traditional code examples, trivially simple isn't it?

And so to the reasons for posting this. Firstly, having "had a bright idea" I thought it should be shared and not just lost on my PC. Secondly, there is a lesson to be learnt about not diving into designing or coding using your first impressions, take your time and look for other ways of viewing the problem, there may be a less obvious, but simpler solution.

Note : I specified Lazarus/Free Pascal because "for x in..." is a language extension specific to that implementation.

Finally, the first version of this game that I wrote was deliberately kept simple as it was only "proof of concept". Curiosity got the better of me and I wondered if I could not only detect a drawn final position but also earlier drawn positions using sets. The answer was yes! The key was to have yet another set called Empty which gets initialised to the power set of the cell numbers and has a member removed on each turn. You can find the details in the "Improved" version of the code in the procedures CheckForDraw<n> where <n> is the number of moves made. However, at the risk of disappointing you all, my curiosity doesn't extend to any further development!