Interesting ending

[Alex_Moiseyev]

While doing a final re-reading the "SIXTH" contest, i find this position. I was curious with verdict and decided to check it with program database. Indeed, my verdict was correct, but I find this position a real "ending Eldorado" and worthy to study. Both sides have alot of possiblities here to play wrongly !

I hope you enjoy it. This position is not a problem, because when you play it, on several occasions there is more than one win or one draw.

Red to move, what result ?


Regards,

Alex

[Kolsz]

Yeah, you are right man! :(

[EdTrice]

While doing a final re-reading the "SIXTH" contest, i find this position. I was curious with verdict and decided to check it with program database. Indeed, my verdict was correct, but I find this position a real "ending Eldorado" and worthy to study. Both sides have alot of possiblities here to play wrongly !

I hope you enjoy it. This position is not a problem, because when you play it, on several occasions there is more than one win or one draw.

Red to move, what result ?


Regards,

Alex

One possible solution:

13-17 2-7* (only move to draw)
17-21 14-10
22-25 7-11* (only move to draw)
25-29 10-6
29-25 6-1
25-22 1-6* (only move to draw)
22-17 6-10
5-9 10-6
9-14 11-15* (only move to draw)
17-13 15-11
14-18 11-15
18-23 15-19
23-27 6-10* (only move to draw)
13-9 10-15
27-32 15-18

...and now just about every red piece that needs to be held is being held. The red king on 32 is held by the white king on its nearest dyke square. The red king on 9 can be mirrored (ex: 9-6 18-15, but not 18-14?? losing to 32-27!)

[AKA]

Very nice analysis by WCC.

[Alex_Moiseyev]

Yes, I never putted the whole solution together. Thanks, Ed !

Alex

[EdTrice]

Very nice analysis by WCC.

It wasn't analyzed by WCC.

I am writing a new program called Only Perfect Checkers which did the analysis. OPC probes the "perfect play" databases in RAM while it searches, meaning not only will it know "win-loss-draw" like the other databases, but information such as:

"win in 171"
"draw with only 2 drawing moves out of 8 legal moves"
"loss in 58"

...will be returned down the search tree.

This way, the program won't just play for the quickest entry into the database that is a win when it is winning -- it will select the win resulting in the quickest termination of the game that can be forced. That is, it will delay entering the database if the resulting forced win will result in an overall shorter game.

And, unlike programs that return only "0" for every one of its billions of draws, OPC will have a precomputed score associated with the level of drawing difficulty.

Draw scores are basically the ratio of legal moves to draws when the draw count is "small", and a different formula is used to penalize draws where almost any legal move will draw.

That way, the program will always select a path to a draw leaving the opponent with the greatest opportunity to lose the draw.

Just imagine 1 move out of 10 lead to a draw, and this situation can be forced for 5 consecutive moves.

What are your chances of finding your way through this draw for just 5 moves?

1 in 10 x 10 x 10 x 10 x 10 = 1 chance in 100,000

If the drawing moves are non-trivial, this "aggressive draw" technique will be able to force an opponent into a difficult position from a great distance.

[matthewkooshad]

Sounds really good, Ed Keep up the good work

[Alex_Moiseyev]

Dear Ed ! I am very excited to hear that you are back to business.

Now I have a challenge for you and all other programmers who reads this. It will be a nice assignment and test tool for OPC.

=========================

HISTORY

Several months ago one of the "Russian checkers" programmers developed (he said it took him only couple days) a piece of code, which extracted from database positions which met one of the following requirement:

"the longest the only winning moves" or "the longest the only drawn moves"

DESCRIPTION.

What does it mean ! The program compose problems !!! I hope you and other checkers programmers who reads this - Martin Fiertz, Ed Gilbert, already got an idea.

The Russian programmer composed around 40-50 wonderful brillian problems and posted on his website. Then he was seriously criticized by composers and lost an interest continue this project.

BENEFITS.

It will be a great benefit and gift to checkers community if you can extract such positions from database and share it with us.

CHALLENGE.

I really hope some of our programers (maybe more than one) accept my challenge (offer) and I can't wait to see first results.

Perhaps bareer for number of "only win" or "only draw" moves could be 12-16. Actually - as more as better! but realistically - I am not sure if we should have too many positions with 30-40 "the only" moves

Respectfully,

Alex Moiseyev

[EdTrice]

When will OPC be out for the public? and will it be expensive?

OPC is mostly just an experimental program for the time being. I am using it more to be a subject of papers I may publish rather than a tool to sell. It runs under Macintosh OS X so it would not have a wide audience of appeal. The good news about OS X: You don't have to "hack" it to get a program to use more than 2 GB of RAM. Ed Gilbert was nice enough to recently send me links concerning what had to be done to get a Windows machine with 4 GB of RAM to be able to use 3 GB of it, the other 1 GB being "hogged" by the operating system.

In the Macintosh world, there are no such bottlenecks. I have tested it on a server with 16 GB of RAM, and it was able to allocate over 15 GB of RAM for its sole use without any problems whatsoever.

What I may do is something similar to what Chinook has done: make a web-based interface that users can log into and play againt the machine.

Still a long ways off.

[EdTrice]

...

HISTORY

Several months ago one of the "Russian checkers" programmers developed (he said it took him only couple days) a piece of code, which extracted from database positions which met one of the following requirement:

"the longest the only winning moves" or "the longest the only drawn moves"...

Hi Alex,

As I understand it, you want to find two positions.

Position #1 - There is only 1 move to win in each of N moves in a row, solve for the greatest number N in the database.

Position #2 - The result is a draw, but the weak side has only 1 move to draw, for M moves in a row, find the greatest number M in the database.

Yes, this is possible to determine, and it is not difficult to extract.

It would have to probe the entire database and there are possibly positions where the streak is interrupted (maybe 2 moves to win) which would otherwise continue for many moves longer, so the chance is that even more difficult positions exist.

There is a problem with Position #2 potentially, in that a draw might occur where there is no subsequent simplification or trade, and the game goes on forever. Just look at king vs. king in the double corner. While there is more than one move to draw in this ending, you can see my point. A "repetition check" must be engaged to minimize the number "M" otherwise the first repeatable position will generate M = infinity, which is not what we want.

[Alex_Moiseyev]

Hi Alex,

As I understand it, you want to find two positions.

Not exactly, Ed ! Not necessarirly two, maybe 22 or 222 ! I don't worry much about record But if we set a limit, lets say - "30 the only winning (or drawn) moves in the row" - can you extract ALL positions in this range ?

Then we can set another limit - "minimum 24 the only moves" etc.

I anticipate here hundred or maybe thousand brilliant positions, which all of us enjoy very much. They are hidden in database, and you can help human find them.

I remember positions generated by programs in Russian checkers - it was a real classic !

So ... again - the program will COMPOSE problems. Can you imagine in checkers literature - the program is an author of some problems. Not analysing, but composing !!!

Alex

[EdTrice]

I anticipate here hundred or maybe thousand brilliant positions, which all of us enjoy very much. They are hidden in database, and you can help human find them.

I remember positions generated by programs in Russian checkers - it was a real classic !

So ... again - the program will COMPOSE problems. Can you imagine in checkers literature - the program is an author of some problems. Not analysing, but composing !!!

Alex

I see. But, you do realize there are 8.5 trillion positions in the 5x5 slice of the 10-piece database, right?

This database is not only being probed, the move generator is being called, every node is visited, w-l-d counts are tabulated, the "paths of optimal play" are being stored, etc.

I think we better start with a smaller database to test the code. This could run for a long time if we are not careful!

By the way, this is called data mining -- you "hunt" for existing data that has already been computed, yet it sits in "huge surroundings", unannounced, waiting to be discovered.

[Alex_Moiseyev]

OK, lets start from 6pc db, no problems. There will be some beauties here as well.

Concerning 8pc database ... Here are additional restrictions:

1. No Kings in initial position.

This restriction could eliminate some worthy positions, but this is acceptable. We can later remove it.

2. No jumps in initial position.

3. Initial position - 4 mans vs 4 mans.

4. Number of "the only winning moves" - 20.

This number is a bit high, but it will guarantee us that extracted positions do not include any "crazy stranger"

All above restictions should seriously drop all your trillions

Alex

============================================================

Ed, the reason I am interesting this - exceptional practical value. If any programmer comlete this - we all say him many thanks, and I will be the first in line !

[EdTrice]

Alex,

Some of the positions I have encountered so far are not all that interesting. In the case of the "only move to draw" positions, usually the strong side's king is chasing a checker up the board where the enemy has 1 or more pieces to one side, so there is only 1 way to go. The problem is, there are usually 2 ways to crown the king at the end, so the "streak ends" since there are 2 choices to draw.

In cases where there is only 1 crowning choice and the streak continues, it is basically like second position. A changing of the guard occurs, and another piece races to crown.

I have only probed the 6-piece database this way so far, perhaps that is why I see the second position theme so often.