CS410: Artificial Intelligence
Homework 3: Local Search & Adversarial Search & MDP
1. Local Search. The traveling salesman problem (TSP) is the problem of
finding the shortest route to visit a set of cities exactly once and return to
the starting city. Describe how to use genetic algorithm for TSP. Propose
a state representation, the corresponding crossover and mutation, and the
fitness function.
2. Game Tree. Prove that with a positive linear transformation of leaf
values (i.e., transforming a value x to ax + b where a > 0), the choice
of move remains unchanged in a game tree, even when there are chance
nodes.
Figure 1: Problem 3.
3. Alpha-Beta Pruning. Consider the above game tree.
(a) Compute the minimax value for each node using Minimax algorithm.
(b) Prune the game tree using Alpha-Beta pruning algorithm. Provide
the final alpha and beta values computed at the root, each internal
node visited, and at the top of pruned branches. Provide the pruned
branches. Assume child nodes are visited from left to right.
1
4. Racing Problem. Consider the racing problem in Page 17, Lecture 6.
Example: Racing
• A robot car wants to travel far, quickly
• Three states: Cool, Warm, Overheated
Cool
Warm
Overheated
Fast
Fast
Slow
Slow
0.5
0.5
0.5
0.5
1.0
1.0
+1
+1
+1
+2
+2
-10
Figure 2: Problem 4.
Assume there is a discount factor 0 < γ < 1 in the MDP of this problem.
Calculate V
∗
(s) for each state s and Q∗
(s, a) for each q-state (s, a) in this
problem.
5. Convergence of Policy Iteration. Prove the policy improvement method
can indeed improve policies and then prove the convergence of policy iteration.
2
