Question about Fruit

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
kasinp
Posts: 217
Joined: Sat Dec 02, 2006 9:47 pm
Location: Toronto
Full name: Peter Kasinski

Question about Fruit

Post by kasinp » Thu Dec 02, 2010 11:56 pm

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
Posts: 12121
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Question about Fruit

Post by Dann Corbit » Fri Dec 03, 2010 12:16 am

kasinp wrote: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

User avatar
MikeB
Posts: 4714
Joined: Thu Mar 09, 2006 5:34 am
Location: Pen Argyl, Pennsylvania

Re: Question about Fruit

Post by MikeB » Fri Dec 03, 2010 1:29 am

Dann Corbit wrote: 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
Posts: 487
Joined: Wed Mar 08, 2006 8:45 pm
Location: Portland, OR
Contact:

Re: Question about Fruit

Post by IanO » Fri Dec 03, 2010 2:23 am

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.

User avatar
MikeB
Posts: 4714
Joined: Thu Mar 09, 2006 5:34 am
Location: Pen Argyl, Pennsylvania

Re: Question about Fruit

Post by MikeB » Fri Dec 03, 2010 3:19 am

IanO wrote: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.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Question about Fruit

Post by Don » Fri Dec 03, 2010 4:45 am

MikeB wrote:
IanO wrote: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.

User avatar
MikeB
Posts: 4714
Joined: Thu Mar 09, 2006 5:34 am
Location: Pen Argyl, Pennsylvania

Re: Question about Fruit

Post by MikeB » Fri Dec 03, 2010 5:24 am

Don wrote: 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
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Question about Fruit

Post by bob » Fri Dec 03, 2010 6:48 am

IanO wrote: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
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Question about Fruit

Post by Tord Romstad » Fri Dec 03, 2010 8:52 am

Dann Corbit wrote: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
Posts: 12121
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Question about Fruit

Post by Dann Corbit » Fri Dec 03, 2010 7:34 pm

Tord Romstad wrote:
Dann Corbit wrote: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.

Post Reply