CS188 Fall 2011 Section 3: CSPs Part 2 and Game Trees1 TrainsA train scheduler must decide when trains A, B and C should depart. Once a train departs, it moves one spacealong its track each hour (in discrete jumps) until it arrives at its destination platform. Each train can depart at 1, 2or 3 pm. The scheduler has two restrictions: All trains must leave at different times, and two trains should not bothoccupy crossing sections of track after any one hour time step is over. Note that train A is two spaces long. Alsonote that the collision constraint is enforced only at the conclusion of every hour - time is discrete in this problem.(a) Describe the constraint satisfaction problem that, when solved, will tell the train scheduler when each trainshould depart. Let the variables A, B and C represent the departure times of the three trains.(b) Draw the constraint graph for the CSP you defined.(c) After selecting A = 2, cross out all values for B and C eliminated by forward checking.A B C2 1 2 3 1 2 31(d) Cross out all values eliminated by arc consistency before assigning any variables.A B C1 2 3 1 2 3 1 2 3(e) After selecting A = 2, cross out all values for B and C eliminated by arc consistency.A B C2 1 2 3 1 2 3(f) Describe the execution of backtracking search using forward checking and the minimum remaining values (MRV)and least constraining values (LCV) heuristics. Specifically, in what order are the variables assigned and what valuesdo they take? Start by assigning variable A. You may not need to fill all the lines below:(1) variable A is assigned value .(2) variable is assigned value .(3) variable is assigned value .(4) variable is assigned value .(5) variable is assigned value .(6) variable is assigned value .22 Minimax SearchIn this problem, we will explore adversarial search.Consider the zero-sum game tree shown below. Trapezoids that point up, such as at the root, represent choices forthe player seeking to maximize; trapezoids that point down represent choices for the minimizer. Outcome values forthe maximizing player are listed for each leaf node. It is your move, and you seek to maximize the expected value ofthe game.(a) Assuming both opponents act optimally, carry out the minimax search algorithm. Write the value of each nodeinside the corresponding trapzoid. What move should you make now? How much is the game worth to you?(b) Now reconsider the same game tree, but use α-β pruning (the tree is printed on the next page). Expand successorsfrom left to right. In the brackets [ , ], record the [α, β] pair that is passed down that edge (through a call to MIN-VALUE or MAX-VALUE). In the parentheses ( ), record the value (v) that is passed up the edge (the value returnedby MIN-VALUE or MAX-VALUE). Circle all leaf nodes that are visited. Put an ‘X’ through edges thatare pruned off. How much is the game worth according to α-β
View Full Document
Unlocking...