Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!

[klx]

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.

[AndrewGrant]

Trolling

[amanjpro]

You probably become the first one that I ignore in this forum, congrats


"Emanuel's efficient ignore list" is probably your next topic

[hgm]

Sounds like you are trying to re-invent MTD(f)...

[smatovic]

Or he mixes up a null-window-search with aspiration-windows with mate-distance-pruning? A parallel multi-window search is IMO pretty lame though, tried it on gpu.

--
Srdja

[Henk]

Yes I don't completely understand but something like aspiration window searches (or variation of MTD(f) ) which I already have in my engine calling Principal Variation Search. They said it was worth 40 Elo so I still did not disable it. All terrible to debug. But misery starts with loops and recursion.

What is Emanuel? Why not call it Gamma.

Maybe if he shows an algorithm/pseudocode I can understand what it is about.

Don't understand this:
"If we use history heuristics, we can use a multiple of the maximum or sum of all heuristics."

[Henk]

Don't understand this:
"If we use history heuristics, we can use a multiple of the maximum or sum of all heuristics."

O wait that is about about multi processing. So it uses history heuristic somehow. But how exactly?

[Henk]

Don't understand this:
"If we use history heuristics, we can use a multiple of the maximum or sum of all heuristics."

O wait that is about about multi processing. So it uses history heuristic somehow. But how exactly?

It uses history heuristic somehow to compute gamma in aspiration searches/MTD(f).
Full window researches are expensive

[tcusr]

i've seen your previous posts, you're funny

[Daniel Shawul]

While I appreciate your thought provoking AND provocative posts, the alpha-beta algorithm has been milked bone dry years ago and the chances of finding an 'exponential reduction' lying around there is 0. Alpha-beta is already proven to be asymptotically optimal among all game searching algorithms

Also, in practice alpha-beta search is done with one bound, either MTD(f) or PVS with narrow windows for the PV search, so it is not right to assume it uses two bounds.