sds

tic_tac_toe

# '-' for empty position
# 'O' for marking O is there
# 'X' for marking X has made a turn there
board = "---------"

# Assuming I already have a dictionary `board_states` for lookup

def nextMove(curr_move):
    board[curr_move] = 'X'
    # simply lookup the value of next move from the dictionary
    index = board_states[board]
    board[index] = 'O'
    return index

# Optimal strategy
# To reduce the number of states to be stores in the dict, one way is to remove the duplicates.
# Initially let's say we have stores only the unique board states.
# Now for lookup, we will check for 4 possible rotations of the current board state and check whichever state is available in the dict and return the corresponding next move.