Determining From squares

[stevemulligan]

Hi David,

Not sure if you still need this but here is an example in c# that I use

[Dave_N]

I wrote some code for a SAN to LAN (Long algebra notation e.g. e2e4) ages ago for my gui, then later I wrote a LAN to SAN converter to create SAN representation for the moves entered by the user. The rooks routine can be complex if you don't know the best way to start ...
using a board represented by an array of characters is one easy method,

Useful functions to implement are

bool IsFileSpanBlocked( int x1, int x2, int y)

bool IsRankSpanBlocked( int x, int y1, int y2)

so you can call the function

bool CanRookReachSquare(...)

and then you need

bool IsPiecePinned( Piece &p, int fromX, int fromY )

because you need to handle the case when the rook is capturing the pinning piece, i.e. another rook.

I basically sat up one night with a load of snacks etc and wrote the whole SAN to LAN in one night, then I had the pleasure of debugging the next day.

[Dave_N]

Bitboards are much faster than looping over all the rooks/promoted rooks and calling these functions though. Also it is better to generate all legal moves in the long run because then you can easily detect mate and stalemate etc. (i didn't read the earlier post).

[whittenizer]

Thank u for the link. The code looks interesting. Ill check it out more detail for sure. Thanks much.

David

[whittenizer]

Hi David,

I actually had the light bulb turn on earlier today and Ive actually converted my piece list to use bitboard approach. I now have routines to generate all possible goto squares for rooks bishops and knights for all starting squares. Im actually doing my occupied squares a bit differently. Lets take WhiteRooks. This is basically a Dictionary<string,ulong> with the key being a square like "c3" and the value will be a ulong value of all squares this piece can move to freely, essentially the attack squares. This dictionary is updated as moves are made. So whenever I get a move like "Rc3" I can do an AND of the values of whiterooks and the square. A bit more involved but thats the jist of it.

I wouldnt consider this a complete bitboard but maybe a hybrid. It behaves pretty nicely. Im really thankful for all the help.

Thanks for the reply.

David

[whittenizer]

Thank u for the link. The code looks interesting. Ill check it out more detail for sure. Thanks much.

David

[jwes]

Hi all,

I'm looking for an efficient algorithm to determine the "from" square given a move such as "Rc3". In this case only one rook can move to this square. There could have been another rook that otherwise could have gone to c3 but it was blocked by another piece. I've implemented something that works but it is very clunky, and I'm not happy with it. I'm thinking I could use bitwise operators but no idea how to even start.

Any hints to get started would be greatly appreciated.

Thanks so much,

David

For bitboards, take the rook bitboard (because of the R in Rc3) and AND that with rook attacks FROM c3. You will get exactly one bit set, assuming your SAN output is correct (Rc3 is not ambiguous, and not impossible).

Or just generate rook moves and ensure that exactly one legal move goes to c3. Thiis will probably use nearly all existing code.

Not sure how that is simpler. In Crafty, my idea would be:

from = MSB(white_rooks & RookAttacks(c3))

That's about as simple as it gets...

The problem is when there are two rooks that could move to c3 and one is pinned.

[bob]

Hi all,

I'm looking for an efficient algorithm to determine the "from" square given a move such as "Rc3". In this case only one rook can move to this square. There could have been another rook that otherwise could have gone to c3 but it was blocked by another piece. I've implemented something that works but it is very clunky, and I'm not happy with it. I'm thinking I could use bitwise operators but no idea how to even start.

Any hints to get started would be greatly appreciated.

Thanks so much,

David

For bitboards, take the rook bitboard (because of the R in Rc3) and AND that with rook attacks FROM c3. You will get exactly one bit set, assuming your SAN output is correct (Rc3 is not ambiguous, and not impossible).

Or just generate rook moves and ensure that exactly one legal move goes to c3. Thiis will probably use nearly all existing code.

Not sure how that is simpler. In Crafty, my idea would be:

from = MSB(white_rooks & RookAttacks(c3))

That's about as simple as it gets...

The problem is when there are two rooks that could move to c3 and one is pinned.

Add a simple bit of code.

If PopCnt(white_rooks & RookAttacks(c3)) == 1
from = MSB(white_rooks & RookAttacks(c3))
else
{here you do a MSB loop checking to see if each from square is legal (not pinned on king) }

[whittenizer]

Hey all,

I've come up with a routine to get this done. I'm using some generic lists and doing some ANDing to get the desired effect. Here's the jist of my routine:

Code: Select all

int indexToMoves = this.Squares[toSquare];
List<ulong> mask = this.RMask&#91;indexToMoves&#93;;

int i = 0;
int index = 0;
ulong p = 0;

for &#40;int j = 0; j < 4; j++)
&#123;
    index = this.RIndexes&#91;indexToMoves, j&#93;;
    for &#40;int k = 0; k < this.RIndexes&#91;indexToMoves, j&#93;; k++)
    &#123;
        p = mask&#91;i&#93;;
        if (&#40;p & this.Board&#41; > 0&#41;
        &#123;
            if (&#40;p & this.WhiteRooks&#41; == 0&#41;
            &#123;
                break;
            &#125;
            else
            &#123;
                //-- We have our piece &#58;-)
                return p;
            &#125;
        &#125;
        i++;
        index--;
    &#125;
    i += index;
&#125;
            
return p;

There's really not too much to it. I do need to hook in "pin" type checking but that shouldn't be too bad. I'm using Dictionaries for some of the lists but the Board, WhiteRooks, etc... are ulong variables. I call this a hyrbid compared to the full blown bitboard. This way it keeps with my current structure and still takes advantage of the bitwise operators.

The code will be more gereric and will pass in the mask being used and the Indexes you see. Just did this to show the rook moves.

I've finally gotten around to getting my site up. Nothing there yet but I will post some code samples later this weekend to explain what I'm doing in more detail. It's a Silverlight project using C#.

I do use some of StockFishes syntax in a few places as this helped me out after looking over some of the code. I've placed comments to include anything related to StockFish.

My url is: http://www.whittenizer.com

Enjoy, and thanks again all.

David

[whittenizer]

Here is the routine I came up with to build up the masks and the indexes:

Code: Select all

private void InitSlidingSquares(int[,] deltas, bool isbishop)
        {
            IDictionary<int, List<ulong>> mask = &#40;isbishop&#41; ? this.BMask &#58; this.RMask;
            int&#91;,&#93; indexes = &#40;isbishop&#41; ? this.BIndexes &#58; this.RIndexes;

            int count = 0;
            int rank = 0;
            int file = 0;
            int index = 0;
            int delta0 = 0;
            int delta1 = 0;
            int delta2 = 0;
            List<ulong> values = null;

            for &#40;int i = 0; i < 64; i++)
            &#123;
                values = new List<ulong>();

                for &#40;int j = 0; j < 4; j++)
                &#123;
                    delta0 = deltas&#91;j, 0&#93;;
                    delta1 = deltas&#91;j, 1&#93;;
                    delta2 = deltas&#91;j, 2&#93;;
                    file = i % 8;
                    rank = i / 8;

                    if &#40;isbishop&#41;
                    &#123;
                        index = i;
                    &#125;

                    count = 0;

                    while (&#40;file + delta1&#41; >= 0 && &#40;file + delta1&#41; <= 7 && &#40;rank + delta2&#41; >= 0 && &#40;rank + delta2&#41; <= 7&#41;
                    &#123;
                        file += delta1;
                        rank += delta2;
                        count++;

                        if &#40;isbishop&#41;
                        &#123;
                            index += delta0;
                        &#125;
                        else
                        &#123;
                            index = &#40;rank * 8&#41; + file;
                        &#125;
                        values.Add&#40;1UL << index&#41;;
                    &#125;
                    indexes&#91;i, j&#93; = count;
                &#125;
                mask&#91;i&#93; = values;
            &#125;
        &#125;

I've tested the heck out of it and it seems to work for every case. Any comments in how I've implemented this would be warmly welcomed.

Thanks,

David