Thanks for the tip, that's nice.

I find the manuals very readable, actually. We had some memory access problems in late 2006 or so with the then-new Intel machines, and one of those manuals with a huge title pretty much had everything I needed about the topic.

Vas

> By the way, the paper doesn't seem to mention what year the given two-fold speedup was

I think the time in quote is about 2002, when GMP 4.1 came out. [I can ask Zimmermann if you really want to know].

All the speed in GMP is still at the assembler level. You can build the "generic" code (no assembler support), and I think you'll get something about 4 times slower. [Unfortunately, I'm having problems testing this]. Indeed, Granlund has been trying to get "vendor sponsorship" from AMD (and others) to include his assembly level optimisations in the GMP distro - a fork has been resisted, but most people use, say, the patches of Gaudry, which, while maybe 10% slower than Granlund's (non-public) code, are still nearly twice as fast as the general ix86 code when used at the bottom level of GMP. [As an example, see the "Optimal" column versus "GMPbench" in the table here].

>I'm not all that sure your first optimization is a win

As I say, the proof would be in the pudding...

> CPUs do _much_ more intelligent branch prediction than just simple yes/no

No matter how intelligent they are [I might agree with much, but not with its underlining] it cannot be a bad idea to reduce randomness in the input - the only question is whether code sprawl would become a worry.

> and the fact that the last branch is almost never taken

You could just simply ignore the while loop over the 3rd and higher bishops - in almost all positions this will not matter. My impression is that a 100% predicted branch should be nearly a NOP, at least when the condition is simple as here - on the other hand, avoidance of it would also allow a gain from avoiding the preceding BTR. There is also the issue that (say) the PHENOM has counters for only 3 branches per (aligned) 16-byte block.

> the Pentium needed at least seven cycles for BTR

BTR is 2 cycles on the PHENOM (assuming mask is in a register) -  see Table 13 in Appendix C here. Also, DEC/AND has pipeline dependencies, in that you are ANDing with the result of the DEC [my impression is that this doesn't matter, but getting AMD and especially Intel to be specific about the vagaries of micro-op decoding is a bit difficult]. Both BTR and DEC/ADD should be 2 bytes in opcodes, though I think DEC might itself become two bytes in 64-bit mode (here is the AMD info; see Table A-2 on the 48-4F row for DEC, with footnote 5 giving the info about REX in 64-bit mode, so the DEC becomes FF/1 with the ModRM extension). Finally, DEC/AND uses 2 registers instead of one.

i just wondered if we mentioned clones here, if the whole thread would be moved to another place.

The true inventor of LMR was Stefan Meyer-Kahlen, of course, which is why S7-S9 completely dominated the computer chess world.  But Fabien gets credit because he published his work.  Stefan didn't, and random message board discussions certainly do not count.

I will also have to assume that you haven't done much programming in C, because you are really underestimating just how great of an optimization job is in Rybka.  Look at Fabien's own statement: He thought that Fruit could be optimized by 25%, not 200%.

cheers,

anthony

The average between opening evaluation and endgame evaluation based on the stage of the game was new for me.
I do not care if it was used by other programs in the past because I did not know it.

I also do not agree about definition of new.
If a chess player plays a strong move that was played 100 years ago and was evaluated wrongly then claiming that the player found nothing new is wrong.

The player found that the move that was played 100 years ago is a strong move and the same is about fruit.
Finding that it is good to use some combination of ideas that were suggested in the past is not finding nothing.

It is not something obvious otherwise other programmers could also do it and it is a fact that the commercial programmers at the time of fruit2.1 did not do it(otherwise they could easily be above the level of fruit together with their own ideas.

Uri

I think this is not his point. It is rather sport versus science. Do you think Leibniz or Newton had any idea how important differential calculus would be 500 years later? There are countless examples where a scientist is driven by pure curiosity - and in the end he found something completely new and useful. 
Academic Science is about inncocent curiosity (innocent in terms of not thinking about profit or usefulness but only about the beauty of thought). This is the difference to industrial research.

What about chess? Is it useful? Does it improve mankinds situation? Does it help to create a better world? Of course, one can use some far-fetched arguments like "trains your mind" and so on, but there are many chess lovers who do this mind-sport due to the intellectual challenge, the search for amazing ideas, for joy without thinking about 'usefulness'.

I cant blame A. Cozzie for his point of view. Even though he seems not to care too much about Zappa (this might be vanity), he created one of the strongest engines. I think this competition stimulates the development of chess engines further. Maybe Rybka 3 would not be as strong as it is according to L. Kaufmann if the defeat in Mexico would not have taken place.

Is search important or evaluation more important?   That has been the question forever in computer chess ... which is more important.  The truth is that it is a combination of both ... and this is also true in human chess.  Unlike what most people think, the biggest difference between a strong player and a weak player is tactical ability which would equate to search in the case of computer chess.  Even a weak player will know to put his rook on the open file ... but a strong player will know that he is looking at that and might see a stronger move that works tactically.  I would equate that to a weak player having poor eyesight and a strong player having great eyesight.  Put glasses on the weak player (such as allow him to check his moves tactically with a computer first) and he will play very strong and maybe even stronger than the strong player.  This is why in many cases a nominal player will be able to compete with even the strongest GM if he has computer assistance ... even it the GM is allowed to have equivalent hardware to also check his moves.  We see this all the time in the freestyle events.  So in the end it is a combination of fast search and good evaluation that matters.

Also I am not so sure that all there is with Rybka is fast search.  Obviously much more is there.  If Rybka gets a 3X speed advantage that would mean that Rybka on 3X slower hardware handicap should be performing equal to Crafty or Fruit.  It would be interesting to put this to a test .... Rybka on say an Athlon 1.2Ghz against a Quadcore 3.2Ghz Crafty.  That would probably be around a 10X speed difference ... yet I think Rybka would easily come out on top.  I have a lot of respect for Anthony but I think he still hasn't seen all there is to see in Rybka.  The evaluation function in Zappa is great ... and in some cases superior to Rybka ... but in the majority of the games I see, Rybka has much better evaluation.  I think people way underrate the value of evaluation tables that are in Rybka ... these have been honed down with thousands of games ... they have been tested and slowly improved and seem to add tremendous knowledge to Rybka.  They are not perfect and probably will never be ... but they definetely are right more times than any other program.  So a combination of faster search with superior evaluation is what makes Rybka strong.

Rybka can still improve quite a bit I think.  Multiprocessor efficiency is still a work in progress and can only improve.  Also a better implementation of endgame tablebases (such as implementing bitbases) would allow Rybka to have all 6 piece EGTB's (and some 7) without any drop off in nps.  As more and more cores are added to CPU's ... being able to efficiently make use of these cores will be paramount to progress.  IMHO the way to do that is to develop the engine in a way where you split the engine into seperate independent modules on independent motherboards ... each module would be extremely good at a specific aspect of the game ... opening ... middle game ... tactics ... positional accuracy ... and ofcourse endgame play.  Then you would have communication between these modules and an algorithim that would change dynamically during the course of the game that would set a system to what move to choose and from which module.  While communicating between these seperate modules would probably have a large latency hit ... if it works and I am sure it would work ... a quick adaptation of these cores on a single machine with many cores would immediately remove the latency hit and thus give you a performance boost.