Artificial Intelligence- TicTacToe game

Tic-Tac-Toe game using MINIMAX algorithm

1. ARTIFICIAL INTELLIGENCE TIC-TAC-TOE Game Name : Manika kumari Roll no . : MT/CS/10006/18 Guided by : Dr.Sanchita Paul

2. Introduction TIC-TAC-TOE Game Two player game – X and O X and O, who take turns mark the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game .

3. Initial State Initially all 1 to 9 places of 3x3 grid are empty 1 4 5 3 6 7 8 9 2

4. Goal State PLAYER X WIN 3 X’s in a column , row or diagonal PLAYER O WIN 3 O’s in a column , row or diagonal DRAW X O O X X O X O O O X X X X O O X O X O

5. Winning Conditions X X X X X X X X X X X X X X X X X X X X X X X X

6. State Space Tree 9 possibilities X X X X X X X X O O O O 8 possibilities X O X O X O X O X O X X X X X

7. MINIMAX Approach Minimax is a recursive algorithm which is used to choose an optimal move for a player assuming that the other player is also playing optimally. Initial state : Initial position of the board/grid . Successor function : I defines what the legal moves from any position Terminal state : I position of the board when the game gets over. Utility function : I function which assigns a numeric value for the outcome of a game . For instance, in tic-tac-toe, the outcome is either a win, a loss, or a draw, and these can be represented by the values +1, -1, or 0, respectively .

8. A Minimax algorithm can be best defined as a recursive function that does the following things: return a value if a terminal state is found (+1, 0, -1) go through available spots on the board call the minimax function on each available spot (recursion) evaluate returning values from function calls and return the best value

9. Python Implementation of TIC-TAC-TOE