Black/White symmetry in move generation

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jaespo
Posts: 7
Joined: Sun Oct 12, 2014 9:58 pm
Location: Omaha Ne

Black/White symmetry in move generation

Post by jaespo » Tue Nov 25, 2014 9:36 pm

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?

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Black/White symmetry in move generation

Post by cdani » Tue Nov 25, 2014 9:47 pm

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
Posts: 179
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: Black/White symmetry in move generation

Post by Stan Arts » Tue Nov 25, 2014 10:21 pm

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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Black/White symmetry in move generation

Post by bob » Tue Nov 25, 2014 11:40 pm

jaespo wrote: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
Posts: 7
Joined: Sun Oct 12, 2014 9:58 pm
Location: Omaha Ne

Re: Black/White symmetry in move generation

Post by jaespo » Wed Nov 26, 2014 12:47 am

Simple enough! I think I'll do that.

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

Re: Black/White symmetry in move generation

Post by bob » Wed Nov 26, 2014 2:22 am

jaespo wrote:Simple enough! I think I'll do that.
Note that it is not exactly symmetric, just "close"...

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Black/White symmetry in move generation

Post by Gerd Isenberg » Wed Nov 26, 2014 11:51 am

jaespo wrote: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
}

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: Black/White symmetry in move generation

Post by SMIRF » Wed Nov 26, 2014 7:40 pm

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
Posts: 4458
Joined: Tue Feb 28, 2012 10:56 pm

Re: Black/White symmetry in move generation

Post by syzygy » Wed Nov 26, 2014 9:19 pm

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
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Black/White symmetry in move generation

Post by Gerd Isenberg » Thu Nov 27, 2014 9:36 am

syzygy wrote: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 ;-)

Post Reply