Prize Problem

[Richard Pask]

Congratulations to Brian Hinkle for his remarkable prize problem!

The fact that the leading computer programs were also baffled should be spread far and wide: the reality of checkers is so different from the paltry picture of the game with which the general public is familiar.

[fierz]

The leading computer programs have been optimized to play the best possible "normal" game of checkers. They have not been optimized to solve problems such as this one. If we wanted our engines to be able to solve such problems, it would very likely be possible - but it would hurt their performance in 99.9999% of all positions...

As I know well from chess, when you know you need to solve a problem, you look for different things than you normally look for in a game. In a way, it is therefore unfair to expect the programs to solve this kind of position, as you (so far) cannot tell them that they are looking at a cunning problem rather than a normal position.

[Richard Pask]

I think Brian's problem is making two key points;

First, that the game of checkers is massively more difficult than most people think.

Secondly, that no computer program is yet an oracle. (99.999% of people think they are and, indeed, that they were 60 years ago!)*

It's incredibly hard to put anything over on the leading programs, so in finding a gap I would give Brian enormous credit - without any reservation.

*Needless to say, we all greatly value the best programs - why anyone should fear them is a mystery.

[Ed Gilbert]

I completely agree with Martin. Computer checkers programs perform relatively poorly on positions with many pitches or with smothers, but that's only because these positions are extremely rare in normal game play. We can certainly design programs that are good at solving such positions, but it would hurt their performance in normal games. However, I was interested to see if there were any simple changes I could make to kingsrow to improve it's performance on problems like Brian's without affecting its operation in normal games. I added a "solve mode" selection in Engine Options. With this mode enabled, kingsrow solves Brian's prize problem in 2-1/2 hours using one search thread, and in under 13 minutes using 12 search threads. Implementing solve mode was basically a one-line change in the search code. With solve mode enabled, kingsrow is about 30 elo weaker in match play, but it is massively faster at solving most problems involving lots of pitches.

When I showed this to Brian, he went to work creating an even tougher problem that kingsrow cannot solve But the point is that we could design programs that perform well on these problems if we put some effort into it.

-- Ed

[Richard Pask]

My overriding, AND FINAL, point is that the game of checkers is truly phenomenal - as evidenced by the fact that incredibly powerful programs have been floored by such problems.

Let's just give Brian, and the game, its due - without reservation or equivocation: this is NOT a criticism of the programs but rather a hearty cheer for the wonderful game of checkers! I, for one, love it, and my for the game will not be the least bit diminished when a genuine oracle is created. (It will actually be yet further enhanced.)

[chipschap]

All points have been well made here. Indeed, the current very powerful computer programs are designed for actual practical play vs. strict problem solving. There's also little doubt that, at the cost of some practical strength, these programs could be made to find the solutions to "off the beaten path" problems.

However, the key point is this. Human ingenuity is boundless. It took great ingenuity and skill to create today's top programs. It took great ingenuity and skill for Brian to create incredibly clever and pleasing problems. And the great game of checkers was the vehicle.

Perhaps it is serendipitous, but to me the cleverest thing of all is the game itself, a game with dead simple rules which can be grasped in minutes, which has entertained for centuries, and as we dig deeper and deeper with both computers and our own minds, produces endless surprises and thrills.

[fierz]

I have been tinkering around over the past 10 days with Cake, and made some changes to make it able to solve Brian's problem. Below you can find my latest version's output - on a single search thread on my laptop it finds the solution in just 30 seconds. It will not show the pitches on the PV, because red has means of delaying the loss by playing in a way that does not allow the direct win.
I really like Brian's problem, and don't mean to depreciate it in any way - but it really isn't hard to change the programs so that they solve it very quickly (I could probably improve the solution time further if I wanted to...), and it is not a good example of something programs cannot do. There are much better examples of that

In any case, the problem, and some similar ones that Ed Gilbert sent me, have made me investigate the reduction/extension mechanisms in Cake more seriously, and I must admit, this was a weakness of Cake that I was not really aware of before, so Brian's prize problem has certainly taught me a good deal about my program

cheers
Martin

depth 1/4/2.1 time 0.00s value=40 nodes 38 3799kN/s db 0% cut 100.0% pv 3-7 10-15
depth 3/10/4.4 time 0.00s value=70 nodes 279 27899kN/s db 0% cut 94.4% pv 3-7 4-8 11x4 2x11 22-18
depth 5/15/7.3 time 0.00s value=88 nodes 1419 1404kN/s db 0% cut 94.8% pv 3-7 10-15 7-10 23-27 32x23 28-32 21-17
depth 7/22/8.8 time 0.01s value=40 nodes 6778 1352kN/s db 0% cut 96.9% pv 3-7 10-15 7-10 20-24 21-17 24-27 17-13 27-31
depth 9/22/10.2 time 0.01s value=40 nodes 15536 1411kN/s db 0% cut 97.5% pv 3-7 10-15 7-10 20-24 10-14 24-27 14-10 27-31
depth 11/27/12.1 time 0.03s value=38 nodes 39158 1565kN/s db 0% cut 98.2% pv 22-18 10-15 25-22 20-24 3-7 24-27 7-10 27-31
depth 13/34/15.3 time 0.08s value=14 nodes 209496 2493kN/s db 50% cut 97.2% pv 3-7 10-15 7-10 20-24 10-14 24-27 21-17 27-31
depth 15/37/18.0 time 0.17s value=32 nodes 543927 3276kN/s db 93% cut 97.0% pv 22-18 19-24 26x19 16x23 3-7 10-15 7-10 15x22
depth 17/40/21.9 time 0.50s value=24 nodes 2008802 4009kN/s db 95% cut 96.9% pv 22-18 19-24 26x19 16x23 3-7 10-15 7-10 15x22
depth 19/44/23.3 time 1.20s value=22 nodes 5002671 4179kN/s db 94% cut 97.1% pv 22-18 19-24 26x19 16x23 3-7 10-15 7-10 15x22
depth 21/50/25.3 time 3.12s value=34 nodes 12874089 4132kN/s db 91% cut 97.3% pv 22-18 19-24 26x19 16x23 3-7 10-15 7-10 15x22
depth 23/51/27.4 time 8.31s value=30 nodes 33874227 4074kN/s db 89% cut 97.3% pv 22-18 19-24 26x19 16x23 3-7 10-15 7-10 15x22
depth 25/55/27.6 time 29.98s value=64 nodes 118907951 3966kN/s db 90% cut 96.9% pv 3-7 10-15 7-10 20-24 21-17 16-20 25-21 12-16
depth 27/55/29.2 time 50.23s value=70 nodes 199092814 3963kN/s db 88% cut 96.6% pv 3-7 10-15 7-10 20-24 21-17 23-27 32x23 28-32