Write a program in python that can play Tic-Tac-Toe effectively. (Section 5.6 of the textbook Goodrich)

1. First you will need to create a game tree T, which is a tree where each position corresponds to a game conguration, which is a representation of the Tic-Tac-Toe board. (Section 8.4.2 Goodrich)

2. The root corresponds to the initial conguration. For each internal position p in T, the children of p correspond to the game states we can reach from ps game state in a single legal move for the appropriate player, A (the rst player) or B (the second player). Positions at even depths correspond to moves for A and positions at odd depths correspond to moves for B. Leaves are either nal game states or are at a depth beyond which we do not want to explore.

3. Score each leaf with a value that indicates how good this state is for player A. In large games, like chess, we have to use a heuristic scoring function, but for small games, like Tic-Tac-Toe, The entire game tree can be constructed and score leaves as +1, 0, 1, indicating whether player A has a win, lose, draw in that conguration.

4. Use MiniMax. In this algorithm, we assign a score to each internal position p in T, such that if p represents As turn, we compute ps score as the maximum of the scores of ps children (which corresponds to As optimal play from p). If an internal node p represents Bs turn, then we compute ps score as the minimum of the scores of ps children (which corresponds to Bs optimal play from p).

in python code please not java code