Question 2 (30 points): Uninformed Search: Peg Solitaire Figure 2. A sample Peg Solitaire board at the start of the game Peg Solitaire is a board game for one player involving movement of pegs on a board with holes. The standard game fills the entire board with pegs except for the central hole. The objective is to empty the entire board except for a solitary peg in the central hole, by making valid moves. A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg. From the Wikipedia entry: "Peg Solitaire" 9 h i B a D E F G H I J K L M Figure 3. Peg Solitaire Board 2.1. [12 points) Represent peg solitaire as a search problem. (You may use the labels provided in Figure 3 for referring to spaces on the board if you wish). (a) 14 points) How would you represent a node/state? (b) [2 points) In your representation, what is the goal node? (c) 13 points How would you represent the arcs? (d) [3 points) How many possible board states are there? Note: this is not the same as the number of "valid" or "reachable" game states, which is a much more challenging problem. 2.2. 19 points. The search tree: (a) [6 points) Write out the first three levels (counting the root as level 1) of the search tree. (Only label the arcs; labeling the nodes would be too much work). (b) [3 points] What can you say about the length of the solution(s)? 2.3. 19 points) The search algorithm: (a) [3 points) What kind of search algorithm would you use for this problem? Justify your answer. (b) [3 points) Would you use cycle-checking? Justify your answer. (c) [3 points] Would you use multiple-path-pruning? Justify your answer. Question 2 (30 points): Uninformed Search: Peg Solitaire Figure 2. A sample Peg Solitaire board at the start of the game Peg Solitaire is a board game for one player involving movement of pegs on a board with holes. The standard game fills the entire board with pegs except for the central hole. The objective is to empty the entire board except for a solitary peg in the central hole, by making valid moves. A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg. From the Wikipedia entry: "Peg Solitaire" 9 h i B a D E F G H I J K L M Figure 3. Peg Solitaire Board 2.1. [12 points) Represent peg solitaire as a search problem. (You may use the labels provided in Figure 3 for referring to spaces on the board if you wish). (a) 14 points) How would you represent a node/state? (b) [2 points) In your representation, what is the goal node? (c) 13 points How would you represent the arcs? (d) [3 points) How many possible board states are there? Note: this is not the same as the number of "valid" or "reachable" game states, which is a much more challenging problem. 2.2. 19 points. The search tree: (a) [6 points) Write out the first three levels (counting the root as level 1) of the search tree. (Only label the arcs; labeling the nodes would be too much work). (b) [3 points] What can you say about the length of the solution(s)? 2.3. 19 points) The search algorithm: (a) [3 points) What kind of search algorithm would you use for this problem? Justify your answer. (b) [3 points) Would you use cycle-checking? Justify your answer. (c) [3 points] Would you use multiple-path-pruning? Justify your