Python Tic-Tac-Toe AI

Not too long ago I began talking to a company which will remain unnamed for now about a Django dev job. Part of their hiring process is to write single player a tic-tac-toe game where the computer always wins in Python. The hiring is on hold over the holidays, but I figured I'd get a head start and document it here for fun.

I start with a couple of basic classes, Board, Player, and AIPlayer.

class Board(object):
    """A tic tac toe board"""

    wins = ((0,1,2), # rows
            (3,4,5),
            (6,7,8),
            (0,3,6), # columns
            (1,4,7),
            (2,5,8),
            (0,4,8), # diagonals
            (2,4,6))

    def __init__(self, *args, **kwargs):
        self.tttboard = [None, None, None,
                         None, None, None,
                         None, None, None]

class Player(object):
    """A tic tact toe player"""

    def __init__(self, board_value, *args, **kwargs):
        """
        board_value should be a single character to display such as X or O.
        """

        self.board_value = board_value  # the value which will represent the player behind the scenes

class AIPlayer(Player):
    """An AI tic tac toe player"""

     def look_for_win(self, board, player=None):
        """Find a space which allows a win for the given player"""
        pass

I just created skeletons plus a couple of things I knew I'd want from having done a similar two player tic-tac-toe game for a previous project.

After that I began to add logic I was pretty sure I'd need. First AIPlayer() got a look_for_win() method. This started out as only looking for wins for that player but I quickly realized that it could be reused to look for blocking wins from the other player as well.

def look_for_win(self, board, player=None):
    """Find a space which allows a win for the given player"""

    win_spot = None
    if player is None:
        player = self

    for group in board.wins:
        # creates a list of just the elements of the board which are
        # part of a specific win group and and not already owned by the player
        # and creates a list of tuples of the element and its value.
        not_mine = [(i, val) for i, val in enumerate(board.tttboard)
                    if i in group
                    and val != player.board_value]

        # If there's only one not owned by the ai player and not owned by
        # the other player then select it and we've won
        if len(not_mine) == 1 and not_mine[0][1] is None:
            # Maybe this should return the selection rather than
            # modifying the board in here.  Decide later.
            win_spot=not_mine[0][0]
            break

    return win_spot

I then added logic to pick a spot if there was no winning spot. This is done based on a priority, aiming for the middle spot first, then corners, then the other edges. This is based on the number of directions a position opens up for a winning row. This logic is the first attempt, but is not what it will need to be in the end. This logic results in a minimum of a tie every time as is and will win if the human player picks position 3, 5, or 7 as their first pick. Fortunately there are strategies to guarantee a win which I can implement, but I wanted to try just doing this logic to see how well it worked before looking up those strategies.

To do this the AIPlayer class has a an attribute POSITION_PRIORITY which is just tuple of positions in the order that it should try to get them and a method which uses those to make a move.

class AIPlayer(Player):
    """An AI tic tac toe player"""

    # High priority board positions in order that they should be selected
    # if the position is open and there are no higher priorities such as
    # a winning opening or blocking a win.
    # This is the middle and then the 4 corners, the positions with the most
    # opportunity for leading to a win.
    POSITION_PRIORITY = (4, 0, 2, 6, 8)

def pick_open_position(self, board):
    """
    Select any open spot on the board.

    This is a fallback to be used when there are no wins or win blockers.
    """

    open_positions = [i for i, value in enumerate(board.tttboard) if value is None]

    # default no priority position
    selected_position = open_positions[0]

    for position in AIPlayer.POSITION_PRIORITY:
        if position in open_positions:
            selected_position = position
            break

    return selected_position

In the end, that basic logic work, I just needed to use different position priorities based on the first spot picked by the human player. I changed the priorities to a list of tuples with each at the index corresponding to the spot the human player had picked. The POSITION_PRIORITY got replaced with the following:

STRATEGIES = [(4, 8, 2),
                        (4, 8, 6, 2, 0),
                        (4, 6, 0),
                        (4, 0, 2, 6, 8),
                        None, # should not happen, we ALWAYS get this first
                        (4, 0, 2, 6, 8),
                        (4, 2, 8),
                        (4, 0, 2, 6, 8),
                        (4, 0, 6)]

A method was added to the AIPlayer class to handle the logic that happens on each turn. On the first turn we always pick position #4, the middle square. On the second turn the human player has gone and so a strategy can be chosen. This strategy then holds for the rest of the game.

def take_turn(self, board, other_player):
        """Implement the logic for a single turn of the AI player"""

        # Always pick the middle box on the first round
        position = 4 if self.turn_count == 0 else None

        if self.turn_count == 1:
            # On the second turn, after the human player has picked
            # their first spot so we can determine our strategy
            assert other_player.board_value in board.tttboard
            player2_position = board.tttboard.index(other_player.board_value)
            self.strategy = AIPlayer.STRATEGIES[player2_position]

        if position is None:
            position = self.look_for_win(board)

        if position is None:
            position = self.look_for_win(board, other_player)

        if position is None:
            position = self.pick_open_position(board)

        self.turn_count += 1
        return position

The full working game is as follows. The Board, Player, and AIPlayer classes could easily be used with a different game loop which does something fancier such as using pygame.

"""
A simple tic tac toe game where the computer always wins or at least ties.
"""
import sys

class PositionAlreadyTakenError(Exception):
    pass

class Board(object):
    """A tic tac toe board"""

    wins = ((0, 1, 2), # rows
            (3, 4, 5),
            (6, 7, 8),
            (0, 3, 6), # columns
            (1, 4, 7),
            (2, 5, 8),
            (0, 4, 8), # diagonals
            (2, 4, 6))

    def __init__(self, *args, **kwargs):
        self.tttboard = [None, None, None,
                         None, None, None,
                         None, None, None]

    def select_position(self, position, player):
        """Sets a position on the board as owned by a player"""

        if self.tttboard[position] is not None:
            raise PositionAlreadyTakenError()

        self.tttboard[position] = player.board_value

    def check_for_win(self, player):
        """Check the board to see if the player has won"""
        winner = False
        for group in Board.wins:
            if self.tttboard[group[0]] == player.board_value \
                    and self.tttboard[group[1]] == player.board_value \
                    and self.tttboard[group[2]] == player.board_value:
                winner = True
                break

        return winner

class Player(object):
    """A tic tact toe player"""

    def __init__(self, board_value, *args, **kwargs):
        """
        board_value should be a single character to display such as X or O.
        """

        # the value which will represent the player behind the scenes
        self.board_value = board_value
        self.turn_count = 0

class AIPlayer(Player):
    """An AI tic tac toe player"""

    # These are the positions to target in order
    # after the first turn and any checks for wins/blocks
    # Each list index aligns with the corresponding board position
    STRATEGIES = [(4, 8, 2),
                  (4, 8, 6, 2, 0),
                  (4, 6, 0),
                  (4, 0, 2, 6, 8),
                  None, # should not happen, we ALWAYS get this first
                  (4, 0, 2, 6, 8),
                  (4, 2, 8),
                  (4, 0, 2, 6, 8),
                  (4, 0, 6)]

    def __init__(self, board_value, *args, **kwargs):
        super(AIPlayer, self).__init__(board_value, *args, **kwargs)
        self.strategy = None

    def look_for_win(self, board, player=None):
        """Find a space which allows a win for the given player"""

        win_spot = None
        if player is None:
            player = self

        for group in board.wins:
            # creates a list of just the elements of the board which are
            # part of a specific win group and and not already owned by the player
            # and creates a list of tuples of the element and its value.
            not_mine = [(i, val) for i, val in enumerate(board.tttboard)
                        if i in group
                        and val != player.board_value]

            # If there's only one not owned by the ai player and not owned by
            # the other player then select it and we've won
            if len(not_mine) == 1 and not_mine[0][1] is None:
                # Maybe this should return the selection rather than
                # modifying the board in here.  Decide later.
                win_spot = not_mine[0][0]
                break

        return win_spot

    def pick_open_position(self, board):
        """
        Select any open spot on the board.

        This is a fallback to be used when there are no wins or win blockers.
        """

        open_positions = [i for i, value in enumerate(board.tttboard) if value is None]

        # default no priority position then see if there's a position open
        # which fits the chosen strategy
        selected_position = open_positions[0]

        for position in self.strategy:
            if position in open_positions:
                selected_position = position
                break

        return selected_position

    def take_turn(self, board, other_player):
        """Implement the logic for a single turn of the AI player"""

        # Always pick the middle box on the first round
        position = 4 if self.turn_count == 0 else None

        if self.turn_count == 1:
            # On the second turn, after the human player has picked
            # their first spot so we can determine our strategy
            assert other_player.board_value in board.tttboard
            player2_position = board.tttboard.index(other_player.board_value)
            self.strategy = AIPlayer.STRATEGIES[player2_position]

        if position is None:
            position = self.look_for_win(board)

        if position is None:
            position = self.look_for_win(board, other_player)

        if position is None:
            position = self.pick_open_position(board)

        self.turn_count += 1
        return position

def draw(board):
    """Draw the game board on screen"""
    # ANSI code to clear the screen
    print chr(27) + "[2J"
    for position, value in enumerate(board.tttboard):
        if value is None:
            sys.stdout.write(str(position))
        else:
            sys.stdout.write(str(value))

        if (position + 1) % 3 != 0:
            sys.stdout.write('|')
        else:
            print ''

        if position == 2 or position == 5:
            print '-' * 5

# A singleton object could be used for the game, but it does't really
# add anything other than some extra complication with the given requirements.
def play_game(board, player1, player2):
    """The main game loop/logic"""

    playing = True
    while playing:
        draw(board)

        if None not in board.tttboard:
            print 'No more moves left.'
            break

        aichoice = player1.take_turn(board, player2)
        board.select_position(aichoice, player1)

        draw(board)
        if board.check_for_win(player1):
            print "Computer Wins!"
            break

        if None not in board.tttboard:
            print 'No more moves left.'
            break

        # player selection
        while True:
            selection = raw_input('Pick a spot: ')
            if selection.lower() == 'q':
                playing = False
                break

            try:
                board.select_position(int(selection), player2)
            except PositionAlreadyTakenError:
                print 'That position is already taken.'
            else:
                if board.check_for_win(player2):
                    # Well, this isn't supposed to happen.
                    print "You Win!"
                    playing = False
                break

if __name__ == '__main__':
    player1 = AIPlayer('X')
    player2 = Player('Y')
    board = Board()

    play_game(board, player1, player2)