Global AI and Data Science

Tic-tac-toe (also known as noughts and crosses or X’s and O’s) is a paper-and pencil game for two players, X and O, who take turns marking the spaces in a 3×3 board. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game. Players soon discover that best play from both parties leads to a draw. Hence, Tic-tac-toe is most often played by young children. Because of the simplicity of tic-tac-toe, it is often used as a pedagogical tool for teaching the concepts of good sportsmanship and the branch of artificial intelligence that deals with the searching of game trees.

It is straightforward to write a computer program to play tic-tac-toe perfectly, to enumerate the 765 essentially different positions (the state space complexity), or the 26,830 possible games up to rotations and reflections (the game tree complexity) on this space.

Several modifications have been tried in the past including playing with one symbol X in a 3 × 3 grid and declaring one to be the looser who makes three in a line (row / column / diagonal) first. YouTube videos are available to study this modification.

The only enhancement I made is to play the above modification in larger board sizes. Following are the observations made on a 4 × 4 board.

1. It is possible to place at most 9 Xs in a 4 × 4 board.
2. It is not possible to finish the game with less than 4 Xs. The only possible numbers of Xs that can finish the game are 4, 6, 7, 8, and 9.
3. When one finishes a game with 9 Xs, the number of empty corners can be 0 and 3 only.
4. It is possible to reach 52 Xs in a 10 × 10 board

Consider a square grid of size n × n. One can go on marking boxes with no adjacent three in a row, column or diagonal. Surely the number of marked boxes will lie between 1 and n². However, the actual bounds are non-trivial. Following chart presents results obtained from simulations with 1000 repetitions.

The game of ‘Harmony’ constitutes of selecting a grid-size, targeting a number of marked boxes and achieving it with a pen and paper diagram.

For extensions, larger board sizes in larger dimensions with shapes other than squares can be thought about. In fact, the rule of ‘k adjacent in a line, k less than n’ can also be modified to create different games.

The ‘Game of Harmony’ is available as a mobile app in both Android and IOS.

QUESTION I: What are possible patterns in a 3 × 3 board so that no three boxes are occupied in any row and column.

QUESTION II: Why it is impossible to finish a solitaire Harmony game with exactly 5 occupied boxes in a 4 × 4 board.