# Tic-Tac-Toe (in Python)
# Written by Brandon Corfman, 9/18/05
#
# Uses minimax algorithm discussed in chapter 6 of Russell and Norvig's
# Artificial Intelligence: A Modern Approach (2nd ed.) However, it
# includes a modification to favor a quicker win if available.

import random

MIN = 0
MAX = 1
PLAYER1 = 1
PLAYER2 = -1
CPU = -1
HUMAN = 1
INFINITY = 9999999

def main():
    global p1_sym, p2_sym
    display_instructions()
    sym1, sym2 = get_player_symbols()
    p1_type, p2_type, p1_sym, p2_sym = get_player_types(sym1, sym2)
    new_game = True
    while new_game:
        board = construct_board()
        while True:
            while True:
                move = get_move(PLAYER1, p1_type, p1_sym, board)
                if is_valid_move(move, board):
                    break
                print "Invalid move. Try again."
            make_move(move, p1_sym, board)
            if terminal_state(board):
                break
            while True:
                move = get_move(PLAYER2, p2_type, p2_sym, board)
                if is_valid_move(move, board):
                    break
                print "Invalid move. Try again."
            make_move(move, p2_sym, board)
            if terminal_state(board):
                break
        display_evaluation(utility(board, HUMAN)*p1_type, board)
        new_game = ask_about_new_game()

def construct_board():
    """ Builds an empty Tic-Tac-Toe board. """
    return [" " for x in range(0,9)]

def construct_positions():
    """ Builds a Tic-Tac-Toe board with numbers designating each square. """
    return [x for x in range(1,10)]

def display_board(board):
    """ Pretty prints the Tic-Tac-Toe board to the screen. """
    print
    print "   |   |   "
    print " %s | %s | %s " % (board[0], board[1], board[2])
    print "   |   |   "
    print "-----------"
    print "   |   |   "
    print " %s | %s | %s " % (board[3], board[4], board[5])
    print "   |   |   "
    print "-----------"
    print "   |   |   "
    print " %s | %s | %s " % (board[6], board[7], board[8])
    print "   |   |   "

def display_instructions():
    print "**** Welcome to Tic-Tac-Toe ****"
    print
    print "You will be playing against the computer."
    print "You make a move by typing a number 1-9 on"
    print "the keyboard. The numbers correspond to the"
    print "following positions:"
    print
    display_board(construct_positions())
    print

def get_player_symbols():
    """ Asks the human player whether they want to use X's or O's, and then
    returns both the human's and the CPU's symbols. """
    while True:
        symbol = raw_input("Do you want to play as X or O? ").upper().strip()
        if symbol == "X" or symbol == "O":
            break
    if symbol == "X":
        return "X", "O"
    else:
        return "O", "X"

def get_player_types(sym1, sym2):
    """ Asks the human player whether they want to go first, and then
    returns the values for those playing the 1st and 2nd players. """
    print
    while (True):
        answer = raw_input("Do you want to go first (Y/N)? ").upper()
        if len(answer) > 0 and (answer[0] == "Y" or answer[0] == "N"):
            break

    if answer[0] == "Y":
        return HUMAN, CPU, sym1, sym2
    else:
        return CPU, HUMAN, sym2, sym1

def get_move(player, type, sym, board):
    """ Gets a move from either the human or the CPU. """
    if type == HUMAN:
        display_board(board)
        return get_human_move(sym)
    elif type == CPU:
        return random.choice(get_cpu_moves(player, sym, board))

def get_human_move(sym):
    """ Asks a human player for their move and then returns it. """
    print
    while True:
        inp = raw_input("Place a '" + sym + "' at what position (1-9)? ").strip()
        if inp.isdigit():
            move = int(inp)
            if move >= 1 and move <= 9:
                return move-1

def get_cpu_moves(player, sym, board):
    """ Calculates moves by the computer using a variant of the minimax
    algorithm that calculates the strength of each remaining position
    on the board. """
    opponent_sym = (sym == "X" and "O" or "X")
    best_moves = []
    best_score = -INFINITY
    for move in range(9):
        if is_valid_move(move, board):
            score = minimax_value(try_move(move, player, sym, board),
                                  opponent_sym, player, MIN,
                                  -INFINITY, INFINITY)
            if score > best_score:
                best_score = score
                best_moves = [move]
            elif score == best_score:
                best_moves.append(move)
    return best_moves

def is_valid_move(move, board):
    """ Tests if a square is empty or not. """
    if board[move] == " ":
        return True
    return False

def try_move(move, type, sym, board):
    """ Creates a new board with a symbol in the designated square. """
    new_board = board[:]
    if new_board[move] == " ":
        new_board[move] = sym
    return new_board

def make_move(move, sym, board):
    """ Places a symbol in the designated square on the board. """
    if board[move] == " ":
        board[move] = sym

def terminal_state(board):
    """ Returns True if a game has ended, False otherwise. """
    global p1_sym, p2_sym
    # test for horizontal win
    for i in range(0, 9, 3):
        if (board[i+0] == board[i+1] == board[i+2] == p1_sym or
            board[i+0] == board[i+1] == board[i+2] == p2_sym):
            return True

    # test for vertical win
    for i in range(3):
        if (board[i+0] == board[i+3] == board[i+6] == p1_sym or
            board[i+0] == board[i+3] == board[i+6] == p2_sym):
            return True

    # test for a diagonal win
    if (board[0] == board[4] == board[8] == p1_sym or
        board[0] == board[4] == board[8] == p2_sym or
        board[2] == board[4] == board[6] == p1_sym or
        board[2] == board[4] == board[6] == p2_sym):
        return True

    # test for all squares being filled
    if count_filled_squares(board) == 9:
        return True

    return False

def count_filled_squares(board):
    """ Counts the number of squares on the board that have a
    X or an O in them. """
    filled_squares = [sq for sq in board if sq == "X" or sq == "O"]
    return len(filled_squares)

def utility(board, player):
    """ Returns a -1, 0 or +1 to indicate whether the game ended in
    a loss, draw or win. """
    global p1_sym, p2_sym
    for i in range(0, 9, 3):
        if board[i+0] == board[i+1] == board[i+2] == p1_sym:
            return 1*player
        if board[i+0] == board[i+1] == board[i+2] == p2_sym:
            return -1*player

    for i in range(3):
        if board[i+0] == board[i+3] == board[i+6] == p1_sym:
            return 1*player
        if board[i+0] == board[i+3] == board[i+6] == p2_sym:
            return -1*player

    if (board[0] == board[4] == board[8] == p1_sym or
        board[2] == board[4] == board[6] == p1_sym):
        return 1*player

    if (board[0] == board[4] == board[8] == p2_sym or
        board[2] == board[4] == board[6] == p2_sym):
        return -1*player

    return 0

def display_evaluation(utility, board):
    """ Prints a message indicating whether the game ended in a win, lose or
    draw, based on the utility number. """
    if utility == 1:
        print "\nYou won the game!\n"
    elif utility == -1:
        display_board(board)
        print "\nI won the game!\n"
    else:
        display_board(board)
        print "\nWe both tied.\n"

def minimax_value(board, sym, player, turn, alpha, beta):
    """ The standard AI game-playing algorithm with alpha-beta pruning.
    Returns a utility value indicating the optimal strategy for
    player MAX, thus deciding what the best first move is.
    (Artificial Intelligence: A Modern Approach, p. 124)"""
    global p1_sym, p2_sym

    new_sym = (sym == p2_sym and p1_sym or p2_sym)
    if terminal_state(board):
        filled_squares = count_filled_squares(board)
        return utility(board, player)*(10-filled_squares)
    else:
        moves = [try_move(move, player, sym, board) for move in range(9)
                 if is_valid_move(move, board)]
        if turn == MAX:
            for move in moves:
                alpha = max(alpha, minimax_value(move, new_sym, player,
                                                 1-turn, alpha, beta))
                if alpha >= beta:
                    return beta
            return alpha
        elif turn == MIN:
            for move in moves:
                beta = min(beta, minimax_value(move, new_sym, player,
                                               1-turn, alpha, beta))
                if beta <= alpha:
                    return alpha
            return beta

def ask_about_new_game():
    """ Asks the human player if they want to try the game again. """
    play_again = raw_input("Do you want to play again? ")
    if play_again != ' ' and play_again.lower() == 'y':
        return True
    return False

if __name__ == "__main__":
    main()