max amount of moves from a position?

[smatovic]

a basic question:

How many possible, legal moves can i get from one board position?

I thought it were 218, but maybe it is less?

--
Srdja

[outAtime]

Yes, I read in another post here its 218 and had that number written down, but that is highly contrived so the maximum number of moves that might realistically occur must be less. Not sure how much less.

[wgarvin]

See here:
http://www.stmintz.com/ccc/index.php?id=424966

In a post in that thread, Vincent Diepeveen mentions a theoretical limit of 220 legal moves, and that he had managed to construct a position with 218 legal moves:
http://www.stmintz.com/ccc/index.php?id=425058

Its also mentioned in that thread that the limit for pseudo-legal moves might be a bit higher (225?).

Edit: lower in the thread, this position is posted:
[D]3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1

It apparently has 218 legal moves, and Steven Edwards lists them all in this post:
http://www.stmintz.com/ccc/index.php?id=424980

[Kempelen]

It is true that you can get a position with lots ( 200 ?? ) of moves, but I coded my engine for a max of 128. getting more is bad for cache use, memory access and so on. I have played hundred of games and never found a seg fault because it. Anyway it would be far more functional and optimized to have an dynamic array, maybe static in size for max moves per game, where you store the first array index for first move and last array index for last move in aech position. You can toy with similar ideas. I think having the just needed space is better than having lot of unused memory space. Maybe I would fix my engine in that direction in the future.

[smatovic]

and that he had managed to construct a position with 218 legal moves:

hmm, does "construct" also mean that this position can be reached during a legal game or is it only a theoretical set of pieces?

--
Srdja

[smatovic]

i think about an parallel processing scheme for all possible moves of an position...maybe i will use 128 an build some kind of overflow handling in.

--
Srdja

[hgm]

I always use a very generous space per ply on my move stack. Large holes in the stack hardy hurt, because memory that is not used is also not cached. Address space is not a very scarce commodity.

E.g., if I use 480 moves of 4 bytes each, i.e. 1920 bytes, i.e. 128 (= 2 cache lines) less than 2KB. This means that after 2 ply the moves are stored 4KB + 256 further in memory, and as the cache ways (on the Intel machines I use) are 4KB, those moves map 256 bytes before it in the cache (taking the address modulo 4K). So I can now store 64 moves before I collide (in cache) with the start of the moves from two ply before.

That is usually enough. (I like to have some leeway, though, because I extend the stack of moves for each ply in two directions, pushing captures on one end, and non-captures on the other, and sort the best move of an IID iterations to front by moving it in front of the captures, which makes the move list slowly creep through memory.) But even if it is not enough, there is plenty of room for the move list to grow further. It does not really overwrite anything if it does. It just causes cache collisions.

And as the L1 cache is 8-way, you can afford a few of those before you really get into trouble. You need one cache way for the stack, one cache way for irregular infrequent memory accesses such as hash probes, and a number of cache ways for your board, piece list, PST, zobrist key tables. If that totals 16KB contiguous memory it would be another 4 cache ways.

[bob]

Yes, I read in another post here its 218 and had that number written down, but that is highly contrived so the maximum number of moves that might realistically occur must be less. Not sure how much less.

Nothing says that is "the most" All one can say is "that is the moves moves from a single position to date..." Which is not quite the same thing...

[Arpad Rusz]

For legal positions with no promoted men the following position holds the record (Jenő Bán, 1960):

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

(144 white moves)

**************************

The max. number of captures for one side in a legal position (T.Marlow, W.Cross, 1967)

[D]r1n1n1b1/1P1P1P1P/1N1N1N2/2RnQrRq/2pKp3/3BNQbQ/k7/4Bq2 w - - 0 1

(74 white captures)

[Arpad Rusz]

The 218 moves record is by A.Dickins (1968).

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