Fortress detection?

[fierz]

I have a question on checkers programming, but the issue is similar in chess, so I hope someone here can help me. It is about fortresses, which also can exist in checkers. Here is an example:



White (silver) is just going 4-8-4-8-... with his lone king, whereas red (gold) is a piece up, has more kings, and can move around wherever he wants, but will never win. Normally in checkers, being one piece up is good enough to win, and having so many more kings is a certain win, so of course my engine doesn't get this. Also, there are far too many options for red to move around with his kings so repetition detection never kicks in.

Is there any way that such "shuffling-around" fortresses can be detected sensibly?

best regards
Martin

[hgm]

Most chess programs do not address the fortress problem. I don't know enough about Checkers to even see why the presented position is a fortress. But I could imagine that it would help to use the reversible-move counter for fortress detection. If the counter exceeds a certain (not-too-large) value, the evaluation should be quickly tapered towards a draw score.

In Chess you could use a similar trick for having too many consecutive moves with the same piece, e.g. to get an early recognition of KQKP draws.

[Gerd Isenberg]

,,,
Is there any way that such "shuffling-around" fortresses can be detected sensibly?

best regards
Martin

In Pawn endings maybe Blockage Detection?
See also Code of Chiron for Detection of Pawn Blockages by Ubaldo Andrea Farina.

[Ajedrecista]

Hello Martin:

Fortress detection is one of the Holy Grails of computer chess. Chess Programming Wiki and searches at TalkChess might help to see what other people do. I already see that Gerd was faster than me!

KingsRow 1.19b also gives winning scores for red side with 8-man EGDB. You are right when you write that red 'have many options to move'. I computed perft values of the position with NebiyuCheckers up to depth 11, then Monte Carlo perft estimates from depth 11 to depth 20:

Code: Select all

7Q/4Q3/8/2Q1Q1Q1/1Q1p1Q1p/p1p1p3/3p3P/q7 w - 1 42

          a b c d e f g h
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
8 * * * * . . . . . . . Q * * * * 8
7 * * * * . . . . Q . . . * * * * 7
6 * * * * . . . . . . . . * * * * 6
5 * * * * . . Q . Q . Q . * * * * 5
4 * * * * . Q . p . Q . p * * * * 4
3 * * * * p . p . p . . . * * * * 3
2 * * * * . . . p . . . P * * * * 2
1 * * * * q . . . . . . . * * * * 1
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
          a b c d e f g h

----------------
perft 1
h2g3           1
h8g7           1
e7f8           1
e7d8           1
e7d6           1
e7f6           1
g5h6           1
g5f6           1
e5f6           1
e5d6           1
c5d6           1
c5b6           1
f4g3           1
b4a5           1
nodes         14
----------------
perft 2
h2g3           1
h8g7           7
e7f8           7
e7d8           7
e7d6           7
e7f6           7
g5h6           7
g5f6           7
e5f6           7
e5d6           7
c5d6           7
c5b6           7
f4g3           1
b4a5           7
nodes         86
----------------
perft 3
h2g3          14
h8g7          58
e7f8          43
e7d8          43
e7d6          37
e7f6          37
g5h6          51
g5f6          45
e5f6          59
e5d6          59
c5d6          58
c5b6          74
f4g3          16
b4a5          52
nodes        646
----------------
perft 4
h2g3          98
h8g7         319
e7f8         229
e7d8         229
e7d6         193
e7f6         193
g5h6         276
g5f6         240
e5f6         316
e5d6         316
c5d6         357
c5b6         465
f4g3         112
b4a5         294
nodes       3637
----------------
perft 5
h2g3         838
h8g7        2401
e7f8        1543
e7d8        1575
e7d6        1205
e7f6        1194
g5h6        1955
g5f6        1577
e5f6        2408
e5d6        2413
c5d6        2945
c5b6        4603
f4g3        1073
b4a5        2256
nodes      27986
----------------
perft 6
h2g3        5072
h8g7       13266
e7f8        8463
e7d8        8655
e7d6        6506
e7f6        6503
g5h6       10829
g5f6        8690
e5f6       13179
e5d6       13101
c5d6       18035
c5b6       28708
f4g3        6493
b4a5       12917
nodes     160417
----------------
perft 7
h2g3       43947
h8g7      112043
e7f8       67408
e7d8       70711
e7d6       49899
e7f6       48697
g5h6       88696
g5f6       67311
e5f6      116062
e5d6      117561
c5d6      163395
c5b6      292717
f4g3       62173
b4a5      115105
nodes    1415725
----------------
perft 8
h2g3      256534
h8g7      613014
e7f8      367121
e7d8      385681
e7d6      267340
e7f6      263551
g5h6      485262
g5f6      366757
e5f6      634069
e5d6      636079
c5d6      968892
c5b6     1754991
f4g3      355407
b4a5      641881
nodes    7996579
----------------
perft 9
h2g3     2297560
h8g7     5698762
e7f8     3263282
e7d8     3523699
e7d6     2343309
e7f6     2251043
g5h6     4423776
g5f6     3222820
e5f6     6208902
e5d6     6419609
c5d6     9391960
c5b6    18482872
f4g3     3542297
b4a5     6205229
nodes   77275120
----------------
perft 10
h2g3    13527649
h8g7    31231238
e7f8    17861934
e7d8    19292266
e7d6    12632850
e7f6    12266462
g5h6    24350347
g5f6    17694907
e5f6    33685014
e5d6    34429824
c5d6    55282869
c5b6   109525892
f4g3    20350685
b4a5    34803058
nodes  436934995
----------------
perft 11
h2g3   129045446
h8g7   311374433
e7f8   171775756
e7d8   191017270
e7d6   121118953
e7f6   114800590
g5h6   240489042
g5f6   170502051
e5f6   350321848
e5d6   370409101
c5d6   569148712
c5b6  1195360549
f4g3   214758930
b4a5   357351367
nodes 4507474048

Code: Select all

7Q/4Q3/8/2Q1Q1Q1/1Q1p1Q1p/p1p1p3/3p3P/q7 w - 1 42

          a b c d e f g h
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
8 * * * * . . . . . . . Q * * * * 8
7 * * * * . . . . Q . . . * * * * 7
6 * * * * . . . . . . . . * * * * 6
5 * * * * . . Q . Q . Q . * * * * 5
4 * * * * . Q . p . Q . p * * * * 4
3 * * * * p . p . p . . . * * * * 3
2 * * * * . . . p . . . P * * * * 2
1 * * * * q . . . . . . . * * * * 1
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
  * * * * * * * * * * * * * * * *
          a b c d e f g h

------------------------------------------------------------------
perftmc 11 (N = 51090 samples)
avg = 4.506710e+09 ; (sqrt{Σ[(sample_i - avg)²]})/N = 2.142231e+06
------------------------------------------------------------------
perftmc 12 (N = 45146 samples)
avg = 2.535752e+10 ; (sqrt{Σ[(sample_i - avg)²]})/N = 1.452082e+07
------------------------------------------------------------------
perftmc 13 (N = 40471 samples)
avg = 2.757799e+11 ; (sqrt{Σ[(sample_i - avg)²]})/N = 2.114642e+08
------------------------------------------------------------------
perftmc 14 (N = 36674 samples)
avg = 1.524398e+12 ; (sqrt{Σ[(sample_i - avg)²]})/N = 1.418613e+09
------------------------------------------------------------------
perftmc 15 (N = 33554 samples)
avg = 1.697516e+13 ; (sqrt{Σ[(sample_i - avg)²]})/N = 2.056086e+10
------------------------------------------------------------------
perftmc 16 (N = 30923 samples)
avg = 9.463964e+13 ; (sqrt{Σ[(sample_i - avg)²]})/N = 1.396105e+11
------------------------------------------------------------------
perftmc 17 (N = 28730 samples)
avg = 1.099909e+15 ; (sqrt{Σ[(sample_i - avg)²]})/N = 2.046285e+12
------------------------------------------------------------------
perftmc 18 (N = 26828 samples)
avg = 6.018354e+15 ; (sqrt{Σ[(sample_i - avg)²]})/N = 1.372541e+13
------------------------------------------------------------------
perftmc 19 (N = 25204 samples)
avg = 6.992525e+16 ; (sqrt{Σ[(sample_i - avg)²]})/N = 1.973487e+14
------------------------------------------------------------------
perftmc 20 (N = 23764 samples)
avg = 3.950268e+17 ; (sqrt{Σ[(sample_i - avg)²]})/N = 1.383354e+15

NebiyuCheckers uses a chess-like notation where a1 means square 4 and the start of the Old Faithful opening would be c3d4 d6c5 b2c3 f6g5 a1b2.

Good luck!

------------------------

[...] I don't know enough about Checkers to even see why the presented position is a fortress. [...]

That checkers position is a fortress because 7-10-11-15 white diamond can not be broken if white wants, plus the white checker at 12 is not forced to advance. The white checker at 13 can be forced to move (5-9 or 14-9 by red, then 13x6), but the white star move with this white checker at 6 is crowning it in square 1 and not in square 2: if white plays 6-2?, then red can force exchanges at square 6, breaking the white diamond with 10x1 at some point and red takes 19x10 (if white king is at square 3) or 19x10x3 (if white king is at square 4), looking really bad for white. For example: 5-9, 13x6; 14-9, 6-2?; 17-13 (preparing 9-6 in the next move).

Just crowning in square 1 allows white to play the white king at 4 to 8 and then to 4 or to 3 ad infinitum: 4-8-x-8-x-8-x-... (x = 3 or 4), not allowing exchanges at square 6, thus keeping closed the position. Please correct me if I am wrong, Martin.

Regards from Spain.

Ajedrecista.

[Uri Blass]

I do not understand how 4-8 is a legal move in checkers.
I know almost nothing about checkers but I know that there is a rule that if you can capture you have to do it
so white has to play 15 capture 18 and 26 or 13 capture 17 and 26 or 15 capture 19 based on my knowledge


Edit:Maybe it is capturing backward and capturing backward is not allowed except the case a king is capturing.

[Ajedrecista]

Hello Uri:

I do not understand how 4-8 is a legal move in checkers.
I know almost nothing about checkers but I know that there is a rule that if you can capture you have to do it
so white has to play 15 capture 18 and 26 or 13 capture 17 and 26 or 15 capture 19 based on my knowledge


Edit:Maybe it is capturing backward and capturing backward is not allowed except the case a king is capturing.

A not so little off-topic about draughts in a computer chess forum:

White pieces (silver in Martin's diagramme) start in squares 21 to 32 in English draughts/American checkers, while black or red pieces (golden) start in squares 1 to 12. Black side starts the game.

Golden checkers go towards higher numbered squares and crown in squares 29 to 32; silver checkers do the opposite: go towards lower numbered squares and crown in squares 1 to 4.

Just how looks the OP's board, the sense of advance of checkers is the same than in chess (white upwards and black downwards), while kings can move both forward and backward one square in each move unless there are captures.

Checkers can not capture backwards, as you already noted in your edit. Other draught variants allow it, such as International draughts (10x10 board). This is not the case in other variants like the present one, Spanish draughts and Italian draughts (checkers can not capture kings in Italian draughts).

There are many variants in draughts, making their history research very interesting IMHO. The older known books are about Spanish draughts in the late 16th century while the first known book about English draughts dates from 1756.

Regards from Spain.

Ajedrecista.

[fierz]

Most chess programs do not address the fortress problem. I don't know enough about Checkers to even see why the presented position is a fortress. But I could imagine that it would help to use the reversible-move counter for fortress detection. If the counter exceeds a certain (not-too-large) value, the evaluation should be quickly tapered towards a draw score.

Thanks for the suggestion! The reversible-move-counter alone will probably not help too much; in the position I showed maybe, but actually this is already quite far from the starting position of the problem - in the starting position, red still had two men that could be crowned to kings, so if for example the counter starts kicking in after 10 ply, there would still be 3 or 4 irreversible moves that red could make, to reset that counter, so it would have to search something like 50 ply which is not feasible. The other issue with reversible counters is that many endgames in checkers are long shuffling-arounds with kings, all reversible moves, but the stronger side slowly taking over the center, and forcing the weaker side to the edge etc, so in those cases it is perfectly find to make lots of reversible moves.
But maybe I can adapt your suggestion somehow, I will think about it!

[mvanthoor]

I don't know enough about Checkers to even see why the presented position is a fortress.

IIRC, in Checkers, you lose when you have no moves left.

Silver has one move, with the king in the top right, going back and forth. Gold can not capture any of the silver pieces. (You jump over them, and land on the free square right after the piece.) Because gold can't capture any silver pieces, and silver has one move left that gold can't take away, gold can't make progress towards a win. It's a fortress, because gold has a huge material advantage, and still can't win.

[hgm]

Silver has one move, with the king in the top right, going back and forth.

Silver has many moves. If he plays top-down, then he can (and I assume must) capture one of the Gold Kings, and moving the King on h8 would be illegal. So I assume he plays bottom-up. In which case he can move all of his checkors except one. (Apparently checkers cannot capture backwards, so that moving the King is legal in that case.)

[mvanthoor]

Silver has many moves. If he plays top-down, then he can (and I assume must) capture one of the Gold Kings, and moving the King on h8 would be illegal. So I assume he plays bottom-up. In which case he can move all of his checkors except one. (Apparently checkers cannot capture backwards, so that moving the King is legal in that case.)

You're right; I missed that in Checkers, capturing is mandatory (at least in the Dutch version). If it isn't, Silver does have a fortress; if he must capture, he has to capture two kings with 15-22-31.