Description

Local Search and Game Playing
40 pts total
Genetic Algorithms [10 pts]
Recall that genetic algorithms represent a type of local search. Genetic algorithms have seen application in electronic chip design, a scheme known as evolvable hardware. (Read a tutorial here: http://folk.uio.no/jimtoer/ fpl04 Torresen.pdf.) Under this scheme, chip layouts can be represented as a series of bits that correspond to placement of the components (e.g., transistors) on this chip. Suppose we have a population of such chip arrangements, as shown in Table 1. Further suppose our parent selection chooses chips 4 and 6, chips 1 and 3, and then chips 5 and 6, respectively, for three mating events. Assume we know that crossover events happen after bits 2, 5, and 8 for the first, second, and third mating events, respectively.
Chip Number Bit String Representation
1 0100010011
2 1011000010
3 1101110010
4 0011110010
5 1000001101
6 0100110011
Table 1: Population of Chips Represented as Bit Strings
a) Follow the genetic algorithm as it’s laid out on the lecture slides. After the three mating events take place, what will the new population be? (Don’t worry about the fitness of the children.)
b) In addition to crossover events, mutations are often also used in genetic algorithms. What are mutation events? Why are they used?
c) Why are genetic algorithms less susceptible to local optima than a standard hillclimbing algorithm?
2
Simulated Annealing [15 pts]
Consider the function f(x) = max{4 − |x|,2 − |x − 6|,2 − |x + 6|}. It has three peaks with one forming a unique global maximum. Perform 8 rounds of simulated annealing using 4 as your start point, and where the temperature can be calculated from the function T(i) = 2(0.9)i, where i is the iteration number. (E.g., for the first iteration, the temperature will be T(1) = 2(0.9)1 = 1.8.) Show all of your work, including the current point, the round temperature, and the probability of changing position given the successor and the temperature.
Note: Recall that a random successor is generated on each iteration of the simulated annealing. If this successor is better than the current state, it is always accepted. If it is not better, it will still be accepted with some probability. Use Table 2 to see which successor was “randomly” chosen at each step, along with the “randomly” generated number which will help you to decide if you should take a non-optimal successor at that step.
Iteration Number Random Successor Random Number Generated
1 3 0.102
2 1 0.223
3 1 0.504
4 4 0.493
5 2 0.312
6 3 0.508
7 4 0.982
8 3 0.887
Table 2: Successor States and Random Numbers
3
Game Playing [15 pts]

Figure 1: Question 3 Graph
a) Refer to Figure 1. Use the Minimax algorithm to compute the minimax value at each node for the tree shown.
b) Refer once more to Figure 1. Use Alpha-Beta Pruning to compute the minimax value at each node for the game tree shown, assuming children are visited left to right. Show the alpha and beta values at each node. Show which branches are pruned, if any.
c) Why do we use Alpha-Beta Pruning?
4