6
$\begingroup$

I know that there are several optimizations for alpha-beta pruning. For example, I have come across iterative deepening, principal variation search, or quiescence search.

However, I am a little bit confused about the nature of these algorithms.

  1. Are these algorithms an extension of the alpha-beta algorithm, or

  2. Are they completely new algorithms, in that they have got nothing to do the alpha-beta algorithm?

On this site, these algorithms fall into one of 4 categories, namely

  • mandatory
  • selectivity
  • scout and friends
  • Alpha-beta goes best-first

Does this mean that the alpha-beta algorithm is split into four areas and that they are specialized optimization algorithms for each area?

How do I even begin to decide which optimized algorithm to pick?

I advise people to visit this site: http://www.fierz.ch/strategy2.htm

$\endgroup$
1
$\begingroup$
  1. Are these algorithms an extension of the alpha-beta algorithm, or

  2. Are they completely new algorithms, in that they have got nothing to do the alpha-beta algorithm?

Most of them are extensions of the Alpha-Beta pruning algorithm. For example, Iterative Deepening is almost the same as Alpha-Beta pruning, but automatically keeps repeating the algorithm with gradually-increasing depth limits until some time limit is reached, rather than just running once for a pre-determined depth limit.

Principal Variation Search also still uses Alpha-Beta as a basis, but performs many searches with significantly smaller [alpha, beta] windows than the standard Alpha-Beta pruning algorithm.

In most cases, these extensions would start out from an existing Alpha-Beta implementation, and build from there with some adaptations in the code. This is not necessarily the case for all of those extensions though, just for most. For example, Transposition Tables are kind of a separate extension that could be plugged into vanilla Minimax, or Alpha-Beta, or Principal Variation Search, or whatever you're using.


On this site, these algorithms fall into one of 4 categories, namely

  • mandatory
  • selectivity
  • scout and friends
  • Alpha-beta goes best-first

Does this mean that the alpha-beta algorithm is split into four areas and that they are specialized optimization algorithms for each area?

Those four categories are not mutually exclusive, they're more like... broad "flavours". What they list under Obligatory are some of the more basic extensions that any programmer should probably look into first if they were developing a chess-playing program. The other category are different "flavours", different "broad ideas". For example, everything listed under "Selectivity" is about searching "interesting" or "exciting" parts of the search tree deeper than "less interesting" or "boring" parts. Many of those ideas could be used regardless of whether you're using Alpha-Beta, Iterative Deepening, or PVS, and probably all could be combined with Transposition Tables as well.

How do I even begin to decide which optimized algorithm to pick?

This is really really difficult to decide just based on the names. In theory, which algorithm is the "best" will also highly depend on your specific game, and maybe even hardware. And, in many cases it's not even a choice between mutually exclusive parts; different ideas can be combined with each other in different ways.

The only solution here is really just to do lots of reading, lots of research, try implementing different things to better understand them.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Note that iterative deepening is not just applied to alpha-beta pruning, but can also be applied to a general search tree. For example, there exists iterative deepening A*. So, iterative deepening is more a search strategy or method (like best-first search algorithms) rather than an algorithm. $\endgroup$ – nbro May 13 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.