1. Consider the game of Tic-Tac-Toe (also called Noughts and Crosses), which is played by two players, an “X” player and an “O” player who alternate putting their symbol in a blank space on a 3 × 3 game-board. A player’s goal is to win by placing three symbols in a row, column, or diagonal; the game ends when a player wins or the board is filled. In the game shown below, player O has just made its third turn. It is Xâ s turn to make its fourth move. The playing agent needs to decide intelligently which of the available 3 moves X should choose next: X1, X2, or X3.

We have started the search tree, with three branches for the three possible moves for X:

Draw the rest of the game tree. Assume the value of the tree is +1 for an X win, −1 for an O win, and 0 for a draw. Show how the values are backed up to give a value for each of the nodes.

What should X do? Is it likely to win, lose or draw?

Could α-β pruning prune any of the tree?