LearnViz CompSci
Home / Learn / AI & Machine Learning / Minimax and Alpha-Beta

Advanced Topic 47 of 51 AI & Machine Learning

Minimax and Alpha-Beta

Game-tree search with pruning.

How it works

Minimax is an algorithm for two-player zero-sum games that assumes both players play optimally: the maximizing player chooses the move with the highest value, and the minimizing player chooses the lowest, recursively down the game tree to terminal states or a depth limit where an evaluation function estimates the position. Alpha-beta pruning keeps track of the best values already guaranteed for each player and skips branches that cannot influence the result, giving the same answer while examining far fewer nodes, up to the square root in the best case with good move ordering.

Step-by-step walkthrough

  1. Minimax assumes both players play optimally.
  2. Max picks the child with the highest value.
  3. Min picks the lowest at its level.
  4. Alpha-beta stops exploring a branch that cannot change the result.
  5. The result is identical with far fewer nodes.

Where it is used

Chess, checkers, tic-tac-toe, Othello and other board-game engines use minimax with alpha-beta, plus iterative deepening, transposition tables and evaluation heuristics.

Common pitfall

The game tree is huge, so depth limits cause the horizon effect, and weak evaluation functions give poor play. Move ordering strongly affects pruning efficiency. Works for perfect-information, deterministic games; chance and hidden information need expectimax or sampling. Modern engines for Go use Monte Carlo tree search with neural networks.

Where it fits in the course

Minimax and Alpha-Beta is topic 47 of 51 in AI & Machine Learning, rated Advanced. It follows Search Algorithms in AI. The next topic is Bayesian Networks.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the AI & Machine Learning quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Minimax and Alpha-Beta?
Game-tree search with pruning. It belongs to AI & Machine Learning and is an advanced-level topic.
Where do people use Minimax and Alpha-Beta?
Chess, checkers, tic-tac-toe, Othello and other board-game engines use minimax with alpha-beta, plus iterative deepening, transposition tables and evaluation heuristics.
What is the most common mistake with Minimax and Alpha-Beta?
The game tree is huge, so depth limits cause the horizon effect, and weak evaluation functions give poor play.
What should I learn before this topic?
Start with Search Algorithms in AI, the topic just before it in AI & Machine Learning.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the AI & Machine Learning quiz.
Is Minimax and Alpha-Beta hard to learn?
It is an Advanced topic. Expect to read the explanation more than once and to connect it with earlier topics. Working through a small example by hand helps most.
How long does it take to learn Minimax and Alpha-Beta?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Minimax and Alpha-Beta?
Search Algorithms in AI, Bayesian Networks, Tokenization are closely connected. The full list is in the related topics section of this page.
What should I study after Minimax and Alpha-Beta?
Continue with Bayesian Networks, the next topic in AI & Machine Learning.

Related topics