2

Can a minimax function with just alpha beta pruning really evaluate 1.8 billion chess positions (3 ply = 356) in just a second?

My chess engine, which uses minimax with only alpha beta pruning, takes 30 seconds to search 2 ply deep, evaluate the leaves, and determine the best move.

Improve this question
1
  • 1
    Wouldn't 3 ply be roughly 30^3 = 27000 positions? Since there are typically around 30 possible choices for each move. Given this, 2 ply is around 900 positions so your engine shouldn't be taking close to 30 seconds.
    – Inertial Ignorance
    Sep 24, 2019 at 22:05

1 Answer 1

Reset to default
2

There're some problems with your question:

  • Alpha-beta pruning doesn't make you search faster, it makes you search further. For illustration (these numbers are not accurate) if your computer is searching at 1 million nodes (here a "node" is a position) per second, without alpha-beta pruning you might only make it 5 ply deep. With it, you might reach 10 ply.
  • Obviously, how fast you search is going to depend on hardware. With sufficiently powerful hardware you can search 1.8 billion nodes per second. For example right now, Fishtesting is running with this hardware: 650 machines 5048 cores 1.21M nps (6127.86M total nps) 8825 games/minute. That's 6.1 billion nodes per second.
  • However note that Fishtesting is running with 5048 cores. A typical desktop computer might have 4 cores, so this is fantastically powerful hardware. If you're getting 1.8 billion nodes per second, and you have reasonably normal hardware, your eval function is probably very simple compared to the top engines.
Improve this answer
4
  • Additionally, alpha-beta works best when it happens to test the best move first at most levels, in other words when your eval function is quite good
    – Hagen von Eitzen
    Sep 25, 2019 at 21:42
  • @Allure Searching further in the same amount of time could be considered equivalent to searching faster though.
    – Inertial Ignorance
    Sep 28, 2019 at 22:57
  • @InertialIgnorance I wouldn't say they're equivalent. Speed is measured directly by nps, while depth is achieved by pruning.
    – Allure
    Sep 28, 2019 at 23:20
  • @Allure mm ok I see what you mean: so the actual processing speed of the computer on evaluating each individual node. I was referring to the speed of the overall search algorithm.
    – Inertial Ignorance
    Sep 28, 2019 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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