#Jay Summet
# CS 1301
# Released to the public domain, Nov 2008
#

#Data structure that represents the current gameboard.
board = [ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ]

#A list of possible winning positions (rows, columns, diagonals)
possWins = [ [0,1,2], [0,4,8], [0,3,6], [1,4,7] , [2,5,8],
    [3,4,5], [ 6,7,8], [2,4,6] ]

#Returns the index (integer position) of all "empty" spaces on the
# board (i.e. possible moves)
def possMoves(board):

    moves = []

    for pos in range(0, len(board) ):
        if (board[pos] == " "):
            moves.append(pos)

    return(moves)


#returns X if X has won, O if O has won, " " if nobody has
# won, or T if a tie has occured
def checkWin(board):
    global possWins

    for pw in possWins:
        Letter = board[ pw[0] ]
        if (Letter != ' '):
            win = True
            for i in range(1, len(pw)):
                if (Letter != board[ pw[i]]):
                    win = False

            if win:
                return Letter
    movesLeft = possMoves(board)
    if len(movesLeft) == 0:
        return 'T'

    return ' '


        


#Prints out a 3x3 board.
def printBoard3(board):
    print board[0], "|", board[1], "|", board[2]
    print "--------"
    print board[3], "|", board[4], "|", board[5]
    print "--------"
    print board[6], "|", board[7], "|", board[8]



#Utility function / helper function to find the other player.
def opponent(player):
    if (player == "X"):
        return( "O")
    else:
        return("X")


#This function will count the number of wins for X,O and Tie
#that are possible from a given board (with player being the next player
#to move.  (Not used by the actual TTT playing program, but demonstrates
#similar concepts in a simpler manner.)
def countWins(board,player):
    xWin = 0
    oWin = 0
    ties = 0

    nextPlayer = opponent(player)
    
    moves = possMoves(board)

    for move in moves:

        newBoard = board[:]

        newBoard[move] = player

        win = checkWin(newBoard)
        if (win == "T"):
            ties = ties+1
        elif ( win == "X"):
            xWin = xWin + 1
        elif ( win == "O"):
            oWin = oWin + 1
        elif (win == " "):
            #Do the next move!
            result = countWins(newBoard, nextPlayer)
            xWin = xWin + result[0]
            oWin = oWin + result[1]
            ties = ties + result[2]

    #printBoard3(board)
    #print [ xWin, oWin, ties]
    #print "\n"

    return(   [ xWin, oWin, ties] )
        
        

#Gets a move from the user, with appropriate error checking.
def getUserMove(board):

    userMoveGood = False

    while(not userMoveGood):
        #Print the current board
        print "Current board:"
        printBoard3(board)

        #make a board showing only valid moves and show it
        #to the user
        cb = board[:]
        i = 0
        while( i < len(cb)):
            if (cb[i] == ' '):
                cb[i] = i
            else:
                cb[i] = "-"
            i = i + 1

        print ""
        printBoard3(cb)


        #Get user input
        userMove = raw_input("Enter number for your move:")

        #Validate user input. Repeat until valid:        
        try:
            um = int(userMove)
            
            if (um in possMoves(board)):
                #User move is valid! Make the move and signal the
                #while loop to stop by toggling the boolean!
                print "Good move!"
                board[um] = "X"
                userMoveGood = True
            else:
                print "Sorry, that's not a valid move!"
                print "Try again!"
        except:
            print "Not a valid number, try again!"



#This funciton returns a score, predicting how likley it
#is that the computer will win. (Based upon the fact that
#the player is trying to minimize the computers score!)

#TODO: This function MUST try all possible moves to return a score.
#it can NOT return a score after only looking ahead a few moves.
#How would you improve the function so that it could be limited to only
#look ahead a specified number of levels and give a "best guess" score?
            
def lookAhead(board, player):

    #Terminating condition.
    result = checkWin(board)

    #If the game is won/lost or tied, we don't look any farther!
    if(result == "X"):
        return(-100)
    if(result == "O"):
        return(100)
    if(result == "T"):
        return(0)


    #Recursive part. We have at least one move left to play
    #Find the possible moves
    pm = possMoves(board)
    
    otherPlayer = opponent(player)
    

    #If we are the next player, maximize our score!
    if (player == "O"):
        score = -100    #Start low, try to get higher....

        for move in pm:
            cb = board[:]
            cb[move] = "O"
            score = max( score, lookAhead(cb,otherPlayer))
    else:
        #Player is human,  minimize (the computers) score!
        score = 100   #Start high, try to go low

        for move in pm:
            cb = board[:]
            cb[move] = "X"
            score = min( score, lookAhead(cb,otherPlayer))

    #Now that we have calculated the best (or worst) score possible
    #for this board, return it. Note that we do not tell which series of
    #moves results in this score, as we assume the computer will always
    #choose the best move based upon the score.
    return(score)


#This function will try all possible remaining moves and use the lookAhead
#function to get a score for each possible moves. It then actually does the
#move that results in the highest score.
#NOTE: Because Perfect TicTacToe will always result in a Tie, most moves will
#score a zero (tie) or -100 (loss) unless the human makes a mistake. When the
#human makes a mistake, one of our moves will score a 100, and we win!

#TODO: This function always makes the FIRST valid move that has the lowest
# score, even if multiple moves have the same highest score. Modify the function
# so that it picks randomly between all possible "best moves".
def makeComputerMove(board):

    pm = possMoves(board)

    ourMove = 0
    bestScore = -100000

    for move in pm:
        cb = board[:]
        cb[move] = 'O'
        tryScore = lookAhead(cb, "X")
        print "score for move:",move," is:", tryScore
        
        if( tryScore > bestScore):
            ourMove = move
            bestScore = tryScore


    #Now that we've found the best score, make that move!
    #Computer is always "O" and goes second.
    board[ourMove] = "O"
    

        


#The actual code to play the game!



done = False

while(not done):
    getUserMove(board)
    result = checkWin(board)
    if(result == "T"):
        print "it's a tie!"
        done = True
    elif(result == "X"):
        print "You won!"
        done = True
    else:
        makeComputerMove(board)
        result = checkWin(board)
        if(result == "O"):
            printBoard3(board)
            print "Computer beat you!"
            done = True
        elif(result == "T"):
            printBoard3(board)
            print "It's a Tie!"
            done = True