Question about Fruit

[kasinp]

I hope I’m not the slowest guy who visits this place. A long while back I wrote a functional chess engine which could spot a mate in 10 even if it did little else well. However, I never had the time (or patience, or resolve) to study Fruit source code.

My request: could someone explain in broad strokes what was so utterly revolutionary about Fruit?

I am looking for a brief (bullet-point?) summary to help me gain the perspective that everyone else seems to share.

Much appreciated,
PK

[Dann Corbit]

I hope I’m not the slowest guy who visits this place. A long while back I wrote a functional chess engine which could spot a mate in 10 even if it did little else well. However, I never had the time (or patience, or resolve) to study Fruit source code.

My request: could someone explain in broad strokes what was so utterly revolutionary about Fruit?

I am looking for a brief (bullet-point?) summary to help me gain the perspective that everyone else seems to share.

Much appreciated,
PK

Fruit was mostly so strong because of solid, bug-free programming.

The most copied idea was Sergei Markov's "Late Move Reductions" which Fruit popularized.

Fabian's search algorithm was better than other search algorithms of that era in that it had a better branching factor due to clever reductions.

There are lots of little, incremental things in the code that made it better than other programs of that time period. It is very hard to put your finger down and list them in importance. I doubt if anyone can do it accurately.

Today, Fruit is well down the list in strength, compared to recent top programs:
http://computerchess.org.uk/ccrl/4040/r ... t_all.html

[MikeB]

Fruit was mostly so strong because of solid, bug-free programming.

The most copied idea was Sergei Markov's "Late Move Reductions" which Fruit popularized.
Fabian's search algorithm was better than other search algorithms of that era in that it had a better branching factor due to clever reductions.

There are lots of little, incremental things in the code that made it better than other programs of that time period. It is very hard to put your finger down and list them in importance. I doubt if anyone can do it accurately.

Today, Fruit is well down the list in strength, compared to recent top programs:
http://computerchess.org.uk/ccrl/4040/r ... t_all.html

LMR -> Game Changer in Chess Programming.
Any program without it , is stronger with it. What's really interesting today is that programs are so much stronger today on equal hardware. Having been away for few years and coming back to computer chess, this is quite noticable. It was almost disconcerting at first - because my mind was not willing to accept that as a fact. The increase in strength just from programming was beyond what I believed was possible.

[IanO]

I'm curious... at what depths does LMR start to give a noticeable improvement? If it had been discovered during the era of strong dedicated chess computers, would it have been game changing? My impression is that the null-move heuristic worked well even at small search depths, and so was a secret weapon for Franz Morsch's dedicated units for a period of time.

[MikeB]

I'm curious... at what depths does LMR start to give a noticeable improvement? If it had been discovered during the era of strong dedicated chess computers, would it have been game changing? My impression is that the null-move heuristic worked well even at small search depths, and so was a secret weapon for Franz Morsch's dedicated units for a period of time.

I think it depends on the hardware - but it is safe to say after a minute of searching, it helps. Yes, I believe it would have been. Programmers are always adpating to faster hardware, but some type of LMR code would have made any dedicated machine stronger. All things being equal, it enables deeper searches with minimal negative effects. You always have certain positions that are negatively impacted by LMR - one such example would be WAC 162 ( although that position for today's hardware is no problem) - but it would have been clearly tougher for programs to solve with LMR running on 1990s hardware.

[Don]

I'm curious... at what depths does LMR start to give a noticeable improvement? If it had been discovered during the era of strong dedicated chess computers, would it have been game changing? My impression is that the null-move heuristic worked well even at small search depths, and so was a secret weapon for Franz Morsch's dedicated units for a period of time.

I think it depends on the hardware - but it is safe to say after a minute of searching, it helps. Yes, I believe it would have been. Programmers are always adpating to faster hardware, but some type of LMR code would have made any dedicated machine stronger. All things being equal, it enables deeper searches with minimal negative effects. You always have certain positions that are negatively impacted by LMR - one such example would be WAC 162 ( although that position for today's hardware is no problem) - but it would have been clearly tougher for programs to solve with LMR running on 1990s hardware.

Reductions have been around for decades - it's not new in itself. What is relatively new is the LMR formalization and how aggressively it is now done.

[MikeB]

Reductions have been around for decades - it's not new in itself. What is relatively new is the LMR formalization and how aggressively it is now done.

Yes - reductions have been around for decades , what was new about LMR was that it was one of the first techniques which reduced the amount of work at the failed low nodes.

[bob]

I'm curious... at what depths does LMR start to give a noticeable improvement? If it had been discovered during the era of strong dedicated chess computers, would it have been game changing? My impression is that the null-move heuristic worked well even at small search depths, and so was a secret weapon for Franz Morsch's dedicated units for a period of time.

It helps at a fraction of a second per move, or at long times per move. I've not found any difference in fact. It is just something that works, like null-move works, regardless of the search depth.

[Tord Romstad]

The most copied idea was Sergei Markov's "Late Move Reductions" which Fruit popularized.

Sergei Markov? No, LMR is a lot older than that. It's one of these techniques which have been around forever, but for some reason almost nobody believed in it until a few years back. I think I spent about a year describing and recommending the technique here on the CCC before anyone even bothered to try it (which is strange, considering that a basic implementation takes just a few minutes of work). The earliest open source engine I'm aware of which uses LMR is Pepito.

[Dann Corbit]

The most copied idea was Sergei Markov's "Late Move Reductions" which Fruit popularized.

Sergei Markov? No, LMR is a lot older than that. It's one of these techniques which have been around forever, but for some reason almost nobody believed in it until a few years back. I think I spent about a year describing and recommending the technique here on the CCC before anyone even bothered to try it (which is strange, considering that a basic implementation takes just a few minutes of work). The earliest open source engine I'm aware of which uses LMR is Pepito.

It was Sergei that I remembered popularizing it. But probably I was mistaken. I have correspondence with a chess programmer in Brazil where we talked about the idea before 2000.