Dynamic aspiration window

[Sergei S. Markoff]

Did anyone tried this idea?
Optimal aspiration window width probably depends on root score and depth. It should be wider if the absolute root score is higher and should be narrower for bigger depths.

[Henk]

I cannot even make safe aspiration windows work. Always giving strange and very severe blunders like giving pieces away. Probably has to do with that when time is up it doesn't do a research or maybe hash table cannot deal with these narrowed window boundaries. So I resigned.

[Dann Corbit]

Octochess iteratively adds 1/2 aspiration window width if the engine is losing and tries again:

Code: Select all

            // Search using aspiration window:
            value = result::loss;
            if( root_alpha == result::loss && d.m.sort != result::loss && max_depth_ > 4 ) {

                int aspiration = 10;
                short alpha = std&#58;&#58;max&#40; static_cast<short>&#40;result&#58;&#58;loss&#41;, static_cast<short>&#40;d.m.sort - aspiration&#41; );
                short beta = std&#58;&#58;min&#40; static_cast<short>&#40;result&#58;&#58;win&#41;, static_cast<short>&#40;d.m.sort + aspiration&#41; );

                while&#40; value == result&#58;&#58;loss ) &#123;
                    short value = -state.step&#40; max_depth_ * DEPTH_FACTOR + MAX_QDEPTH + 1, 1, new_pos, check, -beta, -alpha, false );
                    if&#40; value >= beta ) &#123;
                        if&#40; result&#58;&#58;win - aspiration > beta ) &#123;
                            beta += aspiration;
                        &#125;
                        else &#123;
                            beta = result&#58;&#58;win;
                        &#125;
                    &#125;
                    else if&#40; value <= alpha ) &#123;
                        if&#40; result&#58;&#58;loss + aspiration < alpha ) &#123;
                            alpha -= aspiration;
                        &#125;
                        else &#123;
                            alpha = result&#58;&#58;loss;
                        &#125;
                    &#125;
                    else &#123;
                        break;
                    &#125;
                    aspiration += aspiration / 2;
                &#125;
            &#125;

It's an idea a little bit similar to mate finder mode in some engines.

[Dann Corbit]

Stockfish:

Code: Select all

        // MultiPV loop. We perform a full root search for each PV line
        for &#40;PVIdx = 0; PVIdx < multiPV && !Signals.stop; ++PVIdx&#41;
        &#123;
            // Reset aspiration window starting size
            if &#40;rootDepth >= 5 * ONE_PLY&#41;
            &#123;
                delta = Value&#40;18&#41;;
                alpha = std&#58;&#58;max&#40;rootMoves&#91;PVIdx&#93;.previousScore - delta,-VALUE_INFINITE&#41;;
                beta  = std&#58;&#58;min&#40;rootMoves&#91;PVIdx&#93;.previousScore + delta, VALUE_INFINITE&#41;;
            &#125;

            // Start with a small aspiration window and, in the case of a fail
            // high/low, re-search with a bigger window until we're not failing
            // high/low anymore.
            while &#40;true&#41;
            &#123;
                bestValue = &#58;&#58;search<PV>&#40;rootPos, ss, alpha, beta, rootDepth, false&#41;;

...


                // In case of failing low/high increase aspiration window and
                // re-search, otherwise exit the loop.
                if &#40;bestValue <= alpha&#41;
                &#123;
                    beta = &#40;alpha + beta&#41; / 2;
                    alpha = std&#58;&#58;max&#40;bestValue - delta, -VALUE_INFINITE&#41;;

                    if &#40;mainThread&#41;
                    &#123;
                        mainThread->failedLow = true;
                        Signals.stopOnPonderhit = false;
                    &#125;
                &#125;
                else if &#40;bestValue >= beta&#41;
                &#123;
                    alpha = &#40;alpha + beta&#41; / 2;
                    beta = std&#58;&#58;min&#40;bestValue + delta, VALUE_INFINITE&#41;;
                &#125;
                else
                    break;

                delta += delta / 4 + 5;

                assert&#40;alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE&#41;;
            &#125;

[/code]

[Sergei S. Markoff]

For the last 4 or 5 versions of SmarThink I used 20 cp window. If the resulting value > upper bound, than +120 cp, the next step is +infinite.
If the value is < lower bound, I'm trying all other moves and if all of them fails, restarts with bound -40cp, than -80cp, -160cp and so on until -infinite.

I think it's something like the common approach.
But why 20cp? I think it's worth to explore search behavior and determine proper bounds based on fixed probability of failing high or low.

I just tried a very simple heuristic, based only on my assumptions.

Code: Select all

int eval_aspiration_coeff[64] = {
	246, 248, 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, 278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304, 306, 308, 310, 312, 314, 316, 318, 320, 322, 324, 326, 328, 330, 332, 334, 336, 338, 340, 342, 344, 346, 348, 250, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372 
};

int depth_aspiration_coeff[32] = {
	272, 270, 272, 268, 266, 264, 262, 260, 258, 256, 254, 252, 250, 248, 246, 244, 242, 240, 238, 236, 234, 232, 230, 228, 226, 224, 222, 220, 218, 216, 214, 212
};

// root_depth = root iteration (plies)
int GetBaseAspirationWidth(int root_depth, int current_eval)
{
	int result = ASPIRATION_WIDTH;
	int eval_index = MIN(63, intabs(current_eval) / 10);
	
	result *= eval_aspiration_coeff[eval_index];
	result *= depth_aspiration_coeff[MIN(root_depth, 31)];

	result /= 65536;

	return result;
}

Of course eval_aspiration_coeff should be probably sigmoidal, and all other values should be adjusted based on some research. Nevetherless it looks that despite it's simplicity and nearly random assumptions it works.

After 438 games I have +134-103=200 (of course it can be an error, let's see, but looks promising).

[Sergei S. Markoff]

Still better.
+397-331=580

[Ajedrecista]

Hello Sergei:

Code: Select all

[...]

int depth_aspiration_coeff[32] = {
	272, 270, 272, 268, 266, 264, 262, 260, 258, 256, 254, 252, 250, 248, 246, 244, 242, 240, 238, 236, 234, 232, 230, 228, 226, 224, 222, 220, 218, 216, 214, 212
};

[...]

May I ask why do you do 272, 270, 272, 268, ... instead of 274, 272, 270, 268, ... in this piece of code? Please take in mind that I am not a programmer but it looks suspicious to me, given the constant decreasing rate of the rest of the values.

After 438 games I have +134-103=200 (of course it can be an error, let's see, but looks promising).

Well, after 437 games with your provided info (+134 -103 =200), I get a measured Elo gain of +24.7 ± 24.0 Elo more less (with a confidence level of 95%), and a p-value (or LOS) of circa 97.8%.

Still better.
+397-331=580

With this update up to 1308 games, I get a measured Elo gain of +17.6 ± 14.1 Elo more less (with a confidence level of 95%), and a p-value (or LOS) of circa 99.3%.

It is a good start. Good luck!

Regards from Spain.

Ajedrecista.

[Sergei S. Markoff]

Hello Sergei:

Code: Select all

[...]

int depth_aspiration_coeff[32] = {
	272, 270, 272, 268, 266, 264, 262, 260, 258, 256, 254, 252, 250, 248, 246, 244, 242, 240, 238, 236, 234, 232, 230, 228, 226, 224, 222, 220, 218, 216, 214, 212
};

[...]

May I ask why do you do 272, 270, 272, 268, ... instead of 274, 272, 270, 268, ... in this piece of code?

Just a typo)))

It is a good start. Good luck!

Thank you!)

It will be interesting if anyone will try to add this code to Stockfish)

[op12no2]

I start with score +/- 75 and shrink by 3 each iteration. If there is a fail high/low I restart with +/- 750; probably in an attempt to minimise a series of fails - I can't remember!

source: http://op12no2.me/toys/lozza/lozza.js

lozchess.prototype.go

[Sergei S. Markoff]

Finally: +624-533=893. Probably it works.
I'm going to collect data for a more accurate model.