endgame challenge

[Will Singleton]

Can your program, playing black and without tablebases, avoid losing to a tablebase program playing white?

[d]1Q6/r4kp1/8/2K5/8/8/8/8 b - -

[bob]

Can your program, playing black and without tablebases, avoid losing to a tablebase program playing white?

[d]1Q6/r4kp1/8/2K5/8/8/8/8 b - -

Just ran this on my laptop, and black drew, first move Ra5+. The tablebase version (playing white) says instant draw. Crafty (non-egtb) started at +5 (good for white) but score slowly dropped to zero. There are a _ton_ of checks to work thru to see the final repetition.

[yanquis1972]

playing thru manually against zappa i get this position --

8/2Q3p1/8/5rk1/3K4/8/8/8 b - - 0 5

for some reason other engines immediately see it as drawn but zappa sees it as lost for black. must be lacking some kind of common knowledge.

[shiv]

This problem can be solved by humans. Of course it is far from a trivial problem. The pattern to draw in such positions (according to the human eye) is to put the black Rook on f6 (or h6) reaching a virtual fortress.

Ra5+, Rf5, and Rf6 is planning to achieve the very fortress. There are tricks due to the white king being a little advanced but it is still drawn.

[bob]

This problem can be solved by humans. Of course it is far from a trivial problem. The pattern to draw in such positions (according to the human eye) is to put the black Rook on f6 (or h6) reaching a virtual fortress.

Ra5+, Rf5, and Rf6 is planning to achieve the very fortress. There are tricks due to the white king being a little advanced but it is still drawn.

I understand the concept. But as I said, for a computer, the problem is that once you get the rook on f6, there are a _ton_ of checks by the queen before a repetition (or 50 move draw) is found. Which is really beyond what we would expect a program to find by pure search. This really needs to be solved in the eval, where a specific recognizer for the "general fortress setup" is recognized and categorized as "side with more material can not win".

[shiv]

I understand the concept. But as I said, for a computer, the problem is that once you get the rook on f6, there are a _ton_ of checks by the queen before a repetition (or 50 move draw) is found. Which is really beyond what we would expect a program to find by pure search. This really needs to be solved in the eval, where a specific recognizer for the "general fortress setup" is recognized and categorized as "side with more material can not win".

Right, for a computer, understanding fortresses is really hard. Putting it in the eval is the right fix, but how to exactly program it is still tricky.

I just wanted to mention that the problem is one of rare ones which can be solved somewhat easily by a human but not by a machine.

[bob]

I understand the concept. But as I said, for a computer, the problem is that once you get the rook on f6, there are a _ton_ of checks by the queen before a repetition (or 50 move draw) is found. Which is really beyond what we would expect a program to find by pure search. This really needs to be solved in the eval, where a specific recognizer for the "general fortress setup" is recognized and categorized as "side with more material can not win".

Right, for a computer, understanding fortresses is really hard. Putting it in the eval is the right fix, but how to exactly program it is still tricky.

I just wanted to mention that the problem is one of rare ones which can be solved somewhat easily by a human but not by a machine.

I have looked at the problem from time to time. Recognizing classic fortress-type positions (such as this one) is not that hard (KRP vs KQ). The problem is to recognize that earlier positions are potential fortresses if the winning side is not careful. For example, giving up one pawn to win two and ending up in this position. I've done some stuff with this idea, but just categorizing known fortress positions (any position where the rook forms a clear line of demarcation, with one king on one side, the other king on the other, and the losing side has a piece/pawn to support the rook). Just catching that did not seem to help much, by itself. And I even handled the "supporting piece" safely in that it had to be on the same side of the line of demarcation as the defending king so that it could not be captured. Seems so easy, turns out to be so messy...

[shiv]

Sounds very interesting. How would a computer recognize a classic fortress like position? Would the eval be different, will the engine need to have an abstract notion of making progress?

[bob]

Sounds very interesting. How would a computer recognize a classic fortress like position? Would the eval be different, will the engine need to have an abstract notion of making progress?

I do some of this kind of recognition already. For example, bishop + wrong color rook pawn(s). In Crafty, I have a mechanism to recognize cases where one side or the other can't possibly win. For example, KN vs KNP where the KN has no chance of winning, although the KNP might be able to if the enemy knight is far enough away (also the king). What I had tried was to recognize the positions that fit this set of constraints.

(1) Winning side has a queen only;

(2) losing side has a rook + helper (commonly a pawn).

(3) rook divides the board in half vertically and horizontally. For either one of those dividing lines, the kings have to be on opposite sides.

(4) the losing king and "supporting piece/pawn" have to be on the same side of the line.

(5) the supporting piece/pawn has to be defending the rook.

If all of those were met, then I set the "other side can't win" flag which would eval the position as zero even though the queen is worth much more than R+P.

I'm still working on the draw recognizing code and am going to visit this again.

[shiv]

Sounds interesting and could easily be a new feature in engines.

Is it really hard to have the engine derive the fortress rules by itself? For example, can one code a generic eval function which has some notion of progress made in a position and can autogenerate fortress criterias similar to the ones you mentioned.

The lack of proper evaluation of fortress positions is probably the main weaknesses of engines today.