Winboard Forum

As I mentioned in another thread, I wrote a little magic number generator yesterday. Because it would be a waste to produce these numbers without using them for anything, I've now modified the bitboard version of my program (which used classical rotated bitboards) to use magic-based attack generation instead.

Most of the work was very easy, but I had a few small problems. A problem I still haven't been able to solve cleanly is to find a bitboard of all pinned pieces for a given side. My old rotated bitboard code looks like this:

Code: Select all

Bitboard Position::pinned_pieces(Color c) const {
  Bitboard pinned = EmptyBoardBB, b1, b2;
  Square ksq = this->king_square(c), s;
  Color them = opposite_color(c);
 
  for(Direction d = DIR_E; d <= DIR_NW; d++) {
    b1 = this->sliders_of_color(them, d);
    b2 = this->sliding_attacks(ksq, d) & this->pieces_of_color(c);
    while(b2) {
      s = pop_1st_bit(&b2);
      if(this->sliding_attacks(s, d) & b1) set_bit(&pinned, s);
    }
  }
  return pinned;
}

My current magic bitboard version is a lot messier:

Code: Select all

Bitboard Position::pinned_pieces(Color c) const {
  Bitboard b1, b2, b3, pinned, sliders;
  Square ksq = this->king_square(c);
  Color them = opposite_color(c);

  pinned = EmptyBoardBB;
  b1 = this->occupied_squares();

  sliders = this->rooks_and_queens_of_color(them);
  if(sliders) {
    b2 = this->rook_attacks(ksq) & this->pieces_of_color(c);
    while(b2) {
      b3 = b2 & -b2;
      b2 ^= b3;
      if(rook_attacks_bb(ksq, b1 ^ b3) & sliders) pinned |= b3;
    }
  }
  sliders = this->bishops_and_queens_of_color(them);
  if(sliders) {
    b2 = this->bishop_attacks(ksq) & this->pieces_of_color(c);
    while(b2) {
      b3 = b2 & -b2;
      b2 ^= b3;
      if(bishop_attacks_bb(ksq, b1 ^ b3) & sliders) pinned |= b3;
    }
  }
  return pinned;
}

This is fast enough and has the advantage of avoiding the dreaded bitscanning, but looks awfully ugly and complicated. There has to be a better way to do this. Because magic bitboards generate attacks in several directions at once, I would expect a good magic bitboard solution to be shorter and simpler than the rotated bitboard solution.

Any ideas about how to improve this code?

Tord

Hi Tord,

Despite bitscan and probably even more ugly code, it seems more efficient, to get pinners at once and to traverse pinners rather than potential pinned pieces.

Code: Select all

Bitboard Position::pinned_pieces(Color c) const {
  Bitboard occupied, pinned, sliders, possiblePinned, pinners;
  Square ksq = this->king_square(c);
  Color them = opposite_color(c);

  pinned = EmptyBoardBB;
  occupied = this->occupied_squares();
  sliders = this->rooks_and_queens_of_color(them);
  if(sliders) {
      possiblePinned = rook_attacks_bb(ksq, occupied) & this->pieces_of_color(c);
     pinners = rook_attacks_bb(ksq, occupied ^ possiblePins) & sliders;
     while ( pinners )
     {
        Square sq = bitscan(pinners);
        pinned |= rook_attacks_bb(sq, occupied) & possiblePinned; // only one bit!
        resetBit(pinners, sq);
     }
  }
  ..


Personally i prefer fillstuff for that, to get pinned pieces and possible remove checker in one run.

Gerd

Hello Gerd,

Thanks for the suggestion! Your code does look a bit more efficient - you have to do some bitscans (but only when there are some pinned pieces, and in most positions there are none), but you don't have to generate as many attack bitboards as I do. Great!

I still wish I could find something more simple and compact, but your code will do. Thanks a lot!

Gerd Isenberg wrote:Personally i prefer fillstuff for that, to get pinned pieces and possible remove checker in one run.

I know nothing about filling techniqes. Do they require a 64-bit CPU in order to work well, or are they worth trying even on 32-bit CPUs?

Tord

Tord Romstad wrote:As I mentioned in another thread, I wrote a little magic number generator yesterday. Because it would be a waste to produce these numbers without using them for anything, I've now modified the bitboard version of my program (which used classical rotated bitboards) to use magic-based attack generation instead.

Most of the work was very easy, but I had a few small problems. A problem I still haven't been able to solve cleanly is to find a bitboard of all pinned pieces for a given side. My old rotated bitboard code looks like this:

Code: Select all

Bitboard Position::pinned_pieces(Color c) const {
  Bitboard pinned = EmptyBoardBB, b1, b2;
  Square ksq = this->king_square(c), s;
  Color them = opposite_color(c);
 
  for(Direction d = DIR_E; d <= DIR_NW; d++) {
    b1 = this->sliders_of_color(them, d);
    b2 = this->sliding_attacks(ksq, d) & this->pieces_of_color(c);
    while(b2) {
      s = pop_1st_bit(&b2);
      if(this->sliding_attacks(s, d) & b1) set_bit(&pinned, s);
    }
  }
  return pinned;
}

My current magic bitboard version is a lot messier:

Code: Select all

Bitboard Position::pinned_pieces(Color c) const {
  Bitboard b1, b2, b3, pinned, sliders;
  Square ksq = this->king_square(c);
  Color them = opposite_color(c);

  pinned = EmptyBoardBB;
  b1 = this->occupied_squares();

  sliders = this->rooks_and_queens_of_color(them);
  if(sliders) {
    b2 = this->rook_attacks(ksq) & this->pieces_of_color(c);
    while(b2) {
      b3 = b2 & -b2;
      b2 ^= b3;
      if(rook_attacks_bb(ksq, b1 ^ b3) & sliders) pinned |= b3;
    }
  }
  sliders = this->bishops_and_queens_of_color(them);
  if(sliders) {
    b2 = this->bishop_attacks(ksq) & this->pieces_of_color(c);
    while(b2) {
      b3 = b2 & -b2;
      b2 ^= b3;
      if(bishop_attacks_bb(ksq, b1 ^ b3) & sliders) pinned |= b3;
    }
  }
  return pinned;
}

This is fast enough and has the advantage of avoiding the dreaded bitscanning, but looks awfully ugly and complicated. There has to be a better way to do this. Because magic bitboards generate attacks in several directions at once, I would expect a good magic bitboard solution to be shorter and simpler than the rotated bitboard solution.

Any ideas about how to improve this code?

Tord

Hi Tord

You can delay the expensive stuff until you know for sure there are pinned pieces.

fe

Code: Select all


oldAttacks=AttacksBishop(sq,occupiedSquares)

pinnedPieces=oldAttacks & piecesInterestingEnoughToPin

if (pinnedPieces)
{

   newAttacks=AttacksBishop(sq,occupiedSquares^pinnedPieces)

   pinningAttacks=newAttacks^oldAttacks

   if (pinningAttacks & highOrUndefendedPieces)
   {
      // loop over bits to find the pinned pieces back
   }

}



Cheers,

Tony

Hi Tony!

Tony van Roon-Werten wrote:You can delay the expensive stuff until you know for sure there are pinned pieces.

Thanks! Looks similar to Gerd's suggestion, if I understand your code correctly. I'll try something similar.

A somewhat related question: Do you bitboarders do move legality checking during move generation, or just before the move is made? I have always used the latter approach, because it seems like a waste of time to do legality checking for all moves when many moves end up getting pruned. Perhaps legality checking during move generation (i.e. a legal move generator) is the better approach in a bitboard engine?

Tord

Tord Romstad wrote:Hi Tony!

Tony van Roon-Werten wrote:You can delay the expensive stuff until you know for sure there are pinned pieces.

Thanks! Looks similar to Gerd's suggestion, if I understand your code correctly. I'll try something similar.

A somewhat related question: Do you bitboarders do move legality checking during move generation, or just before the move is made? I have always used the latter approach, because it seems like a waste of time to do legality checking for all moves when many moves end up getting pruned. Perhaps legality checking during move generation (i.e. a legal move generator) is the better approach in a bitboard engine?

Tord

The main difference in my code, is in XiniX, I already generate the bishop attackboard in eval. So most stuf is free. That's why I can use "anyInterestingPieceToPin" and "highOrUndefendedPieces". I don't think Gerds code can (easily).

I don't think it's worth doing legal move generation. I really see no point in doing it, and it will only slow me down.

Then again, my evaluation will give me "single/dual move" information, which could be a reason to do legal move gen.

Tony

Tord Romstad wrote:Hello Gerd,

Thanks for the suggestion! Your code does look a bit more efficient - you have to do some bitscans (but only when there are some pinned pieces, and in most positions there are none), but you don't have to generate as many attack bitboards as I do. Great!

I still wish I could find something more simple and compact, but your code will do. Thanks a lot!

Gerd Isenberg wrote:Personally i prefer fillstuff for that, to get pinned pieces and possible remove checker in one run.

I know nothing about filling techniqes. Do they require a 64-bit CPU in order to work well, or are they worth trying even on 32-bit CPUs?

Tord

If the king is actually in check by a slider, the while-loop makes one not necessary run. Therefor it might be worth to exclude sliders from the initial attack-set of the king by one additional cheap xor.

Code: Select all

Bitboard Position::pinned_pieces(Color c) const {
  Bitboard occupied, pinned, sliders, possiblePinned, pinners;
  Square ksq = this->king_square(c);
  Color them = opposite_color(c);

  pinned = EmptyBoardBB;
  occupied = this->occupied_squares();
  sliders = this->rooks_and_queens_of_color(them);
  if(sliders) {
     attacksFromKing = rook_attacks_bb(ksq, occupied);
     possiblePinned = attacksFromKing  & this->pieces_of_color(c);
     pinners = (rook_attacks_bb(ksq, occupied ^ possiblePins) ^ attacksFromKing) & sliders;
     while ( pinners )
     {
        Square sq = bitscan(pinners);
        pinned |= rook_attacks_bb(sq, occupied) & possiblePinned; // only one bit!
        resetBit(pinners, sq);
     }
  }
  ...


Yes, fillstuff requires 64-bit gp- or simd-registers. I found quad-bitboard using two 128-bit xmm-registers quite usefull for that. I do pure legal move-generation since i already have the information on which direction a piece is absolutely pinned.

Gerd

Tord Romstad wrote:A somewhat related question: Do you bitboarders do move legality checking during move generation, or just before the move is made? I have always used the latter approach, because it seems like a waste of time to do legality checking for all moves when many moves end up getting pruned. Perhaps legality checking during move generation (i.e. a legal move generator) is the better approach in a bitboard engine?

Tord

Most certainly! With bitboards it is not much more expensive to generate legal-moves (except for kings which you can check before actually making them or you can generate them legaly anways because move generation is hardly much processor time compared to eval). The greatest advantage is that it makes it easier to read and write code when there are only legal moves to deal with. The extra speed spent in checking legality can be done in parallel with 1 &. This means you will save some speed by not doing inCheck tests for each move and instead do it all in parallel with a legal move generator. In alphabeta, where you usually get a cutoff from the first move one might think that legal move generation is too expensive but it is not so because for bitboards legal move generation is as cheap as 1 inCheck test. Just try it out

Pradu wrote:

Tord Romstad wrote:A somewhat related question: Do you bitboarders do move legality checking during move generation, or just before the move is made? I have always used the latter approach, because it seems like a waste of time to do legality checking for all moves when many moves end up getting pruned. Perhaps legality checking during move generation (i.e. a legal move generator) is the better approach in a bitboard engine?

Tord

Most certainly! With bitboards it is not much more expensive to generate legal-moves (except for kings which you can check before actually making them or you can generate them legaly anways because move generation is hardly much processor time compared to eval). The greatest advantage is that it makes it easier to read and write code when there are only legal moves to deal with.

This is a moot point, I think. Having a single line with

Code: Select all

if(!move_is_legal(board, move)) continue;

at the beginning of the move loop in the search function doesn't really make the code any harder to read and maintain.

My point was that bitboard and mailbox representations excel at different operations, and that it is probably a good idea to structure the low-level parts of the program in ways that exploit the advantages of the chosen representation. Bitboards are generally fast for computing more complicated information (like finding all pinned pieces at once, generating a legal move list, or finding all the squares a given piece attacks), but tend to be rather slow for more simple, atomic tasks (like testing whether a single piece is pinned, testing whether a single move is legal, or testing whether a given piece attacks a given square). With a mailbox representation, it is precisely the opposite.

For this reason, direct translation of mailbox code into bitboard code (or vice versa) usually doesn't work that well. In a mailbox program, it is a good idea to be lazy, and never compute anything until the moment you need it. In a bitboard program, it seems that it is often better to compute more information than you really need, store the superfluous (for the moment) information somewhere, and hope that it will turn out to be useful later.

The extra speed spent in checking legality can be done in parallel with 1 &. This means you will save some speed by not doing inCheck tests for each move and instead do it all in parallel with a legal move generator. In alphabeta, where you usually get a cutoff from the first move one might think that legal move generation is too expensive but it is not so because for bitboards legal move generation is as cheap as 1 inCheck test. Just try it out

I don't follow you here, I'm afraid. Where do the inCheck tests enter the picture? Do you use your inCheck function in legality checking?

Tord

Tord Romstad wrote:Hi Tony!

Tony van Roon-Werten wrote:You can delay the expensive stuff until you know for sure there are pinned pieces.

Thanks! Looks similar to Gerd's suggestion, if I understand your code correctly. I'll try something similar.

A somewhat related question: Do you bitboarders do move legality checking during move generation, or just before the move is made? I have always used the latter approach, because it seems like a waste of time to do legality checking for all moves when many moves end up getting pruned. Perhaps legality checking during move generation (i.e. a legal move generator) is the better approach in a bitboard engine?

Tord

Hi Tord,

Just for contimplation, I do things differently in RomiChess. Romi does not have a legal move generator, nor does Romi spin the move bits into a move list when they are generated. Instead the move bits are stored by piece index at the current ply and used to verify certain moves like the hash move or killer moves. If the bit exist for one of those moves it is cleared and the move is made. Only later if there is no cut-off will the remaining bits get spun into a move list. Another thing that is done is that every piece has its bits ORed with an attack bitboard and that bitboard is checked at the end of the move generator to see if the enemy's king square is amoung the bits. So, that is just one line to look for a king capture. Also the attack board is saved at each ply and used for what I call 'a poor blind mans SEE' during the move ordering part of the code. If a squares bit is set at the previous ply then a penalty is applied in proportion to the value of the piece moving. So, it is just a one move deep SEE and very inaccurate, however, SEE is also inaccurate, and my method is very fast and works very well. Just my two cents worth.

Mike

Tord Romstad wrote:This is a moot point, I think. Having a single line with

Code: Select all

if(!move_is_legal(board, move)) continue;

at the beginning of the move loop in the search function doesn't really make the code any harder to read and maintain.'

Well I don't have something like this in the move loop, my alpha beta looks something like
int ab(board b, move m, int depth, int a, int b, ....)

So at the beginning of the function you make a test if the move is legal or not which kind of looks ackward. Also there is some difficulty in figuring out whether you are in stalemate or mate because you have to keep a counter of the number of illegal moves.
I've done it before with your method of checking if the move is legal before making it but I must disagree with you when you say it is simple because I do believe this makes it a bit more complicated than it really needs be. I have done it like this before and didn't like it. When it is 1 less messy thing to worry about, I don't see why you wouldn't want to do it.

My point was that bitboard and mailbox representations excel at different operations, and that it is probably a good idea to structure the low-level parts of the program in ways that exploit the advantages of the chosen representation. Bitboards are generally fast for computing more complicated information (like finding all pinned pieces at once, generating a legal move list, or finding all the squares a given piece attacks), but tend to be rather slow for more simple, atomic tasks (like testing whether a single piece is pinned, testing whether a single move is legal, or testing whether a given piece attacks a given square). With a mailbox representation, it is precisely the opposite.

Nothing preventing you from combining both approaches . Bitboards are usually accompanied by some sort of array boards so using bitboards is clearly superior because you have the same abilities you had to array boards with the additional capabilities of bitboards. Bitboards without arrayboards will be slow, and I suspect any that pure bitboard programs are not-optimal and will have some difficult code to read. An example of this would be figuring out what kind of piece was captured from a move. With pure bitboards you have to do some &ing to figure out which bitboard the piece was taken from. With array boards one can use to-square's data from the array.

For this reason, direct translation of mailbox code into bitboard code (or vice versa) usually doesn't work that well. In a mailbox program, it is a good idea to be lazy, and never compute anything until the moment you need it. In a bitboard program, it seems that it is often better to compute more information than you really need, store the superfluous (for the moment) information somewhere, and hope that it will turn out to be useful later.

I don't follow you here, I'm afraid. Where do the inCheck tests enter the picture? Do you use your inCheck function in legality checking?

Nope I don't, I just & out the illegal moves from the move bitboards .

Anyways interesting method Michael.

Hello Michael,

Thanks for your input!

Michael Sherwin wrote:Just for contimplation, I do things differently in RomiChess. Romi does not have a legal move generator, nor does Romi spin the move bits into a move list when they are generated. Instead the move bits are stored by piece index at the current ply and used to verify certain moves like the hash move or killer moves. If the bit exist for one of those moves it is cleared and the move is made. Only later if there is no cut-off will the remaining bits get spun into a move list.

I do it even more lazily. I don't even generate the "move bits" before after the hash move and killer moves have been searched.

Another thing that is done is that every piece has its bits ORed with an attack bitboard and that bitboard is checked at the end of the move generator to see if the enemy's king square is amoung the bits. So, that is just one line to look for a king capture.

King captures are not an issue for me - my program never makes illegal moves (unless I have a bug, of course). Our programs seem to be organized very differently.

Also the attack board is saved at each ply and used for what I call 'a poor blind mans SEE' during the move ordering part of the code. If a squares bit is set at the previous ply then a penalty is applied in proportion to the value of the piece moving. So, it is just a one move deep SEE and very inaccurate, however, SEE is also inaccurate, and my method is very fast and works very well. Just my two cents worth.

It could still be useful, at least for pruning culling losing captures in the qsearch. For this, it is not always necessary to know the exact SEE value, but only whether it is negative. Perhaps I'll try something similar!

Tord

Pradu wrote:

Tord Romstad wrote:This is a moot point, I think. Having a single line with

Code: Select all

if(!move_is_legal(board, move)) continue;

at the beginning of the move loop in the search function doesn't really make the code any harder to read and maintain.'

Well I don't have something like this in the move loop, my alpha beta looks something like
int ab(board b, move m, int depth, int a, int b, ....)

So at the beginning of the function you make a test if the move is legal or not which kind of looks ackward.

But you don't have to do it at the beginning of your function, it seems cleaner (and faster) to do it before ab() is called. Somewhere in your program, you must have some loop or function which picks a move from a move list, extracts a move from a pair of bitboards, or something similar. Just modify this function to do legality checking before it returns a move to search, and you are done.

Also there is some difficulty in figuring out whether you are in stalemate or mate because you have to keep a counter of the number of illegal moves.

This is true, but counting the number of legal moves is useful in any case, because it is nice to have for splitting and reduction decisions.

My point was that bitboard and mailbox representations excel at different operations, and that it is probably a good idea to structure the low-level parts of the program in ways that exploit the advantages of the chosen representation. Bitboards are generally fast for computing more complicated information (like finding all pinned pieces at once, generating a legal move list, or finding all the squares a given piece attacks), but tend to be rather slow for more simple, atomic tasks (like testing whether a single piece is pinned, testing whether a single move is legal, or testing whether a given piece attacks a given square). With a mailbox representation, it is precisely the opposite.

Nothing preventing you from combining both approaches . Bitboards are usually accompanied by some sort of array boards so using bitboards is clearly superior because you have the same abilities you had to array boards with the additional capabilities of bitboards.

It is not that clear, and it depends to a big extent on the program. Combining mailbox and bitboards is very expensive. The board data structure becomes bigger and more complicated, which makes copying boards at splitpoints and doing/undoing moves much slower. Bitboard are also somewhat less efficient with board arrays bigger than 64 entries, because you will either have to expand the size of various mask arrays, or do some extra arithmetics or an additional table lookup in order to convert square indices down to the 0-63 range.

In some programs, using both bitboards and a mailbox board might be worth the price, but in mine it is not. Pure mailbox and pure bitboard is faster than any hybrid solution, for the old Glaurung as well as the new.

Bitboards without arrayboards will be slow, and I suspect any that pure bitboard programs are not-optimal and will have some difficult code to read.

Not necessarily - look at the fabulous OliThink 5 alpha, for instance. Blazingly fast, and one of the most elegant and readable chess programs ever written. It's a pity Oliver never finished it. Does anyone know what he's doing now?

An example of this would be figuring out what kind of piece was captured from a move. With pure bitboards you have to do some &ing to figure out which bitboard the piece was taken from. With array boards one can use to-square's data from the array.

Intuitively this seems plausible, but when I experimented with this recently it seemed that using a board[] array hardly helped at all (the speedup with the array was about 3%), and I removed it in order to make things simpler.

I think some kind of light-weight piece list data structure would give a bigger boost to performance than a board[] array. Bitscanning is one of the most frequent and expensive operations in a bitboard program, and piece lists would help to reduce its usage.

Tord

Tord Romstad wrote:

Pradu wrote:Bitboards without arrayboards will be slow, and I suspect any that pure bitboard programs are not-optimal and will have some difficult code to read.

Not necessarily - look at the fabulous OliThink 5 alpha, for instance. Blazingly fast, and one of the most elegant and readable chess programs ever written. It's a pity Oliver never finished it.

I took a look and I am sorry, but it is not fast. His search is not much more than a perft that keeps track of material and returns a best move. On an athlon64 3400+ his node rate in responce to e2e4 is 5495 knps. My classic bitboard move generator halfwit (that is poorly done as it was my first attempt at bitboards), perfts at 9498 knps. In 64 bit mode the gap would be even more in favor of halfwit as halfwit has only single dimentional lookups and Olithink 5 alpha has a three dimentional lookup with two, two dimentional lookups with an AND inside the third indici and that is just for one diagonal or line.

I do think that his alpa would be a good test bed for comparing various move generators by removing his and plugging in others by adding a second file to the source. I do like Oliver's programming style though!

Halfwit.c

Code: Select all

#include    <stdio.h>
#include    <ctype.h>
#include    <string.h>
#include    <signal.h>
#include    <time.h>
#include    <stdlib.h>

#define     FALSE       0
#define     TRUE        1

#define     OK          0
#define     ERROR       1
   
#define     BLACK       0
#define     WHITE       1
#define     OFF         2

#define     CONSOLE     0
#define     XBOARD      1
#define     UCI         2

#define     A1          0
#define     B1          1
#define     C1          2
#define     D1          3
#define     E1          4
#define     F1          5
#define     G1          6
#define     H1          7
#define     A2          8
#define     B2          9
#define     C2          10
#define     D2          11
#define     E2          12
#define     F2          13
#define     G2          14
#define     H2          15
#define     A3          16
#define     B3          17
#define     C3          18
#define     D3          19
#define     E3          20
#define     F3          21
#define     G3          22
#define     H3          23
#define     A4          24
#define     B4          25
#define     C4          26
#define     D4          27
#define     E4          28
#define     F4          29
#define     G4          30
#define     H4          31
#define     A5          32
#define     B5          33
#define     C5          34
#define     D5          35
#define     E5          36
#define     F5          37
#define     G5          38
#define     H5          39
#define     A6          40
#define     B6          41
#define     C6          42
#define     D6          43
#define     E6          44
#define     F6          45
#define     G6          46
#define     H6          47
#define     A7          48
#define     B7          49
#define     C7          50
#define     D7          51
#define     E7          52
#define     F7          53
#define     G7          54
#define     H7          55
#define     A8          56
#define     B8          57
#define     C8          58
#define     D8          59
#define     E8          60
#define     F8          61
#define     G8          62
#define     H8          63

#define     NOEP        64

#define     WPAWN       0
#define     WKNIGHT     1
#define     WBISHOP     2
#define     WROOK       3
#define     WQUEEN      4
#define     WKING       5
#define     BPAWN       6
#define     BKNIGHT     7
#define     BBISHOP     8
#define     BROOK       9
#define     BQUEEN      10
#define     BKING       11
#define     NONE        12

#define     WKID        15
#define     BKID        31

#define     EMPTY       32

#define     VALP        100
#define     VALN        290
#define     VALB        320
#define     VALR        500
#define     VALQ        900
#define     VALK        0

#define     CWKS        1
#define     CWQS        2
#define     CBKS        4
#define     CBQS        8
#define     WJCS        16
#define     WJCL        32
#define     BJCS        64
#define     BJCL        128
 
#define     IsBlack(x)  ((x)>15&&(x)<32)
#define     IsWhite(x)  ((x)<16)
#define     abs(x)      (((x)>0)?x:-x)

#define     Row(y)      ((y)>>3)
#define     Col(x)      ((x)&7)

#define     ColA        0
#define     Row8        7

#define     s08         signed char
#define     u08         char       
#define     s32         int
#define     u32         unsigned int
#define     s64         __int64
#define     u64         unsigned __int64

s32 __cdecl main        (void);
void        InitChess   (void);
void        Compute     (void);
void        GetCmd      (void);
s32         LoadFen     (u08 *);
s32         SetUp       (void);
s32         FirstOne32  (u32);
s32         LastOne32   (u32);
s32         FirstOne64  (u64);
s32         LastOne64   (u64);
void        MakeMove    (void);
void        TakeBack    (void);
void        PrintBoard  (void);
void        Convert     (void);
s32         MoveGen     (void);
void        Wperf       (void);
void        Bperf       (void);

typedef     struct
{
            s32         i;
            s32         d;
            s32         o;
} vecmap;

typedef     struct
{
            s32         fs;
            s32         ts;
            s32         tsid;
            s32         epsq;
            s32         castle;
            u64         moves[32];
            u64         captures[32];
} history;

typedef     struct
{
            s32         typ;
            s32         val;
            s32         sq;
            s32         ply;
} pieces;

s32         repeat;
s32         xboard;
s32         wtm;
s32         bmf;
s32         fs;
s32         ts;
s32         wmat;
s32         bmat;
s32         computer;
s32         ply;
s32         depth;
s32         fifty;
s32         start;
s32         castle;
u32         whitePieces;
u32         blackPieces;
u64         occupied;
u64         occuByW;
u64         occuByB;
s64         nodes;

u08         cmd[20];
u08         data[256];
u08         firstBit[33][33];
u08         lastBit[33][33];

s32         fenBoard[64];
s32         board[64];
s32         magMap[1024];

u32       mulBy33[33];
u32         mask32s[33];
u32         mask32c[33];

u64         mask64s[65];
u64         mask64c[65];
u64         ray7p[64];
u64         ray8p[64];
u64         ray9p[64];
u64         ray1p[64];
u64         ray7m[64];
u64         ray8m[64];
u64         ray9m[64];
u64         ray1m[64];
u64         knight[64];
u64         king[64];
u64         wPawnMoves[64];
u64         wPawnCapts[64];
u64         bPawnMoves[64];
u64         bPawnCapts[64];
u64         above[65];
u64         below[65];

vecmap      vecMap[240];
vecmap      *vM;

history     hist[400];

pieces      piece[33];

/* From Tom Kerrigan's Simple Chess Program (TSCP). Modified. 
   This is the castle_mask array. We can use it to determine
   the castling permissions after a move. What we do is
   logical-AND the castle bits with the castle_mask bits for
   both of the move's squares. Let's say castle is 1, meaning
   that white can still castle kingside. Now we play a move
   where the rook on h1 gets captured. We AND castle with
   castle_mask[7], so we have 1&14, and castle becomes 0 and
   white can't castle kingside anymore. */

s32         castleMask[64] = {
                     13, 15, 15, 15, 12, 15, 15, 14,
                     15, 15, 15, 15, 15, 15, 15, 15,
                     15, 15, 15, 15, 15, 15, 15, 15,
                     15, 15, 15, 15, 15, 15, 15, 15,
                     15, 15, 15, 15, 15, 15, 15, 15,
                     15, 15, 15, 15, 15, 15, 15, 15,
                     15, 15, 15, 15, 15, 15, 15, 15,
                      7, 15, 15, 15,  3, 15, 15, 11 };

u08         startFen[] ="rnbqkbnr/pppppppp/////PPPPPPPP/RNBQKBNR w KQkq - 0 1";

s32         val[] =     {   100,290,320,500,900,  0,100,290,320,500,900,  0 };         

s32         vec[] =     {   7,   8,   9,   1,  -7,  -8,  -9,  -1,
                            6,  -6,  15, -15,  17, -17,  10, -10  };

u64         *dir[] =    {  ray7p, ray8p, ray9p, ray1p,
                           ray7m, ray8m, ray9m, ray1m  };

s32 __cdecl main()
{
  repeat = TRUE;

  InitChess();

  while(repeat)
  {
    PrintBoard();
    if(computer == wtm) Compute();
    else                 GetCmd();
  }

  return 0;
}

void GetCmd()
{
  s32 retry;
  u32 pieces;
  s32 id;
  u64 tosqs;

  retry=TRUE;
  while(retry)
  {
    retry=FALSE;

    MoveGen();
    pieces = wtm ? whitePieces : blackPieces;
    while(pieces)
    {
      id = FirstOne32(pieces);
      pieces &= mask32c[id];
      fs = piece[id].sq;
      tosqs = hist[ply].captures[id] | hist[ply].moves[id];
      while(tosqs)
      {
        ts = FirstOne64(tosqs);
        tosqs &= mask64c[ts];
        MakeMove();
        if(MoveGen() == OK)
        {
          Convert();
          printf("%s ",cmd);
        }
        TakeBack();
      }
    }

    if(!xboard){printf((wtm)?"\nWhite":"\nBlack");printf("%d> ",(ply+bmf)/2);}
    if(!fgets(data,256,stdin)){retry=FALSE;continue;}
    if(data[0]=='\n')continue;
    sscanf(data,"%s",cmd);
    strlwr(cmd);

    if(!strcmp(cmd,"xb"))
    {
      xboard=xboard^1;
      continue;
    }

    if(!strcmp(cmd,"xboard"))
    {
      xboard=TRUE;
      signal(SIGINT,SIG_IGN);
      printf("\n");
      fflush(stdout);
      continue;
    } 
   
    if(!strcmp(cmd,"white"))
    {
      wtm=WHITE;
      computer=BLACK;
      continue;
    }
     
    if(!strcmp(cmd,"black"))
    {
      wtm=BLACK;
      computer=WHITE;
      continue;
    }
     
    if(!strcmp(cmd,"off") || !strcmp(cmd,"force"))
    {
      computer=OFF;
      continue;
    }
     
    if(!strcmp(cmd,"go"))
    {
      computer=wtm;
      continue;
    }
     
    if(!strcmp(cmd,"u") || !strcmp(cmd,"undo"))
    {
      if(ply<1)continue;
      computer=OFF;
      TakeBack();
      printf("castle = %d\n", castle);
      //high=0;
      continue;
    }

    if(!strcmp(cmd,"r") || !strcmp(cmd,"remove"))
    {
      if(ply<3)continue;
      TakeBack();
      TakeBack();
      ply=0;
      //high=0;
      continue;
    }
     
    if(!strcmp(cmd,"new"))
    {
      InitChess();
      computer=OFF;
      wtm=WHITE;
      //high=0;
      continue;
    }
     
    if(!strcmp(cmd,"quit"))
    {
      repeat=FALSE;
      continue;
    }

    if(!strcmp(cmd,"perft"))
    {
      float sec;
      time_t st, et, dt;
      sscanf(data,"perft %d",&depth);
      nodes = 0;
      st = clock();
      if(wtm)
          Wperf();
      else
          Bperf();
      et = clock();
      dt = et - st;
      sec = (float)dt/CLOCKS_PER_SEC;
      _i64toa(nodes, cmd, 10);
      printf("Nodes = %s,  msec. = %d, nps = %.2f\n",
              cmd, dt, (float)nodes/sec);
      depth = 100;
      continue;
    }
   
    retry = TRUE;;
    fs = cmd[0] - 'a' + 8 * (cmd[1] - '1');
    ts = cmd[2] - 'a' + 8 * (cmd[3] - '1');
    pieces = wtm ? whitePieces : blackPieces;
    if(pieces & mask32s[board[fs]])
    {
      if((hist[ply].captures[board[fs]] & mask64s[ts]) ||
         (hist[ply].moves[board[fs]] & mask64s[ts]))
      {
        MakeMove();
        if(MoveGen() == ERROR)
        {
          TakeBack();
          continue;
        }
        printf("castle = %d\n", castle);
        retry = FALSE;
      }
    }
  }
}

void MakeMove()
{
  s32 fsid;
  s32 tsid;
  s32 typ;
  history *h;

  h = &hist[ply];

  fsid = board[fs];
  tsid = board[ts];

  h->castle = castle;
  castle &= (castleMask[fs] & castleMask[ts]);

  typ = piece[fsid].typ;
  if(wtm)
  {
    if(typ == WPAWN)
    {
      if(fs < A3 && ts > H3)
        (h+1)->epsq = ts - 8;
      else
      if(ts == h->epsq)
      {
        tsid = board[ts - 8];
        board[ts - 8] = EMPTY;
        bmat -= piece[tsid].val;
        occupied &= mask64c[ts - 8];
        occuByB &= mask64c[ts - 8];
      }else
      if(ts > H7)
      {
        wmat += (VALQ - VALP);
        piece[fsid].typ = WQUEEN;
        piece[fsid].ply = ply;
      }
    }else
    if(typ == WKING && fs == E1)
    {
      if(ts == G1)
      {
        board[F1] = board[H1];
        board[H1] = EMPTY;
        piece[board[F1]].sq = F1;
        occupied &= mask64c[H1];
        occupied |= mask64s[F1];
        occuByW &= mask64c[H1];
        occuByW |= mask64s[F1];
        castle |= WJCS;
      }else
      if(ts == C1)
      {
        board[D1] = board[A1];
        board[A1] = EMPTY;
        piece[board[D1]].sq = D1;
        occupied &= mask64c[A1];
        occupied |= mask64s[D1];
        occuByW &= mask64c[A1];
        occuByW |= mask64s[D1];
        castle |= WJCL;
      }
    }
    occuByW &= mask64c[fs];
    occuByW |= mask64s[ts];
    bmat -= piece[tsid].val;
    occuByB &= mask64c[ts];
    blackPieces &= mask32c[tsid];
  }else
  {
    if(typ == BPAWN)
    {
      if(fs > H6 && ts < A6)
        (h+1)->epsq = ts + 8;
      else
      if(ts == h->epsq)
      {
        tsid = board[ts + 8];
        board[ts + 8] = EMPTY;
        wmat -= piece[tsid].val;
        occupied &= mask64c[ts + 8];
        occuByW &= mask64c[ts + 8];
      }else
      if(ts < A2)
      {
        bmat += (VALQ - VALP);
        piece[fsid].typ = BQUEEN;
        piece[fsid].ply = ply;
      }
    }else
    if(typ == BKING && fs == E8)
    {
      if(ts == G8)
      {
        board[F8] = board[H8];
        board[H8] = EMPTY;
        piece[board[F8]].sq = F8;
        occupied &= mask64c[H8];
        occupied |= mask64s[F8];
        occuByB &= mask64c[H8];
        occuByB |= mask64s[F8];
        castle |= BJCS;
      }else
      if(ts == C8)
      {
        board[D8] = board[A8];
        board[A8] = EMPTY;
        piece[board[C8]].sq = D8;
        occupied &= mask64c[A8];
        occupied |= mask64s[D8];
        occuByB &= mask64c[A8];
        occuByB |= mask64s[D8];
        castle |= BJCL;
      }
    }
    occuByB &= mask64c[fs];
    occuByB |= mask64s[ts];
    wmat -= piece[tsid].val;
    occuByW &= mask64c[ts];
    whitePieces &= mask32c[tsid];
  }

  h->fs = fs;
  h->ts = ts;
  h->tsid = tsid;
  board[fs] = EMPTY;
  board[ts] = fsid;
  piece[fsid].sq = ts;
  occupied &= mask64c[fs];
  occupied |= mask64s[ts];

  ply++;
  nodes++;
  wtm = 1 - wtm;
}

void TakeBack()
{
  s32 fsid;
  history *h;

  ply--;
  wtm = 1 - wtm;

  h = &hist[ply];

  fsid = board[h->ts];
  board[h->fs] = fsid;
  piece[fsid].sq = h->fs;
  board[h->ts] = h->tsid;
  occupied |= mask64s[h->fs];
  castle = h->castle;

  if(wtm)
  {
    if(piece[fsid].typ == WPAWN)
    {
      if(h->fs < A3 && h->ts > H3)
        (h+1)->epsq = NOEP;
      else
      if(h->ts == h->epsq)
      {
        board[h->ts - 8] = h->tsid;
        bmat += piece[h->tsid].val;
        occupied |= mask64s[h->ts - 8];
        occupied &= mask64c[h->ts];
        occuByB |= mask64s[h->ts - 8];
        blackPieces |= mask32s[h->tsid];
        board[h->ts] = EMPTY;
      }
    }else
    if(h->fs == E1 && fsid == WKID)
    {
      if(h->ts == G1)
      {
        board[H1] = board[F1];
        board[F1] = EMPTY;
        piece[board[H1]].sq = H1;
        occupied &= mask64c[F1];
        occupied |= mask64s[H1];
        occuByW &= mask64c[F1];
        occuByW |= mask64s[H1];
      }else
      if(h->ts == C1)
      {
        board[A1] = board[D1];
        board[D1] = EMPTY;
        piece[board[A1]].sq = A1;
        occupied &= mask64c[D1];
        occupied |= mask64s[A1];
        occuByW &= mask64c[D1];
        occuByW |= mask64s[A1];
      }
    }else
    if(piece[fsid].ply == ply)
    {
      wmat -= (VALQ - VALP);
      piece[fsid].typ = WPAWN;
      piece[fsid].ply = -1;
    }
    if(h->tsid == EMPTY)
    {
      occupied &= mask64c[h->ts];
    }else
    {
      bmat += piece[h->tsid].val;
      occuByB |= mask64s[h->ts];
      blackPieces |= mask32s[h->tsid];
    }
    occuByW |= mask64s[h->fs];
    occuByW &= mask64c[h->ts];
  }else
  {
    if(piece[fsid].typ == BPAWN)
    {
      if(h->fs > H6 && h->ts < A6)
        (h+1)->epsq = NOEP;
      else
      if(h->ts == h->epsq)
      {
        board[h->ts + 8] = h->tsid;
        wmat += piece[h->tsid].val;
        occupied |= mask64s[h->ts + 8];
        occupied &= mask64c[h->ts];
        occuByW |= mask64s[h->ts + 8];
        whitePieces |= mask32s[h->tsid];
        board[h->ts] = EMPTY;
      }
    }else
    if(h->fs == E8 && fsid == BKID)
    {
      if(h->ts == G8)
      {
        board[H8] = board[F8];
        board[F8] = EMPTY;
        piece[board[H8]].sq = H8;
        occupied &= mask64c[F8];
        occupied |= mask64s[H8];
        occuByB &= mask64c[F8];
        occuByB |= mask64s[H8];
      }else
      if(h->ts == C8)
      {
        board[A8] = board[D8];
        board[D8] = EMPTY;
        piece[board[A8]].sq = A8;
        occupied &= mask64c[D8];
        occupied |= mask64s[A8];
        occuByB &= mask64c[D8];
        occuByB |= mask64s[A8];
      }
    }else
    if(piece[fsid].ply == ply)
    {
      bmat -= (VALQ - VALP);
      piece[fsid].typ = BPAWN;
      piece[fsid].ply = -1;
    }
    if(h->tsid == EMPTY)
    {
      occupied &= mask64c[h->ts];
    }else
    {
      wmat += piece[h->tsid].val;
      occuByW |= mask64s[h->ts];
      whitePieces |= mask32s[h->tsid];
    }
    occuByB |= mask64s[h->fs];
    occuByB &= mask64c[h->ts];
  }
}

void Compute()
{

}

s32 MoveGen()
{
  u32 pieces;
  s32 id;
  s32 fs;
  s32 first;
  u64 enemy;
  u64 eKingSq;
  history *h;

  h = &hist[ply];

  if(wtm)
  {
    pieces = whitePieces;
    enemy = occuByB;
    eKingSq = mask64s[piece[BKID].sq];
  }else
  {
    pieces = blackPieces;
    enemy = occuByW;
    eKingSq = mask64s[piece[WKID].sq];
  }
   
  while(pieces)
  {
    id = FirstOne32(pieces);
    pieces &= mask32c[id];
    fs = piece[id].sq;
    switch(piece[id].typ)
    {
      case WPAWN:
        first = FirstOne64(wPawnMoves[fs] & occupied);
        h->moves[id] = wPawnMoves[fs] & below[first];
        h->captures[id] = wPawnCapts[fs] & (enemy | mask64s[h->epsq]);
        break;
      case WKNIGHT:
      case BKNIGHT:
        h->moves[id] = knight[fs] & ~occupied;
        h->captures[id] = knight[fs] & enemy;
        break;
      case WBISHOP:
      case BBISHOP:
        first = FirstOne64(ray7p[fs] & occupied);
        h->moves[id] = ray7p[fs] & below[first];
        h->captures[id] = mask64s[first];
        first = FirstOne64(ray9p[fs] & occupied);
        h->moves[id] |= ray9p[fs] & below[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray7m[fs] & occupied);
        h->moves[id] |= ray7m[fs] & above[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray9m[fs] & occupied);
        h->moves[id] |= ray9m[fs] & above[first];
        h->captures[id] = (h->captures[id] | mask64s[first]) & enemy;
        break;
      case WROOK:
      case BROOK:
        first = FirstOne64(ray8p[fs] & occupied);
        h->moves[id] = ray8p[fs] & below[first];
        h->captures[id] = mask64s[first];
        first = FirstOne64(ray1p[fs] & occupied);
        h->moves[id] |= ray1p[fs] & below[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray8m[fs] & occupied);
        h->moves[id] |= ray8m[fs] & above[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray1m[fs] & occupied);
        h->moves[id] |= ray1m[fs] & above[first];
        h->captures[id] = (h->captures[id] | mask64s[first]) & enemy;
        break;
       case WQUEEN:
       case BQUEEN:
        first = FirstOne64(ray7p[fs] & occupied);
        h->moves[id] = ray7p[fs] & below[first];
        h->captures[id] = mask64s[first];
        first = FirstOne64(ray9p[fs] & occupied);
        h->moves[id] |= ray9p[fs] & below[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray7m[fs] & occupied);
        h->moves[id] |= ray7m[fs] & above[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray9m[fs] & occupied);
        h->moves[id] |= ray9m[fs] & above[first];
        h->captures[id] |= mask64s[first];
        first = FirstOne64(ray8p[fs] & occupied);
        h->moves[id] |= ray8p[fs] & below[first];
        h->captures[id] |= mask64s[first];
        first = FirstOne64(ray1p[fs] & occupied);
        h->moves[id] |= ray1p[fs] & below[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray8m[fs] & occupied);
        h->moves[id] |= ray8m[fs] & above[first];
        h->captures[id] |= mask64s[first];
        first = LastOne64(ray1m[fs] & occupied);
        h->moves[id] |= ray1m[fs] & above[first];
        h->captures[id] = (h->captures[id] | mask64s[first]) & enemy;
        break;
      case WKING:
        h->moves[id] = king[fs] & ~occupied;
        h->captures[id] = king[fs] & enemy;
        if(castle & 3)
        {
          if(   (castle & 1)
              && board[F1] == EMPTY
              && board[G1] == EMPTY
            ) h->moves[id] |= mask64s[G1];
          if(   (castle & 2)
              && board[D1] == EMPTY
              && board[C1] == EMPTY
              && board[B1] == EMPTY
            ) h->moves[id] |= mask64s[C1];
        }
        break;
      case BPAWN:
        first = LastOne64(bPawnMoves[fs] & occupied);
        h->moves[id] = bPawnMoves[fs] & above[first];
        h->captures[id] = bPawnCapts[fs] & (enemy | mask64s[h->epsq]);
        break;
      case BKING:
        h->moves[id] = king[fs] & ~occupied;
        h->captures[id] = king[fs] & enemy;
        if(castle & 12)
        {
          if(   (castle & 4)
              && board[F8] == EMPTY
              && board[G8] == EMPTY
            ) h->moves[id] |= mask64s[G8];
          if(   (castle & 8)
              && board[D8] == EMPTY
              && board[C8] == EMPTY
              && board[B8] == EMPTY
            ) h->moves[id] |= mask64s[C8];
        }
        break;
    }
    if(eKingSq & h->captures[id])
      return ERROR;
    if(castle & 240)
    {
      if(castle & 48)
      {
        if((castle & 16)
            && ((h->moves[id] & mask64s[E1])
              || (h->captures[id] & mask64s[F1]))
                ) return ERROR;
        if((castle & 32)
            && ((h->moves[id] & mask64s[E1])
              || (h->captures[id] & mask64s[D1]))
                ) return ERROR;
      }else
      {
        if((castle & 64)
            && ((h->moves[id] & mask64s[E8])
              || (h->captures[id] & mask64s[F8]))
                ) return ERROR;
        if((castle & 128)
            && ((h->moves[id] & mask64s[E8])
              || (h->captures[id] & mask64s[D8]))
                ) return ERROR;
      }
    }   
  }
  castle &= 15;
  return OK;
}



void InitChess()
{
  s32 dy;
  s32 dx;
  s32 i;
  s32 d;
  s32 y;
  s32 x;
  s32 s;
  s32 ts;
  u64 *ray;

  vecmap *vm;

  vM = vecMap + 119;

  whitePieces = 0;
  blackPieces = 0;
  occupied = 0;
  occuByW = 0;
  occuByB = 0;
  ply = 0;
  computer = OFF;

  for(dy = -7; dy < 8; dy++)
  for(dx = -7; dx < 9; dx++)
  {
    vm = vM + (dy << 4) + dx;

    vm->d = 0; // direction
    vm->o = 0; // opposite
    vm->i = 0; // index

    if(dy == 0 && dx == 0) continue;

    if(dy == 0)
    {
      if(dx > 0)
      {
        vm->d =  1;
        vm->o = -1;
        vm->i =  3;
      }
      else
      {
        vm->d = -1;
        vm->o =  1;
        vm->i =  7;
      }
    }
    else
    if(dx == 0)
    {
      if(dy > 0)
      {
        vm->d =  8;
        vm->o = -8;
        vm->i =  1;
      }
      else
      {
        vm->d = -8;
        vm->o =  8;
        vm->i =  5;
      }
    }
    else
    if(dy == dx)
    {
      if(dy > 0)
      {
        vm->d =  9;
        vm->o = -9;
        vm->i =  2;
      }
      else
      {
        vm->d = -9;
        vm->o =  9;
        vm->i =  6;
      }
    }
    else
    if(dy + dx == 0)
    {
      if(dy > 0)
      {
        vm->d =  7;
        vm->o = -7;
        vm->i =  0;
      }
      else
      {
        vm->d = -7;
        vm->o =  7;
        vm->i =  4;
      }
    }
    else
    if(abs(dy) + abs(dx) == 3)
       vm->d = (dy << 3) + dx;
  }
// magnitude map
  for(i  = 0; i < 16; i++)
  {
    d = vec[i];
    dy = -3 + Row(28 + d);
    dx = -4 + Col(28 + d);
    for(s = 0; s < 64; s++)
    {
      magMap[(i << 6) + s] = -1;
      y = Row(s);
      x = Col(s);
      while(y >= 0 && y<=7 && x >=0 && x<=7)
      {
        magMap[(i << 6) + s]++;
        y += dy;
        x += dx;
      }
    }
  }
// set mask and clear mask
  for(i = 0; i < 64; i++)
  {
    mask64s[i] = (u64)1 << i;
    mask64c[i] = (u64)0xffffffffffffffff ^ (u64)((u64)1 << i);
    if(i > 31) continue;
    mask32s[i] = (u32)1 << i;
    mask32c[i] = (u32)0xffffffff ^ (u32)((u32)1 << i);
  }
  mask32s[32] = 0;
  mask32c[32] = 0xffffffff;
  mask64s[64] = 0;
  mask64c[64] = 0xffffffffffffffff;

  for(s = 0; s <64; s++)
  {
    for(d = 0; d < 8; d++)
    {
      ray = dir[d];
      *(ray + s) = 0;
      for(i = 1; i <= magMap[(d << 6) + s]; i++)
      {
        ts = s + (i * vec[d]);
        *(ray + s) |= mask64s[ts];
      }
    }
  }

  for(s = 0; s < 64; s++)
  {
    knight[s] = 0;
    for(i = 8; i < 16; i++)
    {
      if(magMap[(i << 6) + s])
        knight[s] |= mask64s[s + vec[i]];
    }
  }

  for(s = 0; s < 64; s++)
  {
    king[s] = 0;
    for(i = 0; i < 8; i++)
    {
      if(magMap[(i << 6) + s])
        king[s] |= mask64s[s + vec[i]];
    }
  }

  for(s = 0; s < 64; s++)
  {
    wPawnMoves[s] = 0;
    wPawnCapts[s] = 0;
    bPawnMoves[s] = 0;
    bPawnCapts[s] = 0;
    if(s < A2 || s > H7) continue;
    wPawnMoves[s] = mask64s[s + 8];
    bPawnMoves[s] = mask64s[s - 8];
    if(s < A3) wPawnMoves[s] |= mask64s[s + 16];
    if(s > H6) bPawnMoves[s] |= mask64s[s - 16];
    if(magMap[s])
    {
      wPawnCapts[s] = mask64s[s + 7];
      bPawnCapts[s] = mask64s[s - 9];
    }
    if(magMap[128 + s])
    {
      wPawnCapts[s] |= mask64s[s + 9];
      bPawnCapts[s] |= mask64s[s - 7];
    }
  }

  for(s = 0; s < 64; s++)
  {
    above[s] = 0;
    for(i = s + 1; i < 64; i++)
        above[s] |= mask64s[i];
    below[s] = 0;
    for(i = 0; i < s; i++)
        below[s] |= mask64s[i];
  }
  above[64] = 0xffffffffffffffff;
  below[64] = 0xffffffffffffffff;

   for(i = 0; i < 33; i++)
      mulBy33[i] = i * 33;

   for(x = 0; x < 33; x++)
   for(y = 0; y < 33; y++)
   {
    if(x != 32)
      i = x;
    else
    if(y != 32)
      i = y + 32;
    else
      i = 64;
    firstBit[x][y] = i;
  }

   for(x = 0; x < 33; x++)
   for(y = 0; y < 33; y++)
   {
    if(x != 32)
      i = x + 32;
    else
    if(y != 32)
      i = y;
    else
      i = 64;
    lastBit[x][y] = i;
  }
  LoadFen(startFen);
  SetUp();
}

// adapted from Gerbil
s32 LoadFen(char *f)
{
    s32 row;
    s32 col;
    s32 sq;
    s32 piece;
 
    for(sq = A1; sq <= H8; sq++) fenBoard[sq] = NONE;

    ply = 0;
    col = ColA;
    row = Row8;
    for(;;f++)
    {
      if(*f == ' ')
      {
        f++;
        break;
      }
      switch(*f)
      {
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
          col += *f-'0';
          continue;
        case '/':
          col = ColA;
          row--;
          continue;
        case 'P':
          piece = WPAWN;
          break;
        case 'N':
          piece = WKNIGHT;
          break; 
        case 'B':
       piece = WBISHOP;
       break;
        case 'R':
          piece = WROOK;
       break;
        case 'Q':
       piece = WQUEEN;
       break;
        case 'K':
       piece = WKING;
       break;
        case 'p':
       piece = BPAWN;
       break;
        case 'n':
       piece = BKNIGHT;
       break;
        case 'b':
        piece = BBISHOP;
       break;
        case 'r':
       piece = BROOK;
          break;
        case 'q':
       piece = BQUEEN;
       break;
        case 'k':
       piece = BKING;
       break;
        default:
       return FALSE;
      }
      fenBoard[row * 8 + col] = piece;
      col++;
    }         
    switch(*f++)
    {
      case 'w': 
        wtm = WHITE;
        bmf = 2;
        break;
      case 'b':
        wtm = BLACK;
        bmf = 3;
        break;
      default:
        return FALSE;
    }
    if(*f++ != ' ') return FALSE;
    if(*f == '-')
    { 
      f++;
      if(*f++ != ' ')
        return FALSE;
    }
    else
    {
      castle = FALSE;
      for(;;)
      {
        if (*f == ' ')
        {
       f++;
       break;
        }
        switch (*f++)
        {
          case 'K':
         castle |= CWKS;
         break;
          case 'Q':
         castle |= CWQS;
            break;
          case 'k':
            castle |= CBKS;
         break;
          case 'q':
            castle |= CBQS;
         break;
          default:
            return FALSE;
        }
      }
    }
    hist[ply].epsq = NOEP;
    if(*f == '-') f++;
    else
    {
      if(*f < 'a' || *f > 'h') return FALSE;
      if(*(f+1) < '0' || *(f+1) > '7') return FALSE;
      row=*(f+1) - '1';
      col=*f - 'a';
      hist[ply].epsq = row * 8 + col;
      f += 2;
    }
    if(*f++ != ' ') return FALSE;
    fifty = 0;
    for(;;)
    {
      if(!isdigit(*f)) break;
      fifty *= 10;
      fifty += *f++ - '0';
    }
    if(*f++ != ' ') return FALSE;
    start = 0;
    for(;;)
    {
      if(!isdigit(*f)) break;
      start *= 10;
      start += *f++ - '0';
    }
    if(start < 1) return FALSE;
    while(*f == ' ') f++;
    if(*f != '\0') return FALSE;
    return TRUE;
}

s32 SetUp()
{
  s32 typ;
  s32 sq;
  s32 i;

  for(sq = A1; sq <= H8; sq++) board[sq] = EMPTY;

  i=0;

  for(typ = WPAWN; typ <= BKING; typ++)
  {
    if(typ > WPAWN && i < 8) i = 8;
    else
    if(typ == WKING) i = 15;
    else
    if(typ > BPAWN && i < 24) i = 24;
    else
    if(typ == BKING) i = 31;
    for(sq = A1; sq <= H8; sq++)
    {
      if(fenBoard[sq] == typ)
      {
        board[sq] = i;
        piece[i].sq = sq;
        piece[i].typ = typ;
        piece[i].val = val[typ];
        piece[i].ply = -1;
        if(i < 16)
        {
          whitePieces |= mask32s[i];
          occupied |= mask64s[sq];
          occuByW |= mask64s[sq];
          wmat += val[typ];
        }
        else
        {
          blackPieces |= mask32s[i];
          occupied |= mask64s[sq];
          occuByB |= mask64s[sq];
          bmat += val[typ];
        }
        i++;
      }
    }
  }
  piece[32].typ = NONE;
  return TRUE;
}

__inline s32 FirstOne32(u32 bits)
{
    __asm
    {
        bsf eax,dword ptr bits
    }
}

__inline s32 LastOne32(u32 bits)
{
    __asm
    {
        bsr eax,dword ptr bits
    }
}

__inline s32 FirstOne64(u64 bits)
{
    __asm
    {
        mov   edx, 32
        mov   eax, 32
        bsf   edx, dword ptr bits
        bsf   eax, dword ptr bits + 4
        mov   edx, [mulBy33 + edx*4]
        movzx eax, [firstBit + edx + eax]
    }
}

__inline s32 LastOne64(u64 bits)
{
    __asm
    {
        mov   edx, 32
        mov   eax, 32
        bsr   eax, dword ptr bits
        bsr   edx, dword ptr bits + 4
        mov   edx, [mulBy33 + edx*4]
        movzx eax, [lastBit + edx + eax]
    }
}

void PrintBoard()
{
  s32 ps;
  s32 fs;
  s32 i;
  u08 pieces[]="PNBRQKpnbrqk.?";

  for(ps=63;ps>=0;ps--)
  {
    fs=7-(ps&7)+(ps>>3)*8;
    i=board[fs];
    i=piece[i].typ;
    if(i>13)i=13;
    printf(" %c ",pieces[i]);
    if((ps&7)==0)printf("\n");
  }
     printf("\n");
}

void Convert()
{
  sprintf(cmd,"%c%d%c%d",(fs&7)+'a',(fs>>3)+1,(ts&7)+'a',(ts>>3)+1);
 
} 

void Wperf()
{
  u32 pieces;
  s32 id;
  u64 tosqs;

  if(MoveGen() == ERROR)
  {
    nodes--;
    return;
  }
  pieces = whitePieces;
  while(pieces)
  {
    id = FirstOne32(pieces);
    pieces &= mask32c[id];
    tosqs = hist[ply].captures[id] | hist[ply].moves[id];
    while(tosqs)
    {
      fs = piece[id].sq;
      ts = FirstOne64(tosqs);
      tosqs &= mask64c[ts];
      if(depth == 1)
      {
        MakeMove();
        TakeBack();
      }else
      {
        MakeMove();
        depth--;
        Bperf();
        TakeBack();
        depth++;
      }
    }
  }
}

void Bperf()
{
  u32 pieces;
  s32 id;
  u64 tosqs;

  if(MoveGen() == ERROR)
  {
    nodes--;
    return;
  }
  pieces = blackPieces;
  while(pieces)
  {
    id = FirstOne32(pieces);
    pieces &= mask32c[id];
    tosqs = hist[ply].captures[id] | hist[ply].moves[id];
    while(tosqs)
    {
      fs = piece[id].sq;
      ts = FirstOne64(tosqs);
      tosqs &= mask64c[ts];
      if(depth == 1)
      {
        MakeMove();
        TakeBack();
      }else
      {
        MakeMove();
        depth--;
        Wperf();
        TakeBack();
        depth++;
      }
    }
  }
}

I made a couple little changes to get it to work for me.

Code: Select all

#include    <stdio.h>
#include    <ctype.h>
#include    <string.h>
#include    <signal.h>
#include    <time.h>
#include    <stdlib.h>

#define     FALSE       0
#define     TRUE        1

#define     OK          0
#define     ERROR       1

#define     BLACK       0
#define     WHITE       1
#define     OFF         2

#define     CONSOLE     0
#define     XBOARD      1
#define     UCI         2

#define     A1          0
#define     B1          1
#define     C1          2
#define     D1          3
#define     E1          4
#define     F1          5
#define     G1          6
#define     H1          7
#define     A2          8
#define     B2          9
#define     C2          10
#define     D2          11
#define     E2          12
#define     F2          13
#define     G2          14
#define     H2          15
#define     A3          16
#define     B3          17
#define     C3          18
#define     D3          19
#define     E3          20
#define     F3          21
#define     G3          22
#define     H3          23
#define     A4          24
#define     B4          25
#define     C4          26
#define     D4          27
#define     E4          28
#define     F4          29
#define     G4          30
#define     H4          31
#define     A5          32
#define     B5          33
#define     C5          34
#define     D5          35
#define     E5          36
#define     F5          37
#define     G5          38
#define     H5          39
#define     A6          40
#define     B6          41
#define     C6          42
#define     D6          43
#define     E6          44
#define     F6          45
#define     G6          46
#define     H6          47
#define     A7          48
#define     B7          49
#define     C7          50
#define     D7          51
#define     E7          52
#define     F7          53
#define     G7          54
#define     H7          55
#define     A8          56
#define     B8          57
#define     C8          58
#define     D8          59
#define     E8          60
#define     F8          61
#define     G8          62
#define     H8          63

#define     NOEP        64

#define     WPAWN       0
#define     WKNIGHT     1
#define     WBISHOP     2
#define     WROOK       3
#define     WQUEEN      4
#define     WKING       5
#define     BPAWN       6
#define     BKNIGHT     7
#define     BBISHOP     8
#define     BROOK       9
#define     BQUEEN      10
#define     BKING       11
#define     NONE        12

#define     WKID        15
#define     BKID        31

#define     EMPTY       32

#define     VALP        100
#define     VALN        290
#define     VALB        320
#define     VALR        500
#define     VALQ        900
#define     VALK        0

#define     CWKS        1
#define     CWQS        2
#define     CBKS        4
#define     CBQS        8
#define     WJCS        16
#define     WJCL        32
#define     BJCS        64
#define     BJCL        128

#define     IsBlack(x)  ((x)>15&&(x)<32)
#define     IsWhite(x)  ((x)<16)
#define     abs(x)      (((x)>0)?x:-x)

#define     Row(y)      ((y)>>3)
#define     Col(x)      ((x)&7)

#define     ColA        0
#define     Row8        7

#define     s08         signed char
#define     u08         char
#define     s32         int
#define     u32         unsigned int
#define     s64         __int64
#define     u64         unsigned __int64

s32 __cdecl     main(void);
void            InitChess(void);
void            Compute(void);
void            GetCmd(void);
s32             LoadFen(u08 *);
s32             SetUp(void);
s32             FirstOne32(u32);
s32             LastOne32(u32);
s32             FirstOne64(u64);
s32             LastOne64(u64);
void            MakeMove(void);
void            TakeBack(void);
void            PrintBoard(void);
void            Convert(void);
s32             MoveGen(void);
void            Wperf(void);
void            Bperf(void);

typedef struct vecmap {
    s32             i;
    s32             d;
    s32             o;
}   vecmap;

typedef struct history {
    s32             fs;
    s32             ts;
    s32             tsid;
    s32             epsq;
    s32             castle;
    u64             moves[32];
    u64             captures[32];
}   history;

typedef struct pieces {
    s32             typ;
    s32             val;
    s32             sq;
    s32             ply;
}   pieces;

s32             repeat;
s32             xboard;
s32             wtm;
s32             bmf;
s32             fs;
s32             ts;
s32             wmat;
s32             bmat;
s32             computer;
s32             ply;
s32             depth;
s32             fifty;
s32             start;
s32             castle;
u32             whitePieces;
u32             blackPieces;
u64             occupied;
u64             occuByW;
u64             occuByB;
s64             nodes;

u08             cmd[20];
u08             data[256];
u08             firstBit[33][33];
u08             lastBit[33][33];

s32             fenBoard[64];
s32             board[64];
s32             magMap[1024];

u32             mulBy33[33];
u32             mask32s[33];
u32             mask32c[33];

u64             mask64s[65];
u64             mask64c[65];
u64             ray7p[64];
u64             ray8p[64];
u64             ray9p[64];
u64             ray1p[64];
u64             ray7m[64];
u64             ray8m[64];
u64             ray9m[64];
u64             ray1m[64];
u64             knight[64];
u64             king[64];
u64             wPawnMoves[64];
u64             wPawnCapts[64];
u64             bPawnMoves[64];
u64             bPawnCapts[64];
u64             above[65];
u64             below[65];

vecmap          vecMap[240];
vecmap         *vM;

history         hist[12000];

pieces          piece[33];

/* From Tom Kerrigan's Simple Chess Program (TSCP). Modified.
   This is the castle_mask array. We can use it to determine
   the castling permissions after a move. What we do is
   logical-AND the castle bits with the castle_mask bits for
   both of the move's squares. Let's say castle is 1, meaning
   that white can still castle kingside. Now we play a move
   where the rook on h1 gets captured. We AND castle with
   castle_mask[7], so we have 1&14, and castle becomes 0 and
   white can't castle kingside anymore. */

s32             castleMask[64] =
{
    13, 15, 15, 15, 12, 15, 15, 14,
    15, 15, 15, 15, 15, 15, 15, 15,
    15, 15, 15, 15, 15, 15, 15, 15,
    15, 15, 15, 15, 15, 15, 15, 15,
    15, 15, 15, 15, 15, 15, 15, 15,
    15, 15, 15, 15, 15, 15, 15, 15,
    15, 15, 15, 15, 15, 15, 15, 15,
7, 15, 15, 15, 3, 15, 15, 11};

u08             startFen[] = "rnbqkbnr/pppppppp/////PPPPPPPP/RNBQKBNR w KQkq - 0 1";

s32             val[] =
{100, 290, 320, 500, 900, 0, 100, 290, 320, 500, 900, 0};

s32             vec[] =
{7, 8, 9, 1, -7, -8, -9, -1,
6, -6, 15, -15, 17, -17, 10, -10};

u64            *dir[] =
{ray7p, ray8p, ray9p, ray1p,
ray7m, ray8m, ray9m, ray1m};

s32             __cdecl
                main()
{
    repeat = TRUE;

    InitChess();

    while (repeat) {
        PrintBoard();
        if (computer == wtm)
            Compute();
        else
            GetCmd();
    }

    return 0;
}

void            GetCmd()
{
    s32             retry;
    u32             pieces;
    s32             id;
    u64             tosqs;

    retry = TRUE;
    while (retry) {
        retry = FALSE;

        MoveGen();
        pieces = wtm ? whitePieces : blackPieces;
        while (pieces) {
            id = FirstOne32(pieces);
            pieces &= mask32c[id];
            fs = piece[id].sq;
            tosqs = hist[ply].captures[id] | hist[ply].moves[id];
            while (tosqs) {
                ts = FirstOne64(tosqs);
                tosqs &= mask64c[ts];
                MakeMove();
                if (MoveGen() == OK) {
                    Convert();
                    printf("%s ", cmd);
                }
                TakeBack();
            }
        }

        if (!xboard) {
            printf((wtm) ? "\nWhite" : "\nBlack");
            printf("%d> ", (ply + bmf) / 2);
        }
        if (!fgets(data, 256, stdin)) {
            retry = FALSE;
            continue;
        }
        if (data[0] == '\n')
            continue;
        sscanf(data, "%s", cmd);
        strlwr(cmd);

        if (!strcmp(cmd, "xb")) {
            xboard = xboard ^ 1;
            continue;
        }
        if (!strcmp(cmd, "xboard")) {
            xboard = TRUE;
            signal(SIGINT, SIG_IGN);
            printf("\n");
            fflush(stdout);
            continue;
        }
        if (!strcmp(cmd, "white")) {
            wtm = WHITE;
            computer = BLACK;
            continue;
        }
        if (!strcmp(cmd, "black")) {
            wtm = BLACK;
            computer = WHITE;
            continue;
        }
        if (!strcmp(cmd, "off") || !strcmp(cmd, "force")) {
            computer = OFF;
            continue;
        }
        if (!strcmp(cmd, "go")) {
            computer = wtm;
            continue;
        }
        if (!strcmp(cmd, "u") || !strcmp(cmd, "undo")) {
            if (ply < 1)
                continue;
            computer = OFF;
            TakeBack();
            printf("castle = %d\n", castle);
            // high=0;
            continue;
        }
        if (!strcmp(cmd, "r") || !strcmp(cmd, "remove")) {
            if (ply < 3)
                continue;
            TakeBack();
            TakeBack();
            ply = 0;
            // high=0;
            continue;
        }
        if (!strcmp(cmd, "new")) {
            InitChess();
            computer = OFF;
            wtm = WHITE;
            // high=0;
            continue;
        }
        if (!strcmp(cmd, "quit")) {
            repeat = FALSE;
            continue;
        }
        if (!strcmp(cmd, "perft")) {
            double          sec;
         double          nps;
            time_t          st,
                            et,
                            dt;
            sscanf(data, "perft %d", &depth);
            nodes = 0;
            st = clock();
            if (wtm)
                Wperf();
            else
                Bperf();
            et = clock();
            dt = et - st;
            sec = (double) dt / CLOCKS_PER_SEC;
            _i64toa(nodes, cmd, 10);
         nps = ((double) nodes) / sec;
            printf("Nodes = %s,  msec. = %d, nps = %.2f\n",
                   cmd, (int) dt, nps);
            depth = 100;
            continue;
        }
        retry = TRUE;;
        fs = cmd[0] - 'a' + 8 * (cmd[1] - '1');
        ts = cmd[2] - 'a' + 8 * (cmd[3] - '1');
        pieces = wtm ? whitePieces : blackPieces;
        if (pieces & mask32s[board[fs]]) {
            if ((hist[ply].captures[board[fs]] & mask64s[ts]) ||
                (hist[ply].moves[board[fs]] & mask64s[ts])) {
                MakeMove();
                if (MoveGen() == ERROR) {
                    TakeBack();
                    continue;
                }
                printf("castle = %d\n", castle);
                retry = FALSE;
            }
        }
    }
}

void            MakeMove()
{
    s32             fsid;
    s32             tsid;
    s32             typ;
    history        *h;

    h = &hist[ply];

    fsid = board[fs];
    tsid = board[ts];

    h->castle = castle;
    castle &= (castleMask[fs] & castleMask[ts]);

    typ = piece[fsid].typ;
    if (wtm) {
        if (typ == WPAWN) {
            if (fs < A3 && ts > H3)
                (h + 1)->epsq = ts - 8;
            else if (ts == h->epsq) {
                tsid = board[ts - 8];
                board[ts - 8] = EMPTY;
                bmat -= piece[tsid].val;
                occupied &= mask64c[ts - 8];
                occuByB &= mask64c[ts - 8];
            } else if (ts > H7) {
                wmat += (VALQ - VALP);
                piece[fsid].typ = WQUEEN;
                piece[fsid].ply = ply;
            }
        } else if (typ == WKING && fs == E1) {
            if (ts == G1) {
                board[F1] = board[H1];
                board[H1] = EMPTY;
                piece[board[F1]].sq = F1;
                occupied &= mask64c[H1];
                occupied |= mask64s[F1];
                occuByW &= mask64c[H1];
                occuByW |= mask64s[F1];
                castle |= WJCS;
            } else if (ts == C1) {
                board[D1] = board[A1];
                board[A1] = EMPTY;
                piece[board[D1]].sq = D1;
                occupied &= mask64c[A1];
                occupied |= mask64s[D1];
                occuByW &= mask64c[A1];
                occuByW |= mask64s[D1];
                castle |= WJCL;
            }
        }
        occuByW &= mask64c[fs];
        occuByW |= mask64s[ts];
        bmat -= piece[tsid].val;
        occuByB &= mask64c[ts];
        blackPieces &= mask32c[tsid];
    } else {
        if (typ == BPAWN) {
            if (fs > H6 && ts < A6)
                (h + 1)->epsq = ts + 8;
            else if (ts == h->epsq) {
                tsid = board[ts + 8];
                board[ts + 8] = EMPTY;
                wmat -= piece[tsid].val;
                occupied &= mask64c[ts + 8];
                occuByW &= mask64c[ts + 8];
            } else if (ts < A2) {
                bmat += (VALQ - VALP);
                piece[fsid].typ = BQUEEN;
                piece[fsid].ply = ply;
            }
        } else if (typ == BKING && fs == E8) {
            if (ts == G8) {
                board[F8] = board[H8];
                board[H8] = EMPTY;
                piece[board[F8]].sq = F8;
                occupied &= mask64c[H8];
                occupied |= mask64s[F8];
                occuByB &= mask64c[H8];
                occuByB |= mask64s[F8];
                castle |= BJCS;
            } else if (ts == C8) {
                board[D8] = board[A8];
                board[A8] = EMPTY;
                piece[board[C8]].sq = D8;
                occupied &= mask64c[A8];
                occupied |= mask64s[D8];
                occuByB &= mask64c[A8];
                occuByB |= mask64s[D8];
                castle |= BJCL;
            }
        }
        occuByB &= mask64c[fs];
        occuByB |= mask64s[ts];
        wmat -= piece[tsid].val;
        occuByW &= mask64c[ts];
        whitePieces &= mask32c[tsid];
    }

    h->fs = fs;
    h->ts = ts;
    h->tsid = tsid;
    board[fs] = EMPTY;
    board[ts] = fsid;
    piece[fsid].sq = ts;
    occupied &= mask64c[fs];
    occupied |= mask64s[ts];

    ply++;
    nodes++;
    wtm = 1 - wtm;
}

void            TakeBack()
{
    s32             fsid;
    history        *h;

    ply--;
    wtm = 1 - wtm;

    h = &hist[ply];

    fsid = board[h->ts];
    board[h->fs] = fsid;
    piece[fsid].sq = h->fs;
    board[h->ts] = h->tsid;
    occupied |= mask64s[h->fs];
    castle = h->castle;

    if (wtm) {
        if (piece[fsid].typ == WPAWN) {
            if (h->fs < A3 && h->ts > H3)
                (h + 1)->epsq = NOEP;
            else if (h->ts == h->epsq) {
                board[h->ts - 8] = h->tsid;
                bmat += piece[h->tsid].val;
                occupied |= mask64s[h->ts - 8];
                occupied &= mask64c[h->ts];
                occuByB |= mask64s[h->ts - 8];
                blackPieces |= mask32s[h->tsid];
                board[h->ts] = EMPTY;
            }
        } else if (h->fs == E1 && fsid == WKID) {
            if (h->ts == G1) {
                board[H1] = board[F1];
                board[F1] = EMPTY;
                piece[board[H1]].sq = H1;
                occupied &= mask64c[F1];
                occupied |= mask64s[H1];
                occuByW &= mask64c[F1];
                occuByW |= mask64s[H1];
            } else if (h->ts == C1) {
                board[A1] = board[D1];
                board[D1] = EMPTY;
                piece[board[A1]].sq = A1;
                occupied &= mask64c[D1];
                occupied |= mask64s[A1];
                occuByW &= mask64c[D1];
                occuByW |= mask64s[A1];
            }
        } else if (piece[fsid].ply == ply) {
            wmat -= (VALQ - VALP);
            piece[fsid].typ = WPAWN;
            piece[fsid].ply = -1;
        }
        if (h->tsid == EMPTY) {
            occupied &= mask64c[h->ts];
        } else {
            bmat += piece[h->tsid].val;
            occuByB |= mask64s[h->ts];
            blackPieces |= mask32s[h->tsid];
        }
        occuByW |= mask64s[h->fs];
        occuByW &= mask64c[h->ts];
    } else {
        if (piece[fsid].typ == BPAWN) {
            if (h->fs > H6 && h->ts < A6)
                (h + 1)->epsq = NOEP;
            else if (h->ts == h->epsq) {
                board[h->ts + 8] = h->tsid;
                wmat += piece[h->tsid].val;
                occupied |= mask64s[h->ts + 8];
                occupied &= mask64c[h->ts];
                occuByW |= mask64s[h->ts + 8];
                whitePieces |= mask32s[h->tsid];
                board[h->ts] = EMPTY;
            }
        } else if (h->fs == E8 && fsid == BKID) {
            if (h->ts == G8) {
                board[H8] = board[F8];
                board[F8] = EMPTY;
                piece[board[H8]].sq = H8;
                occupied &= mask64c[F8];
                occupied |= mask64s[H8];
                occuByB &= mask64c[F8];
                occuByB |= mask64s[H8];
            } else if (h->ts == C8) {
                board[A8] = board[D8];
                board[D8] = EMPTY;
                piece[board[A8]].sq = A8;
                occupied &= mask64c[D8];
                occupied |= mask64s[A8];
                occuByB &= mask64c[D8];
                occuByB |= mask64s[A8];
            }
        } else if (piece[fsid].ply == ply) {
            bmat -= (VALQ - VALP);
            piece[fsid].typ = BPAWN;
            piece[fsid].ply = -1;
        }
        if (h->tsid == EMPTY) {
            occupied &= mask64c[h->ts];
        } else {
            wmat += piece[h->tsid].val;
            occuByW |= mask64s[h->ts];
            whitePieces |= mask32s[h->tsid];
        }
        occuByB |= mask64s[h->fs];
        occuByB &= mask64c[h->ts];
    }
}

void            Compute()
{

}

s32
MoveGen()
{
    u32             pieces;
    s32             id;
    s32             fs;
    s32             first;
    u64             enemy;
    u64             eKingSq;
    history        *h;

    h = &hist[ply];

    if (wtm) {
        pieces = whitePieces;
        enemy = occuByB;
        eKingSq = mask64s[piece[BKID].sq];
    } else {
        pieces = blackPieces;
        enemy = occuByW;
        eKingSq = mask64s[piece[WKID].sq];
    }

    while (pieces) {
        id = FirstOne32(pieces);
        pieces &= mask32c[id];
        fs = piece[id].sq;
        switch (piece[id].typ) {
        case WPAWN:
            first = FirstOne64(wPawnMoves[fs] & occupied);
            h->moves[id] = wPawnMoves[fs] & below[first];
            h->captures[id] = wPawnCapts[fs] & (enemy | mask64s[h->epsq]);
            break;
        case WKNIGHT:
        case BKNIGHT:
            h->moves[id] = knight[fs] & ~occupied;
            h->captures[id] = knight[fs] & enemy;
            break;
        case WBISHOP:
        case BBISHOP:
            first = FirstOne64(ray7p[fs] & occupied);
            h->moves[id] = ray7p[fs] & below[first];
            h->captures[id] = mask64s[first];
            first = FirstOne64(ray9p[fs] & occupied);
            h->moves[id] |= ray9p[fs] & below[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray7m[fs] & occupied);
            h->moves[id] |= ray7m[fs] & above[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray9m[fs] & occupied);
            h->moves[id] |= ray9m[fs] & above[first];
            h->captures[id] = (h->captures[id] | mask64s[first]) & enemy;
            break;
        case WROOK:
        case BROOK:
            first = FirstOne64(ray8p[fs] & occupied);
            h->moves[id] = ray8p[fs] & below[first];
            h->captures[id] = mask64s[first];
            first = FirstOne64(ray1p[fs] & occupied);
            h->moves[id] |= ray1p[fs] & below[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray8m[fs] & occupied);
            h->moves[id] |= ray8m[fs] & above[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray1m[fs] & occupied);
            h->moves[id] |= ray1m[fs] & above[first];
            h->captures[id] = (h->captures[id] | mask64s[first]) & enemy;
            break;
        case WQUEEN:
        case BQUEEN:
            first = FirstOne64(ray7p[fs] & occupied);
            h->moves[id] = ray7p[fs] & below[first];
            h->captures[id] = mask64s[first];
            first = FirstOne64(ray9p[fs] & occupied);
            h->moves[id] |= ray9p[fs] & below[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray7m[fs] & occupied);
            h->moves[id] |= ray7m[fs] & above[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray9m[fs] & occupied);
            h->moves[id] |= ray9m[fs] & above[first];
            h->captures[id] |= mask64s[first];
            first = FirstOne64(ray8p[fs] & occupied);
            h->moves[id] |= ray8p[fs] & below[first];
            h->captures[id] |= mask64s[first];
            first = FirstOne64(ray1p[fs] & occupied);
            h->moves[id] |= ray1p[fs] & below[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray8m[fs] & occupied);
            h->moves[id] |= ray8m[fs] & above[first];
            h->captures[id] |= mask64s[first];
            first = LastOne64(ray1m[fs] & occupied);
            h->moves[id] |= ray1m[fs] & above[first];
            h->captures[id] = (h->captures[id] | mask64s[first]) & enemy;
            break;
        case WKING:
            h->moves[id] = king[fs] & ~occupied;
            h->captures[id] = king[fs] & enemy;
            if (castle & 3) {
                if ((castle & 1)
                    && board[F1] == EMPTY
                    && board[G1] == EMPTY
                    )
                    h->moves[id] |= mask64s[G1];
                if ((castle & 2)
                    && board[D1] == EMPTY
                    && board[C1] == EMPTY
                    && board[B1] == EMPTY
                    )
                    h->moves[id] |= mask64s[C1];
            }
            break;
        case BPAWN:
            first = LastOne64(bPawnMoves[fs] & occupied);
            h->moves[id] = bPawnMoves[fs] & above[first];
            h->captures[id] = bPawnCapts[fs] & (enemy | mask64s[h->epsq]);
            break;
        case BKING:
            h->moves[id] = king[fs] & ~occupied;
            h->captures[id] = king[fs] & enemy;
            if (castle & 12) {
                if ((castle & 4)
                    && board[F8] == EMPTY
                    && board[G8] == EMPTY
                    )
                    h->moves[id] |= mask64s[G8];
                if ((castle & 8)
                    && board[D8] == EMPTY
                    && board[C8] == EMPTY
                    && board[B8] == EMPTY
                    )
                    h->moves[id] |= mask64s[C8];
            }
            break;
        }
        if (eKingSq & h->captures[id])
            return ERROR;
        if (castle & 240) {
            if (castle & 48) {
                if ((castle & 16)
                    && ((h->moves[id] & mask64s[E1])
                        || (h->captures[id] & mask64s[F1]))
                    )
                    return ERROR;
                if ((castle & 32)
                    && ((h->moves[id] & mask64s[E1])
                        || (h->captures[id] & mask64s[D1]))
                    )
                    return ERROR;
            } else {
                if ((castle & 64)
                    && ((h->moves[id] & mask64s[E8])
                        || (h->captures[id] & mask64s[F8]))
                    )
                    return ERROR;
                if ((castle & 128)
                    && ((h->moves[id] & mask64s[E8])
                        || (h->captures[id] & mask64s[D8]))
                    )
                    return ERROR;
            }
        }
    }
    castle &= 15;
    return OK;
}



void            InitChess()
{
    s32             dy;
    s32             dx;
    s32             i;
    s32             d;
    s32             y;
    s32             x;
    s32             s;
    s32             ts;
    u64            *ray;

    vecmap         *vm;

    vM = vecMap + 119;

    whitePieces = 0;
    blackPieces = 0;
    occupied = 0;
    occuByW = 0;
    occuByB = 0;
    ply = 0;
    computer = OFF;

    for (dy = -7; dy < 8; dy++)
        for (dx = -7; dx < 9; dx++) {
            vm = vM + (dy << 4) + dx;

            vm->d = 0;          // direction

            vm->o = 0;          // opposite

            vm->i = 0;          // index

            if (dy == 0 && dx == 0)
                continue;

            if (dy == 0) {
                if (dx > 0) {
                    vm->d = 1;
                    vm->o = -1;
                    vm->i = 3;
                } else {
                    vm->d = -1;
                    vm->o = 1;
                    vm->i = 7;
                }
            } else if (dx == 0) {
                if (dy > 0) {
                    vm->d = 8;
                    vm->o = -8;
                    vm->i = 1;
                } else {
                    vm->d = -8;
                    vm->o = 8;
                    vm->i = 5;
                }
            } else if (dy == dx) {
                if (dy > 0) {
                    vm->d = 9;
                    vm->o = -9;
                    vm->i = 2;
                } else {
                    vm->d = -9;
                    vm->o = 9;
                    vm->i = 6;
                }
            } else if (dy + dx == 0) {
                if (dy > 0) {
                    vm->d = 7;
                    vm->o = -7;
                    vm->i = 0;
                } else {
                    vm->d = -7;
                    vm->o = 7;
                    vm->i = 4;
                }
            } else if (abs(dy) + abs(dx) == 3)
                vm->d = (dy << 3) + dx;
        }
// magnitude map
    for (i = 0; i < 16; i++) {
        d = vec[i];
        dy = -3 + Row(28 + d);
        dx = -4 + Col(28 + d);
        for (s = 0; s < 64; s++) {
            magMap[(i << 6) + s] = -1;
            y = Row(s);
            x = Col(s);
            while (y >= 0 && y <= 7 && x >= 0 && x <= 7) {
                magMap[(i << 6) + s]++;
                y += dy;
                x += dx;
            }
        }
    }
// set mask and clear mask
    for (i = 0; i < 64; i++) {
        mask64s[i] = (u64) 1 << i;
        mask64c[i] = (u64) 0xffffffffffffffff ^ (u64) ((u64) 1 << i);
        if (i > 31)
            continue;
        mask32s[i] = (u32) 1 << i;
        mask32c[i] = (u32) 0xffffffff ^ (u32) ((u32) 1 << i);
    }
    mask32s[32] = 0;
    mask32c[32] = 0xffffffff;
    mask64s[64] = 0;
    mask64c[64] = 0xffffffffffffffff;

    for (s = 0; s < 64; s++) {
        for (d = 0; d < 8; d++) {
            ray = dir[d];
            *(ray + s) = 0;
            for (i = 1; i <= magMap[(d << 6) + s]; i++) {
                ts = s + (i * vec[d]);
                *(ray + s) |= mask64s[ts];
            }
        }
    }

    for (s = 0; s < 64; s++) {
        knight[s] = 0;
        for (i = 8; i < 16; i++) {
            if (magMap[(i << 6) + s])
                knight[s] |= mask64s[s + vec[i]];
        }
    }

    for (s = 0; s < 64; s++) {
        king[s] = 0;
        for (i = 0; i < 8; i++) {
            if (magMap[(i << 6) + s])
                king[s] |= mask64s[s + vec[i]];
        }
    }

    for (s = 0; s < 64; s++) {
        wPawnMoves[s] = 0;
        wPawnCapts[s] = 0;
        bPawnMoves[s] = 0;
        bPawnCapts[s] = 0;
        if (s < A2 || s > H7)
            continue;
        wPawnMoves[s] = mask64s[s + 8];
        bPawnMoves[s] = mask64s[s - 8];
        if (s < A3)
            wPawnMoves[s] |= mask64s[s + 16];
        if (s > H6)
            bPawnMoves[s] |= mask64s[s - 16];
        if (magMap[s]) {
            wPawnCapts[s] = mask64s[s + 7];
            bPawnCapts[s] = mask64s[s - 9];
        }
        if (magMap[128 + s]) {
            wPawnCapts[s] |= mask64s[s + 9];
            bPawnCapts[s] |= mask64s[s - 7];
        }
    }

    for (s = 0; s < 64; s++) {
        above[s] = 0;
        for (i = s + 1; i < 64; i++)
            above[s] |= mask64s[i];
        below[s] = 0;
        for (i = 0; i < s; i++)
            below[s] |= mask64s[i];
    }
    above[64] = 0xffffffffffffffff;
    below[64] = 0xffffffffffffffff;

    for (i = 0; i < 33; i++)
        mulBy33[i] = i * 33;

    for (x = 0; x < 33; x++)
        for (y = 0; y < 33; y++) {
            if (x != 32)
                i = x;
            else if (y != 32)
                i = y + 32;
            else
                i = 64;
            firstBit[x][y] = i;
        }

    for (x = 0; x < 33; x++)
        for (y = 0; y < 33; y++) {
            if (x != 32)
                i = x + 32;
            else if (y != 32)
                i = y;
            else
                i = 64;
            lastBit[x][y] = i;
        }
    LoadFen(startFen);
    SetUp();
}

// adapted from Gerbil
s32
LoadFen(char *f)
{
    s32             row;
    s32             col;
    s32             sq;
    s32             piece;

    for (sq = A1; sq <= H8; sq++)
        fenBoard[sq] = NONE;

    ply = 0;
    col = ColA;
    row = Row8;
    for (;; f++) {
        if (*f == ' ') {
            f++;
            break;
        }
        switch (*f) {
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
            col += *f - '0';
            continue;
        case '/':
            col = ColA;
            row--;
            continue;
        case 'P':
            piece = WPAWN;
            break;
        case 'N':
            piece = WKNIGHT;
            break;
        case 'B':
            piece = WBISHOP;
            break;
        case 'R':
            piece = WROOK;
            break;
        case 'Q':
            piece = WQUEEN;
            break;
        case 'K':
            piece = WKING;
            break;
        case 'p':
            piece = BPAWN;
            break;
        case 'n':
            piece = BKNIGHT;
            break;
        case 'b':
            piece = BBISHOP;
            break;
        case 'r':
            piece = BROOK;
            break;
        case 'q':
            piece = BQUEEN;
            break;
        case 'k':
            piece = BKING;
            break;
        default:
            return FALSE;
        }
        fenBoard[row * 8 + col] = piece;
        col++;
    }
    switch (*f++) {
    case 'w':
        wtm = WHITE;
        bmf = 2;
        break;
    case 'b':
        wtm = BLACK;
        bmf = 3;
        break;
    default:
        return FALSE;
    }
    if (*f++ != ' ')
        return FALSE;
    if (*f == '-') {
        f++;
        if (*f++ != ' ')
            return FALSE;
    } else {
        castle = FALSE;
        for (;;) {
            if (*f == ' ') {
                f++;
                break;
            }
            switch (*f++) {
            case 'K':
                castle |= CWKS;
                break;
            case 'Q':
                castle |= CWQS;
                break;
            case 'k':
                castle |= CBKS;
                break;
            case 'q':
                castle |= CBQS;
                break;
            default:
                return FALSE;
            }
        }
    }
    hist[ply].epsq = NOEP;
    if (*f == '-')
        f++;
    else {
        if (*f < 'a' || *f > 'h')
            return FALSE;
        if (*(f + 1) < '0' || *(f + 1) > '7')
            return FALSE;
        row = *(f + 1) - '1';
        col = *f - 'a';
        hist[ply].epsq = row * 8 + col;
        f += 2;
    }
    if (*f++ != ' ')
        return FALSE;
    fifty = 0;
    for (;;) {
        if (!isdigit(*f))
            break;
        fifty *= 10;
        fifty += *f++ - '0';
    }
    if (*f++ != ' ')
        return FALSE;
    start = 0;
    for (;;) {
        if (!isdigit(*f))
            break;
        start *= 10;
        start += *f++ - '0';
    }
    if (start < 1)
        return FALSE;
    while (*f == ' ')
        f++;
    if (*f != '\0')
        return FALSE;
    return TRUE;
}

s32
SetUp()
{
    s32             typ;
    s32             sq;
    s32             i;

    for (sq = A1; sq <= H8; sq++)
        board[sq] = EMPTY;

    i = 0;

    for (typ = WPAWN; typ <= BKING; typ++) {
        if (typ > WPAWN && i < 8)
            i = 8;
        else if (typ == WKING)
            i = 15;
        else if (typ > BPAWN && i < 24)
            i = 24;
        else if (typ == BKING)
            i = 31;
        for (sq = A1; sq <= H8; sq++) {
            if (fenBoard[sq] == typ) {
                board[sq] = i;
                piece[i].sq = sq;
                piece[i].typ = typ;
                piece[i].val = val[typ];
                piece[i].ply = -1;
                if (i < 16) {
                    whitePieces |= mask32s[i];
                    occupied |= mask64s[sq];
                    occuByW |= mask64s[sq];
                    wmat += val[typ];
                } else {
                    blackPieces |= mask32s[i];
                    occupied |= mask64s[sq];
                    occuByB |= mask64s[sq];
                    bmat += val[typ];
                }
                i++;
            }
        }
    }
    piece[32].typ = NONE;
    return TRUE;
}

__inline        s32
                FirstOne32(u32 bits)
{
    __asm
    {
        bsf             eax,  dword ptr bits
    }
}

__inline        s32
                LastOne32(u32 bits)
{
    __asm
    {
        bsr             eax, dword ptr bits
    }
}

__inline        s32
                FirstOne64(u64 bits)
{
    __asm
    {
        mov edx, 32
        mov eax, 32
        bsf edx, dword ptr bits
        bsf eax, dword ptr bits + 4
        mov edx, [mulBy33 + edx * 4]
        movzx eax, [firstBit + edx + eax]
    }
}

__inline        s32
                LastOne64(u64 bits)
{
    __asm
    {
        mov edx, 32
        mov eax, 32
        bsr eax, dword ptr bits
        bsr edx, dword ptr bits + 4
        mov edx, [mulBy33 + edx * 4]
        movzx eax, [lastBit + edx + eax]
    }
}

void            PrintBoard()
{
    s32             ps;
    s32             fs;
    s32             i;
    u08             pieces[] = "PNBRQKpnbrqk.?";

    for (ps = 63; ps >= 0; ps--) {
        fs = 7 - (ps & 7) + (ps >> 3) * 8;
        i = board[fs];
        i = piece[i].typ;
        if (i > 13)
            i = 13;
        printf(" %c ", pieces[i]);
        if ((ps & 7) == 0)
            printf("\n");
    }
    printf("\n");
}

void            Convert()
{
    sprintf(cmd, "%c%d%c%d", (fs & 7) + 'a', (fs >> 3) + 1, (ts & 7) + 'a', (ts >> 3) + 1);

}

void            Wperf()
{
    u32             pieces;
    s32             id;
    u64             tosqs;

    if (MoveGen() == ERROR) {
        nodes--;
        return;
    }
    pieces = whitePieces;
    while (pieces && depth) {
        id = FirstOne32(pieces);
        pieces &= mask32c[id];
        tosqs = hist[ply].captures[id] | hist[ply].moves[id];
        while (tosqs) {
            fs = piece[id].sq;
            ts = FirstOne64(tosqs);
            tosqs &= mask64c[ts];
            if (depth == 1) {
                MakeMove();
                TakeBack();
            } else {
                MakeMove();
                depth--;
                Bperf();
                TakeBack();
                depth++;
            }
        }
    }
}

void            Bperf()
{
    u32             pieces;
    s32             id;
    u64             tosqs;

    if (MoveGen() == ERROR) {
        nodes--;
        return;
    }
    pieces = blackPieces;
    while (pieces && depth) {
        id = FirstOne32(pieces);
        pieces &= mask32c[id];
        tosqs = hist[ply].captures[id] | hist[ply].moves[id];
        while (tosqs) {
            fs = piece[id].sq;
            ts = FirstOne64(tosqs);
            tosqs &= mask64c[ts];
            if (depth == 1) {
                MakeMove();
                TakeBack();
            } else {
                MakeMove();
                depth--;
                Wperf();
                TakeBack();
                depth++;
            }
        }
    }
}
/*
 r  n  b  q  k  b  n  r
 p  p  p  p  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  P  P  P  P
 R  N  B  Q  K  B  N  R

a2a3 a2a4 b2b3 b2b4 c2c3 c2c4 d2d3 d2d4 e2e3 e2e4 f2f3 f2f4 g2g3 g2g4 h2h3 h2h4 b1a3 b1c3 g1f3 g1h3
White1> perft 6
Nodes = 125039194,  msec. = 13578, nps = 9208955.22
 r  n  b  q  k  b  n  r
 p  p  p  p  p  p  p  p
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 P  P  P  P  P  P  P  P
 R  N  B  Q  K  B  N  R

a2a3 a2a4 b2b3 b2b4 c2c3 c2c4 d2d3 d2d4 e2e3 e2e4 f2f3 f2f4 g2g3 g2g4 h2h3 h2h4 b1a3 b1c3 g1f3 g1h3
White1>
*/


Thanks for the conformation Dann!

The FirstOne64 and LastOne64 functions are slow compared to the Crafty style ones, even though they are branchless. I think that making the data lookup 32 bit instead of 8 bit may make a difference as that will avoid move with zero extend, which I have read is slower. Just going to the Crafty style ones gives a nice boost in speed, but I forget how much.

This might be even messier, but once I run this after each move, I get three pieces of information; pinned pieces, possible checks by discovery, and all distance checks. RookAttacks() and BishopAttacks() are just functions that (for now) call Rmagic() and Bmagic().

Code: Select all

void Board::UpdatePinsDiscoveries()
{
   U64 sliders, pin_ray, poss_pin;
   int from;

   if (WTM) {
      sliders = (RookAttacks(WhiteKing, 0) & (BlackQueens | BlackRooks))
        | (BishopAttacks(WhiteKing, 0) & (BlackQueens | BlackBishops));

      // Iterate through the potential pinners
      while (sliders) {
        from = PopLSB(sliders);
        pin_ray = SquaresBetween(from, WhiteKing);
        poss_pin = pin_ray & Occupancy;

        // No pieces between slider and king; check
        if (!poss_pin) {
          Status[Ply].in_check++;
          continue;
        }

        // Too many pieces in the way
        if ((poss_pin & (poss_pin - 1))) {
          continue;
        }

        // Found a pin
        if (poss_pin & WhiteOccupied) {
          Pins |= poss_pin;
          Pinned[PinIdx] = LSB(poss_pin);
          Pinners[PinIdx] = from;
          PinRay[PinIdx++] = pin_ray;
        }
        // Potential discovery check
        else {
          Discoveries |= poss_pin;
        }         
      }
   }
   else {
   ...
   }
}

Does this look efficient/is there anything you see that I could improve on?