Passed Pawn Move Generation

[Edsel Apostol]

Hi Gerd,

Can you give a pseudo code for this. I can't seem to grasp the idea from your description.

Hi Edsel,
for instance white pawns to the seventh rank, where you even don't need to consider sentries:

Code: Select all

pawnPushTargets7thRank = &#40;whitePawns << 8&#41; & emptySquares & 0x00ff000000000000;
unsigned index = pawnPushTargets7thRank >> 48;
movecpy &#40;movelist, precalcpawnPushes&#91;rank7&#93;&#91;index &#93;.moves, precalcpawnPushes&#91;rank7&#93;&#91;index &#93;.nmoves&#41;;

Thanks Gerd. This method seems faster but my current data structure seems not fit to support this method easily. It is possible but I would have to write a lot of code.

[Edsel Apostol]

Correction again:

Code: Select all

mask = Rank8ByColorBB[pos->side] | ((*FillPtr2[pos->side^1])((*ShiftPtr[pos->side^1])(pos->pawns, 8)))
        | (*FillPtr[pos->side^1])(((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side^1]) & ~FileABB)
        | ((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side]) & ~FileHBB))
        | PawnCaps[pos->kpos[pos->side^1]][pos->side^1];

instead of:

Code: Select all

mask = Rank8ByColorBB[pos->side] & ((*FillPtr2[pos->side^1])((*ShiftPtr[pos->side^1])(pos->pawns, 8)))
        & (*FillPtr[pos->side^1])(((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side^1]) & ~FileABB)
        | ((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side]) & ~FileHBB))
        & PawnCaps[pos->kpos[pos->side^1]][pos->side^1];

[Gerd Isenberg]

This method seems faster

I don't know. 256 possible precalculated movelists for the 7th rank is probably a waste of memory. One will rarely have 8 pawn push target squares there

But the same scheme might be applied for other ranks (not only for passers of course), east and west captures and promotions etc.. One may use one shared rank, but needs then to add some offsets to the move(s). The more disjoint target sets you consider (passers, none-passers), the more ineffective the rank-wise copy movelist approach is. As mentioned, the pawns need to be passers after the push, thus intersect the target sets with the complement of opponent spawns and attack spawns.

Your code looks much too complicated for my taste. Why nested while loops?

Btw. I beautified your cpw-page with your avatar and some more links. Feel free to revert to the previous one, if you don't like that

Cheers,
Gerd

[Edsel Apostol]

This method seems faster

I don't know. 256 possible precalculated movelists for the 7th rank is probably a waste of memory. One will rarely have 8 pawn push target squares there

But the same scheme might be applied for other ranks (not only for passers of course), east and west captures and promotions etc.. One may use one shared rank, but needs then to add some offsets to the move(s). The more disjoint target sets you consider (passers, none-passers), the more ineffective the rank-wise copy movelist approach is. As mentioned, the pawns need to be passers after the push, thus intersect the target sets with the complement of opponent spawns and attack spawns.

Your code looks much too complicated for my taste. Why nested while loops?

Btw. I beautified your cpw-page with your avatar and some more links. Feel free to revert to the previous one, if you don't like that

Cheers,
Gerd

Thanks. It looks great. I will have to update my information there. I'm already working for another company.

Yes, the code seems complicated at first glance. I generalize my code for black and white and in trying to do that I used function pointers that may not readily tell what it does. Even my entire pawn eval code is only 70 lines using that style. Things might have been more simple if there is a negative bit shifting or something in C.

About the nested move loops, that's the design of most of my move generators. For the passed pawn generator the pc_bits inside will only contain 1 bit so it is okay to remove the inner while loop.

Code: Select all

    mv_bits = (*ShiftPtr[pos->side])(pawns, 8) & ~mask & (*ShiftPtr[pos->side])(~pos->occupied, 8); 
    while (mv_bits) { 
        to = popFirstBit(&mv_bits); 
        pc_bits = (PawnMoves[to][pos->side^1] & pawns) & ~dcc; 
        from = popFirstBit(&pc_bits); 
        sort->list[sort->size++].m = GenOneForward(from, to); 
    }

The complicated looking:

Code: Select all

 (*ShiftPtr[pos->side])(pawns, 8)

is equivalent to:

Code: Select all

for black:
pawns >> 8

and for white:
pawns << 8

My move generator:

Code: Select all

    pc_bits = pos->knights & allies;
    while (pc_bits) {
        from = popFirstBit(&pc_bits);
        mv_bits = KnightMoves[from] & mask;
        while (mv_bits) {
            to = popFirstBit(&mv_bits);
            sort->list[sort->size++].m = GenKnightMove(from, to, getPiece(pos, to));
        }
    }
    pc_bits = pos->bishops & allies;
    while (pc_bits) {
        from = popFirstBit(&pc_bits);
        mv_bits = bishopAttacksBB(from, occupied) & mask;
        while (mv_bits) {
            to = popFirstBit(&mv_bits);
            sort->list[sort->size++].m = GenBishopMove(from, to, getPiece(pos, to));
        }
    }
    pc_bits = pos->rooks & allies;
    while (pc_bits) {
        from = popFirstBit(&pc_bits);
        mv_bits = rookAttacksBB(from, occupied) & mask;
        while (mv_bits) {
            to = popFirstBit(&mv_bits);
            sort->list[sort->size++].m = GenRookMove(from, to, getPiece(pos, to));
        }
    }
    pc_bits = pos->queens & allies;
    while (pc_bits) {
        from = popFirstBit(&pc_bits);
        mv_bits = queenAttacksBB(from, occupied) & mask;
        while (mv_bits) {
            to = popFirstBit(&mv_bits);
            sort->list[sort->size++].m = GenQueenMove(from, to, getPiece(pos, to));
        }
    }
    pc_bits = pos->kings & allies;
    while (pc_bits) {
        from = popFirstBit(&pc_bits);
        mv_bits = KingMoves[from] & mask;
        while (mv_bits) {
            to = popFirstBit(&mv_bits);
            sort->list[sort->size++].m = GenKingMove(from, to, getPiece(pos, to));
        }
    }

[Edsel Apostol]

Okay here's the code that's tested and working in my engine already:

Code: Select all

/* this generates non tactical non checking passed pawn moves only */
void genPassedPawnMoves(const position_t *pos, sort_t *sort) {
    static const int Shift[] = {9, 7};
    uint64 pc_bits, mv_bits, pawns, xpawns, mask, dcc;
    int from, to;

    ASSERT(pos != NULL);
    ASSERT(sort != NULL);

    sort->size = 0;
    pawns = pos->pawns & pos->color[pos->side];
    xpawns = pos->pawns & pos->color[pos->side^1];
    dcc = discoveredCheckCandidates(pos, pos->side);
    mask = ~Rank8ByColorBB[pos->side] & ~((*FillPtr2[pos->side^1])((*ShiftPtr[pos->side^1])(pos->pawns, 8)))
        & ~(*FillPtr2[pos->side^1])(((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side^1]) & ~FileABB)
        | ((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side]) & ~FileHBB))
        & ~PawnCaps[pos->kpos[pos->side^1]][pos->side^1];

    mv_bits = mask & (*ShiftPtr[pos->side])(pawns, 8) & ~pos->occupied;
    while (mv_bits) {
        to = popFirstBit(&mv_bits);
        pc_bits = (PawnMoves[to][pos->side^1] & pawns) & ~dcc;
        while (pc_bits) {
            from = popFirstBit(&pc_bits);
            sort->list[sort->size++].m = GenOneForward(from, to);
        }
    }
    mv_bits = mask & Rank4ByColorBB[pos->side] & (*ShiftPtr[pos->side])(pawns, 16)
    & (*ShiftPtr[pos->side])(~pos->occupied, 8) & ~pos->occupied;
    while (mv_bits) {
        to = popFirstBit(&mv_bits);
        pc_bits = pawns & Rank2ByColorBB[pos->side] & FileMask[to] & ~dcc;
        while (pc_bits) {
            from = popFirstBit(&pc_bits);
            sort->list[sort->size++].m = GenTwoForward(from, to);
        }
    }
}

Thanks Marco and Gerd for sharing your ideas. I will stick with my approach for now.

[stegemma]

...
pawns = pos->pawns & pos->color[pos->side];
xpawns = pos->pawns & pos->color[pos->side^1];
...
[/code]

As a good programming pratice, i would suggest to change all pos->side and pos->side^1 with the following code:

const int sideA = pos->side;
const int sideB = pos->side^1;

then you can use sideA and sideB everywhere, in your function, having that:


- the code is more readable
- the compiler itself can optimize better (this has to be verifyed)

Maybe defining posA and posB as register can help, for some compilers.

Stefano

[Edsel Apostol]

...
pawns = pos->pawns & pos->color[pos->side];
xpawns = pos->pawns & pos->color[pos->side^1];
...
[/code]

As a good programming pratice, i would suggest to change all pos->side and pos->side^1 with the following code:

const int sideA = pos->side;
const int sideB = pos->side^1;

then you can use sideA and sideB everywhere, in your function, having that:


- the code is more readable
- the compiler itself can optimize better (this has to be verifyed)

Maybe defining posA and posB as register can help, for some compilers.

Stefano

Good suggestion. I will try to do that. Sometimes there is this thing that makes me blind with the deficiencies in my code while when I see it on another's code that it's so glaring. Though after a week or so and when I stumbled upon this piece of code again when I'm performing some random code review, I could already notice this. Does other programmers noticed the same when working with their code? Or is it just me?

[stegemma]

...
Sometimes there is this thing that makes me blind with the deficiencies in my code while when I see it on another's code that it's so glaring.
...

It's the same for a lot of people (me too) and i think that this will happen in programming the same as in playing chess: often we can't see even simple good moves, while watching people can found them easly.

My little suggestion comes from my experience in two fields: assembly programming (where you have to use registers anytime you can) and business application, where a good debugging is essential and often is required more than code efficency or speed. In chess we can sacrify code clearness for speed... but only where and when it is needed.

Stefano

Stefano

[Sven]

...
pawns = pos->pawns & pos->color[pos->side];
xpawns = pos->pawns & pos->color[pos->side^1];
...
[/code]

As a good programming pratice, i would suggest to change all pos->side and pos->side^1 with the following code:

const int sideA = pos->side;
const int sideB = pos->side^1;

then you can use sideA and sideB everywhere, in your function, having that:


- the code is more readable
- the compiler itself can optimize better (this has to be verifyed)

Maybe defining posA and posB as register can help, for some compilers.

Stefano

The improvement would be very tiny, if existing at all, for both aspects:

- The names "sideA" and "sideB" are not intuitive, slightly better would be "ownSide" and "oppSide" or something similar. But at least the saving in terms of number of characters is neglible, so I don't think it is worth doing it. Readability is not improved a lot IMO.

- Regarding optimization, since 'pos' is already a pointer to const, the compiler will most probably replace all 'pos->xxx' expressions by optimized code that dereferences 'pos' only once, since the value of 'pos->xxx' can't change within that function. Therefore, also 'pos->side^1' will be evaluated only once and can be subject to the same kind of optimization.

Once again regarding readability: you could improve it much more by addressing the most complex lines of code, like this one:

Code: Select all

    mask = ~Rank8ByColorBB[pos->side] & ((*FillPtr2[pos->side^1])((*ShiftPtr[pos->side^1])(pos->pawns, 8)))
        & ~(*FillPtr2[pos->side^1])(((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side^1]) & ~FileABB)
        | ((*ShiftPtr[pos->side^1])(xpawns, Shift[pos->side]) & ~FileHBB))
        & ~PawnCaps[pos->kpos[pos->side^1]][pos->side^1];

or this one:

Code: Select all

    mv_bits = mask & Rank4ByColorBB[pos->side] & (*ShiftPtr[pos->side])(pawns, 16)
    & (*ShiftPtr[pos->side])(~pos->occupied, 8) & ~pos->occupied;

Sven

[wgarvin]

- Regarding optimization, since 'pos' is already a pointer to const, the compiler will most probably replace all 'pos->xxx' expressions by optimized code that dereferences 'pos' only once, since the value of 'pos->xxx' can't change within that function. Therefore, also 'pos->side^1' will be evaluated only once and can be subject to the same kind of optimization.

Actually, you're right that the compiler will probably cache 'pos->side' into a register, but the fact that pos is a pointer to const actually has nothing to do with it. Pointer to const doesn't really give the compiler any useful information, because it only means the programmer can not modify the pointed-to value through that pointer, but the value could still be modified through other pointers or references. So the compiler has to do some sort of dataflow analysis and prove that the value cannot be modified (by this thread at least) between the two access. It can do this analysis just as easily with non-const pointers.

I know its not the case in your code, but one general case where it is useful to cache the values is, if any functions called between the two accesses are not inlined. If the compiler has not seen the definition of that function, it doesn't know what it will do. (Even if it has seen the definition, there may be potential aliasing through global variables or other pointers that it has to take into account). Another common case is when you pass two pointers (e.g. to arrays of data) into a function, with the intention to read from one and write to the other, in a loop. The programmer may know that these two arrays don't point to the same place or overlap with each other, but unless you explain that to the compiler (with __restrict) you might be surprised by the pessimistic code that it generates.

Anyway caching values from a struct or array into a temporary variable is a good idea either (1) to improve readability, or (2) when you want to call other functions or write through pointers, between the various uses of the expression. If you read the value into a temporary variable and don't take the address of that variable (or at least, don't let it 'escape' from the current context) then the compiler will easily discover that the temporary variable cannot be legally changed, regardless of what the code in the unknown function does. Or in the case of writes through pointers, the compiler will easily prove that the pointer you're writing through cannot point (in any legal way at least) to the temporary variable you copied the value into, so the write can not affect its value.

Lots of C++ programmers think that const will help the compiler with optimization, but its not really true. Const is mostly a promise from the programmer to human readers of the code, but its a promise which the language allows them to break with impunity (via aliasing or things like const_cast and mutable) so the compiler can't really rely on it. Fortunately, good compilers are adept at discovering the actual usage of indirect values on their own. They can often prove that a pair of pointers/references is aliased or is not aliased, and generate better code.

Knowing how compilers work can give you a good intuition about whether the compiler needs some 'help' to optimize a particular bit of code. But for speed-critical code, examining the generated code is a good idea. Occasionally you'll be surprised by particularly bad-looking code, and it can take some effort to work out why the compiler generated what it did. Usually its not because the compiler sucks (most mature optimizing compilers are quite good), but rather because your program contains something that confuses it or forces it to make pessimistic assumptions. Sometimes you can "explain" the true situation to the compiler by caching values in temporaries and carefully applying __restrict.