TicTacToe game in Python
Divide Logic and User Intereaction

Why should a function to decide if a move is valid print to the screen? What if you want to change the message? Will you look inside a logic function to change a user-interface message?

I like to keep as many as possible of my functions "pure" so that they only make a calculation and return a result and build a thin interaction skin over it.

Long story short, is_move_valid should not print anything.

Simplification

As far as simplification is concerned, you can just flatten the board, and the function becomes:

def is_move_valid(move):
    return flatten(board)[move] not in ("X", "O")