Idea for recognizing fortress/encouraging progress

[OneTrickPony]

Here's an idea:
-introduce no progress penalty to position representation (NPP)
-it's a number starting from 0 and increasing by 1 with every non-capture/pawn move; it resets to 0 after capture/pawn move
-NPP can't grow higher than DRAWDISTANCE; DRAWDISTANCE is set to maybe 25-30 moves;

-neweval = eval * ((DRAWDISTANCE - NPP)/DRAWDISTANCE)

This way when engine searches the eval for every new ply for non capture/pawn moves is closer and closer to 0. This have two desirable effects:
-fortress is now recognized as draw if searched deep enough
-engine is encouraged to search for pawn breaks in locked positions instead of shuffling pieces; if engine evaluates shuffling at say +0.6 and pawn break at +0.4 after some shuffling the pawn break will be more attractive; no need to wait for 50 move rule and panic;

Maybe instead of linear scale for neweval some reverse algorithmic scale would be better (to not penalize say first 6-7 shuffling moves).
Thoughts ?

[Uri Blass]

Deciding that no capture and no pawn move is no progress is a bad idea because there are many endgames with when you need more than 30 moves with no capture and no pawn moves to win the game and I think that these endgames happen more often than endgames when there is a real fortress.

[hgm]

I thought that everyone already tapers his score gradually towards zero towards the 50-move limit. If they pay attention to the 50-move counter at all. It seems a bad idea to already start doing so from the very first ply, though. It seems better to only start doing this after 40 ply or so.

My engines ignore the 50-move counter, as I noticed that paying attention to it in general makes engines weaker. It just mean they start doing pointless sacrifices to reset the 50-move counter in a position that already was a (misevaluated) draw before the sac, and is often lost after it. Blackmailing the engine to make progress through the 50-move rule is a bad idea; if engines do not make progress in positions where progress is possible there is something wrong with their evaluation, and it would be much better to fix that, than forcing it to panic.

What did work nicely for Joker was to increase the Pawn-push bonus after the 50-move counter in the root exceeded 50 ply. That way it first tries to make progress with reversible moves, and only if that doesn't succeed it tries to make progress by pushing Pawns.

[Evert]

I thought that everyone already tapers his score gradually towards zero towards the 50-move limit. If they pay attention to the 50-move counter at all. It seems a bad idea to already start doing so from the very first ply, though. It seems better to only start doing this after 40 ply or so.

I do it from ply 80 (move 40) or so.

Rather than a global "50 move" counter (or more accurately, 100 ply counter) it may be better to have a "plies since progress" counter for each side, which gets reset when "progress" is made, where progress could include capturing enemy pieces and pawn pushes. Only when the "progress" counter becomes large, drag the score closer to 0. In this way sacrificing your own pieces no longer counts as "progress", and it would even be possible to start adjusting the score well before the 50-move limit is reached. In endings like KBNK you could define progress by driving the defending king to the correct corner (although it's more tricky than that and you don't actually need something like this to make progress there; it's mainly to illustrate the point that you can have a more flexible definition of "progress").

What did work nicely for Joker was to increase the Pawn-push bonus after the 50-move counter in the root exceeded 50 ply. That way it first tries to make progress with reversible moves, and only if that doesn't succeed it tries to make progress by pushing Pawns.

I tried this in Jazz after you mentioned it earlier, and it proved to be a regression for me... shame, because I liked the idea.

[OneTrickPony]

I thought that everyone already tapers his score gradually towards zero towards the 50-move limit. If they pay attention to the 50-move counter at al

I think not. This very simple position:

[d]3r1r1q/4p3/k2pPp2/b1pP1Pp1/1pP1B1Pp/pP5P/P3K3/8 b - - 0 1 [/d]

I beyond reach for Houdini and I already arranged black pieces to correct squares for final sacrifice (Qg8-e6)
Houdini instantly see that taking the pawn is -12 while doing nothing is -21. With my modification it would quickly see Qxe6.

It just mean they start doing pointless sacrifices to reset the 50-move counter in a position that already was a (misevaluated) draw before the sac

Well, "progress" move still needs to have +eval to make it. One can scale not toward 0 but say towards +0.2 or something (so no score below 0.2 is scaled down) to avoid some unpleasant 0.01 sacs in 0.01 positions.

Blackmailing the engine to make progress through the 50-move rule is a bad idea

I agree. Actually my idea is better than that because normally when the engine sees 50th move coming it evaluates shuffling around as 0.00 so even 0.02 panic sacs will be made. With my solution however it's not the case, the eval is just scaled down, not reset to 0 (and ok, scaling it down to say +0.2 or +0.5 sounds like better idea than to 0)

; if engines do not make progress in positions where progress is possible there is something wrong with their evaluation, and it would be much better to fix that, than forcing it to panic.

The very essence of "needing progress" is that other moves leads nowhere. I think eval needs to access history to understand this concept. Static evaluation will never get there.

What did work nicely for Joker was to increase the Pawn-push bonus after the 50-move counter in the root exceeded 50 ply. That way it first tries to make progress with reversible moves, and only if that doesn't succeed it tries to make progress by pushing Pawns.

This is similar to my idea. Giving bonus to one type of move is the same as penalizing other moves.

there are many endgames with when you need more than 30 moves with no capture and no pawn moves to win the game and I think that these endgames happen more often than endgames when there is a real fortress.

That might be true but to lose you need a position where pawn push/capture is still + (say more than +0.2 or +0.5) to make it over scaled down eval of shuffling. I am not sure if such positions happen more often.
I think both situations are very rare so this change is unlikely to bring ELO. It might be useful for analysis though and it would make engines stop looking silly in positions as the one at the top of this post.

[hgm]

The position you give is a good example of there being something wrong with the evaluation. The proper solution would be to have the evaluation recognize this Pawn structure as extremely drawish, applying a factor 1/8 or 1/16 for it. Then breaking the Pawn structure will become an aim in itself, naturally leading to the sacrifice. And, even more important, the leading engine would not even have allowed the Pawn wall to form, so that no sacrifice would have been necessary, or a much cheaper one (like one or two Pawns) would have done the job, rather than sacrificing the Queen. That way it would also have been able to win the game if it would not have had the Bishop and the two Rooks.

Using the 50-move counter to let the engine discover it has manoeuvred itself in a drawish position is 'mustard after the meal', as in 99.9% of the cases you will not be two Rooks plus a Queen ahead, and there will be no escape. "See that you don't get into trouble, then you don't need to get out again!"

What Joker does is actually very different from what you suggest. Because it reacts to the 50-move counter in the root, it won´t see any sacrifices as a solution, and it won´t see Pawn pushes as a solution only because they reset the counter (and get captured afterwards...). It will only consider Pawn pushes that make the Pawn survive in a more advanced position. Because even after the Pawn push the 50/move counter in the root will still be large.

If Houdini never sacs the Queen, it must mean it doesn´t pay attention to the 50-move counter at all. (Which would be logical if paying attention to it makes the engine weaker, as seemed to be the case for my engines.) Not even as a sudden drop in score to 0. Because if it did, its search depth should be enough to still plan an optimal sacrifice when the draw gets near. So it is still not a counter/example to my statement that "everyone that does pay attention to 50/move draws already uses such tapering".

[Don]

Here's an idea:
-introduce no progress penalty to position representation (NPP)
-it's a number starting from 0 and increasing by 1 with every non-capture/pawn move; it resets to 0 after capture/pawn move
-NPP can't grow higher than DRAWDISTANCE; DRAWDISTANCE is set to maybe 25-30 moves;

-neweval = eval * ((DRAWDISTANCE - NPP)/DRAWDISTANCE)

This way when engine searches the eval for every new ply for non capture/pawn moves is closer and closer to 0. This have two desirable effects:
-fortress is now recognized as draw if searched deep enough
-engine is encouraged to search for pawn breaks in locked positions instead of shuffling pieces; if engine evaluates shuffling at say +0.6 and pawn break at +0.4 after some shuffling the pawn break will be more attractive; no need to wait for 50 move rule and panic;

Maybe instead of linear scale for neweval some reverse algorithmic scale would be better (to not penalize say first 6-7 shuffling moves).
Thoughts ?

This idea might work if there is some consideration for determining how blocked the position is. Some positions are not blocked at all however and could go for many moves, such as a BNvsK mate for example.

One problem with this approach in general is that if you demote the score of a position deep in the tree, the program is going to favor shallow positions in the tree so I think this might have a negative effect on the shape of the tree. Normally, a chess program wants to compare 2 positions and be able to clearly determine which is the better one and this idea messes up that concept.

In fact, I have not proved that gradually reducing the score as you approach the 50 move rule actually strengthens a chess program because it has a negative affect on the tree as well as the GHI issues it creates. However it DOES make the program seem smarter when you observe the score dropping - so I think even this rule is more cosmetic than beneficial.

There is no question that this is a really difficult problem though. Larry and I plan to address this with some energy in the near future and we will probably first try to cover it with heuristics and not trickery. (We are not opposed to trickery however, we will do whatever works

Closed positions more than any other factor really comes down to pawn breaks and when to make them and how to prepare them. Yes, there are other issues too but I think this is the primary one.

I have seen positions where one side can win but absolutely has to make a major sacrifice - computers will NEVER find those unless it can actually see the tactical point of the sacrifice or unless the evaluation can somehow understand that. And of course the problem with programs is the understanding part of the equations. So trying to solve this with search is probably not the way to go.

[lucasart]

Here's an idea:
-introduce no progress penalty to position representation (NPP)
-it's a number starting from 0 and increasing by 1 with every non-capture/pawn move; it resets to 0 after capture/pawn move

What you call NPP is not new, it's called the half-move clock:
http://en.wikipedia.org/wiki/Forsyth%E2 ... s_Notation

-neweval = eval * ((DRAWDISTANCE - NPP)/DRAWDISTANCE)

I'm pretty sure this idea will fail. And there's a very good reason for that: it makes your eval incredibly path-dependant, which, in combination with a transposition table, is an absolute disaster.

[Sven]

Here's an idea:
-introduce no progress penalty to position representation (NPP)
-it's a number starting from 0 and increasing by 1 with every non-capture/pawn move; it resets to 0 after capture/pawn move
-NPP can't grow higher than DRAWDISTANCE; DRAWDISTANCE is set to maybe 25-30 moves;

-neweval = eval * ((DRAWDISTANCE - NPP)/DRAWDISTANCE)

This way when engine searches the eval for every new ply for non capture/pawn moves is closer and closer to 0. This have two desirable effects:
-fortress is now recognized as draw if searched deep enough
-engine is encouraged to search for pawn breaks in locked positions instead of shuffling pieces; if engine evaluates shuffling at say +0.6 and pawn break at +0.4 after some shuffling the pawn break will be more attractive; no need to wait for 50 move rule and panic;

Maybe instead of linear scale for neweval some reverse algorithmic scale would be better (to not penalize say first 6-7 shuffling moves).
Thoughts ?

This idea might work if there is some consideration for determining how blocked the position is. Some positions are not blocked at all however and could go for many moves, such as a BNvsK mate for example.

One problem with this approach in general is that if you demote the score of a position deep in the tree, the program is going to favor shallow positions in the tree so I think this might have a negative effect on the shape of the tree. Normally, a chess program wants to compare 2 positions and be able to clearly determine which is the better one and this idea messes up that concept.

In fact, I have not proved that gradually reducing the score as you approach the 50 move rule actually strengthens a chess program because it has a negative affect on the tree as well as the GHI issues it creates. However it DOES make the program seem smarter when you observe the score dropping - so I think even this rule is more cosmetic than beneficial.

There is no question that this is a really difficult problem though. Larry and I plan to address this with some energy in the near future and we will probably first try to cover it with heuristics and not trickery. (We are not opposed to trickery however, we will do whatever works

Closed positions more than any other factor really comes down to pawn breaks and when to make them and how to prepare them. Yes, there are other issues too but I think this is the primary one.

I have seen positions where one side can win but absolutely has to make a major sacrifice - computers will NEVER find those unless it can actually see the tactical point of the sacrifice or unless the evaluation can somehow understand that. And of course the problem with programs is the understanding part of the equations. So trying to solve this with search is probably not the way to go.

I would vote for a static eval approach in a way that helps to assign a static eval of 0 to special pawn chain positions like the one above, so that search can easily find the queen sac that breaks the pawn chain.

A possible idea would be to write code that detects whether an own piece would ever be able to "cross the pawn chain" and attack targets like undefended enemy pawns (e.g. a2 in the position above) or the enemy king, under the basic assumption that the pawn chain remains unchanged. The black bishop as well as both black rooks are definitely unable to cross the chain: there is no "hole" for the bishop to slip through, and there is also no open or semi-open file for the rooks, and the pawn chain is fully connected. For this reason the black bishop and rooks would have to be evaluated as "zero" (i.e., no material or positional value) since they serve for exactly nothing at the moment. The white bishop also gets "zero" of course. In principle the same holds for the black queen as well except for its ability to attack enemy pawns. But the queen should be evaluated as "zero" as well since otherwise the basic idea would not work.

The definition of a "pawn chain" might even be generalized a bit since each of the enemy pawns could be replaced by any other enemy piece. The key point is to detect whether a given piece (QRBN) "serves for nothing" since its "mobility" is restricted to an "unimportant" area of the board.

The idea can also be extended to knights although these might be able to jump across the chain. Usually they can't do so without being subject to immediate capture in case of a fully connected pawn chain. But here some more thoughts may be needed how to handle knights.

What do others think about that approach? It sounds expensive, of course, but maybe there are some simple bitboard tricks that help to drastically restrict the number of cases where such expensive calculation would be applied. The benefit would be to find the "breaking sac" very quickly through search.

The original idea in this thread to make use of the 50-moves counter somehow may well apply for more general fortress cases but I think that at least locked positions of this type can be solved with static eval knowledge.

Sven

[Evert]

I would vote for a static eval approach in a way that helps to assign a static eval of 0 to special pawn chain positions like the one above, so that search can easily find the queen sac that breaks the pawn chain.

A possible idea would be to write code that detects whether an own piece would ever be able to "cross the pawn chain" and attack targets like undefended enemy pawns (e.g. a2 in the position above) or the enemy king, under the basic assumption that the pawn chain remains unchanged. The black bishop as well as both black rooks are definitely unable to cross the chain: there is no "hole" for the bishop to slip through, and there is also no open or semi-open file for the rooks, and the pawn chain is fully connected. For this reason the black bishop and rooks would have to be evaluated as "zero" (i.e., no material or positional value) since they serve for exactly nothing at the moment. The white bishop also gets "zero" of course. In principle the same holds for the black queen as well except for its ability to attack enemy pawns. But the queen should be evaluated as "zero" as well since otherwise the basic idea would not work.

The definition of a "pawn chain" might even be generalized a bit since each of the enemy pawns could be replaced by any other enemy piece. The key point is to detect whether a given piece (QRBN) "serves for nothing" since its "mobility" is restricted to an "unimportant" area of the board.

The idea can also be extended to knights although these might be able to jump across the chain. Usually they can't do so without being subject to immediate capture in case of a fully connected pawn chain. But here some more thoughts may be needed how to handle knights.

What do others think about that approach? It sounds expensive, of course, but maybe there are some simple bitboard tricks that help to drastically restrict the number of cases where such expensive calculation would be applied. The benefit would be to find the "breaking sac" very quickly through search.

I would use "number of blocked pawns" as a metric. That is: how many pawns are unable to advance (because they are blocked or would be captured immediately)? The larger this number, the more draw-like the position becomes. Then simply scale the evaluation (the factor could be taken from a table indexed by number of blocked pawns); the scale would be 1 if there are few blocked pawns and become 0 (or close to it) if there are 16 blocked pawns in total. The transition should probably be quite sharp.

This is a crude approximation of course; the files on which the pawns are blocked are important as well, but all that's really needed is to guide the search in the right direction.

I suspect it may help as "anti-human" chess as well, but overall it's probably wasted effort. I think Crafty used to have similar code in older versions.