Ctrl+K

Tic Tac Toe

29. Tic Tac Toe#

In this exercise, we will implement the classic Tic Tac Toe game. If you’re not familiar with the rules, refer to the wikipedia page on Tic Tac Toe. The game allows us to explore multiple topics such as lists of lists manipulation, sets, and function references. The exercise is broken down into smaller steps to make the overall problem easier to manage.

29.1. Basic Grid Manipulation#

In this first part, we will develop all the functions necessary to manipulate a Tic Tac Toe grid.

29.1.1. Initialization#

We represent the Tic Tac Toe grid as a list of rows, where each row is a list of cells. Each cell will be represented by one of the following strings:

" " (space): for an empty cell;
"x" (cross): player's 1 cross;
"o" (circle): player'2 circle.

At the start of the game, the grid looks like this: [[' ', ' ', ' '], [' ', ' ', ' '], [' ', ' ', ' ']].

Define a function new_grid that takes no parameters and returns an empty grid with all cells initialized to " " (spaces). The grid should be a 3x3 matrix.

def new_grid():
    pass

#new_grid()

29.1.2. Display#

We need a function that displays the grid in a human-friendly format, like this:

    1 2 3 
   ╔═╦═╦═╗
10 ║ ║ ║ ║
   ╠═╬═╬═╣
20 ║ ║ ║ ║
   ╠═╬═╬═╣
30 ║ ║ ║ ║
   ╚═╩═╩═╝

The values 1, 2, 3 at the top indicate the column numbers and 10, 20, 30 on the left represent the row numbers. These will help players later to input coordinates in the form of a two-digit number. For example, entering 12 would refer to the first row, second column.

The grid cells will contain either “x”, “o”, or ” ” (an empty space).

Define a grid_to_str function taking a grid as parameter and returning a string representing the grid.

def grid_to_str(g):
    pass

#g = new_grid()
#print(grid_to_str(g))

29.1.3. Detecting the End of the Game#

To determine if the game has ended with a winner, we need to check if either player has successfully aligned three of their symbols (x or o) in a row, column, or diagonal.

The function should return a tuple with two values:

  • A boolean indicating if there is a winner.

  • The symbol of the winning player (“x” or “o”), or None if there is no winner.

there are three possible return tuple

  • (True, “x”) if player x wins,

  • (True, “o”) if player o wins,

  • (False, None) if there is no winner.

Define a function has_winner that

  • Takes the Tic Tac Toe grid (a 2D list) as input.

  • Checks all possible winning combinations (rows, columns, and diagonals).

  • Returns a tuple indicating whether there is a winner and, if so, which player won.

Hint: it is a little bit fastidious, probably the best way is to use two loops to check rows and columns and then to check both diagonals.

def has_winner(g):
    pass

#has_winner([[' ', ' ', ' '], [' ', ' ', ' '], [' ', ' ', ' ']]) #(False, None)
#has_winner([['x', 'x', 'x'], [' ', ' ', ' '], [' ', ' ', ' ']]) #(True, 'x')
#has_winner([['x', ' ', ' '], ['x', ' ', ' '], ['x', ' ', ' ']]) #(True, 'x')
#has_winner([['x', ' ', ' '], [' ', 'x', ' '], [' ', ' ', 'x']]) #(True, 'x')

29.2. Computer moves#

29.2.1. Finding Available Moves#

To allow the computer (or the player) to make a move, we need a way to identify all the empty positions on the grid where moves can still be made.

Create a function available_positions that:

  • Takes a Tic Tac Toe grid (a 2D list) as input.

  • Returns a set of tuples representing all available (empty) positions on the grid. Each tuple contains two integers representing the row and column index of an empty cell.

For example, on an empty grid, the function must return {(0, 1), (1, 2), (2, 1), (0, 0), (1, 1), (2, 0), (0, 2), (2, 2), (1, 0)}.

Hint: The returned set of tuples does not need to be ordered, since sets in Python are unordered by nature.

def available_positions(g):
    pass

#print(available_positions(g))

29.2.2. Random move#

Now, we will implement a function to allow the computer to make a random move on the grid. This will serve as a basic AI for the game.

Define a function random_move that:

  • Takes two parameters:

    • grid: the current Tic Tac Toe grid (a 2D list).

    • player: a string representing the next player (“x” or “o”).

  • Chooses a random available position from the grid.

  • Modifies the grid by placing the player’s symbol (“x” or “o”) in that position.

  • Returns the tuple representing the position of the move played (row, column).

Hint:

  • Use the available_positions function (from the previous step) to get all possible empty positions on the grid.

  • Randomly select one of these positions using the random.choice function. As you see in documentation the function choice take a sequence (for example a tuple) as parameter. Thus you need to convert your set of available positions into a tuple.

from random import choice

def random_move(grid, player):
    pass
    
#random_move(g, "o")
#print(grid_to_str(g))

29.2.3. Checking if The Game is Over#

To determine if the game has concluded, we need to check if all possible moves have been played on the grid. This would mean that there are no empty cells left for either player to make a move.

Define a function is_over that:

  • Takes a Tic Tac Toe grid (a 2D list) as input.

  • Returns True if all cells in the grid are filled (i.e., there are no empty cells).

  • Returns False if there is at least one empty cell remaining.

def is_over(g):
    pass

29.3. Computer play#

29.3.1. Implementing a Random Strategy#

To simulate a complete game of Tic Tac Toe, we will implement a function that plays out the game using a random strategy. This function will generate moves for the players until the game ends either with a win or a draw.

Define a function random_strategy that:

  • Takes two optional parameters:

    • grid: a 2D list representing the current Tic Tac Toe grid. If not provided, the function should initialize a new grid.

    • player: a string representing the next player to move (“x” or “o”). If not provided, it defaults to “x”.

  • Continues making random moves until the game concludes (either one player wins or the grid is full).

  • Returns:

    • The winning player (“x” or “o”), or “=” if the game ends in a draw.

    • A tuple of all played moves in the order they were made.

The following return values are possible from the random_strategy function. ('o', ((0, 1), (1, 2), (2, 2), (1, 0), (2, 1), (2, 0), (0, 0), (1, 1)))

It indicates that o won and corresponds to the given board.

    1 2 3 
   ╔═╦═╦═╗
10 ║x║x║ ║
   ╠═╬═╬═╣
20 ║o║o║o║
   ╠═╬═╬═╣
30 ║o║x║x║
   ╚═╩═╩═╝

def random_strategy(grid=None, player="x", verbose=False):
    pass

#p, moves = random_strategy(verbose=False)
#p, moves

29.3.2. Evaluating a Strategy#

To assess the effectiveness of a given strategy for Tic Tac Toe, we will implement a function that runs multiple games and keeps track of the results.

Define a function evaluate that:

  • Takes four parameters:

    • strategy: a function that implements the game-playing strategy (typically the random_strategy function defined earlier).

    • grid: an optional 2D list representing the Tic Tac Toe grid. If not provided, it defaults to None, indicating a new game will start.

    • player: a string representing the next player to move (“x” or “o”). This parameter should be specified.

    • num_games: an integer representing the number of times to run the strategy (default to 10000).

  • The function should execute the specified strategy a certain number of times, tracking the outcomes of each game:

    • Count the number of draws.

    • Count the number of wins for player o.

    • Count the number of wins for player x.

  • It should return a tuple with three values: (draws, wins for o, wins for x).

For example, for evaluate(random_strategy), we obtain as return values: (10000, 2949, 5772). It is random, but you should find something close to these values.

Hint: It is necessary to duplicate the grid at each iteration of the loop, otherwise. Once, you play a random game on a grid, you complete it. To copy a list of list the best way is to use the deepcopy function from the module copy. For example b = copy.deepcopy(a) is a copy of a.

import copy

def evaluate(strategy, grid=None, player="x", iterations=10000):
    pass

# evaluate(random_strategy)   # (1298, 2900, 5802)

#grid = [["x", "o", "x"], ["x", "o", "o"], [" ", "x", "o"]]
#evaluate(random_strategy, grid=grid, player="x")  # (0, 0, 10000)
#evaluate(random_strategy, grid=grid, player="o")  # (10000, 0, 0)

29.3.3. Importance of the Middle Cell#

In Tic Tac Toe, starting in the middle cell is often considered a strategic advantage. We will implement a modified random strategy that ensures the game always begins with a move in the middle cell, if possible. Then, we will evaluate and compare the performance of this strategy against the fully random strategy.

Define a function middle_first_random_strategy that mimics the random_strategy but always starts by placing the first player’s symbol in the middle cell of the grid (if it’s empty). The function should take the same parameters as random_strategy.

Use the evaluate function to run middle_first_random_strategy a sufficient number of times (e.g., 10,000). Compare the results with those obtained from the random_strategy.

def middle_random_strategy(verbose=False):
    pass

#middle_random_strategy(verbose=True)
#evaluate(middle_random_strategy)

29.3.4. Importance of Corner Cell#

You may try the same thing with the corner cell. You should find that it is a best choice. In fact, the folling xkcd strip show the best strategy of this game.

def corner_random_strategy(verbose=False):
    pass

#corner_random_strategy(verbose=True)
#evaluate(corner_random_strategy)

29.4. Enumerating all games#

We can numbered all the elements of the grids. A series of moves is then a permutation of the integer from 0 to 8 (included). Enumerating all the games, is equivalent to enumerating all permutation of nine values: \(9!\).

The top left element in the grid is numbered 0 and the bottom right element is numbered 8.

29.4.1. Int to position#

In this step, we will implement a function to convert an integer representation of a grid cell into its corresponding row and column coordinates in a Tic Tac Toe grid. Each cell in the 3x3 grid is numbered from 0 to 8, starting from the top-left corner.

Create a function int_to_position that

  • Takes a single integer parameter index, which should be in the range from 0 to 8.

  • Returns a tuple representing the corresponding coordinates (row, column) of that cell in the 3x3 grid.

def int_to_position(x):
    pass

#print(int_to_position(0)) 
#print(int_to_position(8))
#print(int_to_position(4))
#(0, 0)
#(2, 2)
#(1, 1)

29.4.2. Position to int#

Create a function position_to_int taking a tuple as parameter and doing the inverse operation. Be careful, we want to take a tuple as paramter. This means only one value, not two.

def position_to_int(t):
    pass

#print(position_to_int((0, 0))) # 0
#print(position_to_int(int_to_position(0))) # 0
#print(position_to_int(int_to_position(8))) # 8
#print(position_to_int(int_to_position(4))) # 4

29.4.3. Predicted strategy#

In this step, we will implement a function that simulates a game of Tic Tac Toe based on a predefined list of moves. This function will execute the moves in order and return the outcome of the game, which may finish before all moves are played.

Define a function predicted_strategy that:

  • Takes a single parameter moves, which is a list of tuples representing the moves to be played. Each tuple should contain the coordinates of the cell to be played (row, column).

  • Plays the moves in the order provided, switching between players “x” and “o” for each move.

  • Returns a tuple consisting of:

    • The winning player (“x”, “o”, or “=” if the game ends in a draw).

    • A set of all played moves in the order they were executed.

def predicted_strategy(moves, verbose=False):
    pass


#predicted_strategy(range(9), verbose=True) # "x"
#predicted_strategy((1, 0, 3, 2, 5, 4, 6, 7, 8), verbose=True) # "="

29.4.4. Enumerating All Possible Games#

In this step, we will implement a function to enumerate all possible games of Tic Tac Toe and classify the outcomes into draws, victories for player “o”, and victories for player “x”. This will be achieved using permutations of moves and a set to ensure unique game outcomes.

Define a function enumerate_possible_games that:

  • Uses the permutations to generate all possible sequences of moves for a Tic Tac Toe game.

  • For each permutation, simulate the game using the predicted_strategy function you implemented previously.

  • Count the number of unique games that result in:

    • A draw.

    • A victory for player “o”.

    • A victory for player “x”.

  • Return a tuple with three values: (number of draws, number of victories for o, number of victories for x).

Hint: Using the function permutations from the itertool module, we can iterate over all permutation.

from itertools import permutations
for perm in permutations(range(3)):
    print(perm)

Output:

(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)

from itertools import permutations

def enumerate_possible_games():
    pass

#print(enumerate_possible_games()) # (255168, 77904, 131184)

29.5. Human vs Computer#

We want to chanllenge ourself and play against the computer.

29.5.1. User Move Input#

In this step, we will implement a function that allows a human player to choose their move in the Tic Tac Toe game. The function will display the current grid state and prompt the user for their input.

Define a function choose_move that:

  • Takes a single parameter grid, which represents the current state of the Tic Tac Toe grid.

  • Displays the grid in a user-friendly format.

  • Prompts the user to enter their move in the form of a two-digit number (e.g., 31), which corresponds to the grid’s cell position.

  • Validates the user’s input to ensure it corresponds to an empty cell in the grid.

  • Returns the coordinates of the user’s chosen move as a tuple (row, column).

    1 2 3 
   ╔═╦═╦═╗
10 ║x║o║x║
   ╠═╬═╬═╣
20 ║x║o║o║
   ╠═╬═╬═╣
30 ║ ║x║o║
   ╚═╩═╩═╝
It's your turn, choose where you want to play.

 31

(2, 0)

def choose_move(grid):
    pass
    
#grid = [["x", "o", "x"], ["x", "o", "o"], [" ", "x", "o"]]
#choose_move(grid)

29.5.2. Computer Move Decision#

we will implement a function that determines the best move for the computer player (“o”) based on the current grid state and a specified level of difficulty. The function will evaluate possible moves and choose the one that minimizes the chances of losing.

The function evaluate(strategy, grid=None, player="x", iterations=10000) allows us to determine if a position seems to be a good position or not. The function return a tuple: number of draws, number of winning games for o and number of winning games for x. The computer is o.

For a given grid, we can associate to the each possible move a score. This score is determine as follows:

  1. Apply the move.

  2. Evaluate the grid for the random strategy.

  3. The best move is the one with the smaler ratio of win for the player x. Use the ratio of draws as a tie break rule.

The parameter iterations of the function evaluate allows us to introduce a level of difficulty. If the number of iterations is small, the computer will play randomly. If the number is large, the computer will be better. Thus we can set a level of difficulty as an integer between 1 and 5. The number of iterations is 10**difficulty.

Define a function best_move that:

  • Takes two parameters:

    • grid: The current state of the Tic Tac Toe grid.

    • difficulty: An integer between 1 and 5, representing the level of difficulty.

  • For each available position on the grid, the function should:

    • Simulate placing the computer’s symbol (“o”) in that position.

    • Use the evaluate function to assess the potential outcome of the game from that position.

    • Select the move that results in the lowest ratio of wins for player “x”, using the ratio of draws as a tiebreaker.

  • Return the coordinates of the best move as a tuple (row, column).

Hint: Remember that you need to copy the grid before modifying it.

def best_move(grid, difficulty):
    pass

#best_move(g, 4)

29.5.3. Playing a Game#

Create a function human_vs_computer that

  • takes an integer representing the difficulty as parameter

  • create a new grid

  • let the human play against the computer

  • return the winner

Create a main function to set a difficulty, run the human_vs_computer function and display message depending on the winner.

def human_vs_computer(difficulty):
    pass

def main():
    difficulty = 4
    w = human_vs_computer(difficulty)
    if w == "x":
        print(f"Bravo, you will against the computer of difficulty {difficulty}!")
    elif w == "o":
        print(f"You lose! Difficulty {difficulty} is too much for you!")
    else:
        print(f"Let's call it a draw")

main()

Let's call it a draw
Contents