'''
Simple tic-tac-toe game built using minimax algorithm. AI recursively traverses game tree branches
by alternating between minimum and maximum score values until it finds the optimal move for
the given scenario.
'''

board = [[0, 0, 0],
         [0, 0, 0],
         [0, 0, 0]]

HUMAN = 1
COMPUTER = -1

def evaluate(currentBoard):
    # returns score based on currentBoard
    if checkGameOver(currentBoard, COMPUTER):
        score = +10
    elif checkGameOver(currentBoard, HUMAN):
        score = -10
    else:
        score = 0
    return score


def validMove(x, y):
    if [x, y] in getEmptySpots(board):
        return True
    else:
        return False


def checkGameOver(currentBoard, player):
    # winning combinations
    winState = [
        [currentBoard[0][0], currentBoard[0][1], currentBoard[0][2]],
        [currentBoard[1][0], currentBoard[1][1], currentBoard[1][2]],
        [currentBoard[2][0], currentBoard[2][1], currentBoard[2][2]],
        [currentBoard[0][0], currentBoard[1][0], currentBoard[2][0]],
        [currentBoard[0][1], currentBoard[1][1], currentBoard[2][1]],
        [currentBoard[0][2], currentBoard[1][2], currentBoard[2][2]],
        [currentBoard[0][0], currentBoard[1][1], currentBoard[2][2]],
        [currentBoard[2][0], currentBoard[1][1], currentBoard[0][2]],]
    # check if player has 3 in a row in currentBoard
    if [player, player, player] in winState:
        return True
    else:
        return False


def isGameOver(currentBoard):
    # returns True if someone won
    return checkGameOver(currentBoard, HUMAN) or checkGameOver(currentBoard, COMPUTER)


def getEmptySpots(currentBoard):
    # return available spots to move
    emptyCells = []
    for x, row in enumerate(currentBoard):
        for y, cell in enumerate(row):
            if cell == 0:
                emptyCells.append([x, y])
                print([x, y])
    print('\n')
    print(len(emptyCells)-1)
    return emptyCells


def minimax(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score
    for cell in getEmptySpots(currentBoard):
        x = cell[0]
        y = cell[1]
        currentBoard[x][y] = player
        bestScore = -1000000
        score = minPlay(currentBoard, -player)
        currentBoard[x][y] = 0
        if score > bestScore:
            bestScore = score
            bestMove = cell
            print('Best move:')
            print(bestMove)
            print('\n')
        return bestMove


def minPlay(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score
    for cell in getEmptySpots(currentBoard):
        x = cell[0]
        y = cell[1]
        currentBoard[x][y] = player
        bestScore = 1000000
        score = maxPlay(currentBoard, -player)
        currentBoard[x][y] = 0
        if score < bestScore:
            bestScore = score
        return bestScore


def maxPlay(currentBoard, player):
    if isGameOver(currentBoard):
        score = evaluate(currentBoard)
        return score
    for cell in getEmptySpots(currentBoard):
        x = cell[0]
        y = cell[1]
        currentBoard[x][y] = player
        bestScore = -1000000
        score = minPlay(currentBoard, -player)
        currentBoard[x][y] = 0
        if score > bestScore:
            bestScore = score
        return bestScore


def setMove(x, y, player):
    board[x][y] = player


def printGame(gameState):
    print('|' + str(gameState[0][0]) + '|' + str(gameState[0][1]) + '|' + str(gameState[0][2]))
    print('------')
    print('|' + str(gameState[1][0]) + '|' + str(gameState[1][1]) + '|' + str(gameState[1][2]))
    print('------')
    print('|' + str(gameState[2][0]) + '|' + str(gameState[2][1]) + '|' + str(gameState[2][2]))


def aiMove():
    move = minimax(board, COMPUTER)
    x = move[0]
    y = move[1]
    setMove(x, y, COMPUTER)


def main():
    moves = {
        1: [0, 0], 2: [0, 1], 3: [0, 2],
        4: [1, 0], 5: [1, 1], 6: [1, 2],
        7: [2, 0], 8: [2, 1], 9: [2, 2],}
    choice = input('Would you like to go first? [y/n]\n')
    if choice == 'n':
        aiMove()
    while not isGameOver(board):
        printGame(board)
        move = int(input('Input coordinate as number from 1-9\n'))
        coordinate = moves[move]
        setMove(coordinate[0], coordinate[1], HUMAN)
        aiMove()


if __name__ == '__main__':
    main()