maximum niumber of legal moves

Discussion about development of draughts in the time of computer and Internet.
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 12:26

TAILLE wrote:Let me try a first proposal with legal positions
Image
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
Posts: 1616
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: maximum niumber of legal moves

Post by Rein Halbersma » Tue Jun 19, 2018 12:29

TAILLE wrote:
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?
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
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 12:30

TAILLE wrote: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
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:37

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

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

Re: maximum niumber of legal moves

Post by Rein Halbersma » Tue Jun 19, 2018 13:00

TAILLE wrote:
Fabien Letouzey wrote:
TAILLE wrote:Let me try a first proposal with legal positions
Image
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
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 13:04

TAILLE wrote: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
Posts: 743
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Re: maximum niumber of legal moves

Post by Ed Gilbert » Tue Jun 19, 2018 13:20

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

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

Re: maximum niumber of legal moves

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

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

Re: maximum niumber of legal moves

Post by TAILLE » Tue Jun 26, 2018 23:00

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:

Image
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
Gérard

User avatar
ildjarn
Posts: 1448
Joined: Tue Aug 22, 2006 15:38
Real name: Joost de Heer

Re: maximum niumber of legal moves

Post by ildjarn » Wed Jun 27, 2018 06:46

Fabien Letouzey wrote: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.
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!

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 » Wed Jun 27, 2018 08:32

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

Re: maximum niumber of legal moves

Post by TAILLE » Fri Jun 29, 2018 13:13

Hi,

Image
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

Image
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

Image
you can count 26 capture moves but this position is not legal is it?
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 » Sat Jun 30, 2018 08:23

Hi Gérard,
TAILLE wrote:BTW in the following position
Image
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
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Re: maximum niumber of legal moves

Post by TAILLE » Sat Jun 30, 2018 19:51

Fabien Letouzey wrote:Hi Gérard,
TAILLE wrote:BTW in the following position
Image
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.
Gérard

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

Re: maximum niumber of legal moves

Post by TAILLE » Sun Jul 01, 2018 17:11

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 :P :

Image
45 moves

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

Post Reply