An implementation of tic-tac-toe game with a few play strategies (e.g. human, random, minimax, alpha-beta pruning)

tictactoe.py

import copy
import random

# constants

EMPTY, X, O = '.XO'
ROWS = [[(i, j) for j in range(3)] for i in range(3)]
COLS = [[(j, i) for j in range(3)] for i in range(3)]
DIAGONALS = [
    [(0, 0), (1, 1), (2, 2)],
    [(0, 2), (1, 1), (2, 0)]
]
WIN_POSITIONS = ROWS + COLS + DIAGONALS
ALL_SQUARES = [(i, j) for i in range(3) for j in range(3)]
# values used for minimax algorithm
MIN_VALUE, MAX_VALUE, WIN_VALUE, LOSS_VALUE, DRAW_VALUE = -2, 2, 1, -1, 0

# tic_tac_toe game

def tic_tac_toe(x_strategy, o_strategy, verbose=True):
    '''Play a game of tic-tac-toe.

    X is always the first player.
    '''
    board, player, is_finished = initial_board(), X, False
    while not is_finished:
        strategy = x_strategy if player == X else o_strategy
        make_move(strategy, player, board, verbose)
        is_finished, winner = find_winner(board)
        player = opponent(player)

    if verbose:
        if winner:
            strategy = x_strategy if winner == X else o_strategy
            print(f'The winner is {winner} with {strategy.__name__}. Final board:')
        else:
            print(f'The game is over with a draw. Final board:')
        print_board(board)

    return winner


def make_move(strategy, player, board, verbose):
    # Pass a copy of board. If we passed the real game board,
    # the function could cheat by changing the pieces on the board!
    (x, y) = strategy(player, copy_board(board))
    if is_valid(x, y, board):
        if verbose:
            print(f'{player} moves to {(x, y)}')
        board[x][y] = player
    else:
        print(f'Illegal move: {(x, y)}')
        make_move(strategy, player, board, verbose)

# strategies

def human_strategy(player, board):
    'A human player for the game of Othello.'
    print()
    print_board(board)
    row = input(f'{player} row: ')
    col = input(f'{player} col: ')
    return int(row), int(col)


def random_strategy(player, board):
    'Make any legal move.'
    return random.choice(list(legal_moves(board)))


def minimax_strategy(player, board):
    '''A strategy that searches the whole state space
    and then return best move.

    minimax: https://en.wikipedia.org/wiki/Minimax
    '''
    return minimax(player, board)[1]


def minimax(player, board):
    '''Return the (best_score, best_move) pair.

    If you are interested in general minimax algorithm,
    '''
    is_finished, winner = find_winner(board)
    if is_finished:
        return get_finished_val(winner, player)

    best_move, best_val = None, MIN_VALUE
    for (x, y) in legal_moves(board):
        board2 = copy_board(board)
        board2[x][y] = player
        val = -(minimax(opponent(player), board2)[0])
        if val > best_val:
            best_val, best_move = val, (x, y)

    return (best_val, best_move)


def alpha_beta_strategy(player, board):
    '''A strategy similar to minimax strategy. It computes exact same
    results as the minimax. The only advantage of cutoffs is making
    the search go faster by considering fewer positions.

    alpha–beta: https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
    '''
    return alpha_beta(player, board, MIN_VALUE, MAX_VALUE)[1]


def alpha_beta(player, board, alpha, beta):
    '''Return the (best_score, best_move) pair.

    Using minimax algorithm with alpha-beta pruning whenever possible.
    '''
    is_finished, winner = find_winner(board)
    if is_finished:
        return get_finished_val(winner, player)

    best_move = None
    for (x, y) in legal_moves(board):
        board2 = copy_board(board)
        board2[x][y] = player
        val = -(alpha_beta(opponent(player), board2, -beta, -alpha)[0])
        if val > alpha:
            alpha, best_move = val, (x, y)
        if (alpha >= beta):
            break

    return (alpha, best_move)


def get_finished_val(winner, curr_player):
    if winner:
        score = WIN_VALUE if winner == curr_player else LOSS_VALUE
        return (score, None)
    else:
        return (DRAW_VALUE, None)

# utils

def initial_board():
    'Return a empty 3 X 3 board.'
    return [[EMPTY] * 3 for i in range(3)]


def print_board(board):
    print('   0  1  2')
    for i, row in enumerate(board):
        print(f"{i}  {'  '.join(row)}")


def copy_board(board):
    return copy.deepcopy(board)


def opponent(player):
    return X if player == O else O


def find_winner(board):
    'Return a (is_finished, winner) pair.'
    has_empty = False
    for win_pos in WIN_POSITIONS:
        vals = {board[x][y] for (x, y) in win_pos}
        # find winner
        if len(vals) == 1 and not EMPTY in vals:
            return (True, vals.pop())
        if EMPTY in vals:
            has_empty = True
    return (not has_empty, None)


def is_valid(x, y, board):
    return (0 <= x < 3) and (0 <= y < 3) and (board[x][y] == EMPTY)


def legal_moves(board):
    return ((x,y) for (x, y) in ALL_SQUARES if board[x][y] == EMPTY)


if __name__ == "__main__":
    tic_tac_toe(human_strategy, alpha_beta_strategy)

A sample play between human (X) and minimax strategy (O).

$ python3 tictactoe.py

   0  1  2
0  .  .  .
1  .  .  .
2  .  .  .
X row: 1  // this is human input
X col: 1  // this is human input
X moves to (1, 1)

O moves to (0, 0)

   0  1  2
0  O  .  .
1  .  X  .
2  .  .  .
X row: 2
X col: 0
X moves to (2, 0)

O moves to (0, 2)

   0  1  2
0  O  .  O
1  .  X  .
2  X  .  .
X row: 0
X col: 1
X moves to (0, 1)

O moves to (2, 1)

   0  1  2
0  O  X  O
1  .  X  .
2  X  O  .
X row: 2
X col: 2
X moves to (2, 2)

O moves to (1, 0)

   0  1  2
0  O  X  O
1  O  X  .
2  X  O  X
X row: 1
X col: 2
X moves to (1, 2)

The game is over with a draw. Final board:
   0  1  2
0  O  X  O
1  O  X  X
2  X  O  X