Is it even possible for such a position to be encountered while searching ?
and what about the maximum number of captures and quiets separately ?
Max moves in a position
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Max moves in a position
MahmoudUthman wrote:Is it even possible for such a position to be encountered while searching ?
and what about the maximum number of captures and quiets separately ?
Easiest solution I know of is what I use. A Large array to store the moves, and an pointer per ply that points to the last move generated for this ply + 1 (obviously the pointer for ply - 1 points to the first move for this ply. Now a position with 1000 legal moves would not cause a problem, all I have to worry about is the max size of that array, and since the end is never used in normal positions, you can make it large enough that you feel completely confident it won't be compromised.
One serious advantage is no "gaps" between plies. The array is filled in from position 0 through the max with no unused values between each ply, which makes it about as cache-friendly as can be done.
-
- Posts: 2488
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Max moves in a position
while 218 is the discovered maximum, I ran many test games, and the maximum in real games were 93 (pseudo-legal) moves. My movelist arrays have 150 moves, which is sufficient for real applications.
However, if you aren't as low on RAM as I am (28k stack), you can safely allocate something like 256 moves per position.
However, if you aren't as low on RAM as I am (28k stack), you can safely allocate something like 256 moves per position.
-
- Posts: 570
- Joined: Mon Jul 20, 2015 5:06 pm
Re: Max moves in a position
Try this:lauriet wrote: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.
[d]R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1
from:
http://www.chess.com/forum/view/general ... s-possible
-
- Posts: 395
- Joined: Fri Aug 12, 2016 8:43 pm
Re: Max moves in a position
This is an interesting talk about "Hybrid Data Structures" used by LLVM:bob wrote:The array is filled in from position 0 through the max with no unused values between each ply, which makes it about as cache-friendly as can be done.
https://www.youtube.com/watch?v=vElZc6zSIXM
The idea is to allocate a small vector on the stack that can automatically grow into the heap; he said that in LLVM it improves speed.
-
- Posts: 24
- Joined: Wed Nov 05, 2014 11:28 am
- Location: Italy
Re: Max moves in a position
I add my question: what is the maximum number of capture moves?
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Max moves in a position
Rooks and bishops can capture at most 4 things, and every other piece can capture at most 8 things, so 4*4 + 12*8 = 112 is an upper bound.sasachess wrote:I add my question: what is the maximum number of capture moves?
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Max moves in a position
I think that in the configuration (2R,2B,9Q,2N,1K) that you used a king can only have a maximum of 3 captures (1R , 1B ,1N , Touching it without defending each other).AlvaroBegue wrote:Rooks and bishops can capture at most 4 things, and every other piece can capture at most 8 things, so 4*4 + 12*8 = 112 is an upper bound.sasachess wrote:I add my question: what is the maximum number of capture moves?
-
- 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 see what you mean, but I don't think it's quite right. The opponent could have a different material configuration, and then the king can capture at least five things (five pawns).MahmoudUthman wrote:I think that in the configuration (2R,2B,9Q,2N,1K) that you used a king can only have a maximum of 3 captures (1R , 1B ,1N , Touching it without defending each other).AlvaroBegue wrote:Rooks and bishops can capture at most 4 things, and every other piece can capture at most 8 things, so 4*4 + 12*8 = 112 is an upper bound.sasachess wrote:I add my question: what is the maximum number of capture moves?
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Max moves in a position
yes , I forgot about pawns of the other side but how can you get 5 pawns touching the king without at least defending one of their own ? plus if you add any other piece it will defend more pawns so 4 pawns seems to be the maximum , right ?AlvaroBegue wrote:I see what you mean, but I don't think it's quite right. The opponent could have a different material configuration, and then the king can capture at least five things (five pawns).MahmoudUthman wrote:I think that in the configuration (2R,2B,9Q,2N,1K) that you used a king can only have a maximum of 3 captures (1R , 1B ,1N , Touching it without defending each other).AlvaroBegue wrote:Rooks and bishops can capture at most 4 things, and every other piece can capture at most 8 things, so 4*4 + 12*8 = 112 is an upper bound.sasachess wrote:I add my question: what is the maximum number of capture moves?