# Tic Tac Toe
from myro import *
from random import choice

# game parameters
INFINITY = 100
LEVEL = 0
LEVEL = int(ask("Enter a level:"))

# pieces, default assignment
Me = 'O'
You = 'X'

def makeBoard():
    """Returns a fresh/empty board.
       Empty is represented by a ' '.
    """
    # a 3x3 board is represented as a list of 9 elements.
    # We will use the following numbering to locate a square
    #  0 | 1 | 2
    # ---|---|---
    #  3 | 4 | 5
    # ---|---|---
    #  6 | 7 | 8
    
    return [' ',' ',' ',' ',' ',' ',' ',' ',' ']

def display(board):
    """Displays the current board.
    """
    for i in range(0, 9, 3):
        if i > 0:
            print '---|---|---'
        print " %c | %c | %c " % (board[i],board[i+1],board[i+2])
    print
    
def opponent(player):
    """Returns the opponent piece from player. player-X -> O and vice versa.
    """
    if player == "X":
        return "O"
    else:
        return "X"

# These square triples represent wins (three in a row).
wins = [[0, 1, 2], [3, 4, 5], [6, 7, 8],    # the rows
        [0, 3, 6], [1, 4, 7], [2, 5, 8],    # the columns
        [0, 4, 8], [2, 4, 6]]               # diagonals

def winner(board):
    """Returns the winning piece on the board X/O/' '/'Tie'.
       X/O if either piece has won.
       ' ' means no winner yet.
       'Tie' means all squares are full and there was no winner.
    """
    for win in wins:
        posWinner = board[win[0]]
        if (posWinner != ' ' and
            posWinner == board[win[1]] and
            posWinner == board[win[2]]):
            return posWinner
    # No winner yet, are there empty squares left?
    for i in range(9):
        if board[i] == ' ':
            return ' '
    # The board is full and no one has three in a row
    return 'Tie'

#----
def openings(board, player):
    """Return the number of possible winning positions for player on board.
    """
    possWins = 0
    for position in wins:
        n = 0
        for i in range(3):
            if (board[position[i]] == player) or (board[position[i]] == ' '):
                n += 1
        if n == 3:
            possWins += 1
    return possWins

def evaluate(board):
    """Evaluates the board with respect to the player's perspective.
       Returns a number.
    """
    # if board is a win for player, return INFINITY
    piece = winner(board)
    if piece == Me:
        return INFINITY
    elif piece == You:
        return -INFINITY
    else:
        return openings(board,Me) - openings(board,You)

def bestMove(board, player, moves):
    """Returns the best move of all possible moves.
       The evaluate function returns a score for the player if each move
       were made.
    """
    scores = []
    for m in moves:
        b = copy(board)
        b[m] = player
        scores.append(lookahead(b, opponent(player), 0, LEVEL-1))
        
    return moves[scores.index(max(scores))]

def lookahead(board, player, MAX, level):
    """Do a lookahead search on the board and return the backed up value.
    """
    moves = possibleMoves(board)
    if level == 0 or len(moves)==0:
        return evaluate(board)
    if MAX:

        V = -INFINITY
        for m in moves:
            b = copy(board)
            b[m] = player
            V = max(V, lookahead(b, opponent(player), 1-MAX, level-1))
    else:
        V = INFINITY
        for m in moves:
            b = copy(board)
            b[m] = player
            V = min(V, lookahead(b, opponent(player), 1-MAX, level-1))
    return V

def possibleMoves(board):
    """returns the set of possible moves in the game.
       In this game, all empty squares are viable.
    """
    return [i for i in range(9) if board[i] == ' ']

def move(board, player, user):
    """Make a move for player.
    """
    
    if player == user:      # user's move?
        square = input("Enter your move: ") - 1
    else:                   # my turn
        # player is the computer, make a random choice
        square = bestMove(board, player, possibleMoves(board))
        #square = choice(possibleMoves(board))

    # place player's piece on the chosen square
    board[square] = player

def gameOver(board):
    """Returns True if game is over (someone won or it is a tie)
        False o/w.
    """
    return winner(board) != ' '

def play():

    # Initialize board
    board = makeBoard()

    # Select pieces (X or O) and who goes first
    if askQuestion("Do you want to move first?") == "Yes":
        You = 'X'
    else:
        You = 'O'

    # In Tic Tac Toe, X always goes first
    player = 'X'

    Me = opponent(You)
        
    display(board)
    
    # The game loop
    while not gameOver(board):
        move(board, player, You)
        print "After %s's move..." % player
        display(board)
        player = opponent(player)

    # game over, show outcome
    winningPiece = winner(board)
    if winningPiece != 'Tie':
        print winningPiece, "won."
    else:
        print "It is a tie."