Question for Bob Hyatt

[BubbaTough]

Oh, you're just referring to the fact that Rybka did not count the last three plies, on the grounds that they are highly selective. I don't think that this affects anything

Well, I would disagree with this. A number of programs do very aggressive pruning here, and they count the these plies. Therefore, Rybka is outputing less depth than others while doing the same thing. Keep in mind, I am not bothered at all by this.

the question is, at a given time limit, why is Rybka much less likely to change her mind than other programs? It doesn't matter what depth is reported.

Well, being a very fast, very well coded engine...better than all others by a large margin, it was getting much deeper in the same time than other programs (though it may not have looked that way because of the reporting). If my claim that going deeper stabilizes the pv, then in part the stabler pv can be explained by the extra depth.

Again, I am only talking about Strelka really, which I am confident does not have a super special search besides being really efficient. Rybka 2 and 3 I am sure are quite different.

-Sam

Just an example of what I am talking about.

If program A searches 12 ply, and outputs results a pv from depth 4-12 (chopping off the last 3 moves), and program B search 9 ply, and outputs a pv from depth 1-9, it seems obvious to me the program A will change its pv less. This is purely an effect of the depth of the search. And this may be what was happening with Rybka 1.

-Sam

[lkaufman]

Certainly rybka 1 (or Strelka) was getting much deeper in the same time than other programs, if you add back the 3 plies. The question is whether this was due just to "being a very fast, very well coded engine", or also to some important search differences. I think we can agree that Strelka outsearched other engines by 1-2 plies, which would mean about a three to one speedup if the only difference is how fast and well-coded they are. This 3 to 1 speedup and this explanation were also given by Anthony Cozzie. Nevertheless most programmers seem to feel that this is impossible, that at most maybe a 3-2 speedup could be explained in this way. If they are correct then some search difference must be the explanation.

[lkaufman]

I'd just like to add that when I talk about the PV changing or not, I'm mostly just talking about the actual move choice, which changes much less often in Rybka than in other programs. This is obviously unrelated to display issues.

[lkaufman]

We tried this in Doch for the very reasons you mention but it didn't work.

[BubbaTough]

Certainly rybka 1 (or Strelka) was getting much deeper in the same time than other programs, if you add back the 3 plies. The question is whether this was due just to "being a very fast, very well coded engine", or also to some important search differences. I think we can agree that Strelka outsearched other engines by 1-2 plies, which would mean about a three to one speedup if the only difference is how fast and well-coded they are. This 3 to 1 speedup and this explanation were also given by Anthony Cozzie. Nevertheless most programmers seem to feel that this is impossible, that at most maybe a 3-2 speedup could be explained in this way. If they are correct then some search difference must be the explanation.

I don't think I would go so far as claiming a 3 to 1 speedup...its quite possible for other parts of the program (such as eval) to effect tree size and therefore depth. I am just claiming the search was efficient, and not particularly special besides that. In any case, I believe my explanation that the extra depth coupled with not displaying the first several ply is a reasonable hypothesis addressing your original question, which was why the PV does not change much.

-Sam

[bob]

According to what you are saying, a program with more knowledge and a conventional search should beat Rybka 3. Both Deep Shredder 12 and Stockfish 1.6 probably have more knowledge than R3 (I'm not sure, it's just my impression) but still lose nearly 2-1 to R3. In any case, can you propose some simple changes that could be made to a conventional program, let's say one with a small eval, that would make it behave like Rybka in its concentration on the PV? We could perhaps find out by actual testing whether such ideas help or hurt.

There are lots of such suggestions. Extend more along the PV and limit the extensions more along non-PV branches. LMR already reduces more along non-PV branches (later moves). Some have suggested a "PV" extension that extends along the PV because it is the PV. So to start with, you end up with a pretty asymmetric search.

Secondly, you have to handle the cases where a deeply reduced/pruned/etc move looks good just because of the static evaluation, since the search won't be able to see deeply enough to see the tactical refutation. This one's harder. But if your eval is pretty static in nature, where small changes in the position don't produce large eval changes, this probably will work out by itself.

[bob]

We tried this in Doch for the very reasons you mention but it didn't work.

We tried this in Cray Blitz with some small successes, but the offset was _very_ small. I believe we last used something like 0.005 (we did millipawn evaluations in CB). The primary reason was to stop those PV changes for a score of +.001 improvement, which often was actually to a worse move based on simple static evaluation.

[lkaufman]

Much of this we've already tried. Pure PV extension seems to "almost" work, but not quite. I guess I'm looking for a suggestion that would make the program behave more like Rybka, especially in terms of sticking with the chosen move most of the time. As for reduced and pruned moves, I don't quite get your point. Reduced moves are re-searched if they look good, so they are not subject to the problem you mention, and pruned moves are gone, so they cannot be "too good". What case are you referring to?

[Albert Silver]

"The parameter tuning of material seems a neural network to me. the parameter tuning of the other parameters seems more thoroughly tested". Wow, I've never been called a "neural network" before, but I guess it's a compliment. All evaluation parameters (material and positional) in Rybka 3 were assigned by my intuition originally and then tuned by me for optimum results at roughly game in one second levels (not exactly the long time controls you thought)! It is rather miraculous that they work as well as they do in Rybka 3 at long time controls. It is impossible to tune evaluation features at long time controls, as most features are worth just one or two Elo points and it takes something on the order of 50,000 games or so to prove such small improvements.

My previous post regarding the use of NNs in backgammon was not replied to, so I am presuming I presented it poorly. The idea was simply the tuning of parameters for specific situations via NNs.

For example, let us suppose you are tuning for nuckies (NQEs - not quite endgames) as denoted in Flear's modern masterpiece, "Practical Endgame Play". You have decided to truly fine-tune the science of playing queenless middlegames with only 2 minor pieces at most per side, but want to have parameters tuned for each and every major combination. This would be a daunting task of tuning needless to say. Instead of even trying to do so, you set up templates for all the situations, and then use NNs to do the actual tuning. In backgammon this would be very easy as all NNs are trained at 1-ply depth, which is fundamentally different from chess. Rybka can probably search 5-6 plies in milliseconds (especially in such reduced material situations), so the training would be done thus, and you could train them reasonably well. Time would show how many games were required to reach reasonable results.

This was the essence of the concept.

Obviously, the above is merely the concept. You could create as many scenarios as you wished, the point being you could include far more situations to be tuned for than you would dream of if you had to do them manually.

[bob]

Much of this we've already tried. Pure PV extension seems to "almost" work, but not quite. I guess I'm looking for a suggestion that would make the program behave more like Rybka, especially in terms of sticking with the chosen move most of the time. As for reduced and pruned moves, I don't quite get your point. Reduced moves are re-searched if they look good, so they are not subject to the problem you mention, and pruned moves are gone, so they cannot be "too good". What case are you referring to?

A couple.

First, LMR (Late Moves Reduction) reduces moves that occur later in the move list, something that is not done to PV-type moves. So you search the non-PV moves much more shallowly than the PV moves.

Second, forward pruning (such as futility, etc) doesn't even reduce such moves, it just throws them completely away so that they never can become PV moves at all.

When I first added "history pruning" (now called LMR) to Crafty, the first thing I noticed was that our search became much more stable, with regards to the PV. If you remember the "Crafty goes Deep" paper Monty Newborn and I wrote, we discovered that we changed our mind about once out of every six times when we start a new iteration. Or, 5/6 of the time we stuck with the previous PV, 1/6 times we found a new one. Others confirmed this rate with other programs (Heinz, etc).

I attribute this to the way we search energetically on the PV, going out deeply, but spending less effort on non-PV moves since we reduce or even throw them away.

One simple way to add some hysteresis to the search would be to use the offset window. The higher the window gets offset after the PV search completes, the harder it will be for a new move to displace the original PV move as best. We tried 0.005 in Cray Blitz to avoid those deep thinks, only to see a +.001 eval increase, to a move that was ordered later in the move list. Often this move would be strategically bad (that's why the static eval ordered it late in the move list) and it would be nothing more than some sort of horizon-effect case where we'd play a bad move that did nothing other than hurt our position. If this window were set to +.05 or even +.1 on today's engines, they would still find ways to win material, but they would miss on the .05 positional increase they could have found without the window limitation.