Computer Chess Club Archives


Search

Terms

Messages

Subject: The man behind Rybka and his thoughts as posted here on CCC.

Author: Mike Byrne

Date: 16:24:30 12/31/05


Vasik Rajlich , chess programming superstar in the making, has offered many of
his ideas on chess programming here on CCC - prior to his release of Rybka.

What follws are his words extracted from the CCC archives.  Interesting stuff as
it provides clues into how he programmed Rybka.

=========================================================================
"Interesting. You could also prepare some data structures in the positional
search and use them in the tactical search, a sort of root-node pre-processing
repeated in mid-search.

What I'm curious about is, how expensive is a really heavy evaluation? I've put
into my engine a rather bloated eval and some conservative rules for doing only
lazy eval and still the eval takes up barely over 50% of the total search time.
This number seems hardly worth reducing - even reducing it to zero would only
double the nps, which is less than half an extra ply. It seems much more
important to improve the eval and to guide the search better than to worry about
a factor of 2 in the nps.

Maybe I underestimate the size of a really good eval. (Mine is about 4 months
old.)

Vas
"
==============================================================
"
This appears to be true for shallow searches. I've noticed that with very
shallow searches (like four or five ply) my program wants to play all sorts of
positionally weak moves which it doesn't want to play any more at seven or eight
ply. It seems that this also applies to extending deeper searches, according to
for example the SSDF results for different hardware. Clearly, a higher nps is
good.

I am just wondering where exactly the line lies between maximizing speed and
adding knowledge. Considering the following hypothetical engines:

engine A - spends 10% of its time in eval
engine B - spends 67% of its time in eval

Engine A will have a 3x higher nps, so it will do slightly more than 1/2 ply
extra. Engine B will be spending 20x longer evaluating each position. It seems
that engine A will gain around 50 rating points from its deeper searches (at
least at time controls long enough that engine B can also make it to 8 or 9
ply). It's hard to believe that a few accurate eval computations couldn't
compensate for this.

This would suggest that generally speaking it's quite acceptable to have some
expensive computations in the eval, provided you stay within some sort of an
acceptable limit, say not more than two-thirds of total search time.

Vas
"
======================================================================

"True, an evaluation which is both accurate and fast is ideal

It would be interesting to know the exact profile of the time spent in eval of
the top programs. As I rememember Amir said that Junior spends "less than 10% in
most positions". Does this mean a lot of lazy evals and some very big evals? Or
a truly small evaluation which pinpoints the most important features of the
position and ignores the rest.

In many cases, you arrive in eval needing only to show that the non-material
factors can't add up to more than X. (ie X = material score - alpha, or beta -
material score.) As X gets higher and higher, more and more things could be
ignored. Maybe some sort of a pinpointed lazy eval is the answer.

It seems to me that the areas where an engine can get the most benefit are:

A) Guiding search (ie reducing/extending): very very high
B) Quality of eval: very high
C) Overall speed, including speed of eval: medium/low, unless very big factors
are involved, such as building specialized hardware or getting a chance to run
on a big mp machine

On the other hand, "A" and "B" are quite vague, you never really know if what
you did was an improvement, while "C" is very easy to measure.

Vas
"

==============================================================
"
Hello,

It seems to me that there is a way to deal with this.

Let's say you're at node A going to node B. You can statically evaluate node A,
statically evaluate the move (A->B) in the context of node A, apply the
appropriate reduction/extension, and enter node B with the already
extended/reduced search depth. In this case, node B will go into the hash table
with that new remaining search depth.

If I understand the issue correctly, you'd also like to statically evaluate node
B before deciding on the reduction/extension for move (A->B). However, I am not
sure that that is necessary.

Let's consider the typical node which is a candidate for reduction. It should
have one of two qualities: A) it is extremely static B) it looks unpromising, ie
score somewhat below alpha.

In the case of very static nodes, it's pretty clear that you shouldn't need to
also look at the next move/node. In the case of an unpromising node, I was
thinking that you could do something like identify the few factors which could
change the evaluation. For example, if you're down two pawns but there are some
vague attacking prospects, then king safety would be that factor, and moves that
attack the king would be extended/not reduced, while moves which attack pawns on
the queenside are reduced. If you have an advanced passed pawn, then pushing
that pawn or supporting its advance would be the one way to bring the score
back, and moves which support that would be extended/not reduced. In all of
these cases, it seems to me to be enough to only consider the original node
(node A) and the moves themselves. The static evaluation of the next node can
then be done already knowing the new depth.

Unfortunately I haven't started to implement this, so there might be some issues
here.

At any rate, any reports on your experience in implementing this are welcome.
There appears to be almost nothing in the chess literature about this. The best
I found was Ed Schroeder's description of the pruning in Rebel, but he
concentrates on pruning positions with very bad scores rather than on pruning
irrelevant moves.

It does also seem to me that this is "the key" to a good program, or at least
that it could be "a key".

Vas
"
======================================================================
"
I don't know how much luck you had with the initial debugging of your program.
In my case I had to do some really tedious debugging involving stepping through
the tree node-by-node. One quite funny bug I had was occurring in the search
after 1. e4 e5. My program was analyzing the nonsense variation 2. Nf3 Nc6 3. d4
Bb4+ 4. Bd2 Nf6 5. Nxe5 Nxe4 6. Nxc6 Nxd2 7. Nxd8 Nxf1+ - and crashing.
Actually, from a computer chess point of view, this is a perfectly normal
variation I think, I doubt that there is any sense in trying to prune it.

Basically, if you're going to search several million nodes, you will look at a
lot of junk. The point of a smart search, as I see it, is to try to somehow
increase the relevance of the variations very very slightly, maybe into the 0.1%
range, rather than 0.05%. This means that you can invest some of your available
nodes into some various "lottery tickets" variations, ie. probably won't work,
but you never know.

Re. Qxf7, as you pointed out, the investment won't be so high because you will
be failing low throughout the entire resulting search. It will be even cheaper
than that because:

1) It will fail low right after an immediate null move.
2) It removes material from the board, further reducing the branching factor for
that variation.
3) It creates a big material imbalance so you may be able to A) use lazy eval in
the subtree B) make some reductions later in the tree once things quiet down.
(For example, a quiet move with a big material deficit can be a reduction
criterion.)
4) There are only two replies, again reducing the cost.

It seems that a reduction/extension mechanism shouldn't be trying to figure out
which moves are actually good. It should be trying to figure out which moves are
worth searching, based on:

1) The very small chance that those moves will eventually be in the 0.001% of
moves which are either part of the PV or force a change in the PV, rather than
one of the 99.999% which could have been skipped.
2) The expected cost of the search.

Cheers,
Vas
"
========================================================================
"I more or less agree with this, but there is one caveat: when you first begin,
you have to decide whether to use bitboards or not. If you don't, you'll never
switch to them without a complete rewrite. Based on my experience so far I would
strongly recommend using bitboards. They are not that complicated, they were not
so difficult to debug (as I had slightly feared), and quite a number of
evaluation terms can be very elegantly & efficiently expressed with them.

For example, I use a bunch of precomputed masks to test for various pawn & piece
configuration around the king. I have offline code which precomputes each of
these masks, and creates a .h file of "const BitBoard weak_sq_g4_p = 0x..", and
when each of these is used in eval the compiler will substitute it at compile
time.

Vas
"
=========================================================================
"I have the theory that the greater your search resources (ie combination of
time
and hardware), the less important is the search, and the more important is the
evaluation. I have played around quite a bit with various extensions recently
and they usually are quite good in testsuites, but not at all clear in real
games. It's very easy to have side effects from extensions. At short time
controls, you need to use extensions and reductions in order to pay special
attention to tactics, to avoid getting killed tactically. At some point, though,
you can search enough nodes that the tactics are naturally taken care of by a
plain search, which also naturally takes care of good positional play.

Of course a good clever (ie extending & reducing) search must always be better.
Just something to keep in mind - in the future, hardware will improve, and the
most important games will always have longer time controls and bigger hardware.

Vas
"
=====================================================================

There's much more there too -- I just selected teh more interesting (for me)
tidbits.

Best,

Michael





This page took 0.05 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.