算法代写 | Assignment 2: Search algorithms

本次美国代写主要为算法相关的assignment

1 Questions

Problem 1: Give the values calculated by the minmax algorithm for all states in the tree shown in
Fig. 1 without using alpha-beta pruning. Mark which level corresponds to each player as well as
the selected values.

Problem 2: Give the values calculated by the minmax algorithm for all states in the tree using
alpha-beta pruning. Mark which level corresponds to each player, the selected values and the
pruned branches.

Problem 3: Answer the following questions related to hill climbing and simulated annealing:

1. Which are the problems where hill climbing works better than simulated annealing?

2. Which are the problems where hill climbing with randomly guessing the state works as
well than simulated annealing?

3. Which are the problems where hill climbing with randomly guessing the state works as
well than simulated annealing?

4. For which problems simulated annealing is going to work better?

Figure 2: The start position of a simple game. 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, than 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.) 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.

Problem 4: Consider the two-player game described in Figure 2.

1. Draw the complete game tree, using the following conventions:
• Write each state as (sA, sB) where sA and sB denote the token locations.
• Put each terminal state in a square box and write its game value in a circle.
• Put loop states (states that already appear on the path to the root) in double square
boxes. Since it is not clear how to assign values to loop states, annotate each with a
“?” in a circle.

2. Now mark each node with its backed-up minimax value (also in circle). Explain how you
handled the “?” values and why.

3. Explain why the standard minimax algorithm would fail on this game tree and briefly
sketch how you might fix it, drawing on your previous answer. Does your modified algo-
rithm give optimal decisions for all games with loops?

4. This 4-square game can be generalized to n squares for any n > 2. Prove that A wins if n is
even and loses if n is odd.