Search extensions

Code, algorithms, languages, construction...
Post Reply
ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Search extensions

Post by ppyvabw » Thu Mar 17, 2016 1:39 am

I'm not certain if I am implementing search extensions properly. Although my argument may sound very confused.

Admittedly, the testing for my changes is less than scientific at the moment, as it plays so badly, spending weeks waiting for it to play thousands of games seems a little pointless when it is obvious that it plays badly just after observing a few games against another engine. I have only a very simple search function, yet it is still very slow to my mind -- and writing a better search function would slow it down even more -- so I am primarily looking for more speed at the moment, rather than absolute playing strength.

At present, I extend pv nodes, passed pawns, mate-threats, capture-threats, captures and checks *wherever* they appear in the search tree. Then after doing some reading, I understand that Crafty only applies check extensions now, after it was observed that other extensions made no difference in playing strength. (That is my understanding, but I am happy to be corrected) So I got rid of all extensions except check extensions and extensions by 1/4 ply on pv nodes, and the play drastically improves! (Still by my own judgement after a dozen or so games, but instead of being annihilated after 25 moves by gnuchess, she made it to the time control after 50 moves with a pawn on the seventh rank(whereupon she crashed because of a bug in my time control stuff, which I have yet to fix))

Then it occurred to me, why would I even apply check extensions? The whole point of extending the tree is to avoid the horizon problem, but I deal with checks in quiessence. (so, if I enter quiessence in check, I have a separate block of code that handles it to examine all possible moves out of check).

Following that argument through, it only makes sense to me to extend the tree *at the leaves when there is an unresolved issue* -- so captures and checks are dealt with in quiessence so I don't need to explicitly extend them in the main search; and if I chose to extend passed pawns, mate threats, capture threats and singular replies, surely they too are only necessary at the leaves. So if, say, in a depth 15 search, there is a passed pawn at ply 4 which can be captured at ply 10, there seems very little point in extending to me. If, however the passed pawn is at a leaf, it is very much worth extending to make sure it can be prevented from promoting.

Is that correct?

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Search extensions

Post by H.G.Muller » Thu Mar 17, 2016 12:49 pm

Eventually the only reason to extend is that you see it improves playing strength. Reasoning about it can be tricky.

Search usually benefits from 'balancing' the various branches of the tree, i.e. not trying to waste effort on getting very reliable results (because of high search depth) on some of the moves, while the overall unreliability is dominated by other moves. Because safe checks are ideal delaing tactics (it is hardly ever possible to do something useful during the evasion), you often need more depth to see the same threats/opportunities in branches that contain the check. Searching checks in QS doesn't really help against this; the threat you are in danger of overlooking likely does not involve checks at all. And it is not certain at all that a check you can deliver now will still be possible to deliver (say) 10 ply from now, in QS, to push the loss over the horizon there too.

ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Re: Search extensions

Post by ppyvabw » Sat Mar 19, 2016 2:17 am

Ok, thanks for your reply. I think I am being a bit blinded by my ambition for my engine to get to a similar nominal search depth to the engine I am testing against, which is probably akin to comparing chalk and cheese.

So, I think I will probably just forget about that obsession, tie up a few loose ends in my evaluation function and interface and get some proper testing done.

But how do I do that though? How do I get several thousand games under my belt each time I make a change?

User923005
Posts: 616
Joined: Thu May 19, 2011 1:35 am

Re: Search extensions

Post by User923005 » Sat Mar 19, 2016 4:13 am

Test at high speed using an interface like cutechess-cli

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Search extensions

Post by H.G.Muller » Sat Mar 19, 2016 11:11 am

ppyvabw wrote:Ok, thanks for your reply. I think I am being a bit blinded by my ambition for my engine to get to a similar nominal search depth to the engine I am testing against, which is probably akin to comparing chalk and cheese.
Nominal search depth doesn't mean anything. My engines beat many opponents that have double the nominal search depth. Nominal search depth most and for all is an indication of how much the engine lies about its depth...

Also note the importance of realistic evaluation. Better search can be counter-productive if you badly misevaluate. It would just make the engine more clever in digging its own grave.

Post Reply