maximum niumber of legal moves

Discussion about development of draughts in the time of computer and Internet.
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

maximum niumber of legal moves

Post by TAILLE » Mon Jun 18, 2018 12:35

Hi,

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

Image
120 legal moves

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

Rein Halbersma
Posts: 1617
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: maximum niumber of legal moves

Post by Rein Halbersma » Mon Jun 18, 2018 23:54

TAILLE wrote:Hi,

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

Image
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
Posts: 275
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: maximum niumber of legal moves

Post by Fabien Letouzey » Tue Jun 19, 2018 06:52

Rein Halbersma wrote: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
Posts: 275
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: maximum niumber of legal moves

Post by Fabien Letouzey » Tue Jun 19, 2018 07:10

Fabien Letouzey wrote: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
Posts: 1617
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: maximum niumber of legal moves

Post by Rein Halbersma » Tue Jun 19, 2018 09:15

Fabien Letouzey wrote:
Rein Halbersma wrote: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.
Image

Rein Halbersma
Posts: 1617
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: maximum niumber of legal moves

Post by Rein Halbersma » Tue Jun 19, 2018 09:18

Fabien Letouzey wrote:
Fabien Letouzey wrote: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
Image

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

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: maximum niumber of legal moves

Post by TAILLE » Tue Jun 19, 2018 10:24

Rein Halbersma wrote:
Fabien Letouzey wrote:
Fabien Letouzey wrote: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
Image

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

why not adding, in your last diagramm some new white kings ?
Image
332 moves
Gérard

Fabien Letouzey
Posts: 275
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: maximum niumber of legal moves

Post by Fabien Letouzey » Tue Jun 19, 2018 10:30

TAILLE wrote: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
Posts: 1617
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: maximum niumber of legal moves

Post by Rein Halbersma » Tue Jun 19, 2018 10:48

Fabien Letouzey wrote:
TAILLE wrote: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
Posts: 1617
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: maximum niumber of legal moves

Post by Rein Halbersma » Tue Jun 19, 2018 10:52

Fabien Letouzey wrote:
TAILLE wrote: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?
Image

Fabien Letouzey
Posts: 275
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: maximum niumber of legal moves

Post by Fabien Letouzey » Tue Jun 19, 2018 10:58

Rein Halbersma wrote: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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: maximum niumber of legal moves

Post by TAILLE » Tue Jun 19, 2018 11:17

[quote="TAILLE"]Hi,

Image
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
Image
10-4 46-41

Without this constraint of legal position I would have proposed
Image
128 moves

Let me try a first proposal with legal positions
Image
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!
Gérard

Rein Halbersma
Posts: 1617
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: maximum niumber of legal moves

Post by Rein Halbersma » Tue Jun 19, 2018 11:22

Fabien Letouzey wrote:
Rein Halbersma wrote: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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: maximum niumber of legal moves

Post by TAILLE » Tue Jun 19, 2018 12:07

Rein Halbersma wrote:
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:
Image
By adding a black piece on square 3 you greatly improve the number of moves don't you?
Gérard

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: maximum niumber of legal moves

Post by TAILLE » Tue Jun 19, 2018 12:17

Rein Halbersma wrote:
Fabien Letouzey wrote:
TAILLE wrote: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?
Image
Hi Fabien,

Why do you put white kings on 2 and 15?
Gérard

Post Reply