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.
Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
Moderators: hgm, Rebel, chrisw
-
- Posts: 179
- Joined: Tue Jun 15, 2021 8:11 pm
- Full name: Emanuel Torres
Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
[Moderation warning] This signature violated the rule against commercial exhortations.
-
- Posts: 1754
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
Trolling
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
You probably become the first one that I ignore in this forum, congrats
"Emanuel's efficient ignore list" is probably your next topic
"Emanuel's efficient ignore list" is probably your next topic
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
Sounds like you are trying to re-invent MTD(f)...
-
- Posts: 2645
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
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
--
Srdja
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
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."
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."
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
It uses history heuristic somehow to compute gamma in aspiration searches/MTD(f).
Full window researches are expensive
-
- Posts: 323
- Joined: Tue Aug 31, 2021 10:32 pm
- Full name: tcusr
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
i've seen your previous posts, you're funny
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Alpha-Emanuel-Beta Search -- Enormous Improvement of Alpha-Beta!
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.
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.