max amount of moves from a position?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

smatovic
Posts: 479
Joined: Wed Mar 10, 2010 9:18 pm
Location: Germany
Contact:

max amount of moves from a position?

Post by smatovic » Fri Jun 10, 2011 4:39 pm

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

outAtime
Posts: 226
Joined: Sun Mar 08, 2009 2:08 pm
Location: Canada

Re: max amount of moves from a position?

Post by outAtime » Fri Jun 10, 2011 5:04 pm

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

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: max amount of moves from a position?

Post by wgarvin » Fri Jun 10, 2011 6:35 pm

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

User avatar
Kempelen
Posts: 619
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Re: max amount of moves from a position?

Post by Kempelen » Fri Jun 10, 2011 7:15 pm

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.
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

smatovic
Posts: 479
Joined: Wed Mar 10, 2010 9:18 pm
Location: Germany
Contact:

Re: max amount of moves from a position?

Post by smatovic » Fri Jun 10, 2011 7:22 pm

and that he had managed to construct a position with 218 legal moves:
hmm, does "construct" also mean that this position can be reached during a legal game or is it only a theoretical set of pieces?

--
Srdja

smatovic
Posts: 479
Joined: Wed Mar 10, 2010 9:18 pm
Location: Germany
Contact:

Re: max amount of moves from a position?

Post by smatovic » Fri Jun 10, 2011 7:33 pm

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

User avatar
hgm
Posts: 22180
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: max amount of moves from a position?

Post by hgm » Fri Jun 10, 2011 9:30 pm

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.

bob
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: max amount of moves from a position?

Post by bob » Sat Jun 11, 2011 4:36 am

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.
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...

Arpad Rusz
Posts: 264
Joined: Sat Apr 17, 2010 12:34 pm
Location: Budapest

Re: max amount of moves from a position?

Post by Arpad Rusz » Sat Jun 11, 2011 8:48 am

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)

Arpad Rusz
Posts: 264
Joined: Sat Apr 17, 2010 12:34 pm
Location: Budapest

Re: max amount of moves from a position?

Post by Arpad Rusz » Sat Jun 11, 2011 9:07 am

The 218 moves record is by A.Dickins (1968).

[D]3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1

Post Reply