Castling post has gone

[cms271828]

Hi, I started a post a few days ago called Castling.
Several people replied including Mr Hyatt, and Mr Muller.
But now post is gone, its annoying, because I needed that information.

[Carey]

The chess forum is in the process of moving.

Because of that, several days worth of posts are missing. Plus, other messages seem to suggest other issues, such as damaged posts, posts incorrectly credited to the wrong poster, etc.

However, if you go to the old forum IP address you can still recover the old messages. At least until that gets shut down.

http://216.25.93.108/forum/viewforum.ph ... _view=flat

I suggest you save any important threads or posts to your hard drive. Just go to the 'file' menu and select 'save as' to save a copy to your local drive.

[cms271828]

I'm still confused about this castling thing.

I think I need to use just 1 castling rights value, instead of one for white and one for black, since if white captures on a8 with bishop, it will mean having to update blacks castling value.

So, I can use an array of castling values for each depth in the search so I don't have to undo the make_move operation.

I've been thinking about using an array with...
a1=1,e1=0,h1=2,a8=4,e8=?,h8=8. Rest=15

So if we set CR=15 to start with.
Then suppose a1 rook moves,

CR = CR & array[a1]
CR= CR & array[TO_SQUARE]

so CR=1, which is fine for white, since we now know it can still castle kingside.

But CR=1 doesn't apply to black, since it can still castle both sides.

Can anyone explain.

Thanks

[hgm]

If you AND the modifications into the castling-rights mask, you should only make the bits of the squares zero that spoil the corresponding castling.

So if:
white short = 1
white long = 2
black short = 4
black long = 8

you should make the mask for a1 equal to 1 + 4 + 8 = 15 - 2 = 13, as moving / capturing the Rook there does not spoil white long castling or any black castling.

Similarly, the mask for e1 should be 4 + 8 = 12, as you do not spoil the black castlings.

[cms271828]

That makes sense, I'll take a look at it now

Using the board below:
1011 .......... 0011 ..... 0111
........................................
........................................
........................................
........................................
........................................
........................................
1101 .......... 1100 ..... 1110

With 1111 everywhere else
This seems to work

Thanks

[cms271828]

Yay

I got it working, I've tried it out on 2 chess puzzles
A mate in 2, and a mate in 3, where castling is required to get the
fastest mate, and it has solved them correctly.

Does any one have any mate in N problems which involve castling,
so I can further test it?

Thanks

[Michael Sherwin]

Mostly for curiosity!

But, I would like to hear what others think of this approach.

The code example is actual code from RomiChess and was designed as follows.

1.) It is a method of generating castling moves that allows MakeMove() to not consider (waste time on) castling at all if the move from the move list is not a castling move.

2.) Since WCASKS, WCASQS, BCASKS and BCASQS are 'pseudo pieces' they are part of the piece list for white and black (even if there are no such pieces on the board) and therefore when they are deleted from the piece list, they no longer waste any time in the generation phase, as well.

NOTE: The TakeBack() function had to be designed to accommondate this method. An example is, WCASKR which stands for White CAStle King-side Reselect, and is a 'move type' in a large case statement that reselects (enables) white king-side castling and then undoes the original move type that has been stored in the variable noRh1 (no rook on h1). The disabling move could have been a capture of the rook the previouse ply ((h-1)->typ (h is the history stack pointer)) or a rook move two ply ((h-2)->typ) earlier. So the code here only gets executed if castling has not been deselected and it is also responsible for detecting when castling is not possible and doing the disabling.

Also note, that RomiChess uses the move generator as an inCheck() function and has the pseudo pieces wLegal and bLegal as well. The move generator is bitboard and only generates the bits and stores them (u64 h->moves[id]), but does not 'spin' them into a move list at this time. It is then easy and fast to generate any specific move such as the hash move or killer move by checking for any specific bit set that is indexed by any specific piece index. The generated bits can be used to verify any move.

The end result of all this is that once castling is no longer possible, not one clock cycle will ever be wasted on castling. And that is also the case during any particular search above the point in the tree that castling is disabled. Even if only white king-side castling is disabled then white king-side castling will consume no further cpu time!

Code: Select all

 
      case WCASKS:
        if(board[E1] == WKID)
        {
          if(board[H1] == wkrid)
          {
            if(aPieces & (F1bit | G1bit))
              h->moves[id] = 0;
            else
              if(Attacked(BLACK,E1)||Attacked(BLACK,F1)||Attacked(BLACK,G1))
                h->moves[id] = 0;
              else
                h->moves[id] = G1bit;
          }else
          {
            wIndexs ^= WCASKbit;
            if(board[H1] == EMPTY)
            {
              noRh1 = (h-2)->typ;
              (h-2)->typ = WCASKR;
            }else
            {
              noRh1 = (h-1)->typ;
              (h-1)->typ = WCASKR;
            }
          }
        }else
        {
          wCasBits = wIndexs & (WCASKbit | WCASQbit);
          wIndexs ^= wCasBits;
          indexs &= ~WCASQbit;
          noKe1 = (h-2)->typ;
          (h-2)->typ = WCASTR;
        }
        continue;

[Michael Sherwin]

I guess that I should have mentioned that during the h->moves[id] bit generation I also generate h->attacked. So the pseudo piece wLegal is just one line of code (if(h->attacked & bKings) return ILLEGAL;) that detects an illegal position. Also h->attacked is latter used in 'a poor blind mans SEE'. This is a less accurate see, that is lightning fast (if((h-1)->attacked & setBit[ts]) value -= piece[id].val;). Despite that this is just a one line SEE it produces very good move ordering!

[hgm]

I am not sure I understand where this case-label is located. To skip over a case requires a test and jump as well, doesn't it? Or do you count on an indirect jump? That almost always wastes a large number of cycles, as branches to multiple targets cannot be correctly predicted.

In Joker's move description I use 2 bits to indicate special moves:
0 = normal move
1 = e.p. capture
2 = pawn double move or castling
3 = promotion

An AND and jump-if-equal (resuting from if(ThisMove & H_SPECIAL) { ... } ) branch over the code for special moves in case the move is a normal one. For special moves I first test for case 2 (a compare and a jump). The other cases are extremely rare, so this jump is almost perfectly predicted.

Only in the code for case 2 I have then to separate the pawn moves from the castlings. So if castlings are not in the move list, the only time still wasted on castlings is the test and branch on the moving piece (king or pawn?) that is only done on the occasional pawn double move (which usually drops to less than 10% of the moves early during the game). After castlings are no longer possible, this branch will always be correctly predicted.

The cases for e.p. capture and pawn double moves need no special action during UnMake, so they clear the special-move indicator in the Make part. The decision tree during UnMake then only gets into the special-moves code for castlings and promotions that were atually searched, and can assume that code 2 always means castling. No time is spend on castling except if the searched move was a promotion. (On the other hand, you might argue that time is wasted on testing for promotions if the move searched was a castling. But castlings are not very abundant in the tree either, and after a few moves in the game disappear from the tree entirely. And in the case of a castling a lot of extra work has to be done anyway, making the test for promotion pale in comparison: the Rook target must be tested for check, the Rook must be moved on the board and in the piece list, and the hash key must be accordingly updated.)

[Michael Sherwin]

That dang misprediction penalty. Life was so much better with out it! I use a large case statement in the move generator. That is where the above case statement resides and is accessed by piece type. The MakeMove() and TakeBack() functions also use large case statements that are accessed by move type. The theory at the time of writing was one jump in and one jump out and everything else inline. In practice I would imagine the speed issue to be rather even. A lot of branches (chaind if statements) that are mostly correctly predicted roughly equal a sparse amount of indirect jumps. Still RomiChess's perft runs at twice the rate of Crafty's perft (both are bitboard). So I am not so sure that the case statements suffer that heavily from misprediction penalties!