Not logged inRybka Chess Community Forum
Up Topic Rybka Support & Discussion / Rybka Discussion / a question of search
- - By onursurme (***) Date 2008-08-09 20:56
In a given position, we start Rybka in infinite analysis mode.
There is a 7-depth tactical shot for that position.
Rybka, after reaching depth 10, still isn't aware of the tactic.
But, we don't stop her, and she continue to search.
We think that Rybka thought that (yes, she can think :) ) the line which lead to that tactic isn't worth calculating for, and she choosed to use her time for other moves.
Now, questions :
1) Can we say that Rybka will certainly revisit the tactical line she omitted before and find the tactic (off course if we give her enough time) ?
The other possibility is that she will never find that tactic even she runs for years.

2)If the answer to question 1 is Rybka may not revisit the line and it is possible that she can't find the tactical shot even you give her infinite time, is there any engine which can do this?
Parent - - By likesforests (**) Date 2008-08-09 21:43
Can you post the position in question?
Parent - By onursurme (***) Date 2008-08-09 22:21
This question isn't about a specific position.
This happens frequently.
Parent - - By Vasik Rajlich (Silver) Date 2008-08-10 07:12

> Can we say that Rybka will certainly revisit the tactical line she omitted before and find the tactic (off course if we give her enough time) ?


Yes. Search is basically a matter of prioritization - given enough time, Rybka will find everything.

Vas
Parent - - By BigBen (****) Date 2008-08-10 07:39

>given enough time, Rybka will find everything


I cannot seem to find my car keys this morning and Rybka is not helping one little bit :) ;)

Regards
Parent - By Banned for Life (Gold) Date 2008-08-10 07:43
Rybka 3 is also not cleaning my office, but I think that wasn't scheduled until Rybka 5...

Alan
Parent - By Dragon Mist (****) Date 2008-08-10 13:04
This needs to be added to FAQ, too. :-)
Parent - - By Pablo Vazquez (*) Date 2008-08-10 12:58
Do you mean that all the pruning in rybka is safe?
Parent - - By grolich (***) Date 2008-08-10 13:07
This can hardly be called "safe" unless you REALLY have infinite time for analysis.
Sometimes Rybka won't go back to the previously pruned line even many plies deeper into the search.
It just means that at some point in the future, this line will be revisited. Maybe in 3 plies, maybe in 6, maybe in...

It simply makes a lot more sense than just throwing it away forever.
Makes it safeR, even if not completely "safe".
Parent - - By Pablo Vazquez (*) Date 2008-08-10 13:56
There are some engines that will rarely miss tactical shots even if you give them infinite time. This is caused by unsafe pruning, (for example null-move pruning in zugzwang positions). So unless you have seen rybka's code, I don't know how you can be so sure that rybka will suddenly, with enougth depth, decide to stop pruning something that she pruned before.
Parent - - By grolich (***) Date 2008-08-10 16:31
I assure you, I'm not a clairvoyant.

However, Vas has already answered questions on this topic before on this forum:)
Parent - - By Pablo Vazquez (*) Date 2008-08-10 17:57 Edited 2008-08-10 17:59
I think you are talking about reductions, those will always be safe, although they might delay a tactical shot some iterations. But the only completely safe pruning i know of is alpha beta.
Parent - - By grolich (***) Date 2008-08-10 18:26
Allow me to elaborate.

This a bit risky, because as you have said, I don't know Rybka's code, but I believe I have a pretty good idea as to how this is managed
(once again, Vas, this is how I perceive these issues, correct me if I'm wrong please):

The idea is this:

Alpha beta is a type of pruning called "backward pruning", and is relying solely on search knowledge already available. As you have mentioned, it is 100% safe.

Another type of pruning is sometimes called "forward pruning", in which a variation can be "pruned out" based on either evaluation or partial search knowledge (or both). This, in itself, can be "unsafe", in your terminology.

However, This view misses a very important idea about forward pruning:

IT doesn't have to COMPLETELY prune out ANY line.

The whole idea of pruning is to let the search focus more on what it (or the evaluation) perceives as the more important lines (using selection), by not having to spend time on seemingly inferior lines? But, this begs the question, what if it is wrong? what if the variation pruned out at depth X is a good one? There's a relatively easy way out of this:

An engine wants to "prune out" a line. It must have an idea of just how bad it believes the line is. It then stops searching it FOR NOW, but the pruned out line does not get thrown away. It just gets a a lower priority, depending on just how bad the engine believes the line is.

The priority can, for instance, be given on a depth basis (although I'm sure there are many other ways, and I have no idea which way Rybka uses).
So, at depth d, a pruned out line can, for example, be given the same priority as lines of depth d+5, and it will be discarded until that depth is reached (probably depth is not the only criteria used though, and I'm sure the value can change again the line is actually examined again).

If done well, this can lead to pruned out lines being reexamined having a very small effect on the search time, because by the time you reach depth d+5 (or d+<other_depth>), the number of pruned out lines from depth d is extremely small (at certain reasonable depth differences, it may be negligible) compared with the number of lines at depth d+5.

People are used to thinking about pruning in the pure sense of the word. But I don't think that's how things are (or should be) done.
Forward pruning can mean simply: "pruned for now" (is pruned from being searched with other lines of same base depth).

Hopefully, Vas can reply to my (or your) post with more accurate information than I can ever hope to have about Rybka.
Rybka's pruning has always been a partial mystery to me.
For example, I wonder if there is any limit to how deeper you can get in the search before a previously pruned out line is reexamined.
Parent - - By Vasik Rajlich (Silver) Date 2008-08-11 20:49
Rybka never "prunes" anything completely, she just emphasizes some things and de-emphasizes others.

Vas
Parent - By grolich (***) Date 2008-08-12 04:16 Edited 2008-08-12 04:21
I thought that was the case.
That DOES seem to take everything I've written and congest it down to 2 lines (nice compression) :)

But I wanted to give an example of how I think it works.

I also wasn't completely sure...
Thanks.
Parent - By Roland Rösler (****) Date 2008-08-10 20:19
For sure; and lines which meet at infinity are called parallel! :-)
Parent - By onursurme (***) Date 2008-08-11 18:05
Are other top engines same in this regard ?
Up Topic Rybka Support & Discussion / Rybka Discussion / a question of search

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill