How to generate all possible pawn positions?

[monk64]

Is there an easy way to generate all possible pawn positions for a side?

I was thinking of making a hash of bitboards, pre-analyzing them for things like pawn chains, doubled pawns, etc. and then using this hash to speed up pawn evaluation code. For some things you need enemy pawn information (passed pawns), but I thought I'd start with one side's pawn structure.

Only ranks 2 through 7 need be considered. It's not as simple as turning on or off all bits, because it's not possible for all pawns to move to all files. For example, I don't think the A2 pawn can go further than the F file if somehow it managed to make a diagonal capture each turn (again, only considering to rank 7 - it could presumably promote on g8).

Also, even if we take very unlikely scenarios, like the A file completely filled with pawns this necessarily means other files have no pawns, etc. To get to doubled or tripled, etc. pawns on a file, other files have to be empty.

I'm wondering if there is some code or a database already out there that has all possibilities, without having to write code to generate all the possibilities...?

Thanks, all!

[hgm]

Some digging on an old hard disc made me retreive this program. Not sure exactly what it does anymore, but it could be of use for what you want.

Code: Select all

#define HSIZE (1<<20)

/* 0x88 board, white Pawn = 4, black Pawn = -4 */
char b[128] =
{
0,0,0,0,0,0,0,0,                0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,                0,0,0,0,0,0,0,0,
0,0,4,0,0,0,0,0,                0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,4,                0,0,0,0,0,0,0,0,
0,0,0,0,0,0,4,0,                0,0,0,0,0,0,0,0,
0,4,0,0,0,0,-4,0,                0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,-4,                0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,                0,0,0,0,0,0,0,0
};

long long int Zobrist[128];
long long int Key = 1;

int count;

struct _PHash
{
    long long int Lock;
    char w, b;
    short unsigned int cnt;
} PawnHash[HSIZE];

int Hist[8][8], DHist[100];

void pboard()
{
    int i, j;

    for(i=0; i<121; i++) printf(" %c", i&8 ? (i+=7,10) : b[i]>0?'*':b[i]<0?'+':'.');
}

int structures(int nw, int nb, int d, int wprom, int bprom, int parent)
/* recursive walk of all reachable Pawn structures */
{
    int i, j, p, y, t, depth=0, v, index;
    long long int OldKey, NewKey;

    if(nw<0 || nb<0) return 0; /* more pieces captured than present, abort */

    /* store position in hash table */
    NewKey = Key + wprom*52586268 + bprom * 86586815;
    i = NewKey & HSIZE-1;
    j = 100;
    while(PawnHash[i].Lock && PawnHash[i].Lock != NewKey && j--)
        i = i+1 & HSIZE-1;
    if(j==0) {printf("Pawn-table overflow\n");exit(0);}
    if(PawnHash[i].Lock && PawnHash[i].w >= nw && PawnHash[i].b >= nb)
        return PawnHash[i].cnt; /* abort if already traversed with at least as many pieces */

    Hist[wprom][bprom] += !PawnHash[i].Lock; /* count new entries */
    PawnHash[i].Lock = NewKey;     /* store position in Pawn table */
    PawnHash[i].w = nw;
    PawnHash[i].b = nb;
    index = i;

    /* and try to generate new Pawn structure from it */
    for(i=0x10; i<0x68; i=i+9&~8)
    {   /* scan board */
        p = b[i]; 
        if(p) /* pawn detected */
        {
            y = i+4*p;  /* forward step */
            b[i] = 0; Key ^= Zobrist[i+p+4];  /* take away    */

            /* first, let it be captured */
            if((p>0?nb:nw) != 0 ||                  /* opponent has bare K */
               b[i-4*p+1] != p && b[i-4*p-1] != p ) /* so not if defended  */
                {
                    v = structures(nw, nb, d+1, wprom, bprom, parent);
                    if(v>depth) depth = v;
                }

            if(y+4*p & 0x88) /* promotions: same as captured,       */
            {   if(p>0)      /* but with different number of queens */
                    v = structures(nw, nb, d+1, wprom+1, bprom, parent);
                else
                    v = structures(nw, nb, d+1, wprom, bprom+1, parent);
                if(v>depth) depth = v;
                goto skip;
            }
            /* then non-capture(s) */
            if(b[y]==0) /* square empty, so allowed */
            {
                b[y] = p; Key ^= Zobrist[y+p+4]; /* make */
                v = structures(nw, nb, d+1, wprom, bprom, parent);
                b[y] = 0; Key ^= Zobrist[y+p+4]; /* unmake */
                if(v>depth) depth = v;

                if((i&0x70) == 56-10*p  /* pawn was in original position */
                   && b[y+4*p] == 0)    /* next square also empty */
                {
                    b[y+4*p] = p; Key ^= Zobrist[y+5*p+4];
                    v = structures(nw, nb, d+1, wprom, bprom, parent);
                    b[y+4*p] = 0; Key ^= Zobrist[y+5*p+4];
                    if(v>depth) depth = v;
                }
            }

            /* now captures */
            y--;
            for(j=0; j<=1; j++) /* two captures */
            {
                if(y&0x88) continue; /* off board */
                t = b[y];          /* victim */
                if(t==p) continue; /* own pawn */
                OldKey = Key;
                if(t==-p) /* enemy pawn captured */
                    Key ^= Zobrist[y-p+4];
                b[y] = p; Key ^= Zobrist[y+p+4];
                /* adapt number of non-pawns if capture to empty square */
                v = structures(nw-(!t&p==-4), nb-(!t&p==4), d+1, wprom, bprom, parent);
                if(v>depth) depth = v;
                b[y] = t; Key = OldKey;
                y += 2;
            }
          skip:
            b[i] = p; Key ^= Zobrist[i+p+4];        /* put back */
        }
    }

    /* printf("%d. %2d-%2d\n",d,wprom,bprom); pboard();
    printf("depth = %d\n",depth+1);*/
    PawnHash[index].cnt = depth+1;
    DHist[depth+1]++;
    return depth+1;
}

main()
{
    int i, j, k;

    for(i=0; i<128; i++) Zobrist[i] = rand()<<3 ^ rand()>>16;

    k = structures(0, 1, 1, 0, 0, 0);

    printf("total depth = %d\n", k);

    for(i=0; i<8; i++)
    {    for(j=0; j<8; j++) printf("%6d ",Hist[i][j]);
         printf("\n");
    }
    for(i=0;i<100;i++) if(DHist[i]) printf("%2d. %6d\n",i,DHist[i]);
}

[Edmund]

Is there an easy way to generate all possible pawn positions for a side?

I was thinking of making a hash of bitboards, pre-analyzing them for things like pawn chains, doubled pawns, etc. and then using this hash to speed up pawn evaluation code. For some things you need enemy pawn information (passed pawns), but I thought I'd start with one side's pawn structure.

Only ranks 2 through 7 need be considered. It's not as simple as turning on or off all bits, because it's not possible for all pawns to move to all files. For example, I don't think the A2 pawn can go further than the F file if somehow it managed to make a diagonal capture each turn (again, only considering to rank 7 - it could presumably promote on g8).

Also, even if we take very unlikely scenarios, like the A file completely filled with pawns this necessarily means other files have no pawns, etc. To get to doubled or tripled, etc. pawns on a file, other files have to be empty.

I'm wondering if there is some code or a database already out there that has all possibilities, without having to write code to generate all the possibilities...?

Thanks, all!

Pre-analyzing all possible positions takes unnecessarily much memory. Leaving away your criteria that certain pawns cant reach specific squares (because it complicates index-calculations quite a bit) I get a total of 443.6m different pawn configurations for one side (48+48*47/2+48*47*46/2/3+...)

It is much more common to calculate the values on the fly.

[jwes]

I think the number of possible pawn positions is much too large to evaluate them all. I vaguely remember that someone showed that total number was on the order of 2^56 and had a scheme to encode all possible pawn positions in 64 bits. A more fruitful approach might be to collect a very large number of games (quality does not matter much) and extract all the different pawn positions from them. I would be interested in how many you would find.

[Sven]

The white a-pawn, originally located on a2 and thus being able to capture up to five times while still remaining a pawn, has 6+5+4+3+2+1 = 21 possible squares, plus "not on board" = 22.
b-pawn: 5+6+5+4+3+2+1 = 26 + 1 = 27
c-pawn: 4+5+6+5+4+3+2+1 = 30 + 1 = 31
d-pawn: 3+4+5+6+5+4+3+2 = 32 + 1 = 33
So (22*27*31*33)^2 = approx. 3.69 * 10^11 is an upper bound for the total number of different positions of up to 8 white pawns. A part of these is impossible since each square can contain at most one pawn. Also some combinations can be excluded due to the total number of captures required that exceeds the maximum of 15 enemy pieces. Nevertheless, the order of magnitude remains quite high even when looking at the pieces of only one color, as requested here initially.

Now the major downside: since the declared goal was to speed up pawn evaluation it is not sufficient to look at pawns of only one color, since you just don't get any information about passers, backward pawns etc., so in fact you must combine both colors, getting the square of the numbers given so far.

Therefore enumerating all combinations and evaluating them is by far too expensive. There are better approaches though, by using a pawn hash table for instance that can save a lot of repeated calculation of pawn structure evaluation.

Sven

[Edmund]

Dear Sven and J. Wesley,

did you read my post at all?

Taking advantage of the fact that the pawns are interchangeable you can reduce the number of unique positions.
Having 1 pawn = 48 positions
.. 2 pawns = 48 * 47 / 2!
.. 3 pawns = 48 * 47 * 46 / 3!
...
.. 8 pawns = 48! / (48-8)! / 8!
Adding all those together you get 443.6m different pawn positions

I vaguely remember that someone showed that total number was on the order of 2^56 and had a scheme to encode all possible pawn positions in 64 bits.

So (22*27*31*33)^2 = approx. 3.69 * 10^11 is an upper bound for the total number of different positions of up to 8 white pawns

with this simple calculation you can encode all pawn postitions for one side in 29bits

[jwes]

Dear Sven and J. Wesley,

did you read my post at all?

Taking advantage of the fact that the pawns are interchangeable you can reduce the number of unique positions.
Having 1 pawn = 48 positions
.. 2 pawns = 48 * 47 / 2!
.. 3 pawns = 48 * 47 * 46 / 3!
...
.. 8 pawns = 48! / (48-8)! / 8!
Adding all those together you get 443.6m different pawn positions

I vaguely remember that someone showed that total number was on the order of 2^56 and had a scheme to encode all possible pawn positions in 64 bits.

So (22*27*31*33)^2 = approx. 3.69 * 10^11 is an upper bound for the total number of different positions of up to 8 white pawns

with this simple calculation you can encode all pawn postitions for one side in 29bits

My numbers were for both sides, so they match up pretty well, since once you put on the white pawns, the number of possible positions for black pawns is significantly lower.

[Edmund]

Dear Sven and J. Wesley,

did you read my post at all?

Taking advantage of the fact that the pawns are interchangeable you can reduce the number of unique positions.
Having 1 pawn = 48 positions
.. 2 pawns = 48 * 47 / 2!
.. 3 pawns = 48 * 47 * 46 / 3!
...
.. 8 pawns = 48! / (48-8)! / 8!
Adding all those together you get 443.6m different pawn positions

I vaguely remember that someone showed that total number was on the order of 2^56 and had a scheme to encode all possible pawn positions in 64 bits.

So (22*27*31*33)^2 = approx. 3.69 * 10^11 is an upper bound for the total number of different positions of up to 8 white pawns

with this simple calculation you can encode all pawn postitions for one side in 29bits

My numbers were for both sides, so they match up pretty well, since once you put on the white pawns, the number of possible positions for black pawns is significantly lower.

Alright, I can confirm your number (2^55.44644018)
And also that pregenerating all pawn positions for both sides is out of question.

Your idea concerning the pawn structure database (of previously played games) sounds interesting. Did anyone ever do any research in that field?

[Sven]

Dear Sven and J. Wesley,

did you read my post at all?

Taking advantage of the fact that the pawns are interchangeable you can reduce the number of unique positions.
Having 1 pawn = 48 positions
.. 2 pawns = 48 * 47 / 2!
.. 3 pawns = 48 * 47 * 46 / 3!
...
.. 8 pawns = 48! / (48-8)! / 8!
Adding all those together you get 443.6m different pawn positions

I vaguely remember that someone showed that total number was on the order of 2^56 and had a scheme to encode all possible pawn positions in 64 bits.

So (22*27*31*33)^2 = approx. 3.69 * 10^11 is an upper bound for the total number of different positions of up to 8 white pawns

with this simple calculation you can encode all pawn postitions for one side in 29bits

Yes, I read your post but when writing my post I only had an old idea in mind that does, unfortunately, not take into account interchangeability of the pawns. And yes, your numbers are much smaller than mine. I missed to mention that.

But my key point was that white + black must be combined for pawn structure evaluation, and that whatever you do, the total number of combinations is way too high. This is true for both your numbers and mine.

Sven

[Sven]

I vaguely remember that someone [...] had a scheme to encode all possible pawn positions in 64 bits.

Uri Blass once showed a simple proof that 64 bits are always sufficient for all pawn positions. He wrote that you can use 48 bits to indicate presence or non-presence of a pawn on the 48 squares (rank 2..7), ignoring color, and need at most 16 bits to indicate the colors of 16 pawns.

A more fruitful approach might be to collect a very large number of games (quality does not matter much) and extract all the different pawn positions from them. I would be interested in how many you would find.

I think that the search needs more than that, since a lot of positions being visited during search are reached via bad move sequences which would usually not occur during the game itself but must be evaluated, too. This will cover far more than the small portion of pawn structures you are referring to.

Sven