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
Fortress detection?
Moderators: hgm, Rebel, chrisw
-
- Posts: 72
- Joined: Mon Mar 07, 2016 4:41 pm
- Location: Zürich, Switzerland
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fortress detection?
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.
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.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Fortress detection?
In Pawn endings maybe Blockage Detection?
See also Code of Chiron for Detection of Pawn Blockages by Ubaldo Andrea Farina.
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Fortress detection?
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:
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!
------------------------
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.
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
Good luck!
------------------------
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.
-
- Posts: 10314
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Fortress detection?
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.
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.
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Fortress detection?
Hello Uri:
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.
A not so little off-topic about draughts in a computer chess forum:Uri Blass wrote: ↑Wed Jul 21, 2021 11:38 pm 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.
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.
-
- Posts: 72
- Joined: Mon Mar 07, 2016 4:41 pm
- Location: Zürich, Switzerland
Re: Fortress detection?
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.hgm wrote: ↑Wed Jul 21, 2021 5:36 pm 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.
But maybe I can adapt your suggestion somehow, I will think about it!
-
- Posts: 1784
- Joined: Wed Jul 03, 2019 4:42 pm
- Location: Netherlands
- Full name: Marcel Vanthoor
Re: Fortress detection?
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.
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fortress detection?
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.)
-
- Posts: 1784
- Joined: Wed Jul 03, 2019 4:42 pm
- Location: Netherlands
- Full name: Marcel Vanthoor
Re: Fortress detection?
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.hgm wrote: ↑Tue Jul 27, 2021 6:54 pm 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.)