Categories
algorithm Arduino software

Tic-Tac-Toe and an Experiment in Game Interface

tictactoeThe motivation for this project was to explore the separation between the algorithm for managing a game and the user interface for the game. Discovering a Tic-tac-toe algorithm simple enough to implement on the Arduino allowed an exploration of this concept in a game with simple user interface requirements.

Tic-tac-toe

Tic-tac-toe (also called Noughts and Crosses, Xs and Os) is a pencil-and-paper game most often played by young children. This is simple game is one that most (all?) people have played sometime in their life.

In case there is anyone who has never played this game, two players (X and O) take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game. In the example below, the game is won by the first player, X.

TicTacToe-game

Players soon discover that best play from both parties leads to a draw (often referred to as cat or cat’s game).

Game Strategy

A player can play perfect TTT (win or draw) given they choose the first possible move from the following list.

  • Win: If the player has two in a row, they can place a third to get three in a row.
  • Block: If the opponent has two in a row, the player must play the third themself to block the opponent.
  • Fork: Creation of an opportunity where the player has two threats to win (two non-blocked lines of 2).
  • Center: A player marks the center.
  • Opposite corner: If the opponent is in the corner, the player plays the opposite
    corner.
  • Empty corner: The player plays in a corner square.
  • Empty side: The player plays in a middle square on any of the 4 sides.

Implementing Game Logic

A simple but elegant algorithm for TTT is briefly described  here and explained below. This has been implemented in the game library, along with some additional features to make decisions easier to implement in code. An important feature of this algorithm is that it does not use much memory to implement.

The Playing Board

In TicTacToe, there are 9 positions and 8 wins. Each position is labelled a to i, like this:

 a | b | c
---+---+---
 d | e | f
---+---+---
 g | h | i

Winning Moves

We can assign a matrix of win contributions to each position as a row of 8 elements.

[D1, H1, H2, H3, V1, V2, V3, D2]

where D1 is the main diagonal (left to right), H1, H2, H3 are horizontal wins,
V1, V2, V3 are vertical wins, and D2 is the other diagonal.

For each win element, if a board position occurs in a win, give it a 1, like so:

[a] = [1, 1, 0, 0, 1, 0, 0, 0]
[b] = [0, 1, 0, 0, 0, 1, 0, 0]
[c] = [0, 1, 0, 0, 0, 0, 1, 1]
[d] = [0, 0, 1, 0, 1, 0, 0, 0]
[e] = [1, 0, 1, 0, 0, 1, 0, 1]
[f] = [0, 0, 1, 0, 0, 0, 1, 0]
[g] = [0, 0, 0, 1, 1, 0, 0, 1]
[h] = [0, 0, 0, 1, 0, 1, 0, 0]
[i] = [1, 0, 0, 1, 0, 0, 1, 0]

This table is turned into a 9×8 matrix of constants that governs the moves for all TTT games.

Moves Algorithm

The game win matrix [M] is initialised to 0.

[M] = [0, 0, 0, 0, 0, 0, 0, 0]

Player 1 makes the first move, say position [a]. The line for positions [a] is added to the game matrix [M] to give an game position:

[M] = [1, 1, 0, 0, 1, 0, 0, 0]

Player 2’s move will subtract from the game matrix. If they take position [e], the resulting game matrix will be

[M] = [1, 1, 0, 0, 1, 0, 0, 0] - [1, 0, 1, 0, 0, 1, 0, 1] 
    = [0, 1,-1, 0, 1,-1, 0,-1]

And so-on for subsequent moves, alternately adding and subtracting from [M].

We therefore have a way of tracking how the game is progressing and, more importantly, to test a move against the current board to determine which is the best move at any time. The best move, in order of importance, will be one that

  1. Makes a 3 or -3 (depending on the player), because this means we have made 3 in a row, column or diagonal.
  2. Makes as many 2’s as possible provided there are no 2 or 1 of opposite sign, as it means other player would win the match. Leaving 2 2’s will mean that we are guaranteed to win on the next turn. Leaving a 2 of the opposite sign means that the other player will win next turn.
  3. Makes as many 2’s into 1’s as a last resort. A 2 now will turn into a 3 the next move, and 3 means someone wins!
  4. Makes the highest number of 1’s provided there are no 2 of opposite sign, as it means other player would win the match.

If there is more than one ‘best’ move than it is possible to select randomly between choices that fit the highest criterion. This makes the algorithm slightly unpredictable and can result in moves that allow the other player to win the game, thus relieving the boredom of always losing against the computer!

The game is over when there are any 3’s or -3’s and the column in which this number appears will also tell exactly where to strike through for wins.

To allow manually exploring the concepts outlined above, the algorithm is also implemented in a Microsoft Excel spreadsheet accompanying the library folder.

Implementing the User Interface

While the game management code is the same for all implementations, user interface management will change depending on physical inputs and outputs, so I wanted to create a flexible method to decouple the two parts.

For example, a simple user interface can be implemented to play the game on the Arduino IDE Serial Monitor, or a more complex interface using a 4 line, 20 character, LCD module, shown below.

The integration between game library and user interface is largely implemented through a callback function that allows the user program to update each game cell as the game progresses. This could have equally have been done by extending the MD_TTT C++ class to include virtual methods. Either way, the user code does not need detailed knowledge of the game board current positions, but it does need to manage getting the next move from the human player and the high level flow of the game.

It turns out that 2 parameters are all that the user code needs to know – the player (to set the right token) and the position on the board. The code then translates specified grid position to a location on the screen and sets ‘X’ or ‘O as appropriate.

To round out the library, some additional administrative methods are needed to work out whether the game is completed, who won, where the win line is and, of course, to initiate a move at a game board location.

The example programs provided with the library provide a framework that can be changed for alternative user interfaces.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s