**PLEASE NEED HELP ASAP WITH 2 PROBLEMS** - SIMPLE (WRITTEN/TYPED FORMAT)
C. As described in section 2.2, the recursive method essentially creates the game tree node by node in a depth-first fashion. For the case where there are two packets for each player (so the game is on a 4x4 board), how many nodes are in the entire game tree?
D. Assuming you could see the entire tree, how would you determine whether it is possible for the first player to win?
2.2 Game Trees Consider the following simple two-player game played on an n x n square grid with a border of squares; let's call the players Horace Fahlberg-Remsen and Vera Rebaudi.? Each player has n tokens that they move across the board from one side to the other. Horace's tokens start in the left border, one in each row, and move horizontally to the right; symmetrically, Vera's tokens start in the top border, one in each column, and move vertically downward. The players alternate turns. In each of his turns, Horace either moves one of his tokens one step to the right into an empty square, or jumps one of his tokens over exactly one of Vera's tokens into an empty square two steps to the right. If no legal moves or jumps are available, Horace simply passes. Similarly, Vera either moves or jumps one of her tokens downward in each of her turns, unless no moves or jumps are possible. The first player to move all their tokens off the edge of the board wins. (It's not hard to prove that as long as there are tokens on the board, at least one player can legally move, and therefore someone eventually wins.) oo D DI DI TODI DI M D TUD Figure 2.4. Vera wins the 3 x 3 fake-sugar-packet game. 'I don't know what this game is called, or even if I'm reporting the rules correctly; I learned it (or something like it) from Lenny Pitt, who recommended playing it with fake-sugar packets at 'I don't know what this game is called, or even if I'm reporting the rules correctly; I learned it (or something like it) from Lenny Pitt, who recommended playing it with fake-sugar packets at restaurants. 2 Constantin Fahlberg and Ira Remsen synthesized saccharin for the first time in 1878, while Fahlberg was a postdoc in Remsen's lab investigating coal tar derivatives. In 1900, Ovidio Rebaudi published the first chemical analysis of ka'a he', a medicinal plant cultivated by the Guaran for more than 1500 years, now more commonly known as Stevia rebaudiana. 74 2.2. Game Trees Unless you've seen this game before3, you probably don't have any idea how to play it well. Nevertheless, there is a relatively simple backtracking algorithm that can play this gameor any two-player game without randomness or hidden information that ends after a finite number of movesperfectly. That is, if we drop you into the middle of a game, and it is possible to win against another perfect player, the algorithm will tell you how to win. A state of the game consists of the locations of all the pieces and the identity of the current player. These states can be connected into a game tree, which has an edge from state x to state y if and only if the current player in state x can legally move to state y. The root of the game tree is the initial position of the game, and every path from the root to a leaf is a complete game. VO TTTTTTTIT TIT Figure 2.5. The first two levels of the fake-sugar-packet game tree. To navigate through this game tree, we recursively define a game state to be good or bad as follows: A game state is good if either the current player has already won, or if the current player can move to a bad state for the opposing player. A game state is bad if either the current player has already lost, or if every available move leads to a good state for the opposing player. Equivalently, a non-leaf node in the game tree is good if it has at least one bad child, and a non-leaf node is bad if all its children are good. By induction, any player that finds the game in a good state on their turn can win the game, even if their opponent plays perfectly; on the other hand, starting from a bad state, a player can win only if their opponent makes a mistake. This recursive definition was proposed by Ernst Zermelo in 1913.4 3If you have, please tell me where! In fact, Zermelo considered the more subtle class of games that have a finite number of states, but that allow infinite sequences of moves. (Zermelo defined infinite play to be a draw.) 75 2. BACKTRACKING This recursive definition immediately suggests the following recursive back- tracking algorithm to determine whether a given game state is good or bad. At its core, this algorithm is just a depth-first search of the game tree; equivalently, the game tree is the recursion tree of the algorithm! A simple modification of this backtracking algorithm finds a good move (or even all possible good moves) if the input is a good game state. PLAYANYGAME(X, player): if player has already won in state X return GOOD if player has already lost in state X return BAD for all legal moves X my Y if PLAYANYGAME(Y, player) = BAD return GOOD ((X my Y is a good move) return BAD ((There are no good moves) All game-playing programs are ultimately based on this simple backtracking strategy. However, since most games have an enormous number of states, it is not possible to traverse the entire game tree in practice. Instead, game programs employ other heuristics to prune the game tree, by ignoring states that are obviously (or obviously') good or bad, or at least better or worse than other states, and/or by cutting off the tree at a certain depth (or ply) and using a more efficient heuristic to evaluate the leaves. 2.2 Game Trees Consider the following simple two-player game played on an n x n square grid with a border of squares; let's call the players Horace Fahlberg-Remsen and Vera Rebaudi.? Each player has n tokens that they move across the board from one side to the other. Horace's tokens start in the left border, one in each row, and move horizontally to the right; symmetrically, Vera's tokens start in the top border, one in each column, and move vertically downward. The players alternate turns. In each of his turns, Horace either moves one of his tokens one step to the right into an empty square, or jumps one of his tokens over exactly one of Vera's tokens into an empty square two steps to the right. If no legal moves or jumps are available, Horace simply passes. Similarly, Vera either moves or jumps one of her tokens downward in each of her turns, unless no moves or jumps are possible. The first player to move all their tokens off the edge of the board wins. (It's not hard to prove that as long as there are tokens on the board, at least one player can legally move, and therefore someone eventually wins.) oo D DI DI TODI DI M D TUD Figure 2.4. Vera wins the 3 x 3 fake-sugar-packet game. 'I don't know what this game is called, or even if I'm reporting the rules correctly; I learned it (or something like it) from Lenny Pitt, who recommended playing it with fake-sugar packets at 'I don't know what this game is called, or even if I'm reporting the rules correctly; I learned it (or something like it) from Lenny Pitt, who recommended playing it with fake-sugar packets at restaurants. 2 Constantin Fahlberg and Ira Remsen synthesized saccharin for the first time in 1878, while Fahlberg was a postdoc in Remsen's lab investigating coal tar derivatives. In 1900, Ovidio Rebaudi published the first chemical analysis of ka'a he', a medicinal plant cultivated by the Guaran for more than 1500 years, now more commonly known as Stevia rebaudiana. 74 2.2. Game Trees Unless you've seen this game before3, you probably don't have any idea how to play it well. Nevertheless, there is a relatively simple backtracking algorithm that can play this gameor any two-player game without randomness or hidden information that ends after a finite number of movesperfectly. That is, if we drop you into the middle of a game, and it is possible to win against another perfect player, the algorithm will tell you how to win. A state of the game consists of the locations of all the pieces and the identity of the current player. These states can be connected into a game tree, which has an edge from state x to state y if and only if the current player in state x can legally move to state y. The root of the game tree is the initial position of the game, and every path from the root to a leaf is a complete game. VO TTTTTTTIT TIT Figure 2.5. The first two levels of the fake-sugar-packet game tree. To navigate through this game tree, we recursively define a game state to be good or bad as follows: A game state is good if either the current player has already won, or if the current player can move to a bad state for the opposing player. A game state is bad if either the current player has already lost, or if every available move leads to a good state for the opposing player. Equivalently, a non-leaf node in the game tree is good if it has at least one bad child, and a non-leaf node is bad if all its children are good. By induction, any player that finds the game in a good state on their turn can win the game, even if their opponent plays perfectly; on the other hand, starting from a bad state, a player can win only if their opponent makes a mistake. This recursive definition was proposed by Ernst Zermelo in 1913.4 3If you have, please tell me where! In fact, Zermelo considered the more subtle class of games that have a finite number of states, but that allow infinite sequences of moves. (Zermelo defined infinite play to be a draw.) 75 2. BACKTRACKING This recursive definition immediately suggests the following recursive back- tracking algorithm to determine whether a given game state is good or bad. At its core, this algorithm is just a depth-first search of the game tree; equivalently, the game tree is the recursion tree of the algorithm! A simple modification of this backtracking algorithm finds a good move (or even all possible good moves) if the input is a good game state. PLAYANYGAME(X, player): if player has already won in state X return GOOD if player has already lost in state X return BAD for all legal moves X my Y if PLAYANYGAME(Y, player) = BAD return GOOD ((X my Y is a good move) return BAD ((There are no good moves) All game-playing programs are ultimately based on this simple backtracking strategy. However, since most games have an enormous number of states, it is not possible to traverse the entire game tree in practice. Instead, game programs employ other heuristics to prune the game tree, by ignoring states that are obviously (or obviously') good or bad, or at least better or worse than other states, and/or by cutting off the tree at a certain depth (or ply) and using a more efficient heuristic to evaluate the leaves
