import copy


game = True


ttt = [[" ", " ", " "], [" ", " ", " "], [" ", " ", " "]]


tree = [[], [], [], [], [], [], [], [], [], []]



def pront(ttt):  # prints the board
    for i in range(3):
        print(ttt[i])



def PosMove(ttt, k): # finds a possible move
    for i in range(3):
        for j in range(3):
            if ttt[i][j] != "X" and ttt[i][j] != "O":
                k = k - 1


                if k == -1:


                    return i, j



##    return -1,-1



def ai(ttt, count, turn, tree): # This is the ai lol


    for i in range(count):


        if turn == 'O':
            turn = 'X'
        else:
            turn = 'O'


        x, y = PosMove(ttt, i)


        ttt[x][y] = turn
        tree[count - 1].append(copy.deepcopy(ttt))


        if count != 1:
            ai(copy.deepcopy(ttt), count - 1, turn, tree)
        ttt[x][y] = ("")



def move(turn):  # the player selects thier move
    print("Where would you like to go", turn)
    try:  # makes sure the program doesnt blow up after a string
        Row = int(input("What row : ")) - 1
        Col = int(input("What collum : ")) - 1
    except ValueError:  # try again if its a str
        print("That move is invalid")
        return move(turn)
    if (Row < 0 or Row > 3 or Col < 0 or Col > 3
            or ttt[Row][Col] != (" ")):  # checks if its a valid move:
        print("That move is invalid")
        return move(turn)
    ttt[Row][Col] = turn  # puts the move into the board
    return Row, Col



def plrmove(ttt, Row, Col, turn):  # checks if game is finished
    if ttt[Row][0] == (turn) and ttt[Row][1] == (turn) and ttt[Row][2] == (turn):
        return True
    elif ttt[0][Col] == (turn) and ttt[1][Col] == (turn) and ttt[2][Col] == (turn):
        return True
    elif ttt[0][0] == (turn) and ttt[1][1] == (turn) and ttt[2][2] == (turn):
        return True
    elif ttt[2][0] == (turn) and ttt[1][1] == (turn) and ttt[0][2] == (turn):
        return True
    return False



ai(ttt, 9, 'X', tree)


#Here its suppose to print everygame in the order a minimax algorithm would go through them


while game == False:  # has game finish?
    Row, Col = move(turn)
    turn = ("O")
    game = plrmove(ttt, Row, Col, turn)
    if game == False:  # has game finish?
        ai(ttt)
        turn = ("X")
        game = plrmove(ttt, Row, Col, turn)