An unstoppable passed pawn

[bob]

There are some things you can't reasonably expect search to resolve. As a human I ask "does my opponent have anything that can prevent this pawn from queening? This includes square of the king rule for K+P only endings, if there is a piece left, I only consider if it can attack a square in front of the pawn before the pawn gets there. If we both have a piece it gets more complex in that if I can attack a square my opponent's piece needs to reach a cutoff point, it can't get there. A good idea would probably be hybrid, some sort of "uncertainty" score that can drive the search a bit deeper without blowing up the tree, and some sort of approximation to the score so that the eval can take over as things become slightly clearer.

It is not that easy, trust me...

I trust you. But when I looking trough the code of Stockfish (evaluate passed pawns, pawns), I think that it would be better cut and cut many doubt lines and go deeper, like you wrote. In my opinion, engines should be only stimulated, when I see many orders (high bonuses and penalties). Sometimes I am watching play of Stockfish and think how does it fight with them?
It is only my personal impression, maybe I feel badly.

The problem is tree explosion. If you reach this position in an unimportant variation, and spend many seconds trying to figure out whether the pawn can promote or not, you can end up losing by not going deep enough on the real best move. This is a classic tightrope, sort of like "Goldilocks and the three bears." It has to be "just right" or it has dire consequences. As a general rule, given the choice of searching too deeply or too shallowly, you have to err on the side of going too shallow, since the tree is exponential and going too deep can blow up the search tree and the time required to do the search.

[bob]

Your last sentence is the important. There is always point and counterpoint. Obviously if you add knowledge correctly, it improves skill and Elo. But also, the _cost_ of the knowledge (computational cost) has to factor in, and often this cost is more than the gain. You get better in the positions where the knowledge is critical, but you get worse in positions where the knowledge is not important yet the cost is still present and slows you down.

[mcostalba]

The ELO gain in implementing this rule seem to be not that large, but I'm sure there is one.

I guess you refer to this patch, correct ?

Code: Select all

        // If the other side has only a king, check whether the pawn is
        // unstoppable
        if (pos.non_pawn_material(Them) == Value(0))
        {
            Square qsq;
            int d;

            qsq = relative_square(Us, make_square(square_file(s), RANK_8));
            d =  square_distance(s, qsq)
               - square_distance(theirKingSq, qsq)
               + (Us != pos.side_to_move());

            if (     d < 0
+                || (ei.attacked_by(Us) & squares_in_front_of(Us, s)) == squares_in_front_of(Us, s))
            {
               ... 

Have you tested the patch with real games ?

Now we are in the middle of a regression hunting session, so we don't have any resource to look at it. But in case you have tested and patch is positive for you I will give it a try.

[Ralph Stoesser]

The ELO gain in implementing this rule seem to be not that large, but I'm sure there is one.

I guess you refer to this patch, correct ?

Code: Select all

        // If the other side has only a king, check whether the pawn is
        // unstoppable
        if (pos.non_pawn_material(Them) == Value(0))
        {
            Square qsq;
            int d;

            qsq = relative_square(Us, make_square(square_file(s), RANK_8));
            d =  square_distance(s, qsq)
               - square_distance(theirKingSq, qsq)
               + (Us != pos.side_to_move());

            if (     d < 0
+                || (ei.attacked_by(Us) & squares_in_front_of(Us, s)) == squares_in_front_of(Us, s))
            {
               ... 

Have you tested the patch with real games ?

Now we are in the middle of a regression hunting session, so we don't have any resource to look at it. But in case you have tested and patch is positive for you I will give it a try.

I have tested the below code with 20,000 1 sec self play games (slow machine, Athlon Dual @2400GHz). Result was ~51,8% pro patch. BTW I have not tested against SF 1.7.1 but against a bug fixed version of SF 1.7.1 (static threat bug + open file bonus bug fixed). HTH.

Code: Select all

        // If the other side has only a king, check whether the pawn is
        // unstoppable or whether it's path to the promotion square is protected
        if (pos.non_pawn_material(Them) == Value(0))
        {
        	// is the pawn's path to the promotion square protected?
        	if ((ei.attacked_by(Us) & squares_in_front_of(Us, s)) == squares_in_front_of(Us, s))
        	{
        		int mtg = RANK_8 - relative_rank(Us, s);
        		mtg += count_1s_max_15(squares_in_front_of(Us,s) & pos.occupied_squares());

        		if (!movesToGo[Us] || movesToGo[Us] > mtg)
        		{
        			movesToGo[Us] = mtg;
        			pawnToGo[Us] = s;
        		}
        	}
        	// is the pawn unstoppable?
        	else
        	{
        		Square qsq = relative_square(Us, make_square(square_file(s), RANK_8));
        		int d =    square_distance(s, qsq)
            		     - square_distance(theirKingSq, qsq)
            		     + (Us != pos.side_to_move());

        		if (d < 0)
        		{
        			int mtg = RANK_8 - relative_rank(Us, s);
        			if (squares_in_front_of(Us,s) & pos.occupied_squares())
        			{
        				int blockerCount = count_1s_max_15(squares_in_front_of(Us,s) & pos.occupied_squares());
        				mtg += blockerCount;
        				d += blockerCount;
        			}

        			if (d < 0 && (!movesToGo[Us] || movesToGo[Us] > mtg ))
        			{
        				movesToGo[Us] = mtg;
        				pawnToGo[Us] = s;
        			}
        		}
        	}
        }

[lech]

Last question regarding pawn endgames.
I can’t find separate evaluation for pawn endgames (KP../KP..). Stockfish use the same common function. In many cases it can give a very bad effect.
E.g.
Thanks to bonuses and penalties from code:

Code: Select all

 evaluate.cpp; evaluate_passed_pawns_of_color()
ebonus -= Value(square_distance(ourKingSq, blockSq) * 3 * tr);
            ebonus -= Value(square_distance(ourKingSq, blockSq + pawn_push(Us)) * 1 * tr);
            ebonus += Value(square_distance(theirKingSq, blockSq) * 6 * tr);
…………..
// Are any of the squares in the pawn's path attacked or occupied by the enemy?
                if (b3 == EmptyBoardBB)
                    // No enemy attacks or pieces, huge bonus!
                    // Even bigger if we protect the pawn's path
                    ebonus += Value(tr * (b2 == b4 ? 17 : 15));

[d] 8/3k2p1/8/PK6/7p/7P/8/8 w - -
Stockfish’s score is ca. +2.5 for this lost position. The winning Pawn g7 has penalty too.
I don’t understand, how can Stockfish play any endgame, if can’t score possible pawn endgames correctly? Is there a protection I can’t see?

[zamar]

Last question regarding pawn endgames.
I can’t find separate evaluation for pawn endgames (KP../KP..). Stockfish use the same common function. In many cases it can give a very bad effect.

The Stockfish's great strength in endgame has always been a mystery for me. It doesn't use tablebases, it has very little hard-coded endgame knowledge. I think we could improve a lot by adding carefully designed endgame knowledge, but it's not an easy task.

[rjgibert]

Last question regarding pawn endgames.
I can’t find separate evaluation for pawn endgames (KP../KP..). Stockfish use the same common function. In many cases it can give a very bad effect.
E.g.
Thanks to bonuses and penalties from code:

Code: Select all

 evaluate.cpp; evaluate_passed_pawns_of_color()
ebonus -= Value(square_distance(ourKingSq, blockSq) * 3 * tr);
            ebonus -= Value(square_distance(ourKingSq, blockSq + pawn_push(Us)) * 1 * tr);
            ebonus += Value(square_distance(theirKingSq, blockSq) * 6 * tr);
…………..
// Are any of the squares in the pawn's path attacked or occupied by the enemy?
                if (b3 == EmptyBoardBB)
                    // No enemy attacks or pieces, huge bonus!
                    // Even bigger if we protect the pawn's path
                    ebonus += Value(tr * (b2 == b4 ? 17 : 15));

[d] 8/3k2p1/8/PK6/7p/7P/8/8 w - -
Stockfish’s score is ca. +2.5 for this lost position. The winning Pawn g7 has penalty too.
I don’t understand, how can Stockfish play any endgame, if can’t score possible pawn endgames correctly? Is there a protection I can’t see?

This position is a draw. Consider
[d] 8/8/8/8/7p/5kpP/8/6K1 w - -
with White or Black to move.

[lech]

The Stockfish's great strength in endgame has always been a mystery for me. It doesn't use tablebases, it has very little hard-coded endgame knowledge. I think we could improve a lot by adding carefully designed endgame knowledge, but it's not an easy task.

This confirms my supposition that the less questionable code the better for the engine.

[lech]

Last question regarding pawn endgames.
I can’t find separate evaluation for pawn endgames (KP../KP..). Stockfish use the same common function. In many cases it can give a very bad effect.
E.g.
Thanks to bonuses and penalties from code:

Code: Select all

 evaluate.cpp; evaluate_passed_pawns_of_color()
ebonus -= Value(square_distance(ourKingSq, blockSq) * 3 * tr);
            ebonus -= Value(square_distance(ourKingSq, blockSq + pawn_push(Us)) * 1 * tr);
            ebonus += Value(square_distance(theirKingSq, blockSq) * 6 * tr);
…………..
// Are any of the squares in the pawn's path attacked or occupied by the enemy?
                if (b3 == EmptyBoardBB)
                    // No enemy attacks or pieces, huge bonus!
                    // Even bigger if we protect the pawn's path
                    ebonus += Value(tr * (b2 == b4 ? 17 : 15));

[d] 8/3k2p1/8/PK6/7p/7P/8/8 w - -
Stockfish’s score is ca. +2.5 for this lost position. The winning Pawn g7 has penalty too.
I don’t understand, how can Stockfish play any endgame, if can’t score possible pawn endgames correctly? Is there a protection I can’t see?

This position is a draw. Consider
[d] 8/8/8/8/7p/5kpP/8/6K1 w - -
with White or Black to move.

It's probably not good that the score fluctuates (Stockfish). Is it a bug? Fire and Houdini show a steady score. if someone wants to create a real engine, must take into account the increase of score. It's probably still far ahead.

[Sven]

[d] 8/3k2p1/8/PK6/7p/7P/8/8 w - -
Stockfish’s score is ca. +2.5 for this lost position. The winning Pawn g7 has penalty too.
I don’t understand, how can Stockfish play any endgame, if can’t score possible pawn endgames correctly? Is there a protection I can’t see?

This position is a draw. Consider
[d] 8/8/8/8/7p/5kpP/8/6K1 w - -
with White or Black to move.

Shredder online EGTB confirms that this is a draw with perfect play, and also that the path to draw often goes over positions like the second one given by Ricardo. However, even SF 1.7.1 analysis does not quickly see the draw, neither in the first nor the (much simpler) second position where it took SF 55 iterations and - on my old P4 system - 16 minutes until a draw score was found.

The latter scares me a little bit since SF seems to try virtually each possible square for the black king on the whole board, and also each permutation of moves to these squares, without detecting that none of these king moves helps to improve the position. Maybe this is caused by not quickly detecting the draw after sacrificing the black pawn on g2 and winning back the white h3 pawn, which requires either basic knowledge about KPK with h-pawn or some more plies of search. The latter should be covered by the hash table, though. So the issue remains: no progress is ever made by only moving around the king and visiting a lot of "neutral" squares. How could this be detected?

Of course that is slightly OT here since the original point was about static eval, but it may be of further interest, too.

Regarding that static eval point, I also think that +2.5 for white is way too high, considering that black has a 2:1 kingside majority. Maybe a possible improvement could be to detect such majority patterns as possibly "equivalent to a passed pawn". By analyzing the pattern carefully, and after safely excluding "phantoms" like: white Ph5, black Ph6+g7, one could count the number of steps to promotion just the same as for a passer (in this case: 5 steps with promotion on h1), which would at least neutralize the white a-pawn in the given position and lead to an evaluation which is much closer to draw. It is just a thought, I have no concrete implementation proposal, maybe someone else wants to elaborate further on that idea?

Sven