TalkChess.com

Hello,

I'll be happy for help in settling a dispute.

In an online discussion I participated in, I mentioned the following:

Modern chess software is "lossy" - it aggressively prunes possibilities that potentially could be relevant, but statistically are unlikely to be so, in order to reach such high depth that the tactics become akin to strategy.

By "lossy" I mean that it could miss relevant variants within the specified search depth; Compared to vanilla Alpha-Beta, which only prunes irrelevant possibilities and is thus lossless.

This is what I gathered from my reading of resources like CPW and other references. My understanding is that reaching high depth is key, and this cannot be achieved without some sacrifices. The vast improvement in modern software like Stockfish compared to older software is precisely that it manages to make these sacrifices in an optimized way.

However, an interlocutor replied with the following:

this simply isn't true. This approach was abandoned decades ago.

He also referred to the writings of one Hans Berliner as proof of his claim that chess software is lossless.

So, which is true? And is there a clear, concise, reliable reference which unambiguously answers this question?

Thanks.

The interlocutor is not very up to date.

In 1949, Shannon described two approaches: brute-force search (Type A) and selective search (Type B).

Most early chess programs had to use a selective search, since computers were slow (and not all programmers were aware of the alpha-beta algorithm). Typically, these programs statically selected a small number of "promising" moves in each position and searched only those moves.

Around 1970 or so, programs started to shift to a brute-force approach. From the Tech wiki page:

Until recently the main effort in chess programming has been to develop programs which selectively (and hopefully "intelligently") examine a small subset of the legal moves in any position. The surprising performance of the Varian minicomputer (programmed by K. King and C. Daly) in the First Annual Computer Chess Championship (New York 1970), although due primarily to good luck in the pairings, led to increased speculation about the possibility of playing respectable chess with an unselective "brute force" program.

The pure Type B programs overlooked too many important moves, so Type A programs took over. See also the Chess (Program) wiki page.

But then people started to add pruning and reduction heuristics like the null-move pruning and late-move reductions, which again made the search selective.

Modern top engines are very selective, but they are very different from the early Type B programs in that they use information gathered during the search to make pruning and reduction decisions.

Note that if chess software was lossless we wouldn't have so many threads with people posting a position where it's really hard for the software to find the best move. Most programs just prune the solution, it is lost in the "lossy."

syzygy wrote:
But then people started to add pruning and reduction heuristics like the null-move pruning and late-move reductions, which again made the search selective.

Modern top engines are very selective, but they are very different from the early Type B programs in that they use information gathered during the search to make pruning and reduction decisions.

Presumably though the situation is bound by time rather than in principle. Meaning, if the modern engine was given infinite time, the moves it had pruned out would eventually be searched and thus it would revert back to true Brute Force.

Is that correct?

Ovyron wrote:Note that if chess software was lossless we wouldn't have so many threads with people posting a position where it's really hard for the software to find the best move. Most programs just prune the solution, it is lost in the "lossy."

This is not really true. In huge majority of the cases it is really hard for software to find the best move because of the horizon effect and not because the best move has been pruned.
The most you can say is that potential threats that show the current best move is not the best are pruned due to LMR or null-move heuristics.

syzygy wrote:But then people started to add pruning and reduction heuristics like the null-move pruning and late-move reductions, which again made the search selective.

I don't know how hard is to enclose that code inside #ifdef sections, allowing to compile a non-selective version of the engine.
But it would be interesting to see how engines play against their "complete" version.

Milos wrote:This is not really true. In huge majority of the cases it is really hard for software to find the best move because of the horizon effect and not because the best move has been pruned.
The most you can say is that potential threats that show the current best move is not the best are pruned due to LMR or null-move heuristics.

The horizon effect can be tested by making the move and seeing if the engine does not like it still. If it sees that the move was clearly best, it missed it because of prunning. If it still does not like it, and it takes a similar long time to like it as when missing it from the root, then it's the horizon effect.

Meni Rosenfeld wrote:Compared to vanilla Alpha-Beta, which only prunes irrelevant possibilities and is thus lossless.

So, which is true? And is there a clear, concise, reliable reference which unambiguously answers this question?

https://en.wikipedia.org/wiki/Alpha%E2% ... provements

"Further improvement can be achieved without sacrificing accuracy"
If your question is: Is mathematically proved that improved Alpha-Beta algorithms (with aspiration windows, etc...) give the same results of plain minimax? the answer is yes.

Fulvio wrote: I don't know how hard is to enclose that code inside #ifdef sections, allowing to compile a non-selective version of the engine.
But it would be interesting to see how engines play against their "complete" version.

This crippled version will be terrible weak. Has been done many times.

Werewolf wrote:

syzygy wrote:
But then people started to add pruning and reduction heuristics like the null-move pruning and late-move reductions, which again made the search selective.

Modern top engines are very selective, but they are very different from the early Type B programs in that they use information gathered during the search to make pruning and reduction decisions.

Presumably though the situation is bound by time rather than in principle. Meaning, if the modern engine was given infinite time, the moves it had pruned out would eventually be searched and thus it would revert back to true Brute Force.

Is that correct?

Ideally, yes. In practice, there will be moves that cannot be found within MAX_PLY depth.