Max moves in a position

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lauriet
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Max moves in a position

Post by lauriet » Sat Oct 22, 2016 5:20 am

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
Posts: 3291
Joined: Wed Nov 25, 2009 12:47 am

Re: Max moves in a position

Post by Milos » Sat Oct 22, 2016 5:43 am

uint8 will suffice.

AlvaroBegue
Posts: 913
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Max moves in a position

Post by AlvaroBegue » Sat Oct 22, 2016 5:43 am

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.

User avatar
Evert
Posts: 2909
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Max moves in a position

Post by Evert » Sat Oct 22, 2016 6:12 am

lauriet wrote: 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.

User avatar
hgm
Posts: 23000
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Max moves in a position

Post by hgm » Sat Oct 22, 2016 7:59 am

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
Posts: 4375
Joined: Tue Feb 28, 2012 10:56 pm

Re: Max moves in a position

Post by syzygy » Sat Oct 22, 2016 9:57 am

hgm wrote: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
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Max moves in a position

Post by bob » Sat Oct 22, 2016 3:32 pm

AlvaroBegue wrote: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
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Max moves in a position

Post by bob » Sat Oct 22, 2016 3:36 pm

hgm wrote: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. :)

User avatar
hgm
Posts: 23000
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Max moves in a position

Post by hgm » Sat Oct 22, 2016 4:12 pm

syzygy wrote: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
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Max moves in a position

Post by bob » Sat Oct 22, 2016 5:34 pm

hgm wrote:
syzygy wrote: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.

Post Reply