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?
Black/White symmetry in move generation
Moderators: hgm, Rebel, chrisw
-
- Posts: 7
- Joined: Sun Oct 12, 2014 11:58 pm
- Location: Omaha Ne
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: Black/White symmetry in move generation
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.
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.
Daniel José - http://www.andscacs.com
-
- Posts: 179
- Joined: Fri Feb 14, 2014 10:53 pm
- Location: the Netherlands
Re: Black/White symmetry in move generation
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.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Black/White symmetry in move generation
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 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?
-
- Posts: 7
- Joined: Sun Oct 12, 2014 11:58 pm
- Location: Omaha Ne
Re: Black/White symmetry in move generation
Simple enough! I think I'll do that.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Black/White symmetry in move generation
Note that it is not exactly symmetric, just "close"...jaespo wrote:Simple enough! I think I'll do that.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Black/White symmetry in move generation
A proposal from cpw:jaespo wrote:Simple enough! I think I'll do that.
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
}
-
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Black/White symmetry in move generation
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.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Black/White symmetry in move generation
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
But this was/is not a good idea
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Black/White symmetry in move generation
Why? For which board representation?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
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))