Perhaps better than decreasing aspiration windows?

[vittyvirus]

Decreasing windows don't work well at higher depths for me. So, I tried doing this instead of decreasing window in Chesser:

Code: Select all

const int HighDepth = 9; // Modify accordingly
if (currentdepth >= HighDepth) {
    // At higher depths, the best move score will not change much
    const int SmallerWindowSize = 30;
    alpha = score - SmallerWindowSize;
    beta = score + SmallerWindowSize;
} else {
    const int WindowSize = 40;
    alpha = std::max(score - WindowSize, -LARGE_NUMBER);
    beta = std::min(score + WindowSize, LARGE_NUMBER);
}

You should've gotten the idea. And this got me at least 10-50% speedup...
In Stockfish, the idea is also not very difficult to implement:

Code: Select all

if (depth >= 5)
            {
							if (depth >= 15*ONE_PLY)	// Relatively high depth
							{
								delta = Value(10);
                alpha = std::max(RootMoves[PVIdx].prevScore - delta,-VALUE_INFINITE);
                beta  = std::min(RootMoves[PVIdx].prevScore + delta, VALUE_INFINITE);
							}
							else 
							{					// Depth < 15, use wider delta
                delta = Value(16);
                alpha = std::max(RootMoves[PVIdx].prevScore - delta,-VALUE_INFINITE);
                beta  = std::min(RootMoves[PVIdx].prevScore + delta, VALUE_INFINITE);
							}
            }

That's search.cpp around line 236.
What do you say?

[bob]

Decreasing windows don't work well at higher depths for me. So, I tried doing this instead of decreasing window in Chesser:

Code: Select all

const int HighDepth = 9; // Modify accordingly
if (currentdepth >= HighDepth) {
    // At higher depths, the best move score will not change much
    const int SmallerWindowSize = 30;
    alpha = score - SmallerWindowSize;
    beta = score + SmallerWindowSize;
} else {
    const int WindowSize = 40;
    alpha = std::max(score - WindowSize, -LARGE_NUMBER);
    beta = std::min(score + WindowSize, LARGE_NUMBER);
}

You should've gotten the idea. And this got me at least 10-50% speedup...
In Stockfish, the idea is also not very difficult to implement:

Code: Select all

if (depth >= 5)
            {
							if (depth >= 15*ONE_PLY)	// Relatively high depth
							{
								delta = Value(10);
                alpha = std::max(RootMoves[PVIdx].prevScore - delta,-VALUE_INFINITE);
                beta  = std::min(RootMoves[PVIdx].prevScore + delta, VALUE_INFINITE);
							}
							else 
							{					// Depth < 15, use wider delta
                delta = Value(16);
                alpha = std::max(RootMoves[PVIdx].prevScore - delta,-VALUE_INFINITE);
                beta  = std::min(RootMoves[PVIdx].prevScore + delta, VALUE_INFINITE);
							}
            }

That's search.cpp around line 236.
What do you say?

I've never seen that kind of speedup for ANY aspiration window width, much less just tweaking the delta value.

[jdart]

Doesn't make sense to me either, unless LARGE_NUMBER is very large.

I am not really sure either that it's empircally true that score variance decreases with increasing depth. But this technique is worth a try.

--Jon

[vittyvirus]

Doesn't make sense to me either, unless LARGE_NUMBER is very large.

I am not really sure either that it's empircally true that score variance decreases with increasing depth. But this technique is worth a try.

--Jon

Actually, for a engine like SF or Houdini etc, I see that eval varies much upto depth <10 or 15... But after, it doesn't vary too much _usually_. These engines reach 10-15 depth quite quickly, so this technique might give some speed ups. Also, I haven't tried tinkering with depth and value. But with depth >= 15 and aspiration delta = 10, my compile is able to get to search depth of 25 few seconds before the earlier compile did. Due to search instability, I can't report my results. And bench seems not to search for depth > 15, so the node counts are exact.

EDIT: To me, it seems that at higher depths, evaluation doesn't vary as much as it does at depth 10 or so. I agree that it's not true that after high depth, the evaluation varies less.

[jsgroby]

I may have missed something along the way, is Chesser your engine or an open source engine you started working on? Just curious? I thought you were working on a move generator during the second half of last year. Is Chesser that move generator?

Jeff

[vittyvirus]

I may have missed something along the way, is Chesser your engine or an open source engine you started working on? Just curious? I thought you were working on a move generator during the second half of last year. Is Chesser that move generator?

Jeff

Chesser is a complete chess engine. It's derived from winglet. And BTW, yes, I'm currently writing my sixth movegen for Yaka.

[elcabesa]

Decreasing windows don't work well at higher depths for me. So, I tried doing this instead of decreasing window in Chesser:
....

You should've gotten the idea. And this got me at least 10-50% speedup...

what do you mean by speedup? more knps or it will become faster to reach igher depth (less node searched)?

[vittyvirus]

Decreasing windows don't work well at higher depths for me. So, I tried doing this instead of decreasing window in Chesser:
....

You should've gotten the idea. And this got me at least 10-50% speedup...

what do you mean by speedup? more knps or it will become faster to reach igher depth (less node searched)?

Less nodes to reach higher depths. Pardon me for not being clear.