Consider the following two-player game (players A and B): A B 1 2 3 4 The...

Transcribed Image Text:

Consider the following two-player game (players A and B): A B 1 2 3 4 The starting position of the simple game is shown on the right: 1 2 3 4 Player A moves first. The two players take turns moving, and each player must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, then a player may jump over the opponent to the next open space if any. (For example, if A is on 3 and B is on 2, then A may move back to 1 or forward to 4.) The game ends when one player reaches the opposite end of the board. If player A reaches space 4 first, then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game to A is -1. (a) Draw the complete game tree using the following conventions: (4 Marks) Annotate each terminal state with its game value in a circle. ⚫ Treat loop states as terminal states. Since it is not clear how to assign values to loop states, annotate each with a question mark in a circle. Loop states are states that already appear on their path to the root at a level in which it is the same player's turn to move. (b) Now mark each node with its backed-up minimax value (also in a circle). Explain how you handled the question mark values and why. (2 Marks) (c) This 4-square game can be generalized to n squares for any Give a formal proof that A wins (A has a winning strategy) if n is even and loses (B has a winning strategy) if n is odd. (4 Marks) n>2. Consider the following two-player game (players A and B): A B 1 2 3 4 The starting position of the simple game is shown on the right: 1 2 3 4 Player A moves first. The two players take turns moving, and each player must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, then a player may jump over the opponent to the next open space if any. (For example, if A is on 3 and B is on 2, then A may move back to 1 or forward to 4.) The game ends when one player reaches the opposite end of the board. If player A reaches space 4 first, then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game to A is -1. (a) Draw the complete game tree using the following conventions: (4 Marks) Annotate each terminal state with its game value in a circle. ⚫ Treat loop states as terminal states. Since it is not clear how to assign values to loop states, annotate each with a question mark in a circle. Loop states are states that already appear on their path to the root at a level in which it is the same player's turn to move. (b) Now mark each node with its backed-up minimax value (also in a circle). Explain how you handled the question mark values and why. (2 Marks) (c) This 4-square game can be generalized to n squares for any Give a formal proof that A wins (A has a winning strategy) if n is even and loses (B has a winning strategy) if n is odd. (4 Marks) n>2.

Answer rating: 100% (QA)

a Heres the complete game tree for the 4square game A 1 2 3 4 B A B A 2 3 1 4 2 A B A B A B 3 2 4 1 ... View the full answer