EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Alpha Beta Pruning

By A. SathyanarayananA. Sathyanarayanan

Home » Software Development » Software Development Tutorials » Software Testing Tutorial » Alpha Beta Pruning

Alpha Beta Pruning

Definition of Alpha-Beta Pruning

Alpha-beta (AB) pruning is an improvised version of the Minimax algorithm. The search optimization technique employed by this pruning algorithm cuts down the spread of search and reduces the computation time considerably.

Minimax algorithm exhaustively reviews all the nodes in the search tree for maximizer turn and minimizer turn and decides the best possible course whereas AB-Pruning skips some of the branches in the search tree which yields insignificant value and penetrates to any level in the tree.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

AB pruning deals with two parameters called Alpha and Beta, assigned for maximizer and minimizer respectively at each and every step of the search operation and hence the name AB-Pruning.

What is Alpha Beta Pruning?

Let’s study the AB-Pruning technique in detail.

1. Adversarial Search

Normally any search strategy is associated with a single entity and the result of this strategy will be an optimal action sequence. There may be scenarios where more than one entity will be involved in the search space with confronting intentions and they will be pitted against each other towards reaching their objectives/goals. The search strategy of each of the entity will depend on the opponent’s move and the likely impact it will bring in their pursuit towards meeting the end objectives.

Such search strategies where more than one stakeholder with competing intentions fight in the search space in reaching their goals are known as adversarial searches and it is mostly adopted in Games-like situations. This concept is used in artificial intelligence, game theory, decision theory, statistics, and philosophy fields and it is also applied in decision making in business scenarios where many uncertainties exist.

The strategies adopted by players vary according to the game situation and each one will follow different directions. One player will take the upper hand and try to maximize the gain (Maximizer) and the opponent will try to control damage and minimize the loss (Minimizer).

Popular Course in this category
Sale
All in One Software Development Bundle (600+ Courses, 50+ projects)600+ Online Courses | 3000+ Hours | Verifiable Certificates | Lifetime Access
4.6 (3,144 ratings)
Course Price

View Course

Related Courses
Software Testing Training (9 Courses, 2 Projects)Penetration Testing Training Program (2 Courses)TestNG Training (4 Courses, 2 Project)

2. Minimax Algorithm

Minimax algorithm is built over the minimizer and maximizer concept as explained above, but it is not all that efficient and intuitive. It goes through all the nodes in the game hierarchy end to end and explores all possibilities before arriving at the final game path.

3. Improvements Over Minimax

AB Pruning algorithm is built on the fundamentals of Minimax and improvised with search optimization features. It reduces the number of nodes searched in the game hierarchy and saves time and resources. For Maximizer it computes the maximum value of minimum gain and it is stored in a parameter called Alpha and for Minimizer it computes minimum values of maximum loss and it is stored in a parameter called Beta. The values stored in Alpha and Beta decide the way the search operation is executed.

The depth of the nodes to be examined is exponentially higher in AB algorithm and it cannot be reduced but the number of nodes to be examined can be reduced drastically by eliminating the nodes that do not contribute any value to the outcome and this elimination process is called as pruning.

Functions of Alpha-Beta Pruning

Let us examine a case of two players engaged in a search (or game) with 5 levels of nodes.

  • The topmost level will be the root and it will have only one.
  • The terminal level (5th level) contains leaf nodes and it will have values in all the leaves.
  • Each level will either have maximizer’s turn or minimizer’s turn and it will change alternatively.
  • Each node is connected by branches to another node at a level below.
  • The sequence of Search operations will be from top to bottom and the left node to the right node.
  • Maximizer will have its value in a parameter Alpha and Minimizer will have Beta.
  • The initial value of Alpha will be -∞ (-infinity) the lowest and for the beta will be +∞ (+infinity) the highest.
  • The search starts with an initial value of Alpha and Beta at the root.
  • The values are propagated to the next node (if it is empty) in the one level below (left or right) following the search sequence as explained in step 5.
  • If the level of the tree is Minimum turn, Beta value is compared with the values of the node in the next lower level and the Beta value is changed with the lowest value of all.
  • If the level of the tree is Maximum turn, Alpha value is compared with the values of the node in the next lower level and the Alpha value is changed with the highest value of all.
  • If the value of Alpha is greater than or equal to the value of Beta, the branch below will be pruned and will not be explored further. By this, the number of search operations will be brought down considerably.
  • The above 4 steps (Step 9 to 12) are iterated till all the nodes at all levels other than what is pruned are explored and the best value is chosen for Maximizer and Minimizer and the results are stored in Alpha and Beta parameters.
  • At the end of iteration and completion of the search, Alpha will contain the highest possible score for the maximizer and Beta will contain the lowest possible score for the minimizer.

Search Tree Hierarchy

Alpha Beta Pruning-1.1

Key Points in Alpha Beta Pruning

  • Value of Alpha and Beta will be passed to the nodes down below (Child nodes) in forward.
  • In backward movement in the tree, only node values will be passed on to the upper node as against Alpha and Beta values in the top to down
  • Value of Alpha only will be updated in tree level assigned for
  • Value of Beta only will be updated in tree level assigned for
  • The order in which the nodes are examined (Search movement) is very much important to maximize the pruning and save time and effort. It’s always ideal to start from the leftmost node and move rightwards.
  • The best way to arrive at a good ordering is to start from the shallowest node and check the best nodes first to improve the probability of

Recommended Articles

This is a guide to Alpha Beta Pruning. Here we also discuss the definition and working of alpha beta pruning along with features. You may also have a look at the following articles to learn more –

  1. Alpha and Beta Testing
  2. Alpha Testing
  3. Alpha Testing vs Beta Testing
  4. Beta Testing

All in One Software Development Bundle (600+ Courses, 50+ projects)

600+ Online Courses

3000+ Hours

Verifiable Certificates

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Software Testing Tutorial
  • Advance
    • Cyclomatic Complexity
    • Decision Table Testing
    • Decision Tree Algorithm
    • What is Continuous Integration
    • Mantis Bug Tracker
    • Equivalence Partitioning
    • Gantt Chart Software
    • Acceptance Testing Types
    • Load testing tools
    • Install TestNG
    • Install Unity
    • Defect Management Process
    • Test Plan Template
    • Testing Interview Questions
    • Testing of Mobile application
    • What is Test Automation Frameworks
    • Test Automation Framework
    • Application of Automation
    • Test Automation Process
    • Automation Testing Roles and Responsibilities
    • What is Instruction Cycle?
    • What is Cucumber?
    • 15 Best Popular Bug Reporting Tools
    • What is Automated Testing?
    • Software Maintenance Types
    • Types of Penetration Testing
    • Software Reliability
    • Best Gantt Chart Software
    • Code Coverage
    • Branch Coverage
    • Decision Coverage
    • Statement Coverage
    • What is Test Case
    • Types of Test Case
    • What is Test Scenario
    • Formal Review
    • Alpha Beta Pruning
    • What is Cyclomatic Complexity?
    • Test Coverage
    • How to Write Test Case
    • Testing Documentation
    • Performance Testing Life Cycle
    • Test Harness
    • Test Strategy
    • Software Incident Management
    • What is Debugging
    • What is Defect?
    • Listeners in TestNG
  • Basics
    • What is Software Testing
    • Careers in Software Testing
    • Defect Life Cycle in Software Testing
    • Levels of Software Testing
    • Software Testing Life Cycle
    • Software Tester Work
    • Software Testing Principles
    • Software Testing Services
    • Testing Methodologies
    • Test Approaches
    • Grey Box Testing
    • Types of Software Testing
    • What is a Bug in Software Testing
    • Benefits of Automation Testing
    • What is Automation Testing?
    • Types of Automation
    • Automation Testing Process
    • Mobile Automation Testing
    • Automation Testing Life Cycle
    • Software Quality Assurance
    • Software Quality Assurance
    • What is Test Environment?
    • Verification and Validation Testing
  • Types of Testing
    • Adhoc Testing
    • Types of System Testing
    • Manual Testing Types
    • Unit Testing Types
    • Unit Testing Benefits
    • Agile Testing
    • What is Agile Testing
    • Acceptance Testing
    • Stress Testing Types
    • Alpha and Beta Testing
    • Application Testing
    • Automation Testing
    • Automation Testing Advantages
    • Benchmark Testing
    • Black Box Testing
    • Domain Testing
    • Dynamic Testing
    • Ecommerce Testing
    • Fuzz Testing
    • Gray Box Testing
    • GUI Testing
    • Installation Testing
    • Interface Testing
    • Interoperability Testing
    • Mainframe Testing
    • Manual Testing
    • Mutation Testing
    • Monkey Testing
    • Negative Testing
    • Penetration Testing
    • Penetration testing phases
    • Penetration testing framework
    • Protocol Testing
    • Recovery Testing
    • Regression Testing
    • Mobile Penetration Testing
    • Accessibility Testing
    • Sanity Testing
    • Scalability Testing
    • Security Testing
    • Spike Testing
    • Stability Testing
    • State Transition Testing
    • Static Testing
    • Gatling Load Testing
    • System Integration Testing
    • Structural Testing
    • Locust Load Testing
    • System Testing
    • Control Flow Testing
    • Unit Testing
    • Cypress testing
    • Volume Testing
    • Web Testing Application
    • What is Exploratory Testing
    • What is Stress Testing
    • What is Usability Testing
    • White Box Testing
    • Types of White Box Testing
    • Compatibility Testing?
    • Use Case Testing
    • Beta Testing
    • Integration Testing
    • Non Functional Testing
    • Non Functional Testing Types
    • What is Functional Testing
    • Functional testing types
    • Cookie Testing
    • Alpha Testing
    • Boundary Value Testing
    • Equivalence Class Testing
    • Glass Box Testing
    • SOA Testing
    • Smoke Testing
    • Visual Testing
    • Visual Paradigm
    • Model-Based Testing
  • Testing techniques
    • Software Testing Methodologies
    • Black Box Testing Techniques
    • Static Testing Techniques
    • Test Case Design Techniques
    • What is Static Analysis
  • Testing tools
    • Manual Testing Tools
    • Visual Testing Tools
    • Automation Testing Tools
    • Functional Testing Tools
    • GUI Testing Tools
    • Penetration Testing Tools
    • Performance Testing Tools
    • SOA Testing Tools
    • Accessibility Testing Tools
    • What is QTP
    • Regression Testing Tools
    • Security Testing Tools
    • Test Management Tools
    • Defect Management Tools
    • Code Coverage Tools
    • Test Coverage Tools
    • Defect Tracking Tools
    • Continuous Integration Tools
    • Install Bugzilla
    • Test data generation tool
    • Unit Testing Tools
    • Web Testing Tools
    • Stress Testing Tools
    • Performance Monitoring Tools
    • Mobile Testing Tools
    • Responsive Testing Tool
    • Cross Browser Testing Tools
    • Risk Based Testing
    • Database Testing Tools
    • WinRunner
    • What is Squish?
    • CubicTest
    • What is WinRM?
    • Bugzilla Tool
    • Code review tools
    • Penetration Testing Open Source Tools
  • Inteview Questions
    • Automation Testing Interview Questions
    • Manual Testing Interview Questions
    • ISTQB Interview Questions
    • Cucumber Interview Questions
    • Software Testing Interview Questions
    • Penetration Testing Interview Questions

Related Courses

Software Testing Course

Penetration Training Course

TestNG Training Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Special Offer - All in One Software Development Bundle (600+ Courses, 50+ projects) Learn More