How to Shift Left a Negative Number??

[Steve Maughan]

One of the aims of Maverick is to have minimal (almost zero?) color dependent code. I'm not sure how practical this will be - but it's a starting point.

I thought I had a nice neat way of generating pawn moves:

Code: Select all

int forward = 8 - 16 * to_move;
moves = (&#40;board->piecelist&#91;piece&#93; << forward&#41; & ~&#40;board->all_pieces&#41;);

This relies on forward being +8 for white and -8 for black. The resulting shift for black would be a negative left shift - which didn't work.

I realize it's not the end of the world to add a bit of color dependent code but before I do so I thought I'd ask if there were any tricks I'm missing.

What do others do?

Thanks,

Steve

[spirch]

I hope you know how negative number work.

+8 (signed int64) =
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 1000

-8 (signed int64) =
1111 1111 1111 1111
1111 1111 1111 1111
1111 1111 1111 1111
1111 1111 1111 1000

so there is a huge difference.

go with a bit to specify a color

[AlvaroBegue]

I use an `if' statement.

If you are programming in C++, you could also make most of your functions be templated on the side to move, and have a template class called ColorTraits<to_move> with a function `u64 ColorTrairs<to_move>::forward(u64)'.

I wrote the beginnings of an engine in that style a few years ago, but I never finished it, and I don't think the neat trick is worth the effort.

[Evert]

See http://chessprogramming.wikispaces.com/ ... Operations if you haven't already. It has a section on signed shifts.

In general though, that's just a way to hide the shift.

At the end of the day, there is no escaping that there is a fundamental asymmetry between white and black: when you evaluate advanced pawns you must know, on some level, that white pawns move "up" and black pawns move "down". You can hide that to a large degree, of course, using bitmasks and lookup tables. Sometimes explicit code is just cleaner though.

In Jazz, I have explicit tests for whether a pawn is "black" or "white". In Sjaak, black and white pawns have to be defined as distinct piece types (I usually call them "north bound" and "south bound" pawns) and that's of course a different way to do it. In Leonidas it's the same, but that's because it is designed with Spartan Chess in mind, where black and white have different pawn types.

[hgm]

I use the same method as you, calculating the forward step. E.g. in Spartacus the board is 24 x 10, and side to move 32 (white) or 64 (black), so forward = 48 - stm + (48 - stm >> 1). This is a nice branchless way to calculate the forward step.

I don't use bitboards, though, so Pawn moves are not generated by shifting something.

Variable shifts are treated by i386 modulo word length, so they are by definition positive (0-31 or 0-63 bits). You can't shift the other way by taking a negative number.

In your case, however, I would use

Code: Select all

moves = ((&#40;board->piecelist&#91;piece&#93; << 8&#41; >> 16*to_move&#41; & ~&#40;board->all_pieces&#41;);

Because Pawns are never on the 8th rank, you won't have to worry this loses bits. And I would probably change my encoding of to_move to {0, 16} rather than {0, 1}, to save me the 16*.

[steffan]

Rotate the bits rather than shifting them. For 64 bit quantities, a rotation by 8 bits in one direction is the same as rotation by 56 bits in the other direction.

Cheers,
Steffan

[Edmund]

You can use _rotl64 to do bitwise rotation to the left. It accepts positive and negative shifting/rotation distances. With rotation you however have to think about the relevant overflow masking.

http://msdn.microsoft.com/en-us/library/5cc576c4.aspx

[hgm]

This is also a nice idea. In this case there can be no overflow, as 1st and 8th rank will never contain any Pawns.

[Steve Maughan]

Great Stuff!!

H.G. - I think I'll adopt your method. It's nice and simple.

Stefan & Edmund - _rotl64 interesting! I'll file this away for when I fully go 64 bit.

Thanks

[Gerd Isenberg]

This is also a nice idea. In this case there can be no overflow, as 1st and 8th rank will never contain any Pawns.

Yes, no wrap masks neccessary for pawn pushes. XOP has individual, generalized shifts and rotates, but not AVX/AVX2. But it still takes the extra register cl instead of constant left/right shift, not to mention lookup or some twiddling for the color dependent shift amount. I prefer side to move always White