Aspiration windows

[crybotmark]

hi, I'm currently developing a chess engine in c++ (here is the github repository: https://github.com/crybot/NapoleonPP), it is called NapoleonPP (probably i will change the name...) and it is based on magic bitboards move generation.
I'm now working on the search and I've just implemented transposition tables, killer heuristic, history heuristic, quiescence search, iterative deepening, internal iterative deepening, null move pruning and some other small things.
Then I tried to implement aspiration search but with poor results. The fact is that the engine at some depth outputs stupid moves and the reason is because it evaluates equally all the legal moves (my evaluation function is still quite bad, but not so bad!) . Here is an example:

After 1. e4

This is the evaluation of all the black moves at depth 8:

Code: Select all

a7a5 -95
a7a6 -90
b7b5 -170
b7b6 -105
c7c5 -105
c7c6 -100
d7d5 -75
d7d6 -60
e7e5 -50
e7e6 -50
f7f5 -105
f7f6 -125
g7g5 -130
g7g6 -105
h7h5 -95
h7h6 -90
b8a6 -80
b8c6 -40
g8f6 -55
g8h6 -90

and this is the evaluation of all the black moves at depth 9 using the value from last iteration inside aspiration search:

Code: Select all

a7a5 -10
a7a6 -10
b7b5 -10
b7b6 -10
c7c5 -10
c7c6 -10
d7d5 -10
d7d6 -10
e7e5 -10
e7e6 -10
f7f5 -10
f7f6 -10
g7g5 -10
g7g6 -10
h7h5 -10
h7h6 -10
b8a6 -10
b8c6 -10
g8f6 -10
g8h6 -10

obviously for default the engine takes the first move because it doesn't find a max.

I use an aspiration value of 50 (which I do not increment or decrement for now) and this is my implementation:

Code: Select all

  while(...)
        {
            //            aspiration search
           //             first estimate of val is calculated outside the loop
            temp = searchRoot(depth, val - AspirationValue, val + AspirationValue, move, board);

            if &#40;temp <= val - AspirationValue || temp >= val + AspirationValue&#41;
                temp = searchRoot&#40;depth, -Constants&#58;&#58;Infinity, Constants&#58;&#58;Infinity, move, board&#41;;
            val = temp;

I do not think i'm doing something wrong here (am I?) and I'm sure alphabeta is working properly (the aspiration search doesn't work even without all other optimizations like TT, null move pruning, ecc.).

Could a small value for aspiration cause wrong moves? Shouldn't it just decrease performance?

Thanks all

P.S. sorry for my english, I'm italian

[Sven]

Hi Marco,

welcome to TalkChess!

The value of your AspirationValue constant should not cause this behaviour. It needs to be non-negative of course, everything else is a matter of different performance.

So it is actually a bug, and I'm pretty sure you will find it

I'd suggest that you print out more information about each subtree, e.g. the best white response move, the number of nodes searched in the subtree itself, and the alpha/beta window used for that subtree. I would also print some informative line for each call of your root search. Information like this might help to isolate the cause of the problem.

You already mentioned that the same behaviour also occurs with several search features disabled. For debugging a difficult error, sometimes it is necessary to work with a really minimal program that has almost no features that are irrelevant for the problem. I think this is an important technique. It helps since you don't have to look at the whole code all the time to search for potential problems, and in some cases it can also uncover a surprise, if you were "100% sure" that THIS component would have no influence - but if you disable it the problem goes away.

These are just some thoughts. Take whatever you feel appropriate from it!

Sven

[bob]

Hi Marco,

welcome to TalkChess!

The value of your AspirationValue constant should not cause this behaviour. It needs to be non-negative of course, everything else is a matter of different performance.

So it is actually a bug, and I'm pretty sure you will find it

I'd suggest that you print out more information about each subtree, e.g. the best white response move, the number of nodes searched in the subtree itself, and the alpha/beta window used for that subtree. I would also print some informative line for each call of your root search. Information like this might help to isolate the cause of the problem.

You already mentioned that the same behaviour also occurs with several search features disabled. For debugging a difficult error, sometimes it is necessary to work with a really minimal program that has almost no features that are irrelevant for the problem. I think this is an important technique. It helps since you don't have to look at the whole code all the time to search for potential problems, and in some cases it can also uncover a surprise, if you were "100% sure" that THIS component would have no influence - but if you disable it the problem goes away.

These are just some thoughts. Take whatever you feel appropriate from it!

Sven

Based on the scores, it sort of looks like he has the aspiration window set wrong, and it gets backed up to the root where it is accepted as is, rather than reducing it and trying again (a fail low appears to have happened since ALL scores are -10)..

Aspiration window is a bit more than just narrowing the root alpha/beta bounds. You have to be prepared to get an alpha or beta bound backed up which forces you to relax that bound and search again to get a real score.

I might not be understanding his output, but it certainly looks like that happened to a quick glance...

[Chan Rasjid]

Hello,

If, as you said, your aspiration search cause your program to output obvious dumb moves, then there is a simple way to just confirm if there are bugs unrelated to aspiration search.

You can try this. Do aspiration for all root moves with an estimated score (est_score) for the move with window (est_score - 1pawn, est_score + 1pawn). The estimate could just be the board material difference or the score from a previous iteration. If the search returns a score outside the window, then research with an infinite window (-infi, +inf).

If, with such a simple implementation, your program does dumb moves, then it is certain your search has serious bugs unrelated to aspiration search.

I think proper aspiration search is usually not as the suggestion I have just given.

Best Regards,
Rasjid.

[Sven]

and I'm sure alphabeta is working properly

After looking into your source - I'm sure it isn't

Please have a closer look at how you pass alpha and beta to the next level of search in searchRoot(). It should be "-beta, -alpha" but your current version is "alpha, beta".

Furthermore, please check another important detail of your alpha/beta algorithm. For both the PVS algorithm and the aspiration window technique you must use a fail-soft framework (otherwise you don't get scores outside the alpha/beta window) but as far as I can see you are using either fail-hard or a mixture of both.

Fail-Soft
Fail-Hard

Sven

[emadsen]

For both the PVS algorithm and the aspiration window technique you must use a fail-soft framework (otherwise you don't get scores outside the alpha/beta window).

Fail-soft is not required for PVS. You can use fail-hard and widen the window if the score falls on an aspiration boundary.

[Sven]

For both the PVS algorithm and the aspiration window technique you must use a fail-soft framework (otherwise you don't get scores outside the alpha/beta window).

Fail-soft is not required for PVS. You can use fail-hard and widen the window if the score falls on an aspiration boundary.

In your second sentence you are not talking about PVS but about aspiration window, right?

I agree that "must use fail-soft" is not correct, I should have written "it may be better to use fail-soft". My main concern was that Marco's search code I looked at seemed to be a mixture between fail-hard and fail-soft, by always returning a value >= alpha but not always <= beta. I might have misunderstood it, of course.

Sven

[emadsen]

In your second sentence you are not talking about PVS but about aspiration window, right?

Yes, sorry. I meant to say that fail-soft is not required for aspiration windows.

[crybotmark]

Hi.
Thank you all for your answers, I'm quite newbie, I actually started "studying" search by a few weeks.
I'm now sure there is a bug in my code (as many of you have pointed out) and I'll work hard trying to find it out. I didn't know what a fail soft/fail hard framework was. now I know, so thank you
If any of you have still something to say about my code (any advide is VERY welcome) please let me know your thought.
Thank you again.