Consider the game of Noughts and Crosses. The game is played on a board consisting of nine squares arranged in a 3 x 3 matrix. We number those squares like this: 1 2 3 To play, two players, X and O, take turns to place a piece on the board. A new piece may only be placed on an empty square. The winner is the first player to achieve a line of 3 of their pieces, horizontally, vertically or diagonally. Thus, a winning board for X would be: o o Now consider a computer program that is to play X in the game, from the following position: |ox|x o The program always considers squares in the same order: 1, 2, 3, 4, 5, 6, 7, 8, 9 in the diagram above. Draw the game tree, as generated by a minimax procedure using alpha- beta pruning to optimise the number of states that are considered. Number your states to indicate the order in which they are expanded, using numbers in circles, like this: Do not number states which are added to the agenda but not expanded under minimax. Use the following utility function: Utility = number of lines of 3 with 2 Xs + 10 x number of lines of 3 with 3 Xs - number of lines of 3 with 2 Os - 10 x number of lines of 3 with 3 Os So the utility value for the starting state, above, is -1, as X has one horizontal row of 2 pieces, while o has one vertical and one diagonal row of 2 pieces each. Indicate next to each state what utility value is passed back up the tree in the minimax/alpha- beta pruning process. [25 marks)