Author: Vasik Rajlich
Date: 10:50:09 03/23/04
Go up one level in this thread
On March 23, 2004 at 11:04:15, Tord Romstad wrote: >This was an extremely interesting post, Vasik. Being a MacOS/Linux user >myself, I am not very familiar with Shredder, Junior or Fritz, but I still >enjoyed reading about you observations. > >On March 23, 2004 at 05:05:56, Vasik Rajlich wrote: >> >>True. What exactly the "Big Three" engines do is not 100% clear, however after >>considerable playing around I can make some observations/hypotheses. > >Precisely how do yo do when you "play around" to make such observations? >I find it hard to make any conclusions about how an engine works just >by watching its games and analysis. Well, I wouldn't really say that I have any "conclusions" :-). There are definitely some assumptions involved here ... > >>Shredder is the most aggressively tuned, and the "deepest" searcher. It's >>possible that it is not reporting its NPS rates truthfully, but assuming that it >>is, I believe that it shapes the search tree using aggressive pruning based on >>static tactical analysis. Of course, in principle there is no difference between >>selective search via pruning and selective search via extensions, the two >>approaches could be equivalent. In practice, however (and also for purposes of >>what I write here), selective search via pruning means that most moves get more >>or less the same depth, while "special" moves are tagged for a reduction, even >>if (as in Shredder's case) there are a lot of special moves. > >If I understand correctly, you define "selective by pruning" to be a search >where reductions are more common than extensions, and "selective by extensions" >to be the opposite? Yes. It's slightly artificial. I think extensions can be done more cheaply than reductions - ie less supporting static analysis is necessary. Another way to put it: extensions can be formulated more simply. Big speculation here of course, if this applies to a very mature engine with a very selective search. > >>Shredder's evaluation, given its NPS rate, is not especially good - not better >>for example than Junior's, despite the huge difference in NPS rate. It's harder >>to compare with Fritz's, because unlike Junior and Shredder, Fritz is much less >>aggressively tuned. Furthermore, Shredder, unlike Junior and Fritz, does >>considerable pre-processing. (By considerable I mean that it has a notable >>impact on the scores, of course there is no way to know the term count.) > >How do you recognize a pre-processor? Take a relatively static position, and let the engine analyze it to say 15 ply, noting the score progression. Then, clear the hash table, go to the position a few moves along the PV, and analyze again. Of course you won't get an exact ply-for-ply equivalence, but Shredder's scores will often differ by 0.5 pawns in fairly static positions. Shredder being a pre-processor suggests that SMK doesn't want an expensive eval. That raises the question of where the cycles are going. Incidentally, for Junior we have better data. Amir said that Junior started as a full pre-processor, gradually switched to less and less pre-processing, and now does no pre-processing at all. I have thought several times about doing some pre-processing myself, but never could come up with something attractive enough to implement. > >>What is notable is that Shredder, despite its huge pruning, and despite its low >>NPS rate, is very strong tactically. SMK's static analysis seems to be working. > >This is, to me, one of the most surprising and counterintuitive facts in >computer chess. It is relatively easy to do massive forward pruning and >reductions without losing much tactical strength, but very difficult to >do it without losing positional strength. > Not sure about "easy", but yes, agreed. Note that we're slightly corrupting the word "positional", since an attacking move could also be viewed as "positional". My impression of your search algorithm is that it will throw out some quiet positional moves, which get some square on the queenside, etc. >>Incidentally, Gothmog, in both evaluation and search, is closest to Shredder. > >In the sense of searching few nodes and still be relatively fast at some >kind of tactics, you mean? Or did you have something more in mind? > I meant in the sense of doing an expensive static analysis to guide a very selective search. (As opposed to Junior's very selective but fast search.) >>One nice thing about settling for a lower NPS rate is that you no longer need to >>worry about a whole slew of "minor" optimizations. > >Yes. I feel that I can do almost anything for free. No matter what I do, >my nodes/second count does not drop noticably. :-) > >>Junior also appears to have an extremely selective search, combined with an >>aggressively tuned evaluation function. Somehow these two are a logical >>combination. Aggressive pruning necessarily means overlooking some quieter >>positional moves - it's not always easy to avoid pruning those. It's much easier >>to avoid pruning positional moves which attack the king. >> >>Junior, however, appears to come at the problem of selective search via >>extensions rather than reductions. There are some extremely interesting >>discussions about this in the CCC archives. Amir has claimed that the best way >>to search selectively is via extensions. To complete the reductions vs >>extensions thought from above, an extension strategy will have the profile that >>most moves have the same basic search depth, while certain special moves will >>have a higher search depth. The profile of a search based on reductions compared >>to a search based on extensions will be different. > >I have to look up those old discussions. They sound really interesting. > >>One benefit of having a selective search based on extensions is that they are >>much cheaper to compute, you don't really need any huge static analysis to make >>sure you're not doing anything wrong. You just tune some basic extensions >>revolving around the basic themes: king attack, passed pawn, more forcing moves, >>etc. Junior takes advantage of this by emphasizing speed in the engine, >>apparently everywhere. Once you start emphasizing speed, it's hard to stop - >>every new optimization reveals a new bottleneck. The claim is that Junior spends >>10% of its time in eval, and Amir has posted a number of times about various >>optimizations. > >Only 10%? That's quite amazing! I think it's something like 65% for my >engine. Yes. Amir posted these here last November or December. The point is quite clear - there is no reason to do a big eval. Good != big. The only place where big makes some sense is in guiding the search through tactics. > >>Fritz is the most plain of these engines, I think it's more or less an optimized >>and tuned crafty, although with some slight pruning. Its evaluation is also much >>more quiet, which makes sense given its search strategy. When your search is >>more balanced (ie less selective), your engine will be better at finding and >>considering the subtle positional moves, but it will be at a huge disadvantage >>in the king-attack free-for-alls, where you just need to look deep and it's >>usually clear which moves you should be looking at. When Rybka plays against >>Shredder and Junior, it often just gets crushed, maybe somewhere in the >>neighborhood of half of the games. (At least, what a human would consider >>getting crushed.) Almost all games against Fritz go into the ending, where Fritz >>is, at least for a computer, quite strong. > >How does Fritz do against Shredder and Junior? > Actually, I never did this test. The SSDF results suggest slightly worse. >>One interesting thing to note about all three engines is that they are all very >>congruent. Their search strategies, evaluation strategies, and NPS rates make a >>logical package. Of course, this is important in every sport, not only computer >>chess. The best teams find some approach, and take it to the bank, game after >>game - while the weaker teams are stuck in various dilemnas. >> >>Another, more debatable, conclusion is that, given the margin between Shredder >>and the other two engines, Shredder's approach is best for computer chess. > >Yes, this is very dabatable. I think the top engines are so close that >we cannot yet decide which approach works best. Well, it's debatable just how close the top engines are :-) > >>What's important is the basic broad search depth, and you maximize it by >>pruning, which has to be backed up by extensive static analysis in order to >>minimize mistakes. >> >>Anyway, I hope the above is interesting. > >It is. :-) > >>It's just my impressions, probably the authors would correct me on some >>points. > >I hope they will, if only because it would be fascinating to see what >comments they have to our discussion. > >Tord
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.