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

[Cardoso]

nevermind.

It's your fault smatovic, in the post of "Emanuel proximity table", you asked for Emanuel Tree Pruning,
and you got it.

[Cardoso]

What is Emanuel? Why not call it Gamma.

I have two friends of mine called Emanuel, so at least in my country (Portugal) it's a person's name.

[Henk]

What is Emanuel? Why not call it Gamma.

I have two friends of mine called Emanuel, so at least in my country (Portugal) it's a person's name.

Why use a person's name as a variable in an algorithm. Something like programming style or humor of the 70's.

[JohnWoe]

I got +200 ELO !!!
Many thanks!

[nionita]

Let us make the hypothesis then, that Black side will win.

Decades ago there was a movie, Black Emanuelle. So if you improve the alpha-beta search, you may establish a link between chess and that movie. Not that bad!

[klx]

1) How do you implement isBestMove(move). At least it is not defined in your pseudocode.

Best move is just what you have stored in the transposition table, a move that caused a cut-off. This is completely optional, but is expected to help.

2) max(historyHeuristics). What is historyHeuristics? A list of values I suppose. What are these values.

https://www.chessprogramming.org/History_Heuristic

Just a heuristic to choose your move(s) to try. Other heuristics are also possible!

Why can you skip all moves below gamma = Emanuel?

So this is the whole idea behind Alpha-Emanuel-Beta. We prune on one side only, and as a result we prove the bound on one side only.

[klx]

I just told you that AB is proven to be optimal

Sure but this is not Alpha-Beta. It differs in two ways: 1) It only proves one bound. 2) The bound is not necessarily proven in the minimum number of moves.

I've shown the psuedo code already, I hope it's clear from that that we are talking about a completely different algorithm. Another way to think of it is this: If player A is purely heuristic (e.g. testing a single move at each position), while player B is trying every single move just like in regular Alpha-Beta, and player A still comes out a winner, then we have proven that A will win.

Now, if B wins, we have proven nothing. It's still very much possible that A will win, but we haven't explored the right moves. So we must either reverse the hypothesis (assume that B will win), or use a smaller Emanuel (try more A moves at each position).

If you are talking about unsound prunining techinques (e.g. let search just one move at a ply), then that is a different proposition all in all.

Yes, it's pruning like crazy, but it's all safe pruning. And, yes, it's a very different proposition. It's an entirely new algorithm. Alpha-Emanuel-Beta.

[Daniel Shawul]

I just told you that AB is proven to be optimal

Sure but this is not Alpha-Beta. It differs in two ways: 1) It only proves one bound. 2) The bound is not necessarily proven in the minimum number of moves.

I've shown the psuedo code already, I hope it's clear from that that we are talking about a completely different algorithm. Another way to think of it is this: If player A is purely heuristic (e.g. testing a single move at each position), while player B is trying every single move just like in regular Alpha-Beta, and player A still comes out a winner, then we have proven that A will win.

Now, if B wins, we have proven nothing. It's still very much possible that A will win, but we haven't explored the right moves. So we must either reverse the hypothesis (assume that B will win), or use a smaller Emanuel (try more A moves at each position).

If you are talking about unsound prunining techinques (e.g. let search just one move at a ply), then that is a different proposition all in all.

Yes, it's pruning like crazy, but it's all safe pruning. And, yes, it's a very different proposition. It's an entirely new algorithm. Alpha-Emanuel-Beta.

There is no safe (sound) pruning algorithm better than alpha-beta, that is what it means to be a mathematically proven optimal algorithm.
It means it can't be improved upon without applying unsound pruning techinque, get it ?

This guy needs to be banned for trolling. You have been given the benefit of the doubt but you offer nothing other than repeating crap ad nauseum.

[AndrewGrant]

In a sick twist of events, I would suggest listening to Daniel. He has a more academic approach to computer chess than most, and I would take his claim at face value, especially since he had a source on hand, which at first glance (I'm not good academic paper reader) appears to be exactly as intended.

[Chessnut1071]

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.

There are many examples where that fails, did you try that on a few dozen mating puzzles? You may get lucky on a few and get overly optimistic.