The maximum number of legal moves

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

The maximum number of legal moves

Postby Igor Gorelikov » 17 Mar 2005, 11:15

What is the maximum number of legal moves in a game?
(After going through several games, it is 51 but who knows...)

regards,
Igor
User avatar
Igor Gorelikov
 
Posts: 153
Joined: 27 Sep 2004, 10:12
Location: St. Petersburg, Russia

Re: The maximum number of legal moves

Postby Alessandro Scotti » 17 Mar 2005, 11:48

This one:

[diag]3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1[/diag]

should have about 218 legal moves.
User avatar
Alessandro Scotti
 
Posts: 306
Joined: 20 Nov 2004, 00:10
Location: Rome, Italy

Re: The maximum number of legal moves

Postby Alessandro Scotti » 17 Mar 2005, 11:49

This one:

[diag]q2Q3r/n6R/kpB1N1K1/p1p1Bppp/1PN3P1/1n1pp1b1/P1PPPP1P/r5Rb w - - 0 1[/diag]

has 99 moves with all 32 pieces on the board.
User avatar
Alessandro Scotti
 
Posts: 306
Joined: 20 Nov 2004, 00:10
Location: Rome, Italy

Re: The maximum number of legal moves

Postby Alessandro Scotti » 17 Mar 2005, 11:51

And finally this one:

[diag]n1r1r1b1/1P1P1P1P/1Q6/3NBNK1/R7/4p1p1/3PBPkP/2R5 w - - 0 1[/diag]

has 144 moves and doesn't make use of promoted pieces.
User avatar
Alessandro Scotti
 
Posts: 306
Joined: 20 Nov 2004, 00:10
Location: Rome, Italy

Re: The maximum number of legal moves

Postby Alessandro Scotti » 17 Mar 2005, 11:52

I got the info from an old CCC thread, see:

http://chessprogramming.org/cccsearch/ccc.php?art_id=69703

for some more.
User avatar
Alessandro Scotti
 
Posts: 306
Joined: 20 Nov 2004, 00:10
Location: Rome, Italy

Re: The maximum number of legal moves

Postby Igor Gorelikov » 17 Mar 2005, 12:03

Hi Alessandro!

Thanks a lot for the link.
I think that 92 (the number indicated by Andreas Stabel) is enough for my data structures since I'm looking for the minimum of the maximum ;-)

Igor
User avatar
Igor Gorelikov
 
Posts: 153
Joined: 27 Sep 2004, 10:12
Location: St. Petersburg, Russia

Re: The maximum number of legal moves

Postby Reinhard Scharnagl » 17 Mar 2005, 13:14

Hi Igor,
Igor wrote:I think that 92 (the number indicated by Andreas Stabel) is enough ...

why do you have to implement a limit? Smirf tolerates any square to be filled with a piece and handles as much moves in a ply as existing.

Regards, Reinhard.
Reinhard Scharnagl
 
Posts: 608
Joined: 01 Oct 2004, 08:36
Location: Klein-Gerau, Germany

Re: The maximum number of legal moves

Postby Igor Gorelikov » 17 Mar 2005, 13:45

Hi Reinhard,

I don't know a single computer with unlimited resourses ;-)

Igor
User avatar
Igor Gorelikov
 
Posts: 153
Joined: 27 Sep 2004, 10:12
Location: St. Petersburg, Russia

Re: The maximum number of legal moves

Postby Reinhard Scharnagl » 17 Mar 2005, 13:48

Hi Igor,

Igor Gorelikov wrote:Hi Reinhard,

I don't know a single computer with unlimited resourses ;-)

Igor

allocating ressources at need or organizing then in a pseudo stack does not mean to use unlimited amounts of memory.

Reinhard.
Reinhard Scharnagl
 
Posts: 608
Joined: 01 Oct 2004, 08:36
Location: Klein-Gerau, Germany

Re: The maximum number of legal moves

Postby Dann Corbit » 17 Mar 2005, 19:19

Igor Gorelikov wrote:What is the maximum number of legal moves in a game?
(After going through several games, it is 51 but who knows...)

regards,
Igor

218 is the largest known, but it could be bigger.

Logically, if you need a maximum dimention 256 is a logical choice. It is very unlikely to overflow and it is still quite small.

The latest C standard has variant arrays that are automatic. That means you can dimention things on the fly and they only use the space actually needed. You don't need to know the size at compile time.
Dann Corbit
 

Re: The maximum number of legal moves

Postby Reinhard Scharnagl » 17 Mar 2005, 21:21

Hi Dann,
Dann wrote:The latest C standard has variant arrays that are automatic.

I thought that would be part of STL, but even that container type is not needed. In Smirf there ONCE a pseudo stack is allocated, where each ply can buffer its moves (concatenated).

Of course the size of that array is limited. But it is making more sense to limit the sum of moves of plies instead the amount of each ply, because the average of all will not be that big.

Reinhard.
Reinhard Scharnagl
 
Posts: 608
Joined: 01 Oct 2004, 08:36
Location: Klein-Gerau, Germany

Re: The maximum number of legal moves

Postby Igor Gorelikov » 18 Mar 2005, 10:57

"The latest C standard... "

I use macro assembler (MASM32) to program.

regards,
Igor
User avatar
Igor Gorelikov
 
Posts: 153
Joined: 27 Sep 2004, 10:12
Location: St. Petersburg, Russia

Re: The maximum number of legal moves

Postby Reinhard Scharnagl » 18 Mar 2005, 11:54

Hi Igor,
Igor wrote:I use macro assembler (MASM32) to program. ...

where do you see the advantages? Can you give an example? Still I cannot see what this feature has to do with limiting a ply's moves' storage .

A lot of years ago I started chess programming with Z80 assembler. But today I am convinced, that change of data structures and methods could be done far quicker in C/C++ than in ASM. From that my conclusion is, that switching (partially) to ASM would make sense from that moment, where I would have no more "big" ideas left. Then it could help to optimize the status quo.

Regards, Reinhard.
Reinhard Scharnagl
 
Posts: 608
Joined: 01 Oct 2004, 08:36
Location: Klein-Gerau, Germany

Re: The maximum number of legal moves

Postby Alessandro Scotti » 18 Mar 2005, 15:53

Reinhard Scharnagl wrote:where do you see the advantages? Can you give an example?


Yes there is no reason for it! I've always used TASM and it was much better! :wink:

Reinhard Scharnagl wrote:A lot of years ago I started chess programming with Z80 assembler...


Do you still have some working code? I have developed a Z80 emulator and it would be interesting to see the program running...
User avatar
Alessandro Scotti
 
Posts: 306
Joined: 20 Nov 2004, 00:10
Location: Rome, Italy

Re: The maximum number of legal moves

Postby Igor Gorelikov » 18 Mar 2005, 16:16

Reinhard Scharnagl wrote:Hi Dann,

Of course the size of that array is limited. But it is making more sense to limit the sum of moves of plies instead the amount of each ply, because the average of all will not be that big.

Reinhard.


I need to know that magic number just to allocate temporary one-ply array for move ordering.
Of course, to calculate all-ply storage it is better to use average value.
So the more important number is:

the AVERAGE number of legal moves per a ply

In the articles I read it is about 35-40.
Any opinions?

Igor
User avatar
Igor Gorelikov
 
Posts: 153
Joined: 27 Sep 2004, 10:12
Location: St. Petersburg, Russia

Re: The maximum number of legal moves

Postby Reinhard Scharnagl » 18 Mar 2005, 16:33

Hi Alessandro,
Alessandro Scotti wrote:
Reinhard Scharnagl wrote:where do you see the advantages? Can you give an example?
Yes there is no reason for it! I've always used TASM and it was much better!
I have not targeted the TASM / MASM war (I am using TASM myself sometimes). Instead I want to learn something on the benefits from switching to Assembler language.
Alessandro Scotti wrote:
Reinhard Scharnagl wrote:A lot of years ago I started chess programming with Z80 assembler...
Do you still have some working code? I have developed a Z80 emulator and it would be interesting to see the program running...
No, but I still have some pages of its listing. It will not make sense to reprogram it into an emulator. I always have compared results during the time when working (mostly) on my move generator - and ignoring the improvements of processor speeds, today it is about estimated 10 times faster, mostly based on a far better data structure and board representation. Those days I had started with an 0x88 representation (not knowing that this would be a common approach). Today I use a flat data structure where pieces at the same time are member of two sorted double linked lists and containing bit encoded informations on their gaits and other properties. That structure enables Smirf to have ALL squares filled with pieces if need be, to support additional piece (Capablanca) types like Chancellor and Archbishop, and to switch internally when representing 10x8 instead of 8x8 positions. Thus there is only one Smirf engine supporting 8x8 and 10x8 chess as well, Chess960 castlings included.

Reinhard.
Reinhard Scharnagl
 
Posts: 608
Joined: 01 Oct 2004, 08:36
Location: Klein-Gerau, Germany

Re: The maximum number of legal moves

Postby Alessandro Scotti » 18 Mar 2005, 17:18

Reinhard Scharnagl wrote:Hi Alessandro,
Alessandro Scotti wrote:
Reinhard Scharnagl wrote:where do you see the advantages? Can you give an example?
Yes there is no reason for it! I've always used TASM and it was much better!
I have not targeted the TASM / MASM war (I am using TASM myself sometimes). Instead I want to learn something on the benefits from switching to Assembler language.


Hi Reinhard,
I was only joking on MASM/TASM! :) My opinion is we're all probably doing this thing for fun and assembly programming can give some thrills that higher level languages do not provide anymore... It's not a technical reason IMHO!
User avatar
Alessandro Scotti
 
Posts: 306
Joined: 20 Nov 2004, 00:10
Location: Rome, Italy


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 4 guests