World Draughts Forum

It is currently Mon Sep 24, 2018 01:54

All times are UTC+02:00




Post new topic  Reply to topic  [ 38 posts ]  Go to page 1 2 3 Next
Author Message
PostPosted: Mon Jun 18, 2018 12:35 
Offline

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


Top
   
PostPosted: Mon Jun 18, 2018 23:54 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1604
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


Top
   
PostPosted: Tue Jun 19, 2018 06:52 
Offline

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


Top
   
PostPosted: Tue Jun 19, 2018 07:10 
Offline

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


Top
   
PostPosted: Tue Jun 19, 2018 09:15 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1604
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


Top
   
PostPosted: Tue Jun 19, 2018 09:18 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1604
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


Top
   
PostPosted: Tue Jun 19, 2018 10:24 
Offline

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


Top
   
PostPosted: Tue Jun 19, 2018 10:30 
Offline

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


Top
   
PostPosted: Tue Jun 19, 2018 10:48 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1604
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.


Top
   
PostPosted: Tue Jun 19, 2018 10:52 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1604
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


Top
   
PostPosted: Tue Jun 19, 2018 10:58 
Offline

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


Top
   
PostPosted: Tue Jun 19, 2018 11:17 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 946
Location: FRANCE
[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


Top
   
PostPosted: Tue Jun 19, 2018 11:22 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1604
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 :)


Top
   
PostPosted: Tue Jun 19, 2018 12:07 
Offline

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


Top
   
PostPosted: Tue Jun 19, 2018 12:17 
Offline

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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 38 posts ]  Go to page 1 2 3 Next

All times are UTC+02:00


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited