5
$\begingroup$

I know that they are quite alot of optimizations for alpha-beta pruning but what does it mean exactly:

1) Does it mean that these optimized algorithms are to be integrated into the alpha-beta algorithm or

2) Does it mean that these optimizations are completely new algorithms in that they have got nothing to do the alpha-beta algorithms?

On the note of alpha beta optimizations, I have come across a lot of optimizations like Iterative deepening, Principal variation Search, Quiescence search and many more. My second question is the optimizations listed above are found in the site "https://chessprogramming.wikispaces.com/Search", but this site groups these algorithms into 4 categories namely, Mandatory, Selectivity, Scout and friends and lastly Alpha-beta goes best-first. Does this mean that alpha-beta algorithm is split into four areas and that they are specialized optimization algorithms for each area? This is really confusing me. 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

not, https://chessprogramming.wikispaces.com/Search, this website to beginners like myself is just too distracting with all of its links on each page. This just becomes too overwhelming for a beginner to understand.

$\endgroup$
1
$\begingroup$

1) Does it mean that these optimized algorithms are to be integrated into the alpha-beta algorithm or

2) Does it mean that these optimizations are completely new algorithms in that they have got nothing to do the alpha-beta algorithms?

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.


My second question is the optimizations listed above are found in the site "https://chessprogramming.wikispaces.com/Search", but this site groups these algorithms into 4 categories namely, Mandatory, Selectivity, Scout and friends and lastly Alpha-beta goes best-first. Does this mean that 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.

$\endgroup$

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.