Is modern chess software lossless or lossy?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Meni Rosenfeld
Posts: 10
Joined: Wed Mar 11, 2015 8:42 pm

Is modern chess software lossless or lossy?

Post by Meni Rosenfeld » Wed Jan 10, 2018 10:39 pm

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.

syzygy
Posts: 4374
Joined: Tue Feb 28, 2012 10:56 pm

Re: Is modern chess software lossless or lossy?

Post by syzygy » Thu Jan 11, 2018 12:45 am

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.

User avatar
Ovyron
Posts: 1966
Joined: Tue Jul 03, 2007 2:30 am

Re: Is modern chess software lossless or lossy?

Post by Ovyron » Thu Jan 11, 2018 2:20 am

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."

Werewolf
Posts: 1153
Joined: Thu Sep 18, 2008 8:24 pm

Re: Is modern chess software lossless or lossy?

Post by Werewolf » Thu Jan 11, 2018 11:17 am

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?

Milos
Posts: 3283
Joined: Wed Nov 25, 2009 12:47 am

Re: Is modern chess software lossless or lossy?

Post by Milos » Thu Jan 11, 2018 12:14 pm

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.

Fulvio
Posts: 127
Joined: Fri Aug 12, 2016 6:43 pm

Re: Is modern chess software lossless or lossy?

Post by Fulvio » Thu Jan 11, 2018 4:04 pm

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.

User avatar
Ovyron
Posts: 1966
Joined: Tue Jul 03, 2007 2:30 am

Re: Is modern chess software lossless or lossy?

Post by Ovyron » Thu Jan 11, 2018 4:10 pm

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.

Fulvio
Posts: 127
Joined: Fri Aug 12, 2016 6:43 pm

Re: Is modern chess software lossless or lossy?

Post by Fulvio » Thu Jan 11, 2018 4:32 pm

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.

User avatar
cdani
Posts: 2101
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Is modern chess software lossless or lossy?

Post by cdani » Thu Jan 11, 2018 7:24 pm

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.

syzygy
Posts: 4374
Joined: Tue Feb 28, 2012 10:56 pm

Re: Is modern chess software lossless or lossy?

Post by syzygy » Thu Jan 11, 2018 8:04 pm

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.

Post Reply