Unanswered question from Engine Origins forum

[Don]

So to answer HG's question, I don't hink there is much that Ippo contributed and if I'm wrong nobody here is refuting me.

Biggest revolutionary (although not the first to do this) contribution of Ippolit has been to release the sources of a top rated engine from where all the top engines of today (including Komodo) were heavily influenced, directly or indirectly. Also all the commercial engines of course, but here the progress has been much slower, I guess due to the burden of legacy very old existing code that is not always easy to 'adapt' to new stuff without deep re-engineering.

It is a pity that you pretend Komodo appeared out of the blue,

You must have just come out of hibernation. Komodo was the most rapidly improving program since I started working on it in the Doch days and well before Ippolit came along. Glaurung/Stockfish was another program which was on a rapid improvement path WELL BEFORE Ippo came along. Strangely enough, these two programs remain the strongest of the original programs and that is NOT because of Ippo. Without Ippo it would be Komodo, Stockfish and Rybka on top and by a substantial margin (the gap below us is large even now, despite the "major innovations" introduced by Ippo. Sarcasm intended.

of course testing is everything and of course you can look at all the sources you want but without hard work on your side you go nowhere, but looking you trying to minimize the impact of Ippo leaves me a bad taste, I find Richard's approach based on clearness and transparency much more balanced and fair

Richards program is closely patterned after the clones and he is up front about this and I respect that as well as his honestly. In fact it's outright refreshing.

But what does that have to do with me? How is his approach of closely patterning his program after Ippo and being up front about it more balanced and fair than me NOT copying Ippo? I find your statement rather offensive and I don't understand the name dropping here.

and I don't think Critter used other engines for its development more than Komodo: Larry stated many times that you have checked and tested ideas in open source engines one by one in a very metodhological and 'brute force' approach (please concede that the fact that the ideas were found useful for Komodo or not does not change a dime what we are discussing here and is not a sensible point).

We did test ideas in other programs and I have never apologized for being hungry for ideas - all top chess program authors eat ideas for lunch and always looking for the next good idea. However, the fact remains that hardly any of these ideas worked for us and I would have been ecstatic if they had. None of them other than SE represented something we were not already doing in some form and SE was the single outstanding exception and we did benefit from that I admitted it many times. That idea, by the way, came from Rybka according to Larry. Strangely enough, the highly original program Ippo stumbled on exactly the same idea, SE implemented the same way.

If you read HG question carefully I think you will see there is not an answer. This is yet another post where someone fails to answer his question.

Please note that I'm not saying there was NO benefit to having the Ippolit sources. It is dishonest of you to infer that is what I said. Look at one of my first posts on this thread and I said something like that their contribution was evolutionary, not revolutionary. Every good open source program contributes SOMETHING good to computer chess. You may not agree with me but I believe Stockfish contribute more to computer chess that Ippolito did because as you have already admitted
their primary contribution is sample source code for a really good chess program and Stockfish was a far better example. It doesn't matter that Ippo was stronger unless the intent was to simply copy it (which we know was not the intent), Stockfish was "modern" and a much better source code example.

P.S: You state that your hero is fruit. What are the new ideas brought on the table by fruit ? I mean, real novelties, stuff never heard of before?

There is nothing in computer chess that has never been heard of before. The SE idea is very old but the way it's done in Rybka is new and outstanding. Reducing moves is not anything new, but the way modern program do it qualifies as an innovation. Note that these things are not 1 or 2 ELO things, they are major ELO boosting techniques. They are innovations. Fruit had many of them and yet that all seemed so simple.

The 2 primary things that comes to mind for me is:

1. opening/ending evaluation interpolation.
2. modern LMR

Those are true innovations and major ELO wins. modern LMR is on the same scale as the discovery of null move pruning and check extensions and it's worth 100 ELO in Komodo.

What does Ippo have that is even close to that? Ippo is not innovative unless you just go by the strength, it is innovative in that respect but HG asks what new ideas were brought to computer chess by Ippolit and the only one I can name was already in Rybka. Do you know of any?

[Don]

And a call to everyone:

please don't let this degenerate into a discussion of who stole what from whom, and who you dislike because of what character flaw. This is completely irrelevant to my question, because even if innovating ideas were stolen from a closed-source engine, it would not make them less innovative, or have any less impact when they finally were published.

And getting losts in squibbles about that, will make it very more difficult to answer the original question.

Perhaps I should rephrase the question in a more specific way:

Now that knowledge of the Ippolit code has reach me, how would I go about changing Fruit to bring its strength on par with Ippolit? Would the major improvements come from (say)

More speed by better algorithms (e.g. bitboard, if you are not on a 32-bit machine)
More speed by reaping benefits from hardware improvement (e.g. large memory pages)
Count depth in fractional plies
Be more concise in hashing nodes for the same position that pruned differently
Search many more moves than just captures in the first 3-4 ply of QS
Keep account of how much you gain by non-captures, and extend high-gain moves in QS
Do reduced-depth pilot searches with shifted window to recognize 'easy-move' situations, and give those a singular extension.

You would start by implementing SE in a manner similar to Ippolit. Most of the rest would come from major improvement to the evaluation function. Fruit's evaluation is primitive compared to any of the top programs and is a major impediment to it's strength.

The standard technique these days is to view the evaluation function as an annoyance that gets in the way of the fun stuff - and so you just copy Ivanhoe's evaluation function and move on to the "important stuff", not realizing that this IS the important stuff.

[jdart]

I disagree. The Fruit search code is very simple compared to Ippolit and its derivatives.

Some of the the things it lacks: razoring, static null pruning, the Ippolit trick of selectively move-generating captures based on futility margins, and as you note, singular extensions. Also futility pruning (at least in Fruit 2.0) is at depth 1 only. There are probably other differences, these are just some.

As far as I am aware, nobody recently has based an engine directly on Fruit except for GnuChess 6.

--Jon

[Don]

http://www.talkchess.com/forum/viewtopi ... 79&t=44864

Harm-Geert Muller asked this question on the Engine Origins subforum but so far no one has been able or willing to answer it. I thought it was an interesting question, I don't recall myself that it has been answered in any depth before, on this forum. It is not too controversial I think that it should not be here, unless you want to argue that there may be material propietary to Vas Rajlich that should not be discussed here. I don't think that it would be a problem with Vas discussing Ippolit right now but he could always pass us a message about that. As far as I know he is also still a member here.

Maybe, and it is likely, that there is already some material from Vas himself directly related to the question in the hidden Rybka forum, but I did not have access at the time it could have been discussed there. Possibly, as was the case with the question of the contribution to computer chess techniques from Fruit, it is hard to answer HGM's question.

Eelco

Perhaps a very ignorant question, but what exactly is the contribution of Ippolit to computer Chess in terms of new ideas? (I understand of course that it is a cloner's heaven to have an instant 3000+ engine to start from, but the question is more what you would find that could be helpful if you already had a 2800-Elo engine, if you wanted to boost its Elo, rather than just throw away your own code and use Ippolit in stead.)

Some time ago I had a glance at the Ippolit code (mainly because I wanted to see how a top engine exploits the extra possibilities bitboards offer over mailbox), and what I did notice about its search is that it counts in half-plies, and that its QS (i.e. the possibility to stand pat) already starts at d = 4 ply, using some (marginally) depth-dependent window tuning for deciding which moves to search in the first 4 ply of this QS. And that it used a table to remember the maximum gain effected by each move, used to decide if such a move should be searched in early QS.

Are these Ippolit-specific tricks, and do they contribute a lot to its playing strength?

The best answer so far, which I see in a reference to another thread is this:

http://www.talkchess.com/forum/viewtopi ... 533#396533

where Joona says:

- Singular extensions
- Aggressive LMR
- Aggressive neg. SEE moves pruning

I want to give this a fair answer based on Adams admonition to the group and I cannot do this without proper references. But here goes.

SE is something I already identified and I agree that it is an innovation. However Ippolito should not be getting credit for this as it first appeared in Rybka as far as I know. It was not in Fruit. I apologize for bringing that up but it must be said to answer HG's question properly. I am willing to be corrected if I am wrong.

Aggressive LMR does not qualify as a "new idea" in computer chess unless you want to start considering implementation details of things as new ideas. Komodo has mobility that is different that other programs, it's progressive and is different in other ways but I don't consider that a "new idea in computer chess."

But if you want to label it as such, then I apologize again for bringing attention to the fact that this would have to be considered an innovation belonging to Rybka, not Ippolit. Do you see any point in arguing over who does more LMR and giving that program special honor as being the innovation? I would assume that once the concept of LMR was understood every programmer worth his salt would experiment with it. Am I wrong?

SEE based forward pruning has been in programs for many decades. I'm often surprised at how often the new kids don't know computer chess history and every idea seems new to them. This is not new nor is it an innovation.

I think Marco gave an honest answer when he said their contribution was primarily releasing the source code of a very strong program.
Doing this exposed many Rybka details such as those Joona listed above which were not revealed by many much weaker open source programs. It doesn't matter whether they knew about these ideas from Rybka or not - the fact is that they were in Rybka first and we cannot give HG an answer here.

I would like to add something to Joona's list. We see an excellent example of aggressive forward pruning here - that goes beyond just calling SEE() to see if a move loses. Again, no program before Rybka was this aggressive and this is not a new idea anyway but like LMR Rybka pushed it hard and Ippo exposed these ideas and dressed them up their own way.

However, Glaurung was doing aggressive forward pruning way before Ippo came out and it's unlikely they got this from Rybka or Fruit. Glaurung made use of the null move refutation. I don't know if Rybka did anything like this and I don't know if this was an original idea from Tord or whether he borrowed it from others. It seemed like such a good idea that we tried it in Komodo and was never able to make it work for us. As has been stated many times you cannot just take some idea and "plug it in" like it's some sort of ingredient you pour into your soup to make it better and expect it to work. I don't know how much if any it contributes to Glaurung/Stockfish but since it's still there I would assume it is beneficial for them.

Another idea is this concept of a gains table. I don't know who had this idea first - it seems like a great idea and most of the top programs seem to make good use of that. It's not an Ippo innovation so to answer HG this is not a new idea contribution. It's not used in Komodo but it seemed like such a good idea that we tried hard to benefit from it. We have revisited that one about 3 times, each time being disappointed. This is why you never tell someone that some idea "doesn't work" - all you can say is that "you couldn't make it work."

So we have this list now:

1. Singular Extensions
2. Aggressive LMR
3. SEE pruing
4. position gains array
5. Aggressive forward pruning.

Not a single one of these was introduced by Ippolit and most of them do not qualify as "new ideas" even in Rybka. I believe SE is one exception.

I could add to this list easily - but everything that comes to mind was already in Rybka or pre-Rybka or just very old ideas resurrected. I get the sense as Marco does that exposing these ideas via the source code was the most important contribution - and yet I don't see that any program actually benefited from this in a noticeable way, as Norman observes these programs are still at the top - even the original versions of them. If you removed all the clones and just consider them, they would be around the strength of Rybka 4 and without the Houdini and Critter derivatives they would still be in 3rd or 4th place and well ahead of the pack behind them.

So either these ideas do not exist or else nobody has chose to use them despite the fact that they are in plain sight. Or as Norman would have you believe just Komodo benefited and nobody else. Does that seem the least bit reasonable?

So what are these new ideas?

[hgm]

Some of the the things it lacks: razoring, static null pruning, the Ippolit trick of selectively move-generating captures based on futility margins, and as you note, singular extensions. Also futility pruning (at least in Fruit 2.0) is at depth 1 only. There are probably other differences, these are just some.

What intrigues me most in this list is the 'static null pruning'. Is this the same thing as what I interpreted as searching some classes of non-captures in the first few levels of QS, namely that it returns the current eval (i.e. stands pat) if the latter is above a certain limit when depth < 8 half-ply? This was indeed a thing I had never seen in any other engine. (Which doesn't mean that much, as I hardly ever look at engine codes.)

Razoring and futility are very old techniques. If they were responsible for most of the strength increase of Ippolit compared to previous engines, it would be fair to say that it was mainly new use of old tricks, proving they could be worthwile, and that this inspired others to reconsider those tricks as well in their own engines.

Selective generation of captures depending on futility margin is just a speed optimization that is an obvious benefit coming with bitboards. Even Spartacus (which is mailbox) generates captures victim by victim (in MVV ordering), and stops when it reaches futile victims. With 0x88 generating captures to a square is (per generated capture) much more expensive than plain move generation from the piece list, so there is not much benefit. But with bitboards, where you naturally intersect moves with target bitboards to get the captures, I would not really consider that a 'trick'.

[Don]

I disagree. The Fruit search code is very simple compared to Ippolit and its derivatives.

Yes, I agree. The search in Fruit is greatly improved with Rybka. But as a matter of record you are not adding hundreds of ELO over Fruit with some search tricks. We have made many gains in Komodo with search but none of them accounts for the massive improvement over the past several versions. If you already have a reasonable search implementation such as Fruit has you are not explaining 300 or 400 ELO with a few tricks.

I would estimate that you might get 100 ELO with every search trick seen in Rybka and revealed by Ippoli but as wonderful as Fruit was it needs a serious evaluation upgrade.

By the way, we have tuned the crap out of Komodo's LMR - but I could use a very primitive and simplistic version of it and get most of the benefit. The secret is always pushing for that 2 or 3 ELO difference. A simple and naive version of LMR would probably drop 20 or 30 ELO at most from Komodo. Once you have a reasonable implementation improvements come very difficult.

Some of the the things it lacks: razoring, static null pruning, the Ippolit trick of selectively move-generating captures based on futility margins, and as you note, singular extensions. Also futility pruning (at least in Fruit 2.0) is at depth 1 only. There are probably other differences, these are just some.

As far as I am aware, nobody recently has based an engine directly on Fruit except for GnuChess 6.

--Jon

[Don]

Some of the the things it lacks: razoring, static null pruning, the Ippolit trick of selectively move-generating captures based on futility margins, and as you note, singular extensions. Also futility pruning (at least in Fruit 2.0) is at depth 1 only. There are probably other differences, these are just some.

What intrigues me most in this list is the 'static null pruning'. Is this the same thing as what I interpreted as searching some classes of non-captures in the first few levels of QS, namely that it returns the current eval (i.e. stands pat) if the latter is above a certain limit when depth < 8 half-ply? This was indeed a thing I had never seen in any other engine. (Which doesn't mean that much, as I hardly ever look at engine codes.)

That is an old idea. My programs never did null move pruning on the last 2 or 3 ply but we always did something else to replace it.

Even to this day Komodo does what Rex did decades ago. On the last 2 or 3 ply we do a static analysis of what is attacked and use that as our margin - a lot more sophisticated that using a simplistic and stupid fixed margin. But it's perfectly acceptable to use a large forgiving margin to save the test if possible and we have always done that. Nothing new, been there, done that.

Maybe my idea qualifies as a new idea in computer chess? And if anyone else uses it should I accuse you of plagiarizing me? How stupid would that be? Ideas should not be "owned" but instead should be treasured and used.

Using pure margins is a win and ideal for a minimalist program like the ones you enjoy writing and the difference between doing that and what I am doing is not worth the effort unless you are fighting for every ELO point.

Razoring and futility are very old techniques. If they were responsible for most of the strength increase of Ippolit compared to previous engines, it would be fair to say that it was mainly new use of old tricks, proving they could be worthwile, and that this inspired others to reconsider those tricks as well in their own engines.

Selective generation of captures depending on futility margin is just a speed optimization that is an obvious benefit coming with bitboards. Even Spartacus (which is mailbox) generates captures victim by victim (in MVV ordering), and stops when it reaches futile victims. With 0x88 generating captures to a square is (per generated capture) much more expensive than plain move generation from the piece list, so there is not much benefit. But with bitboards, where you naturally intersect moves with target bitboards to get the captures, I would not really consider that a 'trick'.

Again, some very old program such as Kittinger's programs generated captures one move at a time, and some generated ALL moves one at a time. Maybe his did too. Komodo has a next move generator but internally it generates moves in phases. Hash table move and killers simply tested for legality without generation, captures generated separately - losing captures squirreled away to presented in their proper phase, etc.

All these great idea and Komodo just not using them.

[jdart]

What intrigues me most in this list is the 'static null pruning'. Is this the same thing as what I interpreted as searching some classes of non-captures in the first few levels of QS, namely that it returns the current eval (i.e. stands pat) if the latter is above a certain limit when depth < 8 half-ply? This was indeed a thing I had never seen in any other engine. (Which doesn't mean that much, as I hardly ever look at engine codes.)

Short answer is no.

Static null pruning is this code (from Arasan):

Code: Select all

#ifdef STATIC_NULL_PRUNING
    // static null pruning, as in Stockfish, Protector, etc.
    if (doNull && depth <= 3*DEPTH_INCREMENT) {
        const int margin = FUTILITY_MARGIN_BASE[depth]/2;
        int threshold = node->beta+margin;
        int eval = scoring.evalu8(board,threshold-1,threshold);
        if (eval > threshold) {
            return eval - margin;
        }
    }
#endif

(other programs may use different margins, and I have changed this a bit for 15.0).

Re the Ippolit capture pruning trick: I use this is the q-search but not elsewhere. I think it is somewhat dangerous. It is not quite the same as standard futility pruning because futility pruning normally applies a bunch of other conditions to a move, such as it being a non-checking move, etc. But the Ippo family is very aggressive about pruning.

--Jon

[jdart]

Agree the search differences are by themselves probably not worth 300 points. But the difference is still substantial. You can look at Toga, which had some search enhancements, and is measurably stronger (130 points in CCRL) than Fruit 2.1, which was the last Fruit release with source. Fruit 2.3 is close to Toga 1.4b - this was a version from Ryan Benitez. I do not know what he changed, but it was effective. (This also shows that Ippolit code is not necessary to improve Fruit, or the only way to improve it).

--Jon

[mcostalba]

So what are these new ideas?

I am not able to answer to HGM question because I think it is misleading. Ideas, ideas...but what are these ideas ?

Given for grant the chess engine knowledge freely available today from sites like cpw or from open source code the key point are not the ideas.

I am really convinced that to write a top engine today it takes 10% of effort to build-up an effective laundry list of publicly avilable techniques one wants to implement and 90% of effort to implement them. Of this implementation effort a good 90% is due to testing coverage and 10% is coding skills.

So to build up a top engine today you don't need "ideas" you need a powerful testing framework, a lot of time, a good programming background, and a good knowledge of what is already publicly avilable.

Sorry but there are no shortcuts here. This is what I believe.