Problem set 3

pdf

School

University of California, Davis *

*We aren’t endorsed by this school

Course

170

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by ConstableDiscoveryRedPanda31

Name: ID: 1. (8 points) The Alpha-Beta pruning technique is used to improve the runtime of the minimax algorithm. With a constant branching factor of b, and a search depth of d, answer the following questions about it’s performance: a. (2 point) What is the worst case runtime of minimax using Alpha-Beta pruning? b. (2 point) What is the best case runtime of minimax using Alpha-Beta pruning? c. (2 point) Under what conditions can we achieve the best case runtime? d. (2 point) Under what conditions will Alpha-Beta pruning not prune any branches at all?

2. (7 points) a. (5 points) Execute alpha-beta pruning on the example, write the minimax value at each node (including the nodes got pruned), and cross out the branches that get pruned by the algorithm. If a branch does get pruned, circle the nodes under that branch that you had to explore in order to decide to prune the branch. b. (2 points) How would you reorder the first moves that max makes in order to improve alpha-beta pruning? ( Hint: Reorder the subtrees of the root node )

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Related Documents

Review_CNNs_solution.pdf

HW3a.knit.pdf

FCS 240 Assignment 1 - Winter 24.docx

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Operations Research : Applications and Algorithms

Computer Science

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Brooks Cole

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

New Perspectives on HTML5, CSS3, and JavaScript

Computer Science

ISBN:9781305503922

Author:Patrick M. Carey

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:9781305503922
Author:Patrick M. Carey
Publisher:Cengage Learning