maximum niumber of legal moves

[TAILLE]

Hi,

For me the position without captures leading to the maximum of legal moves is the following:


120 legal moves

What is for you the record if you take into consideration the positions with captures?

[Rein Halbersma]

Hi,

For me the position without captures leading to the maximum of legal moves is the following:


120 legal moves

What is for you the record if you take into consideration the positions with captures?

Hi Gerard,

Nice topic. I must confess that one month ago Fabien alerted me to your discussion of this very topic on the French forum 5 years ago. I won't disclose the positions you found there, to keep other readers guessing. And one week prior to my exchange with Fabien, I wrote to Ed that I would like to enumerate all such capture positions to find the largest. Talking about coincidences

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.

Since I'm only interested in the maximum number, I don't have to build a database of these positions, just generate them on the fly. I think it could be computed in a month or so.

Is such brute force enumeration how you found your positions?

BTW, finding captures in international draughts on an NxN board is NP-hard as N grows:
https://cstheory.stackexchange.com/ques ... -correctly

See also section 30.13: http://jeffe.cs.illinois.edu/teaching/a ... nphard.pdf

[Fabien Letouzey]

Since I'm only interested in the maximum number, I don't have to build a database of these positions, just generate them on the fly. I think it could be computed in a month or so.

Meanwhile, random generation (with your conditions) already gives us a lower bound: 182. I don't know how to display a board; the FEN is W:WK5,K36,K46:B10,17,18,20,24,33,34,38,41,42

Fabien.

[Fabien Letouzey]

Meanwhile, random generation (with your conditions) already gives us a lower bound: 182. I don't know how to display a board; the FEN is W:WK5,K36,K46:B10,17,18,20,24,33,34,38,41,42

And by relaxing the conditions, 251 moves are possible with 4 kings and 14 men: W:WK1,K26,K46,K50:B7,8,11,13,19-21,24,29,30,33,38,41,42

[Rein Halbersma]

Since I'm only interested in the maximum number, I don't have to build a database of these positions, just generate them on the fly. I think it could be computed in a month or so.

Meanwhile, random generation (with your conditions) already gives us a lower bound: 182. I don't know how to display a board; the FEN is W:WK5,K36,K46:B10,17,18,20,24,33,34,38,41,42

Fabien.

[Rein Halbersma]

Meanwhile, random generation (with your conditions) already gives us a lower bound: 182. I don't know how to display a board; the FEN is W:WK5,K36,K46:B10,17,18,20,24,33,34,38,41,42

And by relaxing the conditions, 251 moves are possible with 4 kings and 14 men: W:WK1,K26,K46,K50:B7,8,11,13,19-21,24,29,30,33,38,41,42

Created from https://fmjd.org/dias2/create.php

[TAILLE]

Meanwhile, random generation (with your conditions) already gives us a lower bound: 182. I don't know how to display a board; the FEN is W:WK5,K36,K46:B10,17,18,20,24,33,34,38,41,42

And by relaxing the conditions, 251 moves are possible with 4 kings and 14 men: W:WK1,K26,K46,K50:B7,8,11,13,19-21,24,29,30,33,38,41,42

Created from https://fmjd.org/dias2/create.php

Hi,

why not adding, in your last diagramm some new white kings ?

332 moves

[Fabien Letouzey]

why not adding, in your last diagramm some new white kings ?

Because I trusted Rein's pre-analysis

But indeed more pieces is better. This one has 407 moves using 8 kings and 14 men: W:WK2,K4,K5,K15,K16,K26,K36,K46:B7,8,11,13,19-21,29-31,33,38,41,42

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

[Rein Halbersma]

why not adding, in your last diagramm some new white kings ?

Because I trusted Rein's pre-analysis

I only said 3-4 kings because exhaustive enumeration becomes too expensive for up to 18 kings For random generation, you can go much further.

[Rein Halbersma]

why not adding, in your last diagramm some new white kings ?

Because I trusted Rein's pre-analysis

But indeed more pieces is better. This one has 407 moves using 8 kings and 14 men: W:WK2,K4,K5,K15,K16,K26,K36,K46:B7,8,11,13,19-21,29-31,33,38,41,42

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

[Fabien Letouzey]

I only said 3-4 kings because exhaustive enumeration becomes too expensive for up to 18 kings For random generation, you can go much further.

I see. Random search suggests around 8 kings and 14 men; that seems nearly the worst case for exhaustive search: about half of the available squares (old memories from the binomial distribution).

That last board was generated by starting with a "cross" pattern for men (2 crossing diagonals) and putting the remaining men next to kings. These constraints might not be optimal, but they allow easy generation of positions with 400+ moves. Isn't that 3x more than previously believed?

[TAILLE]

[quote="TAILLE"]Hi,


120 legal moves

Seeing your posts it appears obviously that we have two kinds of problems, depending on whether or nor we accept non legal positions (i.e. position that cannot be reach in game play).
I easily imagine the position above is legal when you start with

10-4 46-41

Without this constraint of legal position I would have proposed

128 moves

Let me try a first proposal with legal positions

174 moves

You may ask why I add a white king on square 5. The reason is that now this position is quite beautiful because there is only one winning move and after this winning move the endgame is still quite elegant!

[Rein Halbersma]

I only said 3-4 kings because exhaustive enumeration becomes too expensive for up to 18 kings For random generation, you can go much further.

I see. Random search suggests around 8 kings and 14 men; that seems nearly the worst case for exhaustive search: about half of the available squares (old memories from the binomial distribution).

That last board was generated by starting with a "cross" pattern for men (2 crossing diagonals) and putting the remaining men next to kings. These constraints might not be optimal, but they allow easy generation of positions with 400+ moves. Isn't that 3x more than previously believed?

It might also be possible to put kings in the middle of the board. I think that the most moves can be gotten if many kings can capture many subsets of the men. Since there can be at most 19 men, the maximum is choose(19,10) or choose(19,9) = 92.378 subsets. If you put men on half of the 32 inner squares, you get choose(16,8) = 12.870 subsets. And that still times the number of kings. Either way, we are not quite at the limit

[TAILLE]

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?

[TAILLE]

why not adding, in your last diagramm some new white kings ?

Because I trusted Rein's pre-analysis

But indeed more pieces is better. This one has 407 moves using 8 kings and 14 men: W:WK2,K4,K5,K15,K16,K26,K36,K46:B7,8,11,13,19-21,29-31,33,38,41,42

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

Hi Fabien,

Why do you put white kings on 2 and 15?