pawn enumeration

[Daniel Shawul]

If I have n pawns (nw white + nb black), how do I enumerate the possible positions so that those closer to promotion are first in the list. White pawns take squares of (47...0) and black pawns (0...47) in that order. The total number of positions will be 48!/(48-n)!nw!nb!. The problem is how to enumerate the pawns in closer to promotion order so that they can be sliced. I have something that can enumerate n alike pieces but this new problem imposes two constraints viz a viz.

a) Two groups enumerated together. This is necessary because enumerating them separately would be wrong since each side could have pawns closer or further from promotion. So exhaustively enumerating one side and moving to the other is wrong. I hope this is clear enough.
Edit: I was not sure if this was clear enough so I put in diagrams
[D]8/P7/8/8/8/8/1P3p2/8 w - - 0 1[/D]

comes before

[D]8/P7/8/8/1P6/5p2/8/8 w - - 0 1[/D]
b) Placement of pieces in a given order which I am not sure what I have already does or does not.
Anyway white pawns in 47..0 and black pawns in 0..47 inter-mixed is what I need.

Thanks

[syzygy]

The problem is how to enumerate the pawns in closer to promotion order so that they can be sliced.

During generation, what you need is an indexing function with the property that if position A can be reached by pawn moves (and piece moves) from position B, then index of position A < index of position B.

Since white pawns move up (assuming A1 = 0, H8 = 63), it helps to take (square ^ 0x38) for white pawns (or if your enumeration is 47...0, then take 47 - square for white pawns to map to 0...47). Then make sure your index function is increasing in all its variables.

During generation, I use a very simple indexing scheme with 6 bits per piece or pawn (first pawns, then pieces), so 24 x 64^(n-1) positions for n pieces/pawns (actually 6 x 64^(n-1), since I generate file by file). After generation you don't have the constraint of promotions first anymore, so you can convert to whatever indexing scheme you like.

Taking into account alike pieces during generation decreases the number of positions to be calculated, but overall probably would reduce generation speed for me. (My current generator takes less than 25s for generating KNNvKP on my 4-core laptop.) However, it might be worth the effort doing something about alike pawns when doing the promotions. Actually, it shouldn't be too difficult to just skip the pawn-slices having a pawn permutation with a "lower" index, or just copy those slices instead of generating them...

[Daniel Shawul]

The problem is how to enumerate the pawns in closer to promotion order so that they can be sliced.

During generation, what you need is an indexing function with the property that if position A can be reached by pawn moves (and piece moves) from position B, then index of position A < index of position B.

Since white pawns move up (assuming A1 = 0, H8 = 63), it helps to take (square ^ 0x38) for white pawns (or if your enumeration is 47...0, then take 47 - square for white pawns to map to 0...47). Then make sure your index function is increasing in all its variables.

I am trying to generate 6 men bitbases with pawns. The pawnless need about 4G of RAM but those with single pawn need as much as 13G without pawn slicing. And that is after a lot of effort using 3bits/pos including a visit indicator. Dedicating a byte to the counter requires too much RAM so I decided to use a visitedor not bit and use a sub-optimal generation method which does forward verification sometimes. For those with pawns, slicing would bring the size to a lot less value. So now I have rearranged the enumeration with pawns so that pawns come first so a KPk would have indices 48x1x1806 with 48 pawn slices. So if I iterate from 47-0 for the pawn, I will have no problems. But with KPPkp, there are problems like the one I shown in the diagram. I am not sure if you remember but you explained to me some years ago how to do enumeration of like pieces. Now I want the same thing for enumerating white and black pawns together given an index. I am not sure if that is possible but it is a good mental excercise. Here is what I had for n alike pieces

Code: Select all

void get_squares_like(int* sq,const int N,const int index) {
   int comb;
   sq[0] = index;
   for(int i = N - 1;i >= 1;i--) {
      sq[i] = i;
      comb = 1;
      while(sq[0] >= comb) {
         sq[0] -= comb;
         comb = combination[++sq[i]][i - 1];
      }
   }
}

I wonder if there is something similar for combined enumeration of white and black pieces.
Your suggestion about using different schemes is nice. I think I could just decide which slices to generate at the root. Generate all the pawn enumerations and sort them based on rank assigned using closeness to promotion. This is good since I get to keep the same indexing !
But you might want to try that one as a mental excersise anyway.

During generation, I use a very simple indexing scheme with 6 bits per piece or pawn (first pawns, then pieces), so 24 x 64^(n-1) positions for n pieces/pawns (actually 6 x 64^(n-1), since I generate file by file). After generation you don't have the constraint of promotions first anymore, so you can convert to whatever indexing scheme you like.

Yes naive indexing schemes may go faster but they could require larger RAM. You are probaly generating DTM tables so that already brings the requirement higher anyway. You would need atleast 2 bytes for the counter and storing the DTM score. I am using 2bits for the score and 1bit for visits.

Taking into account alike pieces during generation decreases the number of positions to be calculated, but overall probably would reduce generation speed for me. (My current generator takes less than 25s for generating KNNvKP on my 4-core laptop.) However, it might be worth the effort doing something about alike pawns when doing the promotions. Actually, it shouldn't be too difficult to just skip the pawn-slices having a pawn permutation with a "lower" index, or just copy those slices instead of generating them...

My main target is 6 men because for 5 men using a byte to store counters already speeds up the generation very well. And the RAM requirement is well below 1G even for single pawn positions. I never tried to make it any faster after that.

[Daniel Shawul]

Now I don't want to store the pawn slices as if they were separate tables (f.i KP3K meaning Pawn at square 3) because with 2 or more pawns that could be too many. Is it possible to allocate a virtual memory larger than physical address using malloc ? Say I have a big array a[100][1000000000] and at any one time during a for loop iteration for(i=1;i<100;i++) , only three blocks a[i-1][],a[] and a[i+1][] are needed. So the access is sequential as will be more or less the case with ordered pawn slices too. So can the OS exploit this locality to swap in/out pages automatically from/to disk and let me treat the operation as if I the array is stored in RAM ? I asked this question elsewhere but didn't get an answer. I can ofcourse simulate this manually myself but why reinvent the wheel if the OS can do it ?

[kbhearn]

As long as all you need is enumeration, you could count the states by duplicating a bit of the state information : i.e. first flip one of the colors so that 'more advanced' is in the same direction. Then make white square counts sq'=sq*2 and black square counts sq' = sq * 2 + 1.

Then you need counting functions for counting the total number of states with so many squares to go.

States(squares, nb, nw) = nCr(wsquares, nw) * nCr(bsquares, nb)

Then you can enumerate the states in a way similar to like pieces keeping an array for the commonly used sums of states. The slight state duplication comes from the fact that you've duplicated each square so there's invalid states where it could be occupied by both a white pawn and a black pawn, but this shouldn't be much of an increase in total state space.

i.e. with your first diagram:
white pawn on 40 & 1. black pawn on 5.
white pawn on 40 becomes 80. on 1 becomes 2. and black pawn on 5 becomes 42 becomes 85.

so you wind up enumerating 85, 80, 2 subject to the constraint that you have one odd number (black pawns) and two even numbers (white pawns).

first you index it by 85 with 96 squares left, 2 white pawns, 1 black pawns.
offset = sum(States(86...95, 2, 1))
now you have 85 squares left, 2 white pawns, 0 black pawns, and are indexing for sq 80.
offset += sum(States(81...84, 2, 0))
and finally you have 80 squares left, and are indexing for 2, with 1 white pawn.
offset += sum(States(3...79, 1, 0))

by keeping an array of sums of States from 0...n, each sum that needs to be added to the offset is merely a difference between two array values.

[Daniel Shawul]

That is great Keven! Atleast the problem of ordering the pieces is solved. If I understand correctly when both black and white are on equal level of promotion then black's pawn is placed first as its squares are assigned as 2*sq+1. I guess there wouldn't be an easy way to enumerate alike pieces of both at the same time without having some duplicates. But that is probably not worth the effort given that even enumeration of single set of alike pieces requires some twisted math (i.e without storing it in an array)
Thanks.

[kbhearn]

Just realised some of my math was wrong, the sums weren't quite right.

the first offset should read

offset = sum(i=86...95, States(i, 2 - ~i & 0x01, 1 - i & 0x01))

the other offsets should be changed similarly and where either nw or nb is < 0, states should of course be zero.

[Daniel Shawul]

Just realised some of my math was wrong, the sums weren't quite right.

the first offset should read

offset = sum(i=86...95, States(i, 2 - ~i & 0x01, 1 - i & 0x01))

the other offsets should be changed similarly and where either nw or nb is < 0, states should of course be zero.

No worries. I decided to use a mixture of your method and what Ronald suggested. I think they combine well. Consider KXPPkypp for example. First I generate (48x47/2) X (46x45)/2 pawn positions of each containing KXky type bitbases with the pawns static. Note there are not duplicates. Then I rank all the positions based on your ranking method that is 2xsq for white pawns and 2x(sq+1) for black. The sum will be the rank for each position. Then I sort that array and generate in that order but save in the original indexing scheme thus there is no need to map index to position using the new indexing technique. Another advantage is that with this method pawn slices will be too small specially when you have 2 or more pawns. At any given time ,I need to load only 2 of those slices, one of them being the one that is being generated and the other one containing all the positions a one pawn move leads too! (I see double pawn moves would require 3 slices).

[kbhearn]

I wouldn't think sum would be the right sort key for what you stated as two pawns on the 5th would sum to greater than one pawn on the 7th and one pawn on the 2nd, rather concatenation where the most advanced pawn is in the most significant byte would make sense if all you need is a sort key :) Also it was (2*sq) + 1 to make the black pawns different than the white squares, but if you just need a sort key, neither the *2 nor the +1 is needed anyways. since say you have 47,20,01 distinguishing which color has the 47 isn't needed anyways as long as you've reflected the coordinates for direction of movement first. For that matter, distinguishing files isn't needed so the sort key could easily just be 5,2,0 in that case.

[Daniel Shawul]

Oh yes I just realized that. It should be something that gives more wieght to the extreme values. May be summing a weight of 8^n where n is the distance to promotion of each pawn will work.
Another things is that I need to load many small slices not just 2. That will be n for n-pawns bitbases.

Also it was (2*sq) + 1 to make the black pawns

I made a typo that is what I meant.

Edit Another alternative is to use file based to reduce size by 8x. I think that would be enough since the size will always be smaller than the largest pawnless bitbase. The only advantage of slicing like I did is that it may compress better since pawns closer to promotion are grouped together not just by file but that is a guess ...