maximum niumber of legal moves

[Fabien Letouzey]

Let me try a first proposal with legal positions

174 moves

If I only allow the cross pattern, I get 225 with 6 kings: W:WK1-3,K6,K16,K26:B10,14,19,22,23,32,33,37,39,41,44

If you want something better, just post an efficient algorithm for legality test, and I'll make sure to use it.

[Rein Halbersma]

The math is pretty easy: a capture victim can only sit in the inner 8x8 board, so 32 squares. You can capture at most 19 men, so you need all binom(32, i) for i = 1 through 19, which is 4 billion positions. Then you put up to 3 or 4 kings on the edges (18 squares), so binom(18, i) for i = 1 through 4, which is 4K positions, so 1.6 10^13, pretty big but comparable to generating 8 pc dbs. If you just fix the number of men to 10 and kings to 3, it's only 52 billion positions.

Hi Rein,

I do not fully understand your reasonning. Why do you exclude black pieces on the edge of the board?
Let's take the following position:

By adding a black piece on square 3 you greatly improve the number of moves don't you?

You are right. As I explained earlier, it was a pragmatic choice to limit the number of enumerations. For random generation, your method is better.

[Fabien Letouzey]

Why do you put white kings on 2 and 15?

The algorithm is the classical "generate and test". In my case:
1) pick the number of kings and place them at random
2) pick the number of men and place them at random (with constraints)
3) count the number of moves

I will add a clean-up phase that removes useless pieces, good idea.

Instead you seem to be suggesting to add kings last, and one by one. It could be more efficient, but that feels a lot slower to me.

[TAILLE]

Let me try a first proposal with legal positions

174 moves

If I only allow the cross pattern, I get 225 with 6 kings: W:WK1-3,K6,K16,K26:B10,14,19,22,23,32,33,37,39,41,44

If you want something better, just post an efficient algorithm for legality test, and I'll make sure to use it.

Fabien,
As I said my proposal was made in the context of legal positions (i.e. positions that can be reach from the initial 20x20 position). When looking at your proposal I doubt it is legal position but I see your point. Unfortunetly I do not know an efficient algorithm to verify if a position is legal or not and my verification is only manual!

[Rein Halbersma]

Let me try a first proposal with legal positions

174 moves

If I only allow the cross pattern, I get 225 with 6 kings: W:WK1-3,K6,K16,K26:B10,14,19,22,23,32,33,37,39,41,44

If you want something better, just post an efficient algorithm for legality test, and I'll make sure to use it.

Fabien,
As I said my proposal was made in the context of legal positions (i.e. positions that can be reach from the initial 20x20 position). When looking at your proposal I doubt it is legal position but I see your point. Unfortunetly I do not know an efficient algorithm to verify if a position is legal or not and my verification is only manual!

I once made a proof game of a position where a white king captures 19 black men: viewtopic.php?f=65&t=276&p=122166#p122166

[Fabien Letouzey]

Unfortunetly I do not know an efficient algorithm to verify if a position is legal or not and my verification is only manual!

No problem: you can be step 4, then.

2 kings:
174 W:WK2,K3:B10,14,18,19,28,29,32,34,37,40,41

3 kings:
180 W:WK26,K36,K48:B10,11,14,17,19,22,23,32,33,39,44
191 W:WK25,K35,K49:B7,10,12,14,18,19,28,29,32,37,41
194 W:WK2-4:B10,14,18,19,28,29,32,34,37,40,41

[Ed Gilbert]

Looks like I will have to increase the size of my movelist. I had not expected more than 128 moves.

[Rein Halbersma]

Looks like I will have to increase the size of my movelist. I had not expected more than 128 moves.

I'm using a Boost container for this: https://www.boost.org/doc/libs/1_67_0/d ... ector.html

"small_vector is a vector-like container optimized for the case when it contains few elements. It contains some preallocated elements in-place, which can avoid the use of dynamic storage allocation when the actual number of elements is below that preallocated threshold."

[TAILLE]

Hi,

I noted the 407 moves of Fabien records (congratulation!) and at the same time, I continued to work on legal positions.
My record is now illustrated by the following positions:


228 moves ... and only one winning move!

Proof of legality:
01.34-29 19-23 02.35-30 23x25 03.40-34 14-19 04.34-30 25x34 05.39x30 20-25 06.33-29 25x23 07.31-27 10-14 08.32-28 23x21 09.36-31 5-10 10.43-39 19-23
11.31-27 21x34 12.45-40 34x45 13.44-40 45x34 14.37-32 17-22 15.41-37 22-27 16.32x21 16x27 17.37-32 27x38 18.42x33 15-20 19.46-41 20-24 20.41-37 24-29
21.33x24 14-19 22.24-20 10-14 23.20-15 23-28 24.50-44 19-23 25.44-39 34x43 26.48x39 14-19 27.39-34 18-22 28.37-31 13-18 29.31-27 22x31 30.47-42 9-13
31.42-38 4-9 32.38-32 28x37 33.49-43 11-17 34.43-38 17-22 35.38-32 37x28 36.15-10 22-27 37. 10-4 6-11 38. 4-15 11-17 39.34-30 17-21 40.15-38 1-6
41.30-25 6-11 42.25-20 11-17 43.20-15 7-11 44.15-10 2-7 45. 10-4 17-22 46.38-49 31-37 47. 4-15 9-14 48.15-38 3-9 49.49-40 12-17 50.38-49 14-20
51.40-45 20-24 52.45-50 23-29 53.49-44 18-23 54.44-49 29-34 55.49-44 23-29 56.44-49 9-14 57.50-45 28-33 58.45-50 22-28 59.50-45 37-42 60.49-44 27-32
61.44-35 32-38 62.35-40 38-43 63.40-35 17-22 64.35-44 22-27 65.44-40 14-20 66.40-35 28-32 67.35-40 24-30 68.40-35 34-40

[ildjarn]

Is there an automated way to convert FEN to a picture?

https://toernooibase.kndb.nl/applet/oer ... 2&size=300
Doesn't seem to support the - for multiple pieces in a row though.

[Fabien Letouzey]

https://toernooibase.kndb.nl/applet/oer ... 2&size=300
Doesn't seem to support the - for multiple pieces in a row though.

Thanks!

That's OK, it's an optional extension in my program.

[TAILLE]

Hi,


228 capture moves

You have seen that my record for the maximum number of moves in a legal position is 228 with the position above.

After having change some constraints in my program I searched the maximum number of capture moves we can reach without any king (typically in a breakthrough draughts environment) for a legal position.

With only one white man on the board I found the following position


13 capture moves

Proof of legality (in a breakthrough draughts environment):
01.31-26 20-25 02.32-27 17-21 03.26x17 11x31 04.37x26 19-23 05.34-29 23x34 06.40x29 12-17 07.33-28 16-21 08.39-33 17-22 09.28x17 21x12 10.44-39 14-19
11.50-44 10-14 12.41-37 14-20 13.37-32 9-14 14.46-41 3-9 15.41-37 6-11 16.32-28 11-17 17.37-32 5-10 18.29-24 19x30 19.35x24 20x29 20.33x24 1-6
21.38-33 6-11 22.42-38 11-16 23.48-42 16-21 24.24-20 15x24 25.45-40 14-19 26.36-31 10-14 27.42-37 25-30 28.33-29 24x22 29.39-33 7-11 30.44-39 14-20
31.32-28 20-24 32.37-32 9-14 33.32-27 21x23 34.38-32 14-20 35.43-38 23-29 36.33-28 22x35 37.31-27 11-16 38.32-28 2-7 39.49-44 4-10 40.26-21 17x26
41.47-41 12-17 42.28-23 19x28 43.41-36 13-19 44.27-21 16x27 45.38-32 27x38 46.36-31 26x37 47.44-39 30-34 48.39x30 35-40 49.30-25 24-30

My current record (with more than 1 white man) is 20 capture moves in a legal breakthrough draughts environment.
Can you get a better record ?

BTW in the following position


you can count 26 capture moves but this position is not legal is it?

[Fabien Letouzey]

Hi Gérard,

BTW in the following position

you can count 26 capture moves but this position is not legal is it?

This one with a nice symmetry:
28 moves: https://toernooibase.kndb.nl/applet/oer ... 4&size=300

For records, you need much weirder positions like those:
41 moves: https://toernooibase.kndb.nl/applet/oer ... 4&size=300
43 moves: https://toernooibase.kndb.nl/applet/oer ... 4&size=300

The FENs are in the URLs.

Fabien.

[TAILLE]

Hi Gérard,

BTW in the following position

you can count 26 capture moves but this position is not legal is it?

This one with a nice symmetry:
28 moves: https://toernooibase.kndb.nl/applet/oer ... 4&size=300

For records, you need much weirder positions like those:
41 moves: https://toernooibase.kndb.nl/applet/oer ... 4&size=300
43 moves: https://toernooibase.kndb.nl/applet/oer ... 4&size=300

The FENs are in the URLs.

Fabien.

Hi Fabien,

As you have seen I did not try to search the record for illegal positions, but, seing your results I will certainly try to confirm your result. I will keep you inform.

I gave you a typical illegal position with only three men in order to show you what kind of position you have to ignore in your algorithm when you consider only legal positions.
Seeing such positions I added some constraints to eliminate all these obviously illegal positions and, for the time being, all positions I found with my new constraints where really legal positions. Does that mean that the constraints I added are too strong? I do not know. May be you can find a better approach?

Anyway my record is still 20 capture moves in a (breakthrough draughts) legal position.

[TAILLE]

Hi Fabien,

Oops if you accept illegal positions then, the position with the maximum moves in a context of men positions (no kings) is not a position with captures but simply the obvious following one :


45 moves

BTW I did not manage to get a better figure than your 43 moves for an illegal position with captures.