Limiting extensions

[vladstamate]

Hi all,

I am currently extending the depth I am searching to by 1 ply when there is a check, a promotion or we are entering in a pawn only ending. I found out that if I am not limiting how many times I extend the search in positions like the one from http://talkchess.com/forum/viewtopic.php?t=33338 the search tree explodes, and my engine kind of gets stuck around depth 9.

So I put a limitation in: I can now limit the number of extensions depending on the overall search depth. So lets say I am currently searching depth 8 in ID and I have limitation=50% then I only allow 4 extensions in the same line. Kind of like this:

Code: Select all

root()
    numberExtensions=0

search()
    gen moves
    etc...
    for all moves
        make move
        ext = extendPos();
        if ext
            if(numberExtensions>maxAllowed)
                ext=0;
            numberExtensions+=ext

        search(..., depth-1+ext)

        numberExtensions -= ext

Question: It seems like while this kind of works allows extensions to happen towards the root and not towards the leafs. What other techniques there are for limiting extensions, so that your search tree does not, for lack of a better word, explode?

Regards,
Vlad.

[LiquidNitrogenOverclocker]

I remember Crafty had a great little formula for determining how much to curtail or extend as a function of the iteration, the present depth, and one other parameter I can't recall.

When I implemented that formula to handle the Gothic Chess search extensions (a much more tactical game, observe this game

http://www.gothicchess.com/animated_html/0000001.html for example!) the tree was trimmed very nicely.

I tried to manipulate Dr. Hyatt's search extension formula, but everything I tried made the game tree larger.

He can probably find that code snippet much more quickly than I can.