I don't want to give up

TommyTC · Post by **TommyTC** » Tue Sep 29, 2020 8:47 pm

Mike Sherwin wrote: ↑Tue Sep 29, 2020 9:54 am
One Idea is to make a RootSearch() and just keep track of the best move as each move is searched. Seems far simpler than the way it is now. But, it upsets me a bit that it means undoing that clever code that you spent so much time on. Do you think it sounds like a good idea, though?

Hi Mike,

At this point in your project, your code is the "golden" code. Anything I write should be considered as "hints" or "suggestions" (although when I point out serious bugs, those should probably be considered "strong suggestions"

) I'm writing all my code as though it can be thrown away and I will always fit my changes to your code. For example, right now I have changes for "TOMDEBUG 4", "TOMDEBUG 5", and "TOMDEBUGB" when I build, but some of those "hints" aren't as important as what I've shown thus far.

Other than creating a chess engine, I don't know what features you plan on implementing and that's perfectly fine for now. You don't need to spend effort trying to explain it. Consider me as a "helper" looking over your shoulder as you do the work.

I'm not that familiar with chess engines, other than a few years ago when I went through the VICE tutorials on Youtube, and a couple decades ago when I briefly looked at Crafty source code. In general I lightly read the comments here at TalkChess. I also follow the threads at FishCooking, and I read the "issues" and "pull request" discussions for Stockfish at Github (usually with little real understanding!)

With that said, I *think* RootSearch is something that other chess engines use. I know it's not as simple as just doing an alpha-beta search and looking at the values returned for each move. The search on earlier moves greatly affects the value assigned to any "second best" move because of the alpha-beta cutoffs. Once a good move is found, the resulting moves are not evaluated for their real value as though that second move was played. You can currently see this with "TOMDEBUG 3", sd 5, and playing E2E4 D7D5 "go". It might show "Score: 0" for all the moves, but only the move played can be guaranteed to have an accurate score.

I am familiar with the concept of "iterative deepening" and was wondering if that is how you might want to proceed.

Kind Regards,
Tommy

Mike Sherwin · Post by **Mike Sherwin** » Tue Sep 29, 2020 10:48 pm

TommyTC wrote: ↑Tue Sep 29, 2020 8:47 pm
Mike Sherwin wrote: ↑Tue Sep 29, 2020 9:54 am
One Idea is to make a RootSearch() and just keep track of the best move as each move is searched. Seems far simpler than the way it is now. But, it upsets me a bit that it means undoing that clever code that you spent so much time on. Do you think it sounds like a good idea, though?
Hi Mike,

At this point in your project, your code is the "golden" code. Anything I write should be considered as "hints" or "suggestions" (although when I point out serious bugs, those should probably be considered "strong suggestions" ) I'm writing all my code as though it can be thrown away and I will always fit my changes to your code. For example, right now I have changes for "TOMDEBUG 4", "TOMDEBUG 5", and "TOMDEBUGB" when I build, but some of those "hints" aren't as important as what I've shown thus far.

Other than creating a chess engine, I don't know what features you plan on implementing and that's perfectly fine for now. You don't need to spend effort trying to explain it. Consider me as a "helper" looking over your shoulder as you do the work.

I'm not that familiar with chess engines, other than a few years ago when I went through the VICE tutorials on Youtube, and a couple decades ago when I briefly looked at Crafty source code. In general I lightly read the comments here at TalkChess. I also follow the threads at FishCooking, and I read the "issues" and "pull request" discussions for Stockfish at Github (usually with little real understanding!)

With that said, I *think* RootSearch is something that other chess engines use. I know it's not as simple as just doing an alpha-beta search and looking at the values returned for each move. The search on earlier moves greatly affects the value assigned to any "second best" move because of the alpha-beta cutoffs. Once a good move is found, the resulting moves are not evaluated for their real value as though that second move was played. You can currently see this with "TOMDEBUG 3", sd 5, and playing E2E4 D7D5 "go". It might show "Score: 0" for all the moves, but only the move played can be guaranteed to have an accurate score.

I am familiar with the concept of "iterative deepening" and was wondering if that is how you might want to proceed.

Kind Regards,
Tommy

Hi Tommy,

Iterative deepening is on my todo list. I seem to remember that it is necessary to implement principle variation search. But, without a triangular array or hash tables to get the best move iterative deepening is only good for time management.

I found an en-passant bug but fixing it is complicated. In RomiChess there is a history structure with a move stack but unlike Bric the game moves are stored at the base of the move stack and ply zero for the search is the game ply. I always hated that kludge so in bric the game move stack was separated out. Makes sense, since Bric will at sometime (if I live long enough) be multi threaded and having say 1 < n < infinity game move stacks would seem silly. But this causes a problem with en-passant. The ply is off by one. When entering the move the ep bit is stored at ply + 1 which is the next moves ply if in search. However, the entered move is not part of the search and a ep rank pawn looks at ply 0. Thus there is a misalignment. So my kludge for that is to (now I do not want to say as it looks totally bogus to me, LOL) before making the game move. That should work but the ep bit is getting destroyed somehow that I do not understand yet. This is what took me 20 hours for two days. And I really do not remember this very well. What I have posted about this bug is what I have reconstructed from my notes. If you have not watched the movie Memento you should--8.4/10 on IMDb. In the movie his short term memory loss was complete after 5 seconds. He made notes on his hands and arms to eventually solve the mystery. My memory works a little differently. For example if you say, "I had a peanut butter and jelly sandwich for lunch" and asked me to repeat it back, I could. But if you were to say it in Dutch then I could not repeat it back. We could do this 100 times or 10,000 times, it would not matter, I will never be able to repeat it back. That is why I like C and not C++. And still in C there are many things I have to relearn every day before I can implement something. Assembler is my favorite language because I can write a complete search and use not even a dozen different mnemonics, that are short and descriptive enough for me to remember. Enough babble, time to get to work.

THANKS!
Mike

Mike Sherwin · Post by **Mike Sherwin** » Wed Sep 30, 2020 12:11 am

So after talking about peanut butter and jelly sandwiches I had to have one, lol. I should eat them more often as the solution to the ep problem just occurred to me.

Code: Select all

void GetCmd(Thread* t) {
  s32 match, i, fs, ts;
  u64 n, epbit; // <-
  char data[256], mvstr[20];

  match = false;
  epbit = epbb[1]; // <-

  PrintBoard(t);

  fgets(data, 256, stdin);
  _strlwr_s(data);

  std::cout << std::endl;

  if (data[0] >= 'a' && data[0] <= 'h' &&
      data[1] >= '1' && data[1] <= '8' &&
      data[2] >= 'a' && data[2] <= 'h' &&
      data[3] >= '1' && data[3] <= '8') {
    epbb[0] = epbit; // <-
    n = GenMoves(t, &move[0]);
    for (i = OO; i < n; i++) {
      fs = move[i].fs;
      ts = move[i].ts;
      sprintf_s(mvstr, 20, "%c%d%c%d\n", (fs & 7) + 'a', (fs >> 3) + 1, (ts & 7) + 'a', (ts >> 3) + 1);
      if (!strcmp(data, mvstr)) {
        gameMoves[gamePly].fs = fs;
        gameMoves[gamePly].ts = ts;
        gameMoves[gamePly].type = move[i].type;
        MakeMove(t, &gameMoves[gamePly]);
        epbb[0] = epbit; // <-
        gamePly++;
        ply--;
        return;
      }
    }
    return;
  }

  if (!strcmp(data, "go\n")) {
    bricabrac = BRICABRAC;
    return;
  }

  if (!strcmp(data, "u\n") || !strcmp(data, "undo\n")) {
    gamePly--;
    ply++;
    TakeBack(t, &gameMoves[gamePly]);
    return;
  }

}

Now when e2e4, g8h6; e4e5; d7d5 is played then e5d6 works as it should. OMG, I could have saved two long days of work if I'd first just had a peanut butter and jelly sandwich.

Mike Sherwin · Post by **Mike Sherwin** » Wed Sep 30, 2020 1:49 am

Wow! That peanut butter really did miracles.

Because a silent minority may be following this and it is not on Github yet I'll post the full code. I'll try to enumerate the changes below.

Code: Select all

// Bricabrac
// A chess engine by Michael J Sherwin
// TommyTC - Chief problem solver,bug squisher and ex honorary co-author
// Sven Schule - some bugs found
// HGM - help with branchless code

#include <intrin.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

#define TOMDEBUGA 2

#define equates 1
#ifdef equates
typedef signed char s08;
typedef unsigned char u08;
typedef int s32;
typedef unsigned long u32;
typedef long long s64;
typedef unsigned long long u64;

constexpr auto one = 1ull;
constexpr auto INF = 0x7fff;
constexpr auto STOP = INF;
constexpr auto ColA = 0;
constexpr auto Row8 = 7;
constexpr auto ILLEGAL = 0x8000;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 1600;
constexpr auto Vq = 800;
constexpr auto Vn = 200;
constexpr auto Vr = 400;
constexpr auto Vb = 200;
constexpr auto WOCCS = 0x0000000000000060;
constexpr auto WOCCL = 0x000000000000000e;
constexpr auto BOCCS = 0x6000000000000000;
constexpr auto BOCCL = 0x0e00000000000000;
constexpr auto WATKS = 0x0000000000000070;
constexpr auto WATKL = 0x000000000000001c;
constexpr auto BATKS = 0x7000000000000000;
constexpr auto BATKL = 0x1c00000000000000;

enum { BLACK, WHITE };

enum { B, R, N, Q };

enum {
  OO, WP, WN, WB, WR, WRC, WQ, WK, WC, BP, BN, BB, BR, BRC, BQ, BK, BC,
  Wd, We, Wb, Wr, Wn, Wq, Bd, Be, Bb, Br, Bn, Bq, WS, WL, BS, BL
};

enum { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };

enum {
  A1, B1, C1, D1, E1, F1, G1, H1,
  A2, B2, C2, D2, E2, F2, G2, H2,
  A3, B3, C3, D3, E3, F3, G3, H3,
  A4, B4, C4, D4, E4, F4, G4, H4,
  A5, B5, C5, D5, E5, F5, G5, H5,
  A6, B6, C6, D6, E6, F6, G6, H6,
  A7, B7, C7, D7, E7, F7, G7, H7,
  A8, B8, C8, D8, E8, F8, G8, H8
};

enum { EXIT, GETCMD, BRICABRAC, MOVE };
#endif 

#define definitions 1
#ifdef definitions
struct Move {
  s32 fs;
  s32 ts;
  s32 type;
  s32 score;
  s32 order; // TommyTC
  s32 wstats;
  s32 bstats;
  s32 status;
};

struct Thread {
  s32 wtm;
  s32 ply;
  s32 start;
  s32 mat[2];
  s32 board[64];
  u64 piece[2];
  u64 king[2];
  u64 epbb[100];
  s32 fifty[100];
  Move move[10000];
};

#define wtm t->wtm
#define ply t->ply
#define fifty t->fifty
#define start t->start
#define mat t->mat
#define board t->board
#define piece t->piece
#define king t->king
#define epbb t->epbb
#define move t->move
#endif

#define variables 1
#ifdef variables
Thread thread;
Thread* t;
s32 bricabrac;
s32 gamePly;
s32 sd;

u64 wPawnMoves[64];
u64 wPawnCapts[64];
u64 bPawnMoves[64];
u64 bPawnCapts[64];
u64 knightMoves[64];
u64 kingMoves[64];

u64 qss[64][256][8];
u64 bob[64];
u64 rob[64];

u64 above[65];
u64 below[65];

Move gameMoves[1000];

s32 value[] = { OO, VP, VN, VB, VR, VR, VQ, VK, VK, VP, VN, VB, VR, VR, VQ, VK, VK,
                Vb, Vr, Vn, Vq, Vb, Vr, Vn, Vq };

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

#endif

void PrintBoard(Thread* t) {
  s32 x, y, sq, pce;

  u08 fig[] = { ".PNBRRQKKpnbrrqkk" };

  for (y = 7; y >= 0; y--) {
    for (x = 0; x < 8; x++) {
      sq = ((y << 3) + x);
      pce = board[sq];
      std::cout << "  " << fig[pce];
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;
}

s32 LoadFen(Thread* t, u08* f) {
  s32 row, col, sq, fs, pce;

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

  col = ColA;
  row = Row8;
  fs = 56;

  mat[WHITE] = OO;
  mat[BLACK] = OO;
  piece[WHITE] = OO;
  piece[BLACK] = OO;

  for (;; f++) {
    if (*f == ' ') break;
    switch (*f) {
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
      col += *f - '0';
      fs = (row * 8 + col) & 63;
      continue;
    case '/':
      col = ColA;
      row--;
      fs = (row * 8 + col) & 63;
      continue;
    case 'P':
      pce = WP;
      mat[WHITE] += VP;
      piece[WHITE] ^= one << fs;
      break;
    case 'N':
      pce = WN;
      mat[WHITE] += VN;
      piece[WHITE] ^= one << fs;
      break;
    case 'B':
      pce = WB;
      mat[WHITE] += VB;
      piece[WHITE] ^= one << fs;
      break;
    case 'R':
      pce = WR;
      mat[WHITE] += VR;
      piece[WHITE] ^= one << fs;
      break;
    case 'Q':
      pce = WQ;
      mat[WHITE] += VQ;
      piece[WHITE] ^= one << fs;
      break;
    case 'K':
      pce = WK;
      piece[WHITE] ^= one << fs;
      king[WHITE] = one << fs;
      break;
    case 'p':
      pce = BP;
      mat[BLACK] += VP;
      piece[BLACK] ^= one << fs;
      break;
    case 'n':
      pce = BN;
      mat[BLACK] += VN;
      piece[BLACK] ^= one << fs;
      break;
    case 'b':
      pce = BB;
      mat[BLACK] += VB;
      piece[BLACK] ^= one << fs;
      break;
    case 'r':
      pce = BR;
      mat[BLACK] += VR;
      piece[BLACK] ^= one << fs;
      break;
    case 'q':
      pce = BQ;
      mat[BLACK] += VQ;
      piece[BLACK] ^= one << fs;
      break;
    case 'k':
      pce = BK;
      piece[BLACK] ^= one << fs;
      king[BLACK] = one << fs;
      break;
    default:
      return false;
    }
    board[fs] = pce;
    col++;
    fs = (row * 8 + col) & 63;
  }
  f++;
  switch (*f++) {
  case 'w':
    wtm = WHITE;
    break;
  case 'b':
    wtm = BLACK;
    break;
  default:
    return false;
  }
  if (*f++ != ' ') return false;
  if (*f == '-') {
    f++;
    if (*f++ != ' ') return false;
  }
  else {
    for (;;) {
      if (*f == ' ') {
        f++;
        break;
      }
      switch (*f++) {
      case 'K':
        board[E1] = WC;
        board[H1] = WRC;
        break;
      case 'Q':
        board[E1] = WC;
        board[A1] = WRC;
        break;
      case 'k':
        board[E8] = BC;
        board[H8] = BRC;
        break;
      case 'q':
        board[E8] = BC;
        board[A8] = BRC;
        break;
      default:
        return false;
      }
    }
  }
  epbb[OO] = OO;
  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';
    epbb[OO] = one << (row * 8 + col);
    f += 2;
  }
  if (*f++ != ' ') return false;
  fifty[OO] = OO;
  for (;;) {
    if (!isdigit(*f)) break;
    fifty[OO] *= 10;
    fifty[OO] += *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;
}

void MakeMove(Thread* t, Move* m) {
  s32 ctype = 0, sq;

  board[m->fs] = OO;
  piece[wtm] ^= one << m->fs;
  piece[wtm] ^= one << m->ts;

  switch (m->type) {
  case OO: break;
  case WP:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WP;
    break;
  case WN:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WN;
    break;
  case WB:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WB;
    break;
  case WR:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WR;
    break;
  case WRC:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WR;
    break;
  case WQ:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WQ;
    break;
  case WK:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WK;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    break;
  case WC:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WK;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    break;
  case BP:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BP;
    break;
  case BN:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BN;
    break;
  case BB:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BB;
    break;
  case BR:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BR;
    break;
  case BRC:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BR;
    break;
  case BQ:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BQ;
    break;
  case BK:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BK;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    break;
  case BC:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BK;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    break;
  case Wd:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WP;
    epbb[ply + 1] = (u64)(m->fs + 16 == m->ts) << (m->fs + 8);
    break;
  case We:
    sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
    ctype = board[sq];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << sq;
    board[sq] = OO;
    board[m->ts] = WP;
    break;
  case Wb:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WB;
    mat[WHITE] += 200;
    break;
  case Wr:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WR;
    mat[WHITE] += 400;
    break;
  case Wn:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WN;
    mat[WHITE] += 200;
    break;
  case Wq:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WQ;
    mat[WHITE] += 800;
    break;
  case Bd:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BP;
    epbb[ply + 1] = (u64)(m->fs - 16 == m->ts) << (m->fs - 8);
    break;
  case Be:
    sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
    ctype = board[sq];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << sq;
    board[sq] = OO;
    board[m->ts] = BP;
    break;
  case Bb:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BB;
    mat[BLACK] += 200;
    break;
  case Br:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BR;
    mat[BLACK] += 400;
    break;
  case Bn:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BN;
    mat[BLACK] += 200;
    break;
  case Bq:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BQ;
    mat[BLACK] += 800;
    break;
  case WS:
    ctype = OO;
    board[G1] = WK;
    board[H1] = OO;
    board[F1] = WR;
    king[WHITE] ^= one << E1;
    king[WHITE] ^= one << G1;
    piece[WHITE] ^= one << H1;
    piece[WHITE] ^= one << F1;
    break;
  case WL:
    ctype = OO;
    board[C1] = WK;
    board[A1] = OO;
    board[D1] = WR;
    king[WHITE] ^= one << E1;
    king[WHITE] ^= one << C1;
    piece[WHITE] ^= one << A1;
    piece[WHITE] ^= one << D1;
    break;
  case BS:
    ctype = OO;
    board[G8] = BK;
    board[H8] = OO;
    board[F8] = BR;
    king[BLACK] ^= one << E8;
    king[BLACK] ^= one << G8;
    piece[BLACK] ^= one << H8;
    piece[BLACK] ^= one << F8;
    break;
  case BL:
    ctype = OO;
    board[C8] = BK;
    board[A8] = OO;
    board[D8] = BR;
    king[BLACK] ^= one << E8;
    king[BLACK] ^= one << C8;
    piece[BLACK] ^= one << A8;
    piece[BLACK] ^= one << D8;
    break;
  }
  m->type |= ctype << 6;
  wtm = 1 - wtm;
  ply++;
}

void TakeBack(Thread* t, Move* m) {
  s32 ctype, sq;

  ply--;
  wtm = 1 - wtm;

  piece[wtm] ^= one << m->ts;
  piece[wtm] ^= one << m->fs;
  ctype = m->type >> 6;
  mat[1 - wtm] += value[ctype];
  m->type &= 0x3f;

  switch (m->type) {
  case OO: break;
  case WP:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WN:
    board[m->ts] = ctype;
    board[m->fs] = WN;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WB:
    board[m->ts] = ctype;
    board[m->fs] = WB;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WR:
    board[m->ts] = ctype;
    board[m->fs] = WR;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WRC:
    board[m->ts] = ctype;
    board[m->fs] = WRC;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WQ:
    board[m->ts] = ctype;
    board[m->fs] = WQ;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WK:
    board[m->ts] = ctype;
    board[m->fs] = WK;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WC:
    board[m->ts] = ctype;
    board[m->fs] = WC;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BP:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BN:
    board[m->ts] = ctype;
    board[m->fs] = BN;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BB:
    board[m->ts] = ctype;
    board[m->fs] = BB;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BR:
    board[m->ts] = ctype;
    board[m->fs] = BR;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BRC:
    board[m->ts] = ctype;
    board[m->fs] = BRC;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BQ:
    board[m->ts] = ctype;
    board[m->fs] = BQ;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BK:
    board[m->ts] = ctype;
    board[m->fs] = BK;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BC:
    board[m->ts] = ctype;
    board[m->fs] = BC;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wd:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    epbb[ply + 1] = OO;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case We:
    sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
    board[m->ts] = OO;
    board[sq] = ctype;
    piece[BLACK] ^= (u64)(ctype != OO) << sq;
    board[m->fs] = WP;
    break;
  case Wb:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 200;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wr:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 400;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wn:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 200;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wq:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 800;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Bd:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    epbb[ply + 1] = OO;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Be:
    sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
    board[m->ts] = OO;
    board[sq] = ctype;
    piece[WHITE] ^= (u64)(ctype != OO) << sq;
    board[m->fs] = BP;
    break;
  case Bb:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 200;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Br:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 400;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Bn:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 200;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Bq:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 800;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WS:
    board[G1] = OO;
    board[E1] = WC;
    board[H1] = WRC;
    board[F1] = OO;
    king[WHITE] ^= one << G1;
    king[WHITE] ^= one << E1;
    piece[WHITE] ^= one << H1;
    piece[WHITE] ^= one << F1;
    break;
  case WL:
    board[C1] = OO;
    board[E1] = WC;
    board[A1] = WRC;
    board[D1] = OO;
    king[WHITE] ^= one << C1;
    king[WHITE] ^= one << E1;
    piece[WHITE] ^= one << A1;
    piece[WHITE] ^= one << D1;
    break;
  case BS:
    board[G8] = OO;
    board[E8] = BC;
    board[H8] = BRC;
    board[F8] = OO;
    king[BLACK] ^= one << G8;
    king[BLACK] ^= one << E8;
    piece[BLACK] ^= one << H8;
    piece[BLACK] ^= one << F8;
    break;
  case BL:
    board[C8] = OO;
    board[E8] = BC;
    board[A8] = BRC;
    board[D8] = OO;
    king[BLACK] ^= one << C8;
    king[BLACK] ^= one << E8;
    piece[BLACK] ^= one << A8;
    piece[BLACK] ^= one << D8;
    break;
  }
}

s32 AtkByWhite(Thread* t, u64 bb) {
  u32 ts, fs;
  u64 b, aPieces = piece[WHITE] | piece[BLACK];
  do {
    _BitScanForward64(&ts, bb);
    bb ^= one << ts;
    b = bPawnCapts[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WP) return true;
    }
    b = knightMoves[ts] & piece[WHITE];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WN) return true;
    }
    b = kingMoves[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WK) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & bob[ts]
      & piece[WHITE];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WB || board[fs] == WQ) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & rob[ts]
      & piece[WHITE];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WR || board[fs] == WQ) return true;
    }
  } while (bb);
  return false;
}

s32 AtkByBlack(Thread* t, u64 bb) {
  u32 ts, fs;
  u64 b, aPieces = piece[WHITE] | piece[BLACK];
  do {
    _BitScanForward64(&ts, bb);
    bb ^= one << ts;
    b = wPawnCapts[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BP) return true;
    }
    b = knightMoves[ts] & piece[BLACK];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BN) return true;
    }
    b = kingMoves[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BK) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & bob[ts]
      & piece[BLACK];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BB || board[fs] == BQ) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & rob[ts]
      & piece[BLACK];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BR || board[fs] == BQ) return true;
    }
  } while (bb);
  return false;
}

__forceinline s32 Sort(Thread* t, Move* m) {
  s32 i, mi = 0, high = -INF;
  Move* mov;
  for (i = 0; (m + i)->status != STOP; i++) {
    mov = m + i;
    if (mov->status == false && mov->score > high) {
      high = mov->score;
      mi = i;
    }
  }
  (m + mi)->status = true;
  return mi;
}

__forceinline s32 Qsort(Thread* t, Move* m, s32 n) {
  s32 i = 0, high = -INF;
  Move* mov;
  for (; n > OO; n--) {
    mov = m - n;
    if (!mov->status && mov->score > high) {
      high = mov->score;
      i = n;
    }
  }
  (m - i)->status = true;
  return i;
}

s32 Qsearch(Thread* t, Move* m, s32 alpha, s32 beta) {
  s32 n, i, mi, type, score;
  u32 fs, ts;
  u64 bb, captures, pieces, aPieces, enemy, empty;
  Move* mov;

  score = mat[wtm] - mat[1 - wtm];

  if (score >= beta) return beta;
  if (score > alpha) alpha = score;

  n = 0;
  bb = 0;
  captures = 0;

  pieces = piece[wtm];
  aPieces = piece[BLACK] | piece[WHITE];
  enemy = aPieces ^ pieces;
  empty = 0xffffffffffffffff ^ aPieces;

  do {
    _BitScanForward64(&fs, pieces);
    pieces ^= one << fs;
    type = board[fs];
    switch (type) {
    case OO: break;
    case WP:
      switch (fs >> 3) {
      case RANK1: break;
      case RANK2:
      case RANK3:
      case RANK4:
      case RANK6:
        bb = wPawnCapts[fs] & enemy;
        break;
      case RANK5:
        bb = wPawnCapts[fs] & (enemy | epbb[ply]);
        type = We;
        break;
      case RANK7:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return -ILLEGAL;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Wb + i;
            m->score = (value[board[ts]] << 4) + value[m->type];
            m->status = false;
            m++;
          }
          n += 4;
        }
        continue;
      }
      break;
    case WN:
    case BN:
      bb = knightMoves[fs] & enemy;
      break;
    case WB:
    case BB:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & bob[fs]
        & enemy;
      break;
    case WR:
    case WRC:
    case BR:
    case BRC:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & rob[fs]
        & enemy;
      break;
    case WQ:
    case BQ:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & enemy;
      break;
    case WK:
    case BK:
    case WC:
    case BC:
      bb = kingMoves[fs] & enemy;
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return -ILLEGAL;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Bb + i;
            m->score = (value[board[ts]] << 4) + value[m->type];
            m->status = false;
            m++;
          }
          n += 4;
        }
        continue;
      case RANK3:
      case RANK5:
      case RANK6:
      case RANK7:
        bb = bPawnCapts[fs] & enemy;
        break;
      case RANK4:
        bb = bPawnCapts[fs] & (enemy | epbb[ply]);
        type = Be;
        break;
      }
      break;
    }

    captures |= bb;

    while (bb) {
      _BitScanForward64(&ts, bb);
      bb ^= one << ts;
      m->fs = (s32)fs;
      m->ts = (s32)ts;
      m->type = type;
      m->score = (value[board[ts]] << 4) - value[m->type];
      m->status = false;
      m++;
      n++;
    }

  } while (pieces);

  if (captures & king[1 - wtm]) return -ILLEGAL;

  for (i = n; i > OO; i--) {
    mi = Qsort(t, m, n);
    mov = (m - mi);
    MakeMove(t, mov);
    mov->score = -Qsearch(t, m, -beta, -alpha);
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score > alpha) {
      if (mov->score >= beta) {
        return beta;
      }
      alpha = mov->score;
    }
  }
  return alpha;
}

u64 GenMoves(Thread* t, Move* m) {
  s32 i, type, score = -INF;
  u32 fs, ts, sq;
  u64 bb = 0, captures = 0;
  Move* n = m;

  u64 pieces = piece[wtm];
  u64 aPieces = piece[BLACK] | piece[WHITE];
  u64 enemy = aPieces ^ pieces;
  u64 empty = 0xffffffffffffffff ^ aPieces;
  u64 notme = 0xffffffffffffffff ^ pieces;

  do {
    _BitScanForward64(&fs, pieces);
    pieces ^= one << fs;
    type = board[fs];
    switch (type) {
    case OO:
      break;
    case WP:
      switch (fs >> 3) {
      case RANK1: break;
      case RANK2:
        _BitScanForward64(&sq, wPawnMoves[fs] & aPieces);
        bb = (wPawnMoves[fs] & below[sq]) | (wPawnCapts[fs] & enemy);
        type = Wd;
        break;
      case RANK3:
      case RANK4:
      case RANK6:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
        break;
      case RANK5:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & (enemy | epbb[ply]));
        type = We;
        break;
      case RANK7:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return OO;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Wb + i;
            m->score = (value[board[m->ts]] << 4) - VP;
            m->status = false;
            m++;
          }
        }
        continue;
      }
      break;
    case WN:
    case BN:
      bb = knightMoves[fs] & notme;
      break;
    case WB:
    case BB:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & bob[fs]
        & notme;
      break;
    case WR:
    case WRC:
    case BR:
    case BRC:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & rob[fs]
        & notme;
      break;
    case WQ:
    case BQ:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & notme;
      break;
    case WK:
    case BK:
      bb = kingMoves[fs] & notme;
      break;
    case WC:
      bb = kingMoves[fs] & notme;
      if (board[H1] == WRC && !(WOCCS & aPieces) && !AtkByBlack(t, WATKS)) {
        m->fs = E1;
        m->ts = G1;
        m->type = WS;
        m->score = 1000;
        m->status = false;
        m++;
      }
      if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
        m->fs = E1;
        m->ts = C1;
        m->type = WL;
        m->score = 1000;
        m->status = false;
        m++;
      }
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return OO;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Bb + i;
            m->score = (value[board[m->ts]] << 4) - VP;
            m->status = false;
            m++;
          }
        }
        continue;
      case RANK3:
      case RANK5:
      case RANK6:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        break;
      case RANK4:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & (enemy | epbb[ply]));
        type = Be;
        break;
      case RANK7:
        _BitScanReverse64(&sq, bPawnMoves[fs] & aPieces);
        bb = (bPawnMoves[fs] & above[sq]) | (bPawnCapts[fs] & enemy);
        type = Bd;
        break;
      }
      break;
    case BC:
      bb = kingMoves[fs] & notme;
      if (board[H8] == BRC && !(BOCCS & aPieces) && !AtkByWhite(t, BATKS)) {
        m->fs = E8;
        m->ts = G8;
        m->type = BS;
        m->score = 1000;
        m->status = false;
        m++;
      }
      if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
        m->fs = E8;
        m->ts = C8;
        m->type = BL;
        m->score = 1000;
        m->status = false;
        m++;
      }
      break;
    }

    captures |= bb;

    while (bb) {
      _BitScanForward64(&ts, bb);
      bb ^= one << ts;
      m->fs = (s32)fs;
      m->ts = (s32)ts;
      m->type = type;
      m->score = (value[board[m->ts]] << 4) - value[board[m->fs]];
      m->status = false;
      m++;
    }

  } while (pieces);

  if (captures & king[1 - wtm]) return OO;

  m->status = STOP;
  m++;

  return m - n;
}

s32 Search(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
  s32 i, mi;
  u64 n;
  Move* mov;

  n = GenMoves(t, m);

  if (!n) return -ILLEGAL;

  depth--;

  for (i = 0; (m + i)->status != STOP; i++) {
    mi = Sort(t, m);
    mov = m + mi;
    mov->order = i; // TommyTC
    MakeMove(t, mov);
    if (!depth) {
      mov->score = -Qsearch(t, m + n, -beta, -alpha);
    }
    else {
      // "TOMDEBUGA 0" Don't display positions during search
      // "TOMDEBUGA 1" Display "sd - 1" positions during search
      // "TOMDEBUGA 2" Display "sd - 1" and "sd - 2" positions during search

#if TOMDEBUGA > 0
      if (depth > (sd - 1 - TOMDEBUGA)) {
        printf("Depth: %i\n", depth);
        PrintBoard(t);
      }
#endif
      mov->score = -Search(t, m + n, -beta, -alpha, depth);
    }
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score >= beta) return beta;
    if (mov->score > alpha) alpha = mov->score;
  }
  return alpha;
}

void Bricabrac(Thread* t) {

  Search(t, &move[0], -INF, INF, sd);

  bricabrac = MOVE;
}

void GetCmd(Thread* t) {
  s32 match, i, fs, ts;
  u64 n, epbit;
  char data[256], mvstr[20];

  match = false;
  epbit = epbb[1];

  PrintBoard(t);

  fgets(data, 256, stdin);
  _strlwr_s(data);

  std::cout << std::endl;

  if (data[0] >= 'a' && data[0] <= 'h' &&
      data[1] >= '1' && data[1] <= '8' &&
      data[2] >= 'a' && data[2] <= 'h' &&
      data[3] >= '1' && data[3] <= '8') {
    epbb[0] = epbit;
    n = GenMoves(t, &move[0]);
    for (i = OO; i < n; i++) {
      fs = move[i].fs;
      ts = move[i].ts;
      sprintf_s(mvstr, 20, "%c%d%c%d\n", (fs & 7) + 'a', (fs >> 3) + 1, (ts & 7) + 'a', (ts >> 3) + 1);
      if (!strcmp(data, mvstr)) {
        gameMoves[gamePly].fs = fs;
        gameMoves[gamePly].ts = ts;
        gameMoves[gamePly].type = move[i].type;
        MakeMove(t, &gameMoves[gamePly]);
        epbb[0] = epbit;
        gamePly++;
        ply--;
        return;
      }
    }
    return;
  }

  if (!strcmp(data, "go\n")) {
    bricabrac = BRICABRAC;
    return;
  }

  if (!strcmp(data, "u\n") || !strcmp(data, "undo\n")) {
    gamePly--;
    ply++;
    TakeBack(t, &gameMoves[gamePly]);
    return;
  }


}

void DoMove(Thread* t) {
  s32 i, j = 0, score;

  s32 PrevSearchOrder = 1000; // TommyTC

  score = -INF;

  for (i = 0; move[i].status != STOP; i++) {

    // TommyTC
    printf("%i: ", i);
    printf("%c%c", 'A' + (move[i].fs & 7), '1' + (move[i].fs >> 3));
    printf("%c%c", 'A' + (move[i].ts & 7), '1' + (move[i].ts >> 3));
    printf("  Score: %i  ", move[i].score);
    printf("order: %i\n", move[i].order);

    // TommyTC
    if (move[i].score != ILLEGAL) {
      if (move[i].score > score) {
        score = move[i].score;
        PrevSearchOrder = move[i].order;
        j = i;
      }
      else
      if (move[i].score == score && move[i].order < PrevSearchOrder) {
        PrevSearchOrder = move[i].order;
        j = i;
      }
    }
  }

  // TommyTC
  printf("\nMove Played: ");
  printf("%c%c", 'A' + (move[j].fs & 7), '1' + (move[j].fs >> 3));
  printf("%c%c\n", 'A' + (move[j].ts & 7), '1' + (move[j].ts >> 3));

  gameMoves[gamePly].fs = move[j].fs;
  gameMoves[gamePly].ts = move[j].ts;
  gameMoves[gamePly].type = move[j].type;
  MakeMove(t, &gameMoves[gamePly]);
  epbb[0] = epbb[1];

  ply--;
  gamePly++;
  bricabrac = GETCMD;
}

void InitializeQSS() {
  u08 sq, sqr, k, l;
  s08 x, y, dx, dy;
  s32 i;
  u64 b, bb;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    bob[sq] = 0;
    rob[sq] = 0;
    for (i = 0; i < 256; i++) {
      for (k = 0, l = 0; k <= 56; k += 8, l++) {
        bb = 0;
        b = (u64)i << k;
        for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1; x + dx > -1; dx--) {
          sqr = (y << 3) + x + dx;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = +1; x + dx < +8; dx++) {
          sqr = (y << 3) + x + dx;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dy = +1; y + dy < +8; dy++) {
          sqr = ((y + dy) << 3) + x;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dy = -1; y + dy > -1; dy--) {
          sqr = ((y + dy) << 3) + x;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        qss[sq][i][l] = bb;
      }
    }
  }
}

void InitializeRNK() {
  u08 sq, sqr, i;
  s08 x, y, dx, dy;
  u64 bb, b;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    for (i = 0; i < 128; i++) {
      bb = 0;
      b = (u64)i << (sq & 56);
      for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1; x + dx > -1; dx--) {
        sqr = (y << 3) + x + dx;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = +1; x + dx < +8; dx++) {
        sqr = (y << 3) + x + dx;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dy = +1; y + dy < +8; dy++) {
        sqr = ((y + dy) << 3) + x;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dy = -1; y + dy > -1; dy--) {
        sqr = ((y + dy) << 3) + x;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      qss[sq][i][0] = bb;
    }
  }
}

void InitPieceBB() {
  s32 sq, x, y;

  above[0] = 0xffffffffffffffff;
  below[0] = 0xffffffffffffffff;

  for (sq = A1; sq <= H8; sq++) {
    x = sq & 7;
    y = sq >> 3;

    above[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) ^ 1) << (sq + 1);
    below[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) << (sq + 1)) ^ 0xffffffffffffffff;

    wPawnMoves[sq] = 0;
    wPawnCapts[sq] = 0;
    bPawnMoves[sq] = 0;
    bPawnCapts[sq] = 0;
    if (sq > H1 && sq < A8) {
      // White Pawn Moves
      wPawnMoves[sq] |= one << (sq + 8);
      if (sq < A3) wPawnMoves[sq] |= one << (sq + 16);
      // White Pawn Captures
      if (x + 1 < +8) wPawnCapts[sq] |= one << (sq + 9);
      if (x - 1 > -1) wPawnCapts[sq] |= one << (sq + 7);
      // Black Pawn Moves
      bPawnMoves[sq] |= one << (sq - 8);
      if (sq > H6) bPawnMoves[sq] |= one << (sq - 16);
      // Black Pawn Captures
      if (x + 1 < +8) bPawnCapts[sq] |= one << (sq - 7);
      if (x - 1 > -1) bPawnCapts[sq] |= one << (sq - 9);
    }
    // Knight Moves
    knightMoves[sq] = 0;
    if (y + 2 < +8 && x + 1 < +8) knightMoves[sq] |= one << (sq + 17);
    if (y + 1 < +8 && x + 2 < +8) knightMoves[sq] |= one << (sq + 10);
    if (y - 1 > -1 && x + 2 < +8) knightMoves[sq] |= one << (sq - +6);
    if (y - 2 > -1 && x + 1 < +8) knightMoves[sq] |= one << (sq - 15);
    if (y - 2 > -1 && x - 1 > -1) knightMoves[sq] |= one << (sq - 17);
    if (y - 1 > -1 && x - 2 > -1) knightMoves[sq] |= one << (sq - 10);
    if (y + 1 < +8 && x - 2 > -1) knightMoves[sq] |= one << (sq + +6);
    if (y + 2 < +8 && x - 1 > -1) knightMoves[sq] |= one << (sq + 15);
    // King Moves
    kingMoves[sq] = 0;
    if (y + 1 < +8) kingMoves[sq] |= one << (sq + 8);
    if (y - 1 > -1) kingMoves[sq] |= one << (sq - 8);
    if (x + 1 < +8) kingMoves[sq] |= one << (sq + 1);
    if (x - 1 > -1) kingMoves[sq] |= one << (sq - 1);
    if (y + 1 < +8 && x + 1 < +8) kingMoves[sq] |= one << (sq + 9);
    if (y - 1 > -1 && x + 1 < +8) kingMoves[sq] |= one << (sq - 7);
    if (y - 1 > -1 && x - 1 > -1) kingMoves[sq] |= one << (sq - 9);
    if (y + 1 < +8 && x - 1 > -1) kingMoves[sq] |= one << (sq + 7);
  }
  InitializeQSS();
  InitializeRNK();
}

void NewGame(Thread* t) {
  LoadFen(t, startFen);
}

void Initialize() {
  bricabrac = GETCMD;
  gamePly = OO;
  wtm = WHITE;
  ply = OO;
  InitPieceBB();
  NewGame(t);
}

// TommyTC
void SetSearchDepth()
{
    char data[256];
    int x = 0;
    printf("Enter SEARCH DEPTH (sd): \n");
    fgets(data, 4, stdin);
    while ((data[x] >= '0') && (data[x] <= '9')) {
      sd = 10 * sd + (data[x++] - '0');
    }
}

s32 main() {

  printf("TOMDEBUG:  %i\n\n", 3);
  SetSearchDepth(); // TommyTC 

  t = &thread;

  Initialize();

  do {
    if (bricabrac == BRICABRAC) Bricabrac(t);
    if (bricabrac == MOVE) DoMove(t);
    GetCmd(t);
  } while (bricabrac);

  return 0;
}

With TOMDEBUG 2 searching sd = 5 e2e4 f7f5 e4f5 a7a6 f5f6 d7d6 f6f7 the black king is never missing from the printed board.
TOMDEBUG was removed and TOMDEBUG 3 is built in.
Line: Change
14 #define TOMDEBUGA 2
30 constexpr auto ILLEGAL = 0x8000;
36 constexpr auto VK = 1600;
979 in case RANK7, if (bb & king[1 - wtm]) return -ILLEGAL;
987 in case RANK7, m->score = (value[board[ts]] << 4) + value[m->type];
1049 in case RANK2, if (bb & king[1 - wtm]) return -ILLEGAL;
1057 in case RANK2, m->score = (value[board[ts]] << 4) + value[m->type];
1086 in While(bb), m->score = (value[board[ts]] << 4) - value[m->type];
1151 if (bb & king[1 - wtm]) return OO;
1159 m->score = (value[board[m->ts]] << 4) - VP;
1214 1226 m->score = 1000;
1237 if (bb & king[1 - wtm]) return OO;
1245 m->score = (value[board[m->ts]] << 4) - VP;
1273 1281 m->score = 1000;
1296 m->score = (value[board[m->ts]] << 4) - value[board[m->fs]];
1331- 1340
// "TOMDEBUGA 0" Don't display positions during search
// "TOMDEBUGA 1" Display "sd - 1" positions during search
// "TOMDEBUGA 2" Display "sd - 1" and "sd - 2" positions during search

#if TOMDEBUGA > 0
if (depth > (sd - 1 - TOMDEBUGA)) {
printf("Depth: %i\n", depth);
PrintBoard(t);
}
#endif
1360 u64 n, epbit;
1364 match = false; // after match = false;
1377 epbb[0] = epbit; // before n = GenMoves(t, &move[0]);
1388 epbb[0] = epbit; // after MakeMove
1452 epbb[0] = epbb[1]; // after MakeMove

Mike Sherwin · Post by **Mike Sherwin** » Wed Sep 30, 2020 2:49 am

RootSearch() was added and the best move is recorded in RootSearch(). It plays the exact same moves as the previous method. The reason it plays the same moves is that Alpha starts at -INF and as a move comes along that raises alpha it also records a new best move.

Here is my current working code.

Code: Select all

// Bricabrac
// A chess engine by Michael J Sherwin
// TommyTC - Chief problem solver,bug squisher and ex honorary co-author
// Sven Schule - some bugs found
// HGM - help with branchless code

#include <intrin.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

#define equates 1
#ifdef equates
typedef signed char s08;
typedef unsigned char u08;
typedef int s32;
typedef unsigned long u32;
typedef long long s64;
typedef unsigned long long u64;

constexpr auto one = 1ull;
constexpr auto INF = 0x7fff;
constexpr auto STOP = INF;
constexpr auto ColA = 0;
constexpr auto Row8 = 7;
constexpr auto ILLEGAL = 0x8000;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 1600;
constexpr auto Vq = 800;
constexpr auto Vn = 200;
constexpr auto Vr = 400;
constexpr auto Vb = 200;
constexpr auto WOCCS = 0x0000000000000060;
constexpr auto WOCCL = 0x000000000000000e;
constexpr auto BOCCS = 0x6000000000000000;
constexpr auto BOCCL = 0x0e00000000000000;
constexpr auto WATKS = 0x0000000000000070;
constexpr auto WATKL = 0x000000000000001c;
constexpr auto BATKS = 0x7000000000000000;
constexpr auto BATKL = 0x1c00000000000000;

enum { BLACK, WHITE };

enum { B, R, N, Q };

enum {
  OO, WP, WN, WB, WR, WRC, WQ, WK, WC, BP, BN, BB, BR, BRC, BQ, BK, BC,
  Wd, We, Wb, Wr, Wn, Wq, Bd, Be, Bb, Br, Bn, Bq, WS, WL, BS, BL
};

enum { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };

enum {
  A1, B1, C1, D1, E1, F1, G1, H1,
  A2, B2, C2, D2, E2, F2, G2, H2,
  A3, B3, C3, D3, E3, F3, G3, H3,
  A4, B4, C4, D4, E4, F4, G4, H4,
  A5, B5, C5, D5, E5, F5, G5, H5,
  A6, B6, C6, D6, E6, F6, G6, H6,
  A7, B7, C7, D7, E7, F7, G7, H7,
  A8, B8, C8, D8, E8, F8, G8, H8
};

enum { EXIT, GETCMD, BRICABRAC, MOVE };
#endif 

#define definitions 1
#ifdef definitions
struct Move {
  s32 fs;
  s32 ts;
  s32 type;
  s32 score;
  s32 wstats;
  s32 bstats;
  s32 status;
};

struct Thread {
  s32 wtm;
  s32 ply;
  s32 start;
  s32 mat[2];
  s32 board[64];
  u64 piece[2];
  u64 king[2];
  u64 epbb[100];
  s32 fifty[100];
  Move move[10000];
};

#define wtm t->wtm
#define ply t->ply
#define fifty t->fifty
#define start t->start
#define mat t->mat
#define board t->board
#define piece t->piece
#define king t->king
#define epbb t->epbb
#define move t->move
#endif

#define variables 1
#ifdef variables
Thread thread;
Thread* t;
s32 bricabrac;
s32 gamePly;
s32 sd;

u64 wPawnMoves[64];
u64 wPawnCapts[64];
u64 bPawnMoves[64];
u64 bPawnCapts[64];
u64 knightMoves[64];
u64 kingMoves[64];

u64 qss[64][256][8];
u64 bob[64];
u64 rob[64];

u64 above[65];
u64 below[65];

Move gameMoves[1000];
Move bestMove;

s32 value[] = { OO, VP, VN, VB, VR, VR, VQ, VK, VK, VP, VN, VB, VR, VR, VQ, VK, VK,
                Vb, Vr, Vn, Vq, Vb, Vr, Vn, Vq };

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

#endif

void PrintBoard(Thread* t) {
  s32 x, y, sq, pce;

  u08 fig[] = { ".PNBRRQKKpnbrrqkk" };

  for (y = 7; y >= 0; y--) {
    for (x = 0; x < 8; x++) {
      sq = ((y << 3) + x);
      pce = board[sq];
      std::cout << "  " << fig[pce];
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;
}

s32 LoadFen(Thread* t, u08* f) {
  s32 row, col, sq, fs, pce;

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

  col = ColA;
  row = Row8;
  fs = 56;

  mat[WHITE] = OO;
  mat[BLACK] = OO;
  piece[WHITE] = OO;
  piece[BLACK] = OO;

  for (;; f++) {
    if (*f == ' ') break;
    switch (*f) {
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
      col += *f - '0';
      fs = (row * 8 + col) & 63;
      continue;
    case '/':
      col = ColA;
      row--;
      fs = (row * 8 + col) & 63;
      continue;
    case 'P':
      pce = WP;
      mat[WHITE] += VP;
      piece[WHITE] ^= one << fs;
      break;
    case 'N':
      pce = WN;
      mat[WHITE] += VN;
      piece[WHITE] ^= one << fs;
      break;
    case 'B':
      pce = WB;
      mat[WHITE] += VB;
      piece[WHITE] ^= one << fs;
      break;
    case 'R':
      pce = WR;
      mat[WHITE] += VR;
      piece[WHITE] ^= one << fs;
      break;
    case 'Q':
      pce = WQ;
      mat[WHITE] += VQ;
      piece[WHITE] ^= one << fs;
      break;
    case 'K':
      pce = WK;
      piece[WHITE] ^= one << fs;
      king[WHITE] = one << fs;
      break;
    case 'p':
      pce = BP;
      mat[BLACK] += VP;
      piece[BLACK] ^= one << fs;
      break;
    case 'n':
      pce = BN;
      mat[BLACK] += VN;
      piece[BLACK] ^= one << fs;
      break;
    case 'b':
      pce = BB;
      mat[BLACK] += VB;
      piece[BLACK] ^= one << fs;
      break;
    case 'r':
      pce = BR;
      mat[BLACK] += VR;
      piece[BLACK] ^= one << fs;
      break;
    case 'q':
      pce = BQ;
      mat[BLACK] += VQ;
      piece[BLACK] ^= one << fs;
      break;
    case 'k':
      pce = BK;
      piece[BLACK] ^= one << fs;
      king[BLACK] = one << fs;
      break;
    default:
      return false;
    }
    board[fs] = pce;
    col++;
    fs = (row * 8 + col) & 63;
  }
  f++;
  switch (*f++) {
  case 'w':
    wtm = WHITE;
    break;
  case 'b':
    wtm = BLACK;
    break;
  default:
    return false;
  }
  if (*f++ != ' ') return false;
  if (*f == '-') {
    f++;
    if (*f++ != ' ') return false;
  }
  else {
    for (;;) {
      if (*f == ' ') {
        f++;
        break;
      }
      switch (*f++) {
      case 'K':
        board[E1] = WC;
        board[H1] = WRC;
        break;
      case 'Q':
        board[E1] = WC;
        board[A1] = WRC;
        break;
      case 'k':
        board[E8] = BC;
        board[H8] = BRC;
        break;
      case 'q':
        board[E8] = BC;
        board[A8] = BRC;
        break;
      default:
        return false;
      }
    }
  }
  epbb[OO] = OO;
  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';
    epbb[OO] = one << (row * 8 + col);
    f += 2;
  }
  if (*f++ != ' ') return false;
  fifty[OO] = OO;
  for (;;) {
    if (!isdigit(*f)) break;
    fifty[OO] *= 10;
    fifty[OO] += *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;
}

void MakeMove(Thread* t, Move* m) {
  s32 ctype = 0, sq;

  board[m->fs] = OO;
  piece[wtm] ^= one << m->fs;
  piece[wtm] ^= one << m->ts;

  switch (m->type) {
  case OO: break;
  case WP:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WP;
    break;
  case WN:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WN;
    break;
  case WB:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WB;
    break;
  case WR:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WR;
    break;
  case WRC:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WR;
    break;
  case WQ:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WQ;
    break;
  case WK:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WK;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    break;
  case WC:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WK;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    break;
  case BP:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BP;
    break;
  case BN:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BN;
    break;
  case BB:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BB;
    break;
  case BR:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BR;
    break;
  case BRC:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BR;
    break;
  case BQ:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BQ;
    break;
  case BK:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BK;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    break;
  case BC:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BK;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    break;
  case Wd:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WP;
    epbb[ply + 1] = (u64)(m->fs + 16 == m->ts) << (m->fs + 8);
    break;
  case We:
    sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
    ctype = board[sq];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << sq;
    board[sq] = OO;
    board[m->ts] = WP;
    break;
  case Wb:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WB;
    mat[WHITE] += 200;
    break;
  case Wr:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WR;
    mat[WHITE] += 400;
    break;
  case Wn:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WN;
    mat[WHITE] += 200;
    break;
  case Wq:
    ctype = board[m->ts];
    mat[BLACK] -= value[ctype];
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = WQ;
    mat[WHITE] += 800;
    break;
  case Bd:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BP;
    epbb[ply + 1] = (u64)(m->fs - 16 == m->ts) << (m->fs - 8);
    break;
  case Be:
    sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
    ctype = board[sq];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << sq;
    board[sq] = OO;
    board[m->ts] = BP;
    break;
  case Bb:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BB;
    mat[BLACK] += 200;
    break;
  case Br:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BR;
    mat[BLACK] += 400;
    break;
  case Bn:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BN;
    mat[BLACK] += 200;
    break;
  case Bq:
    ctype = board[m->ts];
    mat[WHITE] -= value[ctype];
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    board[m->ts] = BQ;
    mat[BLACK] += 800;
    break;
  case WS:
    ctype = OO;
    board[G1] = WK;
    board[H1] = OO;
    board[F1] = WR;
    king[WHITE] ^= one << E1;
    king[WHITE] ^= one << G1;
    piece[WHITE] ^= one << H1;
    piece[WHITE] ^= one << F1;
    break;
  case WL:
    ctype = OO;
    board[C1] = WK;
    board[A1] = OO;
    board[D1] = WR;
    king[WHITE] ^= one << E1;
    king[WHITE] ^= one << C1;
    piece[WHITE] ^= one << A1;
    piece[WHITE] ^= one << D1;
    break;
  case BS:
    ctype = OO;
    board[G8] = BK;
    board[H8] = OO;
    board[F8] = BR;
    king[BLACK] ^= one << E8;
    king[BLACK] ^= one << G8;
    piece[BLACK] ^= one << H8;
    piece[BLACK] ^= one << F8;
    break;
  case BL:
    ctype = OO;
    board[C8] = BK;
    board[A8] = OO;
    board[D8] = BR;
    king[BLACK] ^= one << E8;
    king[BLACK] ^= one << C8;
    piece[BLACK] ^= one << A8;
    piece[BLACK] ^= one << D8;
    break;
  }
  m->type |= ctype << 6;
  wtm = 1 - wtm;
  ply++;
}

void TakeBack(Thread* t, Move* m) {
  s32 ctype, sq;

  ply--;
  wtm = 1 - wtm;

  piece[wtm] ^= one << m->ts;
  piece[wtm] ^= one << m->fs;
  ctype = m->type >> 6;
  mat[1 - wtm] += value[ctype];
  m->type &= 0x3f;

  switch (m->type) {
  case OO: break;
  case WP:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WN:
    board[m->ts] = ctype;
    board[m->fs] = WN;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WB:
    board[m->ts] = ctype;
    board[m->fs] = WB;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WR:
    board[m->ts] = ctype;
    board[m->fs] = WR;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WRC:
    board[m->ts] = ctype;
    board[m->fs] = WRC;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WQ:
    board[m->ts] = ctype;
    board[m->fs] = WQ;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WK:
    board[m->ts] = ctype;
    board[m->fs] = WK;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WC:
    board[m->ts] = ctype;
    board[m->fs] = WC;
    king[WHITE] ^= one << m->fs;
    king[WHITE] ^= one << m->ts;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BP:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BN:
    board[m->ts] = ctype;
    board[m->fs] = BN;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BB:
    board[m->ts] = ctype;
    board[m->fs] = BB;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BR:
    board[m->ts] = ctype;
    board[m->fs] = BR;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BRC:
    board[m->ts] = ctype;
    board[m->fs] = BRC;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BQ:
    board[m->ts] = ctype;
    board[m->fs] = BQ;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BK:
    board[m->ts] = ctype;
    board[m->fs] = BK;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case BC:
    board[m->ts] = ctype;
    board[m->fs] = BC;
    king[BLACK] ^= one << m->fs;
    king[BLACK] ^= one << m->ts;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wd:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    epbb[ply + 1] = OO;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case We:
    sq = m->ts - ((epbb[ply] == (one << m->ts)) << 3);
    board[m->ts] = OO;
    board[sq] = ctype;
    piece[BLACK] ^= (u64)(ctype != OO) << sq;
    board[m->fs] = WP;
    break;
  case Wb:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 200;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wr:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 400;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wn:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 200;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Wq:
    board[m->ts] = ctype;
    board[m->fs] = WP;
    mat[WHITE] -= 800;
    piece[BLACK] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Bd:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    epbb[ply + 1] = OO;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Be:
    sq = m->ts + ((epbb[ply] == (one << m->ts)) << 3);
    board[m->ts] = OO;
    board[sq] = ctype;
    piece[WHITE] ^= (u64)(ctype != OO) << sq;
    board[m->fs] = BP;
    break;
  case Bb:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 200;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Br:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 400;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Bn:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 200;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case Bq:
    board[m->ts] = ctype;
    board[m->fs] = BP;
    mat[BLACK] -= 800;
    piece[WHITE] ^= (u64)(ctype != OO) << m->ts;
    break;
  case WS:
    board[G1] = OO;
    board[E1] = WC;
    board[H1] = WRC;
    board[F1] = OO;
    king[WHITE] ^= one << G1;
    king[WHITE] ^= one << E1;
    piece[WHITE] ^= one << H1;
    piece[WHITE] ^= one << F1;
    break;
  case WL:
    board[C1] = OO;
    board[E1] = WC;
    board[A1] = WRC;
    board[D1] = OO;
    king[WHITE] ^= one << C1;
    king[WHITE] ^= one << E1;
    piece[WHITE] ^= one << A1;
    piece[WHITE] ^= one << D1;
    break;
  case BS:
    board[G8] = OO;
    board[E8] = BC;
    board[H8] = BRC;
    board[F8] = OO;
    king[BLACK] ^= one << G8;
    king[BLACK] ^= one << E8;
    piece[BLACK] ^= one << H8;
    piece[BLACK] ^= one << F8;
    break;
  case BL:
    board[C8] = OO;
    board[E8] = BC;
    board[A8] = BRC;
    board[D8] = OO;
    king[BLACK] ^= one << C8;
    king[BLACK] ^= one << E8;
    piece[BLACK] ^= one << A8;
    piece[BLACK] ^= one << D8;
    break;
  }
}

s32 AtkByWhite(Thread* t, u64 bb) {
  u32 ts, fs;
  u64 b, aPieces = piece[WHITE] | piece[BLACK];
  do {
    _BitScanForward64(&ts, bb);
    bb ^= one << ts;
    b = bPawnCapts[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WP) return true;
    }
    b = knightMoves[ts] & piece[WHITE];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WN) return true;
    }
    b = kingMoves[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WK) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & bob[ts]
      & piece[WHITE];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WB || board[fs] == WQ) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & rob[ts]
      & piece[WHITE];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == WR || board[fs] == WQ) return true;
    }
  } while (bb);
  return false;
}

s32 AtkByBlack(Thread* t, u64 bb) {
  u32 ts, fs;
  u64 b, aPieces = piece[WHITE] | piece[BLACK];
  do {
    _BitScanForward64(&ts, bb);
    bb ^= one << ts;
    b = wPawnCapts[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BP) return true;
    }
    b = knightMoves[ts] & piece[BLACK];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BN) return true;
    }
    b = kingMoves[ts];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BK) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & bob[ts]
      & piece[BLACK];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BB || board[fs] == BQ) return true;
    }
    b = qss[ts][(aPieces >> (ts & 56)) & 127][0]
      & qss[ts][(aPieces >> 8) & 255][1]
      & qss[ts][(aPieces >> 16) & 255][2]
      & qss[ts][(aPieces >> 24) & 255][3]
      & qss[ts][(aPieces >> 32) & 255][4]
      & qss[ts][(aPieces >> 40) & 255][5]
      & qss[ts][(aPieces >> 48) & 255][6]
      & rob[ts]
      & piece[BLACK];
    while (b) {
      _BitScanForward64(&fs, b);
      b ^= one << fs;
      if (board[fs] == BR || board[fs] == BQ) return true;
    }
  } while (bb);
  return false;
}

__forceinline s32 Sort(Thread* t, Move* m) {
  s32 i, mi = 0, high = -INF;
  Move* mov;
  for (i = 0; (m + i)->status != STOP; i++) {
    mov = m + i;
    if (mov->status == false && mov->score > high) {
      high = mov->score;
      mi = i;
    }
  }
  (m + mi)->status = true;
  return mi;
}

__forceinline s32 Qsort(Thread* t, Move* m, s32 n) {
  s32 i = 0, high = -INF;
  Move* mov;
  for (; n > OO; n--) {
    mov = m - n;
    if (!mov->status && mov->score > high) {
      high = mov->score;
      i = n;
    }
  }
  (m - i)->status = true;
  return i;
}

s32 Qsearch(Thread* t, Move* m, s32 alpha, s32 beta) {
  s32 n, i, mi, type, score;
  u32 fs, ts;
  u64 bb, captures, pieces, aPieces, enemy, empty;
  Move* mov;

  score = mat[wtm] - mat[1 - wtm];

  if (score >= beta) return beta;
  if (score > alpha) alpha = score;

  n = 0;
  bb = 0;
  captures = 0;

  pieces = piece[wtm];
  aPieces = piece[BLACK] | piece[WHITE];
  enemy = aPieces ^ pieces;
  empty = 0xffffffffffffffff ^ aPieces;

  do {
    _BitScanForward64(&fs, pieces);
    pieces ^= one << fs;
    type = board[fs];
    switch (type) {
    case OO: break;
    case WP:
      switch (fs >> 3) {
      case RANK1: break;
      case RANK2:
      case RANK3:
      case RANK4:
      case RANK6:
        bb = wPawnCapts[fs] & enemy;
        break;
      case RANK5:
        bb = wPawnCapts[fs] & (enemy | epbb[ply]);
        type = We;
        break;
      case RANK7:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return -ILLEGAL;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Wb + i;
            m->score = (value[board[ts]] << 4) + value[m->type];
            m->status = false;
            m++;
          }
          n += 4;
        }
        continue;
      }
      break;
    case WN:
    case BN:
      bb = knightMoves[fs] & enemy;
      break;
    case WB:
    case BB:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & bob[fs]
        & enemy;
      break;
    case WR:
    case WRC:
    case BR:
    case BRC:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & rob[fs]
        & enemy;
      break;
    case WQ:
    case BQ:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & enemy;
      break;
    case WK:
    case BK:
    case WC:
    case BC:
      bb = kingMoves[fs] & enemy;
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return -ILLEGAL;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Bb + i;
            m->score = (value[board[ts]] << 4) + value[m->type];
            m->status = false;
            m++;
          }
          n += 4;
        }
        continue;
      case RANK3:
      case RANK5:
      case RANK6:
      case RANK7:
        bb = bPawnCapts[fs] & enemy;
        break;
      case RANK4:
        bb = bPawnCapts[fs] & (enemy | epbb[ply]);
        type = Be;
        break;
      }
      break;
    }

    captures |= bb;

    while (bb) {
      _BitScanForward64(&ts, bb);
      bb ^= one << ts;
      m->fs = (s32)fs;
      m->ts = (s32)ts;
      m->type = type;
      m->score = (value[board[ts]] << 4) - value[m->type];
      m->status = false;
      m++;
      n++;
    }

  } while (pieces);

  if (captures & king[1 - wtm]) return -ILLEGAL;

  for (i = n; i > OO; i--) {
    mi = Qsort(t, m, n);
    mov = (m - mi);
    MakeMove(t, mov);
    mov->score = -Qsearch(t, m, -beta, -alpha);
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score > alpha) {
      if (mov->score >= beta) {
        return beta;
      }
      alpha = mov->score;
    }
  }
  return alpha;
}

u64 GenMoves(Thread* t, Move* m) {
  s32 i, type, score = -INF;
  u32 fs, ts, sq;
  u64 bb = 0, captures = 0;
  Move* n = m;

  u64 pieces = piece[wtm];
  u64 aPieces = piece[BLACK] | piece[WHITE];
  u64 enemy = aPieces ^ pieces;
  u64 empty = 0xffffffffffffffff ^ aPieces;
  u64 notme = 0xffffffffffffffff ^ pieces;

  do {
    _BitScanForward64(&fs, pieces);
    pieces ^= one << fs;
    type = board[fs];
    switch (type) {
    case OO:
      break;
    case WP:
      switch (fs >> 3) {
      case RANK1: break;
      case RANK2:
        _BitScanForward64(&sq, wPawnMoves[fs] & aPieces);
        bb = (wPawnMoves[fs] & below[sq]) | (wPawnCapts[fs] & enemy);
        type = Wd;
        break;
      case RANK3:
      case RANK4:
      case RANK6:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
        break;
      case RANK5:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & (enemy | epbb[ply]));
        type = We;
        break;
      case RANK7:
        bb = (wPawnMoves[fs] & empty) | (wPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return OO;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Wb + i;
            m->score = (value[board[m->ts]] << 4) - VP;
            m->status = false;
            m++;
          }
        }
        continue;
      }
      break;
    case WN:
    case BN:
      bb = knightMoves[fs] & notme;
      break;
    case WB:
    case BB:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & bob[fs]
        & notme;
      break;
    case WR:
    case WRC:
    case BR:
    case BRC:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & rob[fs]
        & notme;
      break;
    case WQ:
    case BQ:
      bb = qss[fs][(aPieces >> (fs & 56)) & 127][0]
        & qss[fs][(aPieces >> 8) & 255][1]
        & qss[fs][(aPieces >> 16) & 255][2]
        & qss[fs][(aPieces >> 24) & 255][3]
        & qss[fs][(aPieces >> 32) & 255][4]
        & qss[fs][(aPieces >> 40) & 255][5]
        & qss[fs][(aPieces >> 48) & 255][6]
        & notme;
      break;
    case WK:
    case BK:
      bb = kingMoves[fs] & notme;
      break;
    case WC:
      bb = kingMoves[fs] & notme;
      if (board[H1] == WRC && !(WOCCS & aPieces) && !AtkByBlack(t, WATKS)) {
        m->fs = E1;
        m->ts = G1;
        m->type = WS;
        m->score = 1000;
        m->status = false;
        m++;
      }
      if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
        m->fs = E1;
        m->ts = C1;
        m->type = WL;
        m->score = 1000;
        m->status = false;
        m++;
      }
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        if (bb & king[1 - wtm]) return OO;
        while (bb) {
          _BitScanForward64(&ts, bb);
          bb ^= one << ts;
          for (i = Q; i >= B; i--) {
            m->fs = (s32)fs;
            m->ts = (s32)ts;
            m->type = Bb + i;
            m->score = (value[board[m->ts]] << 4) - VP;
            m->status = false;
            m++;
          }
        }
        continue;
      case RANK3:
      case RANK5:
      case RANK6:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        break;
      case RANK4:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & (enemy | epbb[ply]));
        type = Be;
        break;
      case RANK7:
        _BitScanReverse64(&sq, bPawnMoves[fs] & aPieces);
        bb = (bPawnMoves[fs] & above[sq]) | (bPawnCapts[fs] & enemy);
        type = Bd;
        break;
      }
      break;
    case BC:
      bb = kingMoves[fs] & notme;
      if (board[H8] == BRC && !(BOCCS & aPieces) && !AtkByWhite(t, BATKS)) {
        m->fs = E8;
        m->ts = G8;
        m->type = BS;
        m->score = 1000;
        m->status = false;
        m++;
      }
      if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
        m->fs = E8;
        m->ts = C8;
        m->type = BL;
        m->score = 1000;
        m->status = false;
        m++;
      }
      break;
    }

    captures |= bb;

    while (bb) {
      _BitScanForward64(&ts, bb);
      bb ^= one << ts;
      m->fs = (s32)fs;
      m->ts = (s32)ts;
      m->type = type;
      m->score = (value[board[m->ts]] << 4) - value[board[m->fs]];
      m->status = false;
      m++;
    }

  } while (pieces);

  if (captures & king[1 - wtm]) return OO;

  m->status = STOP;
  m++;

  return m - n;
}

s32 Search(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
  s32 i, mi;
  u64 n;
  Move* mov;

  n = GenMoves(t, m);

  if (!n) return -ILLEGAL;

  depth--;

  for (i = 0; (m + i)->status != STOP; i++) {
    mi = Sort(t, m);
    mov = m + mi;
    MakeMove(t, mov);
    if (!depth) {
      mov->score = -Qsearch(t, m + n, -beta, -alpha);
    }
    else {
      mov->score = -Search(t, m + n, -beta, -alpha, depth);
    }
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score >= beta) return beta;
    if (mov->score > alpha) alpha = mov->score;
  }
  return alpha;
}

s32 RootSearch(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
  s32 i, mi;
  u64 n;
  Move* mov;

  n = GenMoves(t, m);

  if (!n) return -ILLEGAL;

  depth--;

  for (i = 0; (m + i)->status != STOP; i++) {
    mi = Sort(t, m);
    mov = m + mi;
    MakeMove(t, mov);
    if (!depth) {
      mov->score = -Qsearch(t, m + n, -beta, -alpha);
    }
    else {
      mov->score = -Search(t, m + n, -beta, -alpha, depth);
    }
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score > alpha) {
      alpha = mov->score;
      bestMove.fs = mov->fs;
      bestMove.ts = mov->ts;
      bestMove.type = mov->type;
    }
  }
  return alpha;
}

void Bricabrac(Thread* t) {

  RootSearch(t, &move[0], -INF, INF, sd);

  bricabrac = MOVE;
}

void GetCmd(Thread* t) {
  s32 match, i, fs, ts;
  u64 n, epbit;
  char data[256], mvstr[20];

  match = false;
  epbit = epbb[1];

  PrintBoard(t);

  fgets(data, 256, stdin);
  _strlwr_s(data);

  std::cout << std::endl;

  if (data[0] >= 'a' && data[0] <= 'h' &&
      data[1] >= '1' && data[1] <= '8' &&
      data[2] >= 'a' && data[2] <= 'h' &&
      data[3] >= '1' && data[3] <= '8') {
    epbb[0] = epbit;
    n = GenMoves(t, &move[0]);
    for (i = OO; i < n; i++) {
      fs = move[i].fs;
      ts = move[i].ts;
      sprintf_s(mvstr, 20, "%c%d%c%d\n", (fs & 7) + 'a', (fs >> 3) + 1, (ts & 7) + 'a', (ts >> 3) + 1);
      if (!strcmp(data, mvstr)) {
        gameMoves[gamePly].fs = fs;
        gameMoves[gamePly].ts = ts;
        gameMoves[gamePly].type = move[i].type;
        MakeMove(t, &gameMoves[gamePly]);
        epbb[0] = epbit;
        gamePly++;
        ply--;
        return;
      }
    }
    return;
  }

  if (!strcmp(data, "go\n")) {
    bricabrac = BRICABRAC;
    return;
  }

  if (!strcmp(data, "u\n") || !strcmp(data, "undo\n")) {
    gamePly--;
    ply++;
    TakeBack(t, &gameMoves[gamePly]);
    return;
  }


}

void DoMove(Thread* t) {
  s32 i, j = 0, score;

  score = -INF;

  if (bestMove.score != ILLEGAL) {
    // TommyTC
    printf("\nMove Played: ");
    printf("%c%c", 'A' + (bestMove.fs & 7), '1' + (bestMove.fs >> 3));
    printf("%c%c\n", 'A' + (bestMove.ts & 7), '1' + (bestMove.ts >> 3));
    gameMoves[gamePly].fs = bestMove.fs;
    gameMoves[gamePly].ts = bestMove.ts;
    gameMoves[gamePly].type = bestMove.type;
    MakeMove(t, &gameMoves[gamePly]);
    epbb[0] = epbb[1];
    ply--;
    gamePly++;
  }
  bricabrac = GETCMD;
}

void InitializeQSS() {
  u08 sq, sqr, k, l;
  s08 x, y, dx, dy;
  s32 i;
  u64 b, bb;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    bob[sq] = 0;
    rob[sq] = 0;
    for (i = 0; i < 256; i++) {
      for (k = 0, l = 0; k <= 56; k += 8, l++) {
        bb = 0;
        b = (u64)i << k;
        for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
          sqr = (((y + dy) << 3) + x + dx);
          bb |= one << sqr;
          bob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = -1; x + dx > -1; dx--) {
          sqr = (y << 3) + x + dx;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dx = +1; x + dx < +8; dx++) {
          sqr = (y << 3) + x + dx;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dy = +1; y + dy < +8; dy++) {
          sqr = ((y + dy) << 3) + x;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        for (dy = -1; y + dy > -1; dy--) {
          sqr = ((y + dy) << 3) + x;
          bb |= one << sqr;
          rob[sq] |= one << sqr;
          if ((one << sqr) & b) break;
        }
        qss[sq][i][l] = bb;
      }
    }
  }
}

void InitializeRNK() {
  u08 sq, sqr, i;
  s08 x, y, dx, dy;
  u64 bb, b;

  for (sq = 0; sq < 64; sq++) {
    y = sq >> 3;
    x = sq & 7;
    for (i = 0; i < 128; i++) {
      bb = 0;
      b = (u64)i << (sq & 56);
      for (dx = +1, dy = +1; x + dx < +8 && y + dy < +8; dx++, dy++) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1, dy = +1; x + dx > -1 && y + dy < +8; dx--, dy++) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = +1, dy = -1; x + dx < +8 && y + dy > -1; dx++, dy--) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1, dy = -1; x + dx > -1 && y + dy > -1; dx--, dy--) {
        sqr = (((y + dy) << 3) + x + dx);
        bb |= one << sqr;
        bob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = -1; x + dx > -1; dx--) {
        sqr = (y << 3) + x + dx;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dx = +1; x + dx < +8; dx++) {
        sqr = (y << 3) + x + dx;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dy = +1; y + dy < +8; dy++) {
        sqr = ((y + dy) << 3) + x;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      for (dy = -1; y + dy > -1; dy--) {
        sqr = ((y + dy) << 3) + x;
        bb |= one << sqr;
        rob[sq] |= one << sqr;
        if ((one << sqr) & b) break;
      }
      qss[sq][i][0] = bb;
    }
  }
}

void InitPieceBB() {
  s32 sq, x, y;

  above[0] = 0xffffffffffffffff;
  below[0] = 0xffffffffffffffff;

  for (sq = A1; sq <= H8; sq++) {
    x = sq & 7;
    y = sq >> 3;

    above[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) ^ 1) << (sq + 1);
    below[sq + 1] = ((0xffffffffffffffff >> (sq + 1)) << (sq + 1)) ^ 0xffffffffffffffff;

    wPawnMoves[sq] = 0;
    wPawnCapts[sq] = 0;
    bPawnMoves[sq] = 0;
    bPawnCapts[sq] = 0;
    if (sq > H1 && sq < A8) {
      // White Pawn Moves
      wPawnMoves[sq] |= one << (sq + 8);
      if (sq < A3) wPawnMoves[sq] |= one << (sq + 16);
      // White Pawn Captures
      if (x + 1 < +8) wPawnCapts[sq] |= one << (sq + 9);
      if (x - 1 > -1) wPawnCapts[sq] |= one << (sq + 7);
      // Black Pawn Moves
      bPawnMoves[sq] |= one << (sq - 8);
      if (sq > H6) bPawnMoves[sq] |= one << (sq - 16);
      // Black Pawn Captures
      if (x + 1 < +8) bPawnCapts[sq] |= one << (sq - 7);
      if (x - 1 > -1) bPawnCapts[sq] |= one << (sq - 9);
    }
    // Knight Moves
    knightMoves[sq] = 0;
    if (y + 2 < +8 && x + 1 < +8) knightMoves[sq] |= one << (sq + 17);
    if (y + 1 < +8 && x + 2 < +8) knightMoves[sq] |= one << (sq + 10);
    if (y - 1 > -1 && x + 2 < +8) knightMoves[sq] |= one << (sq - +6);
    if (y - 2 > -1 && x + 1 < +8) knightMoves[sq] |= one << (sq - 15);
    if (y - 2 > -1 && x - 1 > -1) knightMoves[sq] |= one << (sq - 17);
    if (y - 1 > -1 && x - 2 > -1) knightMoves[sq] |= one << (sq - 10);
    if (y + 1 < +8 && x - 2 > -1) knightMoves[sq] |= one << (sq + +6);
    if (y + 2 < +8 && x - 1 > -1) knightMoves[sq] |= one << (sq + 15);
    // King Moves
    kingMoves[sq] = 0;
    if (y + 1 < +8) kingMoves[sq] |= one << (sq + 8);
    if (y - 1 > -1) kingMoves[sq] |= one << (sq - 8);
    if (x + 1 < +8) kingMoves[sq] |= one << (sq + 1);
    if (x - 1 > -1) kingMoves[sq] |= one << (sq - 1);
    if (y + 1 < +8 && x + 1 < +8) kingMoves[sq] |= one << (sq + 9);
    if (y - 1 > -1 && x + 1 < +8) kingMoves[sq] |= one << (sq - 7);
    if (y - 1 > -1 && x - 1 > -1) kingMoves[sq] |= one << (sq - 9);
    if (y + 1 < +8 && x - 1 > -1) kingMoves[sq] |= one << (sq + 7);
  }
  InitializeQSS();
  InitializeRNK();
}

void NewGame(Thread* t) {
  LoadFen(t, startFen);
}

void Initialize() {
  bricabrac = GETCMD;
  gamePly = OO;
  wtm = WHITE;
  ply = OO;
  InitPieceBB();
  NewGame(t);
}

// TommyTC
void SetSearchDepth()
{
    char data[256];
    int x = 0;
    printf("Enter SEARCH DEPTH (sd): \n");
    fgets(data, 4, stdin);
    while ((data[x] >= '0') && (data[x] <= '9')) {
      sd = 10 * sd + (data[x++] - '0');
    }
}

s32 main() {

  printf("TOMDEBUG:  %i\n\n", 3);
  SetSearchDepth(); // TommyTC 

  t = &thread;

  Initialize();

  do {
    if (bricabrac == BRICABRAC) Bricabrac(t);
    if (bricabrac == MOVE) DoMove(t);
    GetCmd(t);
  } while (bricabrac);

  return 0;
}

Mike Sherwin · Post by **Mike Sherwin** » Wed Sep 30, 2020 8:53 pm

I was wrong.

TommyTC wrote:I am familiar with the concept of "iterative deepening" and was wondering if that is how you might want to proceed.

Dumb Donkey wrote:Iterative deepening is on my todo list. I seem to remember that it is necessary to implement principle variation search. But, without a triangular array or hash tables to get the best move iterative deepening is only good for time management.

sd = 9
I just had a position where black played c7c1 mate. It took a long time to find because Q moving to an empty square has a lower move ordering priority. So ID while preserving the root move list between iterations would obviously allow finding c7c1 mate instantly. And just improve move ordering at the root in general. So ID is now at the top of my todo list!

TommyTC · Post by **TommyTC** » Fri Oct 02, 2020 1:03 am

Hi Mike,

Bug 1:

"u" from starting position. Oops! Program exception in TakeBack.

=====

Bug 2:
The score values assigned for pawn promotion (with or without capture) are not correct.

Here are the key definitions:

enum { B, R, N, Q };

enum {
OO, WP, WN, WB, WR, WRC, WQ, WK, WC, BP, BN, BB, BR, BRC, BQ, BK, BC,
Wd, We, Wb, Wr, Wn, Wq, Bd, Be, Bb, Br, Bn, Bq, WS, WL, BS, BL
};

s32 value[] = { OO, VP, VN, VB, VR, VR, VQ, VK, VK, VP, VN, VB, VR, VR, VQ, VK, VK,
Vb, Vr, Vn, Vq, Vb, Vr, Vn, Vq };

*Note the missing "value"s for Wd, We, Bd, Be (and others)*

Here is the offending code:

for (i = Q; i >= B; i--) {

m->type = Wb + i;
m->score = (value[board[ts]] << 4) + value[m->type];

For example, the "value[m->type]" for i=Q resolves to Vr (value 400) instead of Vq (value 800).

=====

The next inconsistency I found (about 2 weeks ago) isn't a "bug" per se. It doesn't produce any ill effects right now, but could be an issue in the future.

The "above[]" and "below[]" arrays are currently used in GenMoves to determine if a pawn on it's initial square can move 0, 1, or 2 squares forward.

If you don't plan on ever using them for anything else, then it's ok to stop reading now, but if you ever might use them for other purposes there is an inconsistency that could rear its ugly head.

above[65] is defined as an array of bitboards for each square on the chessboard. A bitboard for a square describes all those squares numbered higher than it. For example, above[C1] is all squares from D1 to H8.

below[65] is defined similarly, but for those squares numbered lower than it.

Here are some of the currently defined values:

above[A1] = 0xffffffffffffffff
above[B1] = 0xfffffffffffffffc
above[C1] = 0xfffffffffffffff8
above[D1] = 0xfffffffffffffff0
...
above[G8] = 0x8000000000000000
above[H8] = 0x0000000000000000
above[H8+1] = 0xfffffffffffffffe

below[A1] = 0xffffffffffffffff
below[B1] = 0x0000000000000001
below[C1] = 0x0000000000000003
below[D1] = 0x0000000000000007
...
below[G8] = 0x3fffffffffffffff
below[H8] = 0x7fffffffffffffff
below[H8+1] = 0x0000000000000000

The first question concerning above[65] and below[65] was "Why 65 and not 64?" And then I noticed that "above[A1]" includes the square A1!? And that "below[A1]" is the entire board!?

I would think the following are more consistent:

above[A1] = 0xfffffffffffffffe
below[A1] = 0x0000000000000000

I looked at the code and kind of saw why it was written that way, but wondered if it couldn't be written better -- with [64] and with the consistent values for above[A1] and below[A1]. Along the way I discovered the following slight oddity with C compilers:

0xffffffffffffffff >> 64 is undefined behavior
0xffffffffffffffff << 64 is undefined behavior

And also that with _BitScanForward64(&sq, 0), the function returns the value of 0 when no bits are found, but otherwise returns non-zero. Not to be confused with _BitScanForward64(&sq, 1) setting sq to 0.

Ok, so here is my suggested code:

1. u64 above[64];
u64 below[64];

2. In GenMoves() for WP: and RANK2:

if (! _BitScanForward64(&sq, wPawnMoves[fs] & aPieces)) {
sq = H8;
}

3. In GenMoves() for BP: and RANK7:

if (! _BitScanReverse64(&sq, bPawnMoves[fs] & aPieces)) {
sq = A1;
}

4. In InitPieceBB(), remove the following:

above[0] = 0xffffffffffffffff;
below[0] = 0xffffffffffffffff;

5. In InitPieceBB(), replace the current code (above[sq + 1] and below[sq + 1]) with:

above[sq] = sq == H8 ? 0 : (0xffffffffffffffff >> (sq + 1)) << (sq + 1);
below[sq] = sq == A1 ? 0 : (0xffffffffffffffff << (64 - sq)) >> (64 - sq);

=====

I'm still going over your most recent changes, including RootSearch(), but thought I'd pass these observations to you now.

Kind Regards,
Tommy

Mike Sherwin · Post by **Mike Sherwin** » Fri Oct 02, 2020 3:07 am

TommyTC wrote: ↑Fri Oct 02, 2020 1:03 am Hi Mike,

Bug 1:

"u" from starting position. Oops! Program exception in TakeBack.

=====

Bug 2:
The score values assigned for pawn promotion (with or without capture) are not correct.

Here are the key definitions:

enum { B, R, N, Q };

enum {
OO, WP, WN, WB, WR, WRC, WQ, WK, WC, BP, BN, BB, BR, BRC, BQ, BK, BC,
Wd, We, Wb, Wr, Wn, Wq, Bd, Be, Bb, Br, Bn, Bq, WS, WL, BS, BL
};

s32 value[] = { OO, VP, VN, VB, VR, VR, VQ, VK, VK, VP, VN, VB, VR, VR, VQ, VK, VK,
Vb, Vr, Vn, Vq, Vb, Vr, Vn, Vq };

*Note the missing "value"s for Wd, We, Bd, Be (and others)*

Here is the offending code:

for (i = Q; i >= B; i--) {

m->type = Wb + i;
m->score = (value[board[ts]] << 4) + value[m->type];

For example, the "value[m->type]" for i=Q resolves to Vr (value 400) instead of Vq (value 800).

=====

The next inconsistency I found (about 2 weeks ago) isn't a "bug" per se. It doesn't produce any ill effects right now, but could be an issue in the future.

The "above[]" and "below[]" arrays are currently used in GenMoves to determine if a pawn on it's initial square can move 0, 1, or 2 squares forward.

If you don't plan on ever using them for anything else, then it's ok to stop reading now, but if you ever might use them for other purposes there is an inconsistency that could rear its ugly head.

above[65] is defined as an array of bitboards for each square on the chessboard. A bitboard for a square describes all those squares numbered higher than it. For example, above[C1] is all squares from D1 to H8.

below[65] is defined similarly, but for those squares numbered lower than it.

Here are some of the currently defined values:

above[A1] = 0xffffffffffffffff
above[B1] = 0xfffffffffffffffc
above[C1] = 0xfffffffffffffff8
above[D1] = 0xfffffffffffffff0
...
above[G8] = 0x8000000000000000
above[H8] = 0x0000000000000000
above[H8+1] = 0xfffffffffffffffe

below[A1] = 0xffffffffffffffff
below[B1] = 0x0000000000000001
below[C1] = 0x0000000000000003
below[D1] = 0x0000000000000007
...
below[G8] = 0x3fffffffffffffff
below[H8] = 0x7fffffffffffffff
below[H8+1] = 0x0000000000000000

The first question concerning above[65] and below[65] was "Why 65 and not 64?" And then I noticed that "above[A1]" includes the square A1!? And that "below[A1]" is the entire board!?

I would think the following are more consistent:

above[A1] = 0xfffffffffffffffe
below[A1] = 0x0000000000000000

I looked at the code and kind of saw why it was written that way, but wondered if it couldn't be written better -- with [64] and with the consistent values for above[A1] and below[A1]. Along the way I discovered the following slight oddity with C compilers:

0xffffffffffffffff >> 64 is undefined behavior
0xffffffffffffffff << 64 is undefined behavior

And also that with _BitScanForward64(&sq, 0), the function returns the value of 0 when no bits are found, but otherwise returns non-zero. Not to be confused with _BitScanForward64(&sq, 1) setting sq to 0.

Ok, so here is my suggested code:

1. u64 above[64];
u64 below[64];

2. In GenMoves() for WP: and RANK2:

if (! _BitScanForward64(&sq, wPawnMoves[fs] & aPieces)) {
sq = H8;
}

3. In GenMoves() for BP: and RANK7:

if (! _BitScanReverse64(&sq, bPawnMoves[fs] & aPieces)) {
sq = A1;
}

4. In InitPieceBB(), remove the following:

above[0] = 0xffffffffffffffff;
below[0] = 0xffffffffffffffff;

5. In InitPieceBB(), replace the current code (above[sq + 1] and below[sq + 1]) with:

above[sq] = sq == H8 ? 0 : (0xffffffffffffffff >> (sq + 1)) << (sq + 1);
below[sq] = sq == A1 ? 0 : (0xffffffffffffffff << (64 - sq)) >> (64 - sq);

=====

I'm still going over your most recent changes, including RootSearch(), but thought I'd pass these observations to you now.

Kind Regards,
Tommy

Hi Tommy,

You are showing me how much I have slipped in the last 15 years, lol. One can fight time but one can't win!

Bug 1: I'm aware of bug 1. I was being lazy but now I will add the necessary check.

Bug 2: I saw that but because of my memory problem I forgot to change it. Thanks for the reminder.

Inconsistency: u64 above[65] is a fopa on my part. I meant above[64]. There is a catch 22 or at least I imagined one. _BitScanForward64() returns zero if no bits are set. As there is always at least one bit set in the cases where it is used I was trying to avoid an if statement. But right now that is all I can remember so it will need to be reinvestigated. Of course A1 is immaterial for pawns and above[] is only used for pawns. However, correctness is important!

I will work on correcting all these, thanks.

best wishes
Mike

Mike Sherwin · Post by **Mike Sherwin** » Fri Oct 02, 2020 3:23 am

Now I remember my confusion. My board is 0 to 63 but _BitScan f/r stores 1 to 64. So I did have above[64] and then changed it to above[65]. No, I'm not remembering correctly, above[65] was intended. I'll just look to see how it was done in RomiChess. I'll get back to you on this.

EDIT:

Code: Select all

above[s] = 0;
    for(i = s + 1; i <= H8; i++)
      above[s] |= setBit[i];
    above[64] = 0xffffffffffffffff;

Code: Select all

__inline s32 FirstBit(u64 bits) {
	s32 index;
	if(_BitScanForward64(&index, bits))
		return index;
	return 64;
}

The if statement in this code is what I was trying to avoid.

Mike Sherwin · Post by **Mike Sherwin** » Fri Oct 02, 2020 3:53 am

Okay, I just can't remember anything. In Microsoft docs, "Enter a positive integer as the mask: Mask: 12 Index: 2". Index 2 sees 100b which is 0,1,2 on the board therefore the first bit in the mask is indeed stored as 0 in index. Okay I need to get on this before I forget.

I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up

Re: I don't want to give up