BPP against NP

[Arpad Rusz]

A nice endgame position by John Daniel Bryant. This is probably very hard for engines because the longest winning line has almost 50 moves without capture:

[D]2n5/7k/5B1p/2K4P/6P1/8/8/8 w - - 0 1

White wins

Playing only DTM-optimal moves after 36(!) moves the position will look like this:

[D]2n5/7k/5B1p/2K4P/6P1/8/8/8 b - - 0 36

Not a big change, isn't? We have only WTM -> BTM!
If there is no other winning way than reaching again this position (but with the other side to move) then this could be the deepest "Vital Zugzwang" discovered so far.

See the author's analysis here:
http://www.youtube.com/watch?v=2h_b0puS8Vk

[Arpad Rusz]

I have found a much deeper win leading eventually to Bryant's position. This position is a "win in 88 moves" acording to FinalGen (but of course would be draw by the 50 moves rule).

[D]K2B3k/8/7p/7P/6P1/8/8/1n6 w - - 0 1

[zamar]

Also in KNNKP endings it's a common theme that player with knights can spend ~15 moves (maybe even more!) just to force losing one tempo.

[guyhaw]

As discussed off the board, you are in effect asking if the position is a Vital (Type B) Zugzwang, as defined in our 2011 paper http://centaur.reading.ac.uk/23799/3/AC ... dgames.pdf .

The 'Vital Zug test' defined in that paper requires partial EGTs to be created for variants of Chess where certain positions, in this case the shallower btm version of the position, are defined to be a DRAW rather than the win they are in Chess.

Eiko Bleicher has responded positively to my request for a version of FREEZER which can generate EGTs for such variants of chess. He has then proved that the position you cite IS indeed a Vital Zugzwang.

This in turn means that the depths (to 'Known Win', DTKW) provided by FinalGen can be compared with each other, even if they are not correct in DTC, DTM or DTZ terms.

It therefore follows that the zug-depth of this Vital Zug is 36m or 73p, and is the deepest Vital Zug I know.

Kudos to the combination of Bryant, Rusz and Bleicher.

g