klx wrote: ↑Thu Sep 02, 2021 7:03 am
Background
1956. Alpha-Beta was invented by John McCarthy. Over the years, it was further researched by giants such as Donald Knuth.
Fast forward 65 years. Not much has changed. Chess engines are still based on the same technique.
September 1, 2021. Yours truly was out for a morning jog (half marathon), when suddenly a stroke of genius attacked.
There is a fundamental improvement possible in Alpha-Beta search! Easily overlooked, having gone undetected for all these years, but once you see it, it will change the way you think of game search.
The Idea
The basic idea is as follows. In Alpha-Beta, we are proving both an upper and lower bound. Alpha-Emanuel-Beta, in contrast, proves only one bound.
For sake of example, let say we are searching for a mate (but can be any bound). Let us make the hypothesis then, that Black side will win. The genius realization is:
we no longer need to analyze every single black move. It is enough to find a
single black move at every step that leads to a win. Of course, we still need to try all white moves in response, but due to cut-offs they will generally be few.
What we have obtained now, is a mind-boggling
exponential reduction in number of nodes visited.
Emanuel
There is but one complication. Our search may show that Black side loses, while in fact there were black moves leading to a win that we never explored. To deal with this, we define a variable `long Emanuel`, where we only try black moves with score above this variable. Emanuel can then be progressively lowered, so that we start with a big Emanuel, and if the hypothesis fails, we try a smaller Emanuel. More specifically then -- how do we choose Emanuel? Well, it depends on the scoring. If we use history heuristics, we can use a multiple of the maximum or sum of all heuristics.
Concurrency
Now, you may think, if the hypothesis fails, and we need to re-search for the other side to win, or another Emanuel, it will waste time. Well, not so! Unlike regular Alpha-Beta search, Alpha-Emanuel-Beta is very amenable to parallelizing; we can start these searches in separate threads and since they're completely independent there is close to 100% multithreading efficiency!
Epilogue
I am releasing this idea in the public domain, for anyone to implement and profit from. How will we look back at this discovery in 65 years? Only time will tell.