"Global" cycle detection

[TAILLE]

Hi,

I do not know if white could win in the following position.


White to play

For Damy it looks like a "global" cycle in which the white king remains on the 06-50 diagonal and black king remains on the diagonal 03-25 or on squares 9, 25 or 48.

Could you find the result ? If it is a win what are the corresponding good white moves ?

Is Ed. able to solve the problem with the 8-9 partial endgame database ?

Gérard

[Ed Gilbert]

Kingsrow does not find a conclusive result. I think the position is a probably a draw. Kingsrow moves the kings around as you described. If I force white to try to break up the black diamond with 40-34 then kingsrow sees a database draw.

-- Ed

[Rein Halbersma]

Kingsrow does not find a conclusive result. I think the position is a probably a draw. Kingsrow moves the kings around as you described. If I force white to try to break up the black diamond with 40-34 then kingsrow sees a database draw.

-- Ed

What you could do is keep the black pieces on 19,23,24,29 and the white pieces on 35,40,45 fixed and then enumerate all placements of the remaining black king and the two white men and white king. Essentially this is a 4-piece database on a 43-square board (and for simplicity keeping the white king on the double diagonal). However, for each position you generate moves for all pieces so that you test whether moves as 40-34 or 35-30 don't win for white. This way you will find out quickly whether white can force black into a loss.

The chess folks have an algorithm to generate special endgame databases for such positions, called "freezer chess". See an informal description at http://www.chesscafe.com/text/mueller50.pdf
http://www.freezerchess.com/index.php?topic=examples

Once you have adapted your endgame generation code for such restricted boards, it should be feasible to generate such small (4 to 5 pieces) tables during the search. The difficulty is detecting which pieces are frozen and which pieces one should vary. But with some heuristics that might be doable.

[TAILLE]

What you could do is keep the black pieces on 19,23,24,29 and the white pieces on 35,40,45 fixed and then enumerate all placements of the remaining black king and the two white men and white king. Essentially this is a 4-piece database on a 43-square board (and for simplicity keeping the white king on the double diagonal). However, for each position you generate moves for all pieces so that you test whether moves as 40-34 or 35-30 don't win for white. This way you will find out quickly whether white can force black into a loss.

The chess folks have an algorithm to generate special endgame databases for such positions, called "freezer chess". See an informal description at http://www.chesscafe.com/text/mueller50.pdf
http://www.freezerchess.com/index.php?topic=examples

Once you have adapted your endgame generation code for such restricted boards, it should be feasible to generate such small (4 to 5 pieces) tables during the search. The difficulty is detecting which pieces are frozen and which pieces one should vary. But with some heuristics that might be doable.

Hi Rein,

I know this method but I do not use it for Damy. In this specific example it might not work efficiently : the corresponding 4 pieces database is made of (43x44)/2 x 41 x 40 i.e. about 1,5M positions and it iseems very difficult to know the result of 40-34 and 35-30 for each of these positions.

This method is certainly very interesting when the number of pieces is one piece above your endgame database.

Gérard

[Ed Gilbert]

What you could do is keep the black pieces on 19,23,24,29 and the white pieces on 35,40,45 fixed and then enumerate all placements of the remaining black king and the two white men and white king.

Rein, in 8x8 checkers there is a endgame formation called a bridge. These are quite common, and I have a book (Boland's Bridges) which is devoted to just these endings. Here is an example:

<img src="http://fmjd.org/dias2/save/12346101061.png">

The black men on 1 and 3 and white man on 10 form the bridge. In these positions the white king is usually constrained to the 3 squares behind its man to protect it. These positions are often too difficult to resolve using an 8-piece database. But it should be no problem to build a db where the 3 bridge men are fixed and then solve for all possible combinations of the remaining 7 pieces. I once considered doing this. A 7piece db can be built in a day or two, and these bridge positions appear often enough that such a db would be useful. But now that we have 10-piece dbs for checkers there is no need.

-- Ed