Noughts and crosses, also inexplicably called tic-tac-toe by Yanks, is a game in which two players alternately place noughts and crosses on a three-by-three grid; the winner is the first player to place three of their symbol in a straight line: horizontally, vertically or diagonally.

Consult the relevant Wikipeda article and its citations for more information on noughts and crosses than you could ever want.

Python is the de facto programming language for learning, teaching and artificial intelligence (amongst many other fields). For the scope of this tutorial, using any other programming language would be gratuitous.

The best books on Python are Fluent Python by Luciano Ramalho and Effective Python by Brett Slatkin. For beginners, there are copious stellar resources available; any search engine is your friend. The Pythonic idioms to be aware of here, are list comprehension and dunders. More generally, within this tutorial, the most difficult programming paradigms used are recursion and currying; The Little Schemer by Daniel P. Friedman and Matthias Felleisen is an excellent primer on both of these concepts.

The opponent exhaustively considers every possible move, and determines which move has the lowest chance of leading to a loss. Many aspects of the program leave much to be desired. However, the primary purpose of this tutorial is to demonstrate how to create a simple, non-optimised, artificially intelligent opponent, and not to win a beauty pageant.

Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

We represent an empty starting board as:

board = " "*9

where a space denotes an empty cell, "0" a nought and "1" a cross. Players are represented as False for noughts and True for crosses.

We define which indices represent each row, column and diagonal. Remember that Python begins indexing at 0, not 1, as Dijkstra ordained.

def rowx(x):
    return [3*x, 3*x+1, 3*x+2]

def coly(y):
    return [0+y, 3+y, 6+y]

diagdown = [0, 4, 8]
diagup = [2, 4, 6]
rows = [rowx(i) for i in range(3)]
cols = [coly(i) for i in range(3)]
diags = [diagdown, diagup]
all_directions = rows + cols + diags

To return a list of cells which are still empty:

def possible(board):
    return [i for i, x in enumerate(board) if x == " "]

If we insist that noughts always starts first (it is called noughts and crosses for a reason), we can determine whose turn it is by counting how many cells are still empty. One great consequence of programming our own game, is being beholden to our own prejudices and setting our own idiosyncratic rules. Note: noughts is denoted by False, crosses by True.

def player(board):
    return (board.count(" ")-1) % 2

Knowing the player allows us to figure out what the board looks like after a move. Note: int(True) = 1 and int(False) = 0.

def new_board(board, move):
    return board[:move] + str(int(player(board))) + board[move+1:]

The following allows us to find out if the game has finished, and if so, who the winner is:

def moves_left(board):
    return board.count(" ")

def winner(board):
    if moves_left(board) < 5:
        for direction in all_directions:
            try:
                if sum(int(board[i]) for i in direction) == 3:
                    return "X"
                if sum(int(board[i]) for i in direction) == 0:
                    return "O"
            except ValueError:
                continue
        if moves_left(board) == 0:
            return "nobody"
    return False

Humans are visual creatures. Even for geeks with no more than an ASCII console, a 9 character long string does not suffice as a representation for a board. We must make at least some minimal pretension to aesthetic nous.

def display_possible(board):
    return ", ".join(str(x) for x in possible(board))

def display_player(p):
    return "X" if p else "O"

def display_cell(x):
    if x == "1":
        return "X"
    if x == "0":
        return "O"
    return x

def display(board):
    print()
    print(
        "\n_ _ _\n".join(
            "|".join(display_cell(board[3*x+y]) for y in range(3))
            for x in range(3)
        )
    )
    print()

Humans are not only visual creatures, but also butter-fingered. Use exceptions to limit the damage a human can do when they mash the keyboard. while True loops forever, providing ample time for the not-so-fleet-footed.

def get_human_player():
    while True:
        x = input("Would you like to be noughts O or crosses X?: ")
        return True if x.lower() == "x" else False

def human_move(board):
    while True:
        try:
            move = input(f"Choose a move from {display_possible(board)}: ")
            if int(move) in possible(board):
                return new_board(board, int(move))
            print("That number was not valid, please choose another.")
        except (ValueError, TypeError):
            print("Please input a number, not a string.")

The enemy of my enemy is my friend.

The algorithm we implement for the computer is called minimax. Namely, the computer chooses the move which maximises its chances that its opponent will have minimal chances to win. To calculate the score, minimax recursively calls itself exhaustively until all potential scenarios have been considered.

def score(result):
    if result == "O":
        return 1
    if result == "X":
        return -1
    return 0

def maxmin(x, maximise):
    return max(x) if maximise else min(x)

def minimax(board, maximise=True):
    if result:=winner(board):
        return score(result)
    return maxmin(
        [
            minimax(new_board(board, move), not maximise)
            for move in possible(board)
        ],
        maximise
    )

def computer_best_move(board):
    best_minimax_score = None
    best_move = None
    for move in possible(board):
        minimax_score = minimax(new_board(board, move), maximise=player(board))
        if (
                best_move is None or
                (player(board) and minimax_score < best_minimax_score) or
                (not player(board) and minimax_score > best_minimax_score)
        ):
            best_minimax_score = minimax_score
            best_move = move
    return best_move

def computer_move(board):
    move = computer_best_move(board)
    return new_board(board, move)

We then put the pieces together to create a playable game. The EOFError and KeyboardInterrupt allow the human player to exit at any time. The dunders in __name__ == "__main__" are daft, but alas, all languages have their defects.

def main(human=False):
    try:
        board = " "*9
        while not winner(board):
            display(board)
            if player(board) == human:
                board = human_move(board)
            else:
                board = computer_move(board)
        display(board)
        print(f"Finished! Winner is {winner(board)}")
    except (EOFError, KeyboardInterrupt):
        print("\nAbort\n")
        exit()

if __name__ == "__main__":
    HUMAN = get_human_player()
    main(human=HUMAN)

The complete code is available here.

Once you have tired of playing against your new-fledged playmate, change it up. Rewrite the program with other data representations:

1. keep track of the moves, not the board;

2. rewrite the board as an object;

3. use a three-by-three matrix instead of a 9 character long string.

Or improve it! The program could:

1. choose better moves (not just the least worst);

2. take symmetry into account, as a three-by-three grid is highly symmetrical;

3. use alpha beta pruning;

4. have a plusher user interface.

Alternatively, you can translate the program to another programming language. Or you can create an adversary for another game. Consult your nearest games cupboard for inspiration.

To venture further into the cybernetic meadows, let Richard Brautigan, Andrew Ng, Deep Learning by Ian Goodfellow and Yoshua Bengio and Aaron Courville, and Neural Networks and Learning Machines by Simon Haykin be your guides. Bon voyage!