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
max amount of moves from a position?
Moderators: hgm, Rebel, chrisw
-
- Posts: 2644
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
-
- Posts: 226
- Joined: Sun Mar 08, 2009 3:08 pm
- Location: Canada
Re: max amount of moves from a position?
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.
outAtime
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: max amount of moves from a position?
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
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
-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: max amount of moves from a position?
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.
-
- Posts: 2644
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: max amount of moves from a position?
hmm, does "construct" also mean that this position can be reached during a legal game or is it only a theoretical set of pieces?and that he had managed to construct a position with 218 legal moves:
--
Srdja
-
- Posts: 2644
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: max amount of moves from a position?
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
--
Srdja
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: max amount of moves from a position?
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.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: max amount of moves from a position?
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...outAtime wrote: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.
-
- Posts: 273
- Joined: Sat Apr 17, 2010 2:34 pm
- Location: Budapest
Re: max amount of moves from a position?
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)
[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)
-
- Posts: 273
- Joined: Sat Apr 17, 2010 2:34 pm
- Location: Budapest
Re: max amount of moves from a position?
The 218 moves record is by A.Dickins (1968).
[D]3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1
[D]3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1