TicTacToe - MiniMax AI based on a scoring matrix of the game tree

TicTacToe.py

'''
TicTacToe Game

Console based.
MiniMax AI based on a scoring matrix of the game tree

Python 2.7.9 - 32 bit

@author Andre Cruz
'''


# Constants
EMPTY = 1
PLAYERX = 2
PLAYERO = 3 
DRAW = 4

# Map player constants to letters for printing
STRMAP = {EMPTY: " ",
          PLAYERX: "X",
          PLAYERO: "O"}

class TTTBoard:
    """
    Class to represent a Tic-Tac-Toe board.
    """

    def __init__(self, dim, reverse = False, board = None):
        self._dim = dim
        self._reverse = reverse
        if board == None:
            # Create empty board
            self._board = [[EMPTY for dummycol in range(dim)] 
                           for dummyrow in range(dim)]
        else:
            # Copy board grid
            self._board = [[board[row][col] for col in range(dim)] 
                           for row in range(dim)]
            
    def __str__(self):
        """
        Human readable representation of the board.
        """
        rep = "  "
        for idx in range(self._dim):
            rep += str(idx + 1) + '   '
        rep += '\n'
        for row in range(self._dim):
            rep += str(row + 1) + ' '
            for col in range(self._dim):
                rep += STRMAP[self._board[row][col]]
                if col == self._dim - 1:
                    rep += "\n"
                else:
                    rep += " | "
            if row != self._dim - 1:
                rep += '  '
                rep += "-" * (4 * self._dim - 3)
                rep += "\n"
        return rep

    def get_dim(self):
        """
        Return the dimension of the board.
        """
        return self._dim
    
    def square(self, row, col):
        """
        Return the status (EMPTY, PLAYERX, PLAYERO) of the square at
        position (row, col).
        """
        return self._board[row][col]

    def get_empty_squares(self):
        """
        Return a list of (row, col) tuples for all empty squares
        """
        empty = []
        for row in range(self._dim):
            for col in range(self._dim):
                if self._board[row][col] == EMPTY:
                    empty.append((row, col))
        return empty

    def move(self, row, col, player):
        """
        Place player on the board at position (row, col).

        Does nothing if board square is not empty.
        """
        if self._board[row][col] == EMPTY:
            self._board[row][col] = player

    def check_win(self):
        """
        If someone has won, return player.
        If game is a draw, return DRAW.
        If game is in progress, return None.
        """
        board = self._board
        dim = self._dim
        dimrng = range(dim)
        lines = []

        # rows
        lines.extend(board)

        # cols
        cols = [[board[rowidx][colidx] for rowidx in dimrng]
                for colidx in dimrng]
        lines.extend(cols)

        # diags
        diag1 = [board[idx][idx] for idx in dimrng]
        diag2 = [board[idx][dim - idx -1] 
                 for idx in dimrng]
        lines.append(diag1)
        lines.append(diag2)

        # check all lines
        for line in lines:
            if len(set(line)) == 1 and line[0] != EMPTY:
                if self._reverse:
                    return switch_player(line[0])
                else:
                    return line[0]

        # no winner, check for draw
        if len(self.get_empty_squares()) == 0:
            return DRAW

        # game is still in progress
        return None
            
    def clone(self):
        """
        Return a copy of the board.
        """
        return TTTBoard(self._dim, self._reverse, self._board)
    
def switch_player(player):
    """
    Convenience function to switch players.
    
    Returns other player.
    """
    if player == PLAYERX:
        return PLAYERO
    else:
        return PLAYERX


################################################################
## MiniMax

# SCORING VALUES
SCORES = {PLAYERX: 1,
          DRAW: 0,
          PLAYERO: -1}

iterations = 0

def mm_move(board, player):
    """
    Make a move on the board.
    
    Returns a tuple with two elements.  The first element is the score
    of the given board and the second element is the desired move as a
    tuple, (row, col).
    """
    global iterations
    iterations += 1
    
    if board.check_win() != None:
        # base case
        score = SCORES[board.check_win()]
        return score, (-1, -1)
    
    # recursive case
    scores = {}
    
    for square in board.get_empty_squares():
        clone = board.clone()
        clone.move(square[0], square[1], player)
        move = mm_move(clone, switch_player(player))
        score = move[0]
        
        if (score == 1 and player == PLAYERX) or (score == -1 and player == PLAYERO):
            return score, square
        
        scores[score] = square
    
    if player == PLAYERX:
        best_score = max(scores)
    elif player == PLAYERO:
        best_score = min(scores)
        
    return best_score, scores[best_score]

def move_wrapper(board, player, trials):
    """
    Wrapper to allow the use of the same infrastructure that was used
    for Monte Carlo Tic-Tac-Toe.
    """
    global iterations
    move = mm_move(board, player)
    print 'Iterations: ', iterations
    iterations = 0
    assert move[1] != (-1, -1), "returned illegal move (-1, -1)"
    return move[1]

################################################################
## Game functions
    
def play_mc_game(mc_move_function, ntrials, reverse = False):
    """
    Function to play a game with two machine players.
    """
    # Setup game
    board = TTTBoard(3, reverse)
    curplayer = PLAYERX
    winner = None
    
    # Run game
    while winner == None:
        # Move
        row, col = mc_move_function(board, curplayer, ntrials)
        board.move(row, col, curplayer)

        # Update state
        winner = board.check_win()
        curplayer = switch_player(curplayer)

        # Display board
        print board
        print
        
    # Print winner
    if winner == PLAYERX:
        print "X wins!"
    elif winner == PLAYERO:
        print "O wins!"
    elif winner == DRAW:
        print "Tie!"
    else:
        print "Error: unknown winner"

def play_vs_ai(mc_move_function, dimension = 3, ntrials = 1, reverse = False):
    '''
    Function to play a human versus AI game
    '''
    # Setup game
    boardObj = TTTBoard(dimension, reverse)
    human_player = PLAYERX
    ai_player = PLAYERO
    winner = None

    curplayer = human_player # Current player
    
    print
    print boardObj
    
    # Run game
    while winner == None:
        if curplayer == human_player:
            # Player move
            while True:
                print
                row = input('Row: ') - 1
                col = input('Column: ') - 1
                print

                if (row, col) in boardObj.get_empty_squares() and \
                   0 <= row < dimension and 0 <= col < dimension: # Checks if the move is valid
                    boardObj.move(row, col, curplayer)
                    break
                else:
                    print '\nInvalid move\n'

        elif curplayer == ai_player:
            # AI Move
            row, col = mc_move_function(boardObj, curplayer, ntrials)
            boardObj.move(row, col, curplayer)            

        # Update state
        winner = boardObj.check_win()
        curplayer = switch_player(curplayer)

        # Display board
        print
        print boardObj
        print

    # Print winner
    if winner == PLAYERX:
        print "X wins!"
    elif winner == PLAYERO:
        print "O wins!"
    elif winner == DRAW:
        print "Tie!"
    else:
        print "Error: unknown winner"

    if str(raw_input('New game? (y/n)\n')) == 'y':
        play_vs_ai(mc_move_function, dimension, ntrials)


# Play a machine vs machine game
play_mc_game(move_wrapper, 1, False)

# Play a human vs machine game
#play_vs_ai(move_wrapper, 3, 1, False)