How to Shift Left a Negative Number??

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Steve Maughan
Posts: 1091
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

How to Shift Left a Negative Number??

Post by Steve Maughan » Fri Apr 05, 2013 7:24 pm

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
Posts: 64
Joined: Thu Nov 08, 2012 11:36 pm

Re: How to Shift Left a Negative Number??

Post by spirch » Fri Apr 05, 2013 7:39 pm

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
Posts: 930
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: How to Shift Left a Negative Number??

Post by AlvaroBegue » Fri Apr 05, 2013 7:40 pm

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.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: How to Shift Left a Negative Number??

Post by Evert » Fri Apr 05, 2013 7:42 pm

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.

User avatar
hgm
Posts: 26542
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How to Shift Left a Negative Number??

Post by hgm » Fri Apr 05, 2013 8:14 pm

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
Posts: 28
Joined: Sat Mar 11, 2006 11:08 pm
Location: Midlands, England

Re: How to Shift Left a Negative Number??

Post by steffan » Fri Apr 05, 2013 8:49 pm

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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: How to Shift Left a Negative Number??

Post by Edmund » Fri Apr 05, 2013 8:53 pm

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

User avatar
hgm
Posts: 26542
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How to Shift Left a Negative Number??

Post by hgm » Fri Apr 05, 2013 9:01 pm

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

User avatar
Steve Maughan
Posts: 1091
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: How to Shift Left a Negative Number??

Post by Steve Maughan » Fri Apr 05, 2013 9:19 pm

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

Re: How to Shift Left a Negative Number??

Post by Gerd Isenberg » Fri Apr 05, 2013 9:31 pm

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

Post Reply