Noughts and Crosses in Python

In this post I will implement a simple Noughts and Crosses game, sometimes known as Tic Tac Toe.

The project consists of two files:

  • nac.py
  • nacconsole.py

They can be downloaded as a zip, or you can clone/download the Github repository if you prefer.

Source Code Links

ZIP File
GitHub

The nac.py file contains a class implementing the game logic, independently of any user interface. The nacconsole.py file contains a class providing a console-based UI using curses. I wrote an introduction to curses a while ago which you might like to read before this article.

This is the rather long NaC class. You might like to read the descriptions of the various functions first before coming back to the code.

nac.py

import random
from enum import Enum

class NaC(object):

    class Levels(Enum):

        IDIOT = 0
        AVERAGE = 1
        GENIUS = 2

    def __init__(self, on_change, on_game_over):

        self.level = self.Levels.AVERAGE
        self._on_change = on_change
        self._on_game_over = on_game_over
        self._move_count = 0
        self._game_over = False
        self._win_paths = self.__create_win_paths()
        self._squares = [[" ", " ", " "],[" ", " ", " "],[" ", " ", " "]]

    #--------------------------------------------------------------------
    # "PUBLIC" METHODS
    #--------------------------------------------------------------------

    def human_move(self, square):

        """
        To be called by UI when user makes move.
        square argument is number of square when
        arranged:
            1 2 3
            4 5 6
            7 8 9
        """

        if self._game_over != True:

            row_column = self.__get_row_column(square)

            if self._squares[row_column["row"]][row_column["column"]] == " ":

                self._squares[row_column["row"]][row_column["column"]] = "X"
                self._on_change(row_column["column"], row_column["row"], "X")

                self._move_count += 1

                if self.__check_for_winner() == False:
                    self.computer_move()

    def computer_move(self):

        """
        Called by this class after human_move, or
        called by UI to make computer start.
        """

        if self.level == self.Levels.IDIOT:
            self.__computer_move_idiot()
        elif self.level == self.Levels.AVERAGE:
            self.__computer_move_average()
        elif self.level == self.Levels.GENIUS:
            self.__computer_move_genius()

        self._move_count += 1

        self.__check_for_winner()

    def new_game(self):

        """
        Resets relevant attributes to start new game.
        """

        self._squares = [[" ", " ", " "],[" ", " ", " "],[" ", " ", " "]]
        self._move_count = 0
        self._game_over = False

    def get_level_string(self):

        """
        Returns the current level as a human-readable string.
        """

        return ["Idiot", "Average", "Genius"][self.level.value]

    #--------------------------------------------------------------------
    # "PRIVATE" METHODS
    #--------------------------------------------------------------------

    def __computer_move_idiot(self):

        """
        Choose square at random
        """

        random.seed()

        while True:

            row = random.randint(0, 2)
            column = random.randint(0, 2)

            if self._squares[row][column] == " ":
                self._squares[row][column] = "O"
                self._on_change(column, row, "O")
                break

    def __computer_move_average(self):

        """
        Choose idiot or genius level
        at random with 50:50 probability
        """

        if random.randint(0, 1) == 0:
            self.__computer_move_idiot()
        else:
            self.__computer_move_genius()

    def __computer_move_genius(self):

        """
        Calculates the move most likely to
        result in a win.
        """

        # if first move of game use centre square
        # as this is in more win paths than other squares
        if self._move_count == 0:
            self._squares[1][1] = "O"
            self._on_change(1, 1, "O")
            return

        self.__populate_win_paths()

        # check if any moves give computer immediate win
        # 2 noughts and 1 empty
        for win_path in self._win_paths:
            if win_path["nought_count"] == 2 and win_path["empty_count"] == 1:
                empty_square = self.__find_empty_square(win_path)
                if empty_square != None:
                    self._squares[empty_square["row"]][empty_square["column"]] = "O"
                    self._on_change(empty_square["column"], empty_square["row"], "O")
                return

        # check if any moves give player immediate win
        # 2 crosses and 1 empty
        for win_path in self._win_paths:
            if win_path["cross_count"] == 2 and win_path["empty_count"] == 1:
                empty_square = self.__find_empty_square(win_path)
                if empty_square != None:
                    self._squares[empty_square["row"]][empty_square["column"]] = "O"
                    self._on_change(empty_square["column"], empty_square["row"], "O")
                return

        # check if any moves give computer potential win next go
        # 1 nought and 2 empty
        for win_path in self._win_paths:
            if win_path["nought_count"] == 1 and win_path["empty_count"] == 2:
                empty_square = self.__find_empty_square(win_path)
                if empty_square != None:
                    self._squares[empty_square["row"]][empty_square["column"]] = "O"
                    self._on_change(empty_square["column"], empty_square["row"], "O")
                return

        # check if any moves give player potential win next go
        # 1 cross and 2 empty
        for win_path in self._win_paths:
            if win_path["cross_count"] == 1 and win_path["empty_count"] == 2:
                empty_square = self.__find_empty_square(win_path)
                if empty_square != None:
                    self._squares[empty_square["row"]][empty_square["column"]] = "O"
                    self._on_change(empty_square["column"], empty_square["row"], "O")
                return

        # cannot find useful move so call
        # __computer_move_idiot to make random move
        self.__computer_move_idiot()

    def __get_row_column(self, square):

        """
        Get row and column numbers as dictionary
        for squares numbered:
        1 2 3
        4 5 6
        7 8 9
        """

        column = 0
        row = 0

        if square in [1,4,7]:
            column = 0
        elif square in [2,5,8]:
            column = 1
        else:
            column = 2

        if square in [1,2,3]:
            row = 0
        elif square in [4,5,6]:
            row = 1
        else:
            row = 2

        return {"row": row, "column": column}

    def __check_for_winner(self):

        """
        Called after each move to check if there is a
        winner or if the game is over with no winner.
        """

        # check columns
        for column in range(0, 3):
            if self._squares[0][column] != " ":
                if self._squares[0][column] == self._squares[1][column] \
                and self._squares[0][column] == self._squares[2][column]:
                    self._on_game_over(self._squares[0][column])
                    self._game_over = True
                    return True

        # check rows
        for row in range(0, 3):
            if self._squares[row][0] != " ":
                if self._squares[row][0] == self._squares[row][1] \
                and self._squares[row][0] == self._squares[row][2]:
                    self._on_game_over(self._squares[row][0])
                    self._game_over = True
                    return True

        # check diagonals
        if self._squares[0][0] != " ":
            if self._squares[0][0] == self._squares[1][1] \
            and self._squares[0][0] == self._squares[2][2]:
                self._on_game_over(self._squares[0][0])
                self._game_over = True
                return True

        if self._squares[2][0] != " ":
            if self._squares[2][0] == self._squares[1][1] \
            and self._squares[2][0] == self._squares[0][2]:
                self._on_game_over(self._squares[0][2])
                self._game_over = True
                return True

        # draw if no winner but all 9 squares used
        if self._move_count == 9:
            self._on_game_over(" ")
            self._game_over = True
            return True

        # game not yet over
        return False

    def __create_win_paths(self):

        """
        Create list of the 8 win paths, each with a
        dictionary of:
            squares
            cross_count
            nought_count
            empty_count
        """

        win_paths = []

        # rows
        for row in range(0, 3):
            win_path = {"squares": [],
                        "cross_count": 0,
                        "nought_count": 0,
                        "empty_count": 0}

            for col in range(0, 3):
                win_path["squares"].append({"row": row,
                                           "column": col})

            win_paths.append(win_path)

        # columns
        for col in range(0, 3):
            win_path = {"squares": [],
                        "cross_count": 0,
                        "nought_count": 0,
                        "empty_count": 0}

            for row in range(0, 3):
                win_path["squares"].append({"row": row,
                                           "column": col})

            win_paths.append(win_path)

        # diagonals
        # top left -> bottom right
        win_path = {"squares": [],
                    "cross_count": 0,
                    "nought_count": 0,
                    "empty_count": 0}

        for row_col in range(0, 3):

            win_path["squares"].append({"row": row_col,
                                       "column": row_col})

        win_paths.append(win_path)

        # top right -> bottom left
        win_path = {"squares": [],
                    "cross_count": 0,
                    "nought_count": 0,
                    "empty_count": 0}

        for row in range(0, 3):

            win_path["squares"].append({"row": row,
                                       "column": 2 - row})

        win_paths.append(win_path)

        return win_paths

    def __populate_win_paths(self):

        """
        Set the totals of each win path.
        """

        for win_path in self._win_paths:

            win_path["cross_count"] = 0
            win_path["nought_count"] = 0
            win_path["empty_count"] = 0

            for square in win_path["squares"]:
                if self._squares[square["row"]][square["column"]] == " ":
                    win_path["empty_count"] += 1
                elif self._squares[square["row"]][square["column"]] == "X":
                    win_path["cross_count"] += 1
                elif self._squares[square["row"]][square["column"]] == "O":
                    win_path["nought_count"] += 1

    def __find_empty_square(self, win_path):

        """
        Finds an empty square in the given win paths
        for computer's next move.
        """

        for square in win_path["squares"]:
            if self._squares[square["row"]][square["column"]] == " ":
                return {"row": square["row"], "column": square["column"]}

        return None

Levels enum

Not essential as I could just use arbitrary numbers or strings but it does make the code neater.

__init__

The on_change and on_game_over arguments are functions injected by the code instantiating an object, and are called when the respective situations occur. We'll see the UI use these later on.

The rest of __init__ just creates a few variables for use within the class.

human_move

This method is for the UI to call when the human (or other sentient being capable of using a keyboard) makes a move. The argument is the square as described in the docstring. We convert that into a row/column pair using the __get_row_column function and then check the square hasn't already been filled. If not the square's value is set to "X" and the _on_change function called to let the UI know it needs to draw the symbol in the square. Lastly _move_count is implemented and we check whether the game is now over.

computer_move

This is called after human_move, or by the UI if the user decides to let the computer move first.

It calls one of three other functions depending on the level, before incrementing _move_count and checking for a winner.

new_game

Here we just need to reset the variables representing the game state.

get_level_string

This function returns the level as a string suitable for displaying in a UI.

__computer_move_idiot

In idiot mode the computer searches at random for an empty square to place its "O" in.

__computer_move_average

The average level uses either idiot level or genius level at random with 50:50 probability.

__computer_move_genius

If it is starting the game the computer will always select the centre square. Otherwise it uses a list of win paths which I'll describe in a moment to find the optimum square. The stages it goes through are:

  • Check if any squares give the computer an immediate win
  • Check if any squares give the user an immediate win; if so block them
  • Check if any squares give the computer a potential win next time
  • Check if any squares give the user a potential win next time; if so block them
  • If none of these succeed call __computer_move_idiot to use a random square

__get_row_column

This converts the square numbers 1-9 entered by the user to a row/column pair.

__check_for_winner

Check the three rows, three columns and two diagonals to see if any have three matching symbols.

__create_win_paths

This function creates a list of nine dictionaries representing the nine possible win paths, ie straight lines of three squares. Each dictionary contains the row/column numbers of the three squares as well as the counts of each of the three possible states of a square: empty, "O" and "X".

__populate_win_paths

Here we set the counts of each possible state per win path for use by __computer_move_genius as described above.

__find_empty_square

If __computer_move_genius finds a win path it wishes to use for its next move it calls this function to find an empty square in this path. If there are two the first is returned.

That's the NaC class finished so now we can move on to writing a UI. As I mentioned above I have written a console UI with curses but the NaC class has no user interface code so can be used with any library or framework, for example PyGame, Tkinter, PyQt or whatever.

nacconsole.py

import curses

import nac


class NaCConsole(object):

    def __init__(self):

        self.screen = curses.initscr()
        curses.curs_set(False)
        curses.noecho()

        curses.start_color()
        curses.init_pair(1, curses.COLOR_WHITE, curses.COLOR_GREEN)
        curses.init_pair(2, curses.COLOR_BLACK, curses.COLOR_WHITE)
        curses.init_pair(3, curses.COLOR_BLACK, curses.COLOR_YELLOW)

        self.game = nac.NaC(on_change=self.on_game_changed,
                            on_game_over=self.on_game_over)

        self.__draw_board()
        self.__show_level()

        self.__event_loop()

    def __event_loop(self):

        while True:

            key = self.screen.getch()

            if key in range(49, 58):
                self.game.human_move(int(key) - 48)
            elif chr(key) == "x":
                curses.endwin()
                exit()
            elif chr(key) == "s":
                self.game.computer_move()
            elif chr(key) == "i":
                self.game.level = self.game.Levels.IDIOT
                self.__show_level()
            elif chr(key) == "a":
                self.game.level = self.game.Levels.AVERAGE
                self.__show_level()
            elif chr(key) == "g":
                self.game.level = self.game.Levels.GENIUS
                self.__show_level()
            elif chr(key) == "n":
                self.game.new_game()
                self.__draw_board()
                self.__show_level()

    def __draw_board(self):

        self.screen.clear()

        width = 56

        row1 = "                  |                  |                  \n"
        row2 = "------------------|------------------|------------------\n"

        def draw_rows_1():
            for r in range(0, 9):
                self.screen.addstr(row1, curses.color_pair(1) | curses.A_BOLD)

        draw_rows_1()
        self.screen.addstr(row2, curses.color_pair(1) | curses.A_BOLD)
        draw_rows_1()
        self.screen.addstr(row2, curses.color_pair(1) | curses.A_BOLD)
        draw_rows_1()

        x = 0
        y = 0
        s = 1

        for h in range(0, 3):
            for v in range(0, 3):
                self.screen.addstr(y, x, str(s), curses.color_pair(1) | curses.A_BOLD)
                x += 19
                s += 1
            x = 0
            y += 10

        self.screen.addstr(30, 0, " Computer start     s".ljust(width, " "),
                           curses.color_pair(2) | curses.A_BOLD)
        self.screen.addstr(31, 0, " Place an X         1-9".ljust(width, " "),
                           curses.color_pair(2) | curses.A_BOLD)
        self.screen.addstr(32, 0, " Idiot              i".ljust(width, " "),
                           curses.color_pair(2) | curses.A_BOLD)
        self.screen.addstr(33, 0, " Average            a".ljust(width, " "),
                           curses.color_pair(2) | curses.A_BOLD)
        self.screen.addstr(34, 0, " Genius             g".ljust(width, " "),
                           curses.color_pair(2) | curses.A_BOLD)
        self.screen.addstr(35, 0, " New game           n".ljust(width, " "),
                           curses.color_pair(2) | curses.A_BOLD)
        self.screen.addstr(36, 0, " Exit               x".ljust(width, " "),
                           curses.color_pair(2) | curses.A_BOLD)

        self.screen.refresh()

    def __show_level(self):

        width = 56

        level_string = " Current level:     {}".format(self.game.get_level_string(), width=width)
        level_string += " " * (56 - len(level_string))
        self.screen.addstr(29, 0, level_string, curses.color_pair(2) | curses.A_BOLD)
        self.screen.refresh()

    def on_game_changed(self, column, row, shape):

        x = 2 + (19 * column)
        y = 1 + (10 * row)

        if(shape == "X"):
            self.screen.addstr(y + 0, x, "XX          XX", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 1, x, "  XX      XX  ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 2, x, "    XX  XX    ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 3, x, "      XX      ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 4, x, "    XX  XX    ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 5, x, "  XX      XX  ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 6, x, "XX          XX", curses.color_pair(1) | curses.A_BOLD)
        elif(shape == "O"):
            self.screen.addstr(y + 0, x, "      OO     ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 1, x, "    OO  OO   ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 2, x, "  OO      OO ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 3, x, " OO        OO", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 4, x, "  OO      OO ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 5, x, "    OO  OO   ", curses.color_pair(1) | curses.A_BOLD)
            self.screen.addstr(y + 6, x, "      OO     ", curses.color_pair(1) | curses.A_BOLD)

        self.screen.refresh()

    def on_game_over(self, winner):

            width = 56
            message_width = 18

            if winner == "X":
                winner_string = "You won".center(message_width, " ")
            elif winner == "O":
                winner_string = "The computer won".center(message_width, " ")
            else:
                winner_string = "Game ended in draw".center(message_width, " ")

            self.screen.addstr(13, 19, " " * message_width, curses.color_pair(3) | curses.A_BOLD)
            self.screen.addstr(14, 19, winner_string, curses.color_pair(3) | curses.A_BOLD)
            self.screen.addstr(15, 19, " " * message_width, curses.color_pair(3) | curses.A_BOLD)

            self.screen.refresh()


cons = NaCConsole()

__init__

After a load of stuff to set up curses we create an instance of NaC before calling functions to draw the board and show the level. Finally we call a function to start the event loop.

__event_loop

After being created user interfaces just sit and wait for the user to do something, that something mostly being hitting a key or moving/clicking the mouse. We therefore need an infinite loop which "listens" for such events and responds accordingly. This program only accepts keyboard input so we call self.screen.getch() in the loop and then check if the key is one which is meaningful for the game.

The characters which we need to respond to are numbers 1 to 9 (ASCII 49 to 58) and a few letters. The relevant functions are called in an if/elif stack and any others are ignored.

Note that although this is an infinite loop we do provide a way out via "x" for exit.

__draw_board

This is a fiddly but straightforward function which draws the nine empty squares and also a panel at the bottom listing the valid characters for user input.

__show_level

Showing the level is done by a separate function so it can be called without redrawing the whole game.

on_game_changed

This is one of the functions passed to the NaC class's __init__, and is called by the NaC class when either the computer or the user make a move. It therefore just needs to draw an "X" or "O" in the correct square.

on_game_over

This is the other function passed to the NaC class and is called when the game is over. The winner argument is "X" for the player, "O" for the computer or " " for a draw. The function uses this to create a suitable message which is then displayed in an orange box in the middle of the board.

Lastly we create an instance of the NaCConsole class which is all that is necessary to kick off a new game.

Running the Program

The coding is finished so lets run the program.

Run

python3.7 nacconsole.py

This is a screenshot of a sample game after completion.