Black/White symmetry in move generation

[jaespo]

I've been spending some of my spare time writing a chess engine (https://github.com/jaespo/Fiesty.git).

Right now I'm just working on move generation and I noticed something -- because I'm using popLsb the moves are generated in the following order (a1, a2, ... h8).

So white's moves will be searched "nearest" first, whereas black's will be "farthest away" first, unless I do something.

Am I worrying about nothing, or do I need to do something about the asymmetry?

[cdani]

Hi.
Previously in Andscacs I had a move generation with reversed order for black pieces, because it proved a very little bit better. But not now with staged move generation.
Really seems nothing especially important. Just on your own.

[Stan Arts]

Nah. You'll sort moves that are likely to cause cutoffs to the front anyway.
But in my programs I've always generated my moves from one end of to the board to the other as well and long ago did some not very significant tests to see which is better.

In the opening back to front is much better. Getting pieces off the back rank or moving them forward in general often makes for the best moves and perhaps a lot of random forward pawnmoves are generally losing.

Intuitively in the middle and endgame you'd probably expect front to back to be better but that's hardly the case. Better in some positions worse in others. Probably makes sense as for every threat worth searching you have to search a defence as well and those tend to happen further back the board as well as check evasions etc.
So I always settled on back to front as the worst case (opening) is less bad.
Small difference and doing one side in reversed further halves that difference that becomes smaller still as your movesorting heuristics improve.

[bob]

I've been spending some of my spare time writing a chess engine (https://github.com/jaespo/Fiesty.git).

Right now I'm just working on move generation and I noticed something -- because I'm using popLsb the moves are generated in the following order (a1, a2, ... h8).

So white's moves will be searched "nearest" first, whereas black's will be "farthest away" first, unless I do something.

Am I worrying about nothing, or do I need to do something about the asymmetry?

That's easy to partially solve. There is an an advantage to generate moves that advance before moves that retreat. But use LSB and MSB (intel has BSF/BSR to do these). Then you use MSB for white to pick up most advanced target squares, then LSB for black to do the same...

[jaespo]

Simple enough! I think I'll do that.

[bob]

Simple enough! I think I'll do that.

Note that it is not exactly symmetric, just "close"...

[Gerd Isenberg]

Simple enough! I think I'll do that.

A proposal from cpw:

Code: Select all

if ( x ) {
   U64 m = (U64)color - 1; // e.g. -1 if white, 0 for black
   int o = (int)m & 56;
   x = x ^ ((x ^ flipVertical(x)) & m); // conditional flip
   do {
      int idx = bitScanForward(x) ^ o; // square index from 0..63
      *list++ = foo(idx , ...);
   } while (x &= x-1); // reset LS1B
}

[SMIRF]

I actually am continuing my work on a new engine, which is completely achromatic. Maybe I already have written some details on it here. Thus the (growing) engine internally cannot at all distinguish a position from its swapped one (positions mirrored and piece colors and move right inverted), so it will work absolutely symmetric.

[syzygy]

If I remember well, the first version of my engine only generated moves for white and flipped the board after every move.

But this was/is not a good idea

[Gerd Isenberg]

If I remember well, the first version of my engine only generated moves for white and flipped the board after every move.

But this was/is not a good idea

Why? For which board representation?

Reinhard keeps both a normal and color flipped board and has more effort to incrementally update them, and gains from some special piece encoding. I like the color-flipping idea with a compact board representation i.e. one quad-bitboard so that the flip based on four bswaps is quite cheap, with following zobrist key relation:

Code: Select all

zobristkey(piece, square) == bswap (zobristkey(piece^1, square^56))

with some extra TT hits if playing symmetrical positions