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.
Max moves in a position
Moderators: hgm, Rebel, chrisw
-
- Posts: 4190
- Joined: Wed Nov 25, 2009 1:47 am
Re: Max moves in a position
uint8 will suffice.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Max moves in a position
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.
I use 256 entries in an array that holds the moves.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Max moves in a position
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.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.
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.
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Max moves in a position
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).
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Max moves in a position
Wouldn't that lose 64 bytes of cache per ply on average?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).
Hardware prefetching might mean the loss is higher.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Max moves in a position
That's the maximum that has been found. No formal proof of what is the actual maximum possible.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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Max moves in a position
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.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).
This is the trick my architecture class had to figure out in order to measure set associativity on an unknown machine, no CPUID allowed.
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Max moves in a position
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.syzygy wrote:Wouldn't that lose 64 bytes of cache per ply on average?
I though hardware prefetching was only done from DRAM, not between cache levels.Hardware prefetching might mean the loss is higher.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Max moves in a position
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.hgm wrote: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.syzygy wrote:Wouldn't that lose 64 bytes of cache per ply on average?
I though hardware prefetching was only done from DRAM, not between cache levels.Hardware prefetching might mean the loss is higher.