Q1. Consider the graph shown below:
Starting from state A, execute DFS. The goal node is G. Illustrate the order in which the nodes are expanded. Suppose that the alphabetically smaller node is expanded first to break ties.
Q2. Illustrate the meaning of Alpha-Beta pruning? On what factor the effectiveness of the Alpha-Beta procedure based on?
Q3. Consider the game of tic-tac-toe. Suppose that X is the MAX player. Let the utility of a win for X is 10, a loss for X is -10 and a draw is 0. Given the game board board1 below where it is X’s turn to play next, show the whole game tree. Mark the utilities of each terminal state and use the minimax algorithm to compute the optimal move.
