New version page

Berkeley COMPSCI 188 - Section 3 - CSPs Part 2 and Game Trees

Documents in this Course
CSP

CSP

42 pages

Metrics

Metrics

4 pages

HMMs II

HMMs II

19 pages

NLP

NLP

23 pages

Midterm

Midterm

9 pages

Agents

Agents

8 pages

Lecture 4

Lecture 4

53 pages

CSPs

CSPs

16 pages

Midterm

Midterm

6 pages

MDPs

MDPs

20 pages

mdps

mdps

2 pages

Games II

Games II

18 pages

Load more
Upgrade to remove ads

This preview shows page 1 out of 4 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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
Download Section 3 - CSPs Part 2 and Game Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Section 3 - CSPs Part 2 and Game Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Section 3 - CSPs Part 2 and Game Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?