Max moves in a position

[lauriet]

Hi All,

Does anyone know the maximum possible moves in a position (any position).
I am working on my move gen and want to allow enough spots in the array, but not too many.

Thanks
Laurie.

[Milos]

uint8 will suffice.

[AlvaroBegue]

I believe 218 is the right number, but I am not sure if it is the maximum known or if it is known to be the maximum.

I use 256 entries in an array that holds the moves.

[Evert]

Does anyone know the maximum possible moves in a position (any position).
I am working on my move gen and want to allow enough spots in the array, but not too many.

As mentioned, the maximum seems to be 218 for chess. Using maximum number of moves on an empty board and ignoring blockers, you get an upper limit of 300 moves or so.

Having said that, if you don't allocate your move list on the stack, but in an array indexed by ply level, there is no reason not to grow the list dynamically. The few times you need to realloc() it are insignificant. I do this in SjaakII, which can play variants where the number of moves can be several hundred or a thousand in actual middle-game positions.

[hgm]

I usually keep a dedicated software stack for moves. Because there is virtually no performance penalty on leaving contiguous chunks of memory unused (as these would never be cached, and it is cache space that is the scarce resource), I skip some 200 bytes between the move list of the previous ply and a new one for the next. That allows me to grow the list in two directions during generation and sorting. So that the captures can be added to the front of the list, (in the gap) and the non-captures to the end (at the topof the stack).

[syzygy]

I usually keep a dedicated software stack for moves. Because there is virtually no performance penalty on leaving contiguous chunks of memory unused (as these would never be cached, and it is cache space that is the scarce resource), I skip some 200 bytes between the move list of the previous ply and a new one for the next. That allows me to grow the list in two directions during generation and sorting. So that the captures can be added to the front of the list, (in the gap) and the non-captures to the end (at the topof the stack).

Wouldn't that lose 64 bytes of cache per ply on average?

Hardware prefetching might mean the loss is higher.

[bob]

I believe 218 is the right number, but I am not sure if it is the maximum known or if it is known to be the maximum.

I use 256 entries in an array that holds the moves.

That's the maximum that has been found. No formal proof of what is the actual maximum possible.

[bob]

I usually keep a dedicated software stack for moves. Because there is virtually no performance penalty on leaving contiguous chunks of memory unused (as these would never be cached, and it is cache space that is the scarce resource), I skip some 200 bytes between the move list of the previous ply and a new one for the next. That allows me to grow the list in two directions during generation and sorting. So that the captures can be added to the front of the list, (in the gap) and the non-captures to the end (at the topof the stack).

There can be a performance hit here. If you go too far with this spacing, you can effectively reduce the size of cache to 50% or 25%, because the set associativity still relies on direct mapping. IE if you allow 4K bytes per ply of moves (1K moves) but only use the first 800 bytes, you have a bunch of memory blocks that alias to the same cache set unnecessarily. Once you blow the set size, you thrash unnecessarily.

This is the trick my architecture class had to figure out in order to measure set associativity on an unknown machine, no CPUID allowed.

[hgm]

Wouldn't that lose 64 bytes of cache per ply on average?

Indeed, but that is a pretty small price. The move stack is not terribly frequently accessed data, not even the list for the current node. If you use five move lists near the top of the stack frequently enough that it would matter whether it is cached, or flushes something out when you access it, you would waste 320 bytes = 1% of L1.

Hardware prefetching might mean the loss is higher.

I though hardware prefetching was only done from DRAM, not between cache levels.

[bob]

Wouldn't that lose 64 bytes of cache per ply on average?

Indeed, but that is a pretty small price. The move stack is not terribly frequently accessed data, not even the list for the current node. If you use five move lists near the top of the stack frequently enough that it would matter whether it is cached, or flushes something out when you access it, you would waste 320 bytes = 1% of L1.

Hardware prefetching might mean the loss is higher.

I though hardware prefetching was only done from DRAM, not between cache levels.

There are lots of variations, but in general, prefetching applies everywhere. IE L1 will prefetch from L2, etc. I believe there are some hardware controls on this stuff but I have not been interested enough to do the zillion experiments necessary to figure out the effects.