Sunday 13 January 2008

Benchmark Chess Problems


The problem shown on the right is a reasonably famous one in the area of computer chess programs. It was used in the 70's as an example of how 'directed search' programs could solve deep mates (In this case White to move and mate in 10). It is also included in Fred Reinfelds 1001 Brilliant Ways to Checkmate and it is the first problem in this test set that my program fails to solve as 1 second a move (It is problem 31 btw).
If I switch my program to do a fixed depth search of 8 ply (ie 8 half moves or 4 moves) it will find the solution in about 45 seconds (NB While starting with an 8 ply search various search extensions based on checks and captures push the depth to 19 ply). Frustratingly Fritz 8 finds the answer in about 12 seconds, and I am sure Rybka, Fruit etc are just as fast.
While that is pretty fast I believe that good human players would find the right move just as quickly, but with one catch. They may choose the right move in under 10 seconds, but take far longer to confirm it works. And more importantly, if they had something riding on the answer, like the result of a real game, if they couldn't confirm it 100% they very well may choose not to play it.
How fast does it take you to find the right move?

3 comments:

TrueFiendish said...

I figure it's Qh5+, fxe6+ and Bc2+ etc, but it would take a while for me to confirm it leads to mate. I have other work to do! One problem weaker humans (or at least I) have is in going back over old lines repeatedly due to getting lost or not trusting your analysis.

TrueFiendish said...

1.Qh5+ Nxh5 2.fxe6+ Kg6 3.Bc2+ Kg5 4.Rf5+ Kg6 5.Rf6+ Kg5 6.Rg6+ Kh4 (...Kf4 7.g3+ Nxg3 8.hxg3+ Kf3
9.Bd1 mate) 7.Re4+ Nf4 8.Rxf4+ Kh5 9.g3 and 10.Rh4 mate.
Took about 15 mins, should have taken 5. Course, maybe I missed something...
Cheers, AO

Shaun Press said...

No, you didn't miss anything. A lot of the early moves are easy to spot, although unless you already know a mate is there, you may not know that they lead to something.
Probably the hardest move for computers (and possibly humans) is 9.g3 as it is neither a check or a capture, and most programs don't "extend" (generate replies) on quiet moves. The computer will then evaluate the position and go "Where did my queen go?" and decide it is all bad. If humans can visualise the the position after move 8, then a move like 9.g3 isn't so hard to spot.
So for humans to solve this under game conditions they need to (a) visual the position accurately and (b) know what they are looking for in the first place