The maximum number of legal moves

[Igor Gorelikov]

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

regards,
Igor

[Alessandro Scotti]

This one:

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

should have about 218 legal moves.

[Alessandro Scotti]

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.

[Alessandro Scotti]

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.

[Alessandro Scotti]

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

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

for some more.

[Igor Gorelikov]

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

[Reinhard Scharnagl]

Hi Igor,

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.

[Igor Gorelikov]

Hi Reinhard,

I don't know a single computer with unlimited resourses

Igor

[Reinhard Scharnagl]

Hi Igor,

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.

[Dann Corbit]

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.

[Reinhard Scharnagl]

Hi Dann,

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.

[Igor Gorelikov]

"The latest C standard... "

I use macro assembler (MASM32) to program.

regards,
Igor

[Reinhard Scharnagl]

Hi Igor,

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.

[Alessandro Scotti]

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!

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...

[Igor Gorelikov]

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

[Reinhard Scharnagl]

Hi Alessandro,

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.

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.

[Alessandro Scotti]

Hi Alessandro,

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!