BPP against NP

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Arpad Rusz
Posts: 270
Joined: Sat Apr 17, 2010 12:34 pm
Location: Budapest

BPP against NP

Post by Arpad Rusz » Sun Jul 22, 2012 10:37 pm

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
Posts: 270
Joined: Sat Apr 17, 2010 12:34 pm
Location: Budapest

Re: BPP against NP

Post by Arpad Rusz » Sun Jul 22, 2012 11:04 pm

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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: BPP against NP

Post by zamar » Mon Jul 23, 2012 2:45 pm

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.
Joona Kiiski

guyhaw

Re: BPP against NP

Post by guyhaw » Sat Aug 11, 2012 2:28 pm

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

Post Reply