Tic-Tac-Toe coding challenge

Coding challenges

Software developers love challenges. After all, programming is basically one big puzzle.

At Quba we like to run coding challenges for a bit of fun. You learn something doing them, but learn more seeing how other people did it - there are always multiple solutions to the same problem.

What is tic-tac-toe?

The challenge on this occasion was determining the winner of tic-tac-toe puzzles. For the unitiated tic-tac-toe is made up of a 3x3 grid. Players take in turns to add an X or O, and the wins by having three in a row horizontally, vertically or diagonally.

There are three possible outcomes:

• Noughts win
• Crosses win
• Draw

The challenge

The challenge that was sent to the tean this time was thus:

The challenge is to get the correct result of each of the 5000 mock games in the quickest time possible – you must also prove each result is correct. For example, you could write each result to the screen to show this.

For this challenge a skeleton .NET core command line project had been setup with the following:

GameResult.cs

Defines the status/result of a game.

public class GameResult
{
   public char[] Board { get; set; }
   public GameResultType Result { get; set; }

    public GameResult(char[] board, GameResultType result)
   {
       Board = board;
       Result = result;
   }
}

GameResultType

Enum defining the possible outcomes. Importantly, an extra state is included, In Progress, that denotes an incomplete game (this adds a bit more complexity to the task).

public enum GameResultType
{
   Draw,
   Noughts,
   Crosses,
   InProgress
}

MockTicTacToeResults.cs

Contains 5000 entries to match against, for example:

new GameResult(new char[] { 'O', 'X', 'O', 'X', 'X', 'X', 'O', ' ', ' ' }, GameResultType.Crosses)

Program.cs

Contains the timing mechanism, and the basis of loading the game states.

The idea is the stopwatch is used to calculate the time taken to solve the puzzles. As with other challenges, proof of the puzzles actually being solved by validating with the CSV was also required.

Note: for fairness each entry was run 3 times and an average taken to account for different background resource usage.

Solutions

From all of the entries the quickest time achieved was 0.05 seconds, and the slowest was 0.9 seconds - quite a range.

So why were they different and what did we learn?

Release is better than debug

It may be an obvious statement, but running the solution in release mode was 100% quicker than running it in debug mode. This is because release mode is an optimised version, and does not load all of the symbols required for debugging.

Calculating the result

As the board is fixed size, and there are only n amount of possible winning combinations for Xs and Os, the quickest way was to simply check for the position of Xs and Os:

static GameResultType ComputeResult(ReadOnlySpan<char> board)
{
   // Fast check for any remaining moves
   bool hasEmpty = board.Contains(' ');

    // Check all winning combinations using no loops for speed since it is a fixed size board.

   // Rows
   if (board[0] != ' ' && board[0] == board[1] && board[1] == board[2]) return Winner(board[0]);
   if (board[3] != ' ' && board[3] == board[4] && board[4] == board[5]) return Winner(board[3]);
   if (board[6] != ' ' && board[6] == board[7] && board[7] == board[8]) return Winner(board[6]);

    // Columns
   if (board[0] != ' ' && board[0] == board[3] && board[3] == board[6]) return Winner(board[0]);
   if (board[1] != ' ' && board[1] == board[4] && board[4] == board[7]) return Winner(board[1]);
   if (board[2] != ' ' && board[2] == board[5] && board[5] == board[8]) return Winner(board[2]);

    // Diagonals
   if (board[0] != ' ' && board[0] == board[4] && board[4] == board[8]) return Winner(board[0]);
   if (board[2] != ' ' && board[2] == board[4] && board[4] == board[6]) return Winner(board[2]);

    // If no win and board is full: Draw, else: InProgress
   return hasEmpty ? GameResultType.InProgress : GameResultType.Draw;
}

Inlining

Marking up methods with the following had a massive speed boost:

[MethodImpl(MethodImplOptions.AggressiveInlining)]

This tells the JIT compiler to inline the code - basically adding methods into oneanother in the body to reduce the overhead of calling the method itself. The compiler often does this itself, so in effect we are overriding the compiler and telling it what to do.

You might think, just stick this on every method? However, this ends up having a negative impact for larger programs where methods are more complex and not called as often. If you stick it everywhere you basically increase the size of the program as you end up doubling code.

In this case it worked, but the rule of thumb is that normally the compiler is already smart enough!

Pre-allocate memory

For outputting the results (via a StringBuilder) it is better to define the amount of memory the StringBuilder should use. This prevents excessive memory allocation, and makes the program more efficient.

// Pre-allocate output buffer for performance (60 chars per result * result count) O(1) on memory and O(n) on speed instead of O(n^2) for string concatenation
var output = new StringBuilder(capacity: results.Count * 60);

Multithreading

Firing multiple threads concurrently increased the efficiency. This means that multiple puzzles can be solved in parallel, and the program does not have to wait for one to be solved to move onto the next. 

Luckily .NET has a ready made thread safe option for this in the form of:

Parallel.ForEach(lines, line =>

However, on this occasion it actually caused the the program to be slower. The reason for this is that the amount of puzzles, 5000, was solved so quickly using the logic that firing other threads caused more memory to be used and slowed the program down. 

This is the opposite of the sudoku puzzle, in which it made it more efficient.

Final thoughts

Working on this challenge allowed us to use techniques that we may not use in every day development, and they provide a great way to collaborate on learning new skills.

There are likely to be many more ways to make the program even faster, but for now we move onto a new challenge.

If you would like to the source code to do it yourself, or think you can do it quicker, we'd love to hear from you.

Look out for the next challenge coming soon.