The Game

TicTacToe is a game you are likely familiar with. It is also boring to play because it takes only a small amount of strategy to make every game a draw.

Instead we are going to look at a variant called NoTakTo (Links to an external site.). Technically it is an impartial, misere variant. This means both players play as X, and you win by forcing your opponent to take a game ending move.

It is a two player game with simple rules:

· When it is your turn, you may place an X on an empty square.

· When a move is played that completes a row, column, or diagonal, the player making that move loses.

Often this is played with multiple boards, where you can play on any board that isn’t completed. This version of NoTakTo is solved for 3×3 boards. This means that with perfect strategy, the outcome of the game is known (if there are an odd number of boards, player 1 wins, an even number, player 2 wins). If you wish to try this, there is a free version you can play on iOS or Android (Links to an external site.). There are also a series of videos on Youtube by the channel Numberphile Pt1 (Links to an external site.) Pt2 (Links to an external site.) Pt3 (Links to an external site.).

So instead of playing a solved variant, we will play the game where there is not a known perfect strategy, a single 4×4 board.

Your Program

You will write a program to play a 4×4 NoTakTo with just one board. Importantly it must be split into multiple files.

Suggested Approach

The following is an outline of a suggested approach. Each of these steps imply testing the functionality as you go, even if not explicitly listed. Many of the steps have further details below.

1. Determine an appropriate structure to represent the board

2. Write a print_board function

3. Write a read_move function

4. Write an is_valid_move function

5. Write an apply_move function

6. Write a game_over function

7. Tie everything together in main

Descriptions of Helpful Individual Functions

· read_move – This function should prompt the user to enter a row and column and validate the entered values are between 1 to 4 (inclusive) and return the values by reference.

· create_board – This function should create an appropriate std::vector and set it up as an empty board.

· print_board – This function should print out the board

· is_valid_move – This function should validate that a move is valid for the current board by ensuring the row and column of the move are in a reasonable range, and the specified spot on the board is empty.

· apply_move – This function should mark the specified space on the board

· game_over – This function should look at the board and return true if any row, column, or diagonal are all filled in.

What to have in main

The general approach for this game is to have the idea of a game loop. The general process is:

while (not game over) { print the current board read a move from the current player if (move is valid) { apply the move and switch the current player } else { print an error } }

This general approach applies to more than just this game. Most games can be modeled this way.

Example Output

User input is in bold

….

….

….

….

Player 1’s turn

Enter a row and column: 0 0

Error: Row out of range

Enter a row and column: 1 1

X…

….

….

….

Player 2’s turn

Enter a row and column: 4 4

X…

….

….

…X

Player 1’s turn

Enter a row and column: 1 3

X.X.

….

….

…X

Player 2’s turn

Enter a row and column: 2 2

X.X.

.X..

….

…X

Player 1’s turn

Enter a row and column: 3 2

X.X.

.X..

.X..

…X

Player 2’s turn

Enter a row and column: 3 3

X.X.

.X..

.XX.

…X

Player 1 Wins!

Hints

· In read_move, subtract one from the row and column before returning. This allows the user to enter a value from 1 to 4, but the Move stores 0 to 3 for indices into an array.