I don't want to give up

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Mike Sherwin
Posts: 103
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: I don't want to give up

Post by Mike Sherwin » Tue Sep 15, 2020 8:10 am

TommyTC wrote:
Tue Sep 15, 2020 2:25 am
Hi Mike,

Another bug.

After either side castles, some legal moves are disallowed, and some illegal moves are allowed.

Analysis:

In MakeMove, the 4 castling moves (WS, WL, BS, BL) fail to update king[WHITE] or king[BLACK] for both the "from" and "to" locations.

Fix:

For WS and WL insert the following:

king[WHITE] ^= one << m->fs;
king[WHITE] ^= one << m->ts;

For BS and BL insert the following:

king[BLACK] ^= one << m->fs;
king[BLACK] ^= one << m->ts;

TakeBack needs the same changes.

Tommy
Hi Tommy, I made the changes, ty. Also I really appreciate your continued help. I have not worked on it for the last couple of days. Was not feeling very well. Tomorrow I plan on jumping back in though. Thanks again! :D

Mike

Mike Sherwin
Posts: 103
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: I don't want to give up

Post by Mike Sherwin » Tue Sep 15, 2020 2:48 pm

Part way there! Found the major problem. Setting search depth to 1. Entering the moves e2e4, d7d5, e4d5 and then go it plays d8d5 capturing the pawn. Then chasing the queen begins until chasing the queen is a mistake and it plays the correct move! It will be clear in the pgn.

Since I'm changing it to full pseudo legal move generation there is more work to be done but here is the source so far.

Code: Select all

// Bricabrac
// A chess engine by Michael J Sherwin

#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 ColA = 0;
constexpr auto Row8 = 7;
constexpr auto ILLEGAL = 0xffff;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 2000;
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 Sns {
  s32 n;
  s32 score;
};

union Snu {
  Sns sns;
  u64 snu;
};

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];

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 n) {
  s32 i = 0, high = -INF;
  Move* mov;
  for (; n > OO; n--) {
    mov = m - n;
    if (mov->status == false && mov->score > high) {
      high = mov->score;
      i = n;
    }
  }
  (m - i)->status = true;
  return i;
}

__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 depth) {
  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);
        captures |= bb;
        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]] + 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);
        captures |= bb;
        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]] + 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]] - 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, depth);
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score > alpha) {
      if (mov->score >= beta) {
        return beta;
      }
      alpha = mov->score;
    }
  }
  return alpha;
}

u64 GenLegalQ(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
  Snu snu;
  s32 n = 0, i, type, score = -INF;
  u32 fs, ts, sq;
  u64 bb = 0;

  snu.snu = 0;

  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);
        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]] - VP;
            m->status = false;
            m++;
            n++;
          }
        }
        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 = 40;
        m->status = false;
        m++;
        n++;
      }
      if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
        m->fs = E1;
        m->ts = C1;
        m->type = WL;
        m->score = 40;
        m->status = false;
        m++;
        n++;
      }
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        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]] - VP;
            m->status = false;
            m++;
            n++;
          }
        }
        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 = 40;
        m->status = false;
        m++;
        n++;
      }
      if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
        m->fs = E8;
        m->ts = C8;
        m->type = BL;
        m->score = 40;
        m->status = false;
        m++;
        n++;
      }
      break;
    }

    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]] - value[board[m->fs]];
      m->status = false;
      m++;
      n++;
    }

  } while (pieces);

  snu.sns.n = n;
  snu.sns.score = score;

  return snu.snu;
}

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

  sna.sns.score = alpha;

  snu.snu = GenLegalQ(t, m, alpha, beta, depth);
  n = snu.sns.n;
  m = m + n;
  depth--;
  for (i = n; i > 0; i--) {
    mi = Sort(t, m, n);
    mov = m - mi;
    MakeMove(t, mov);
    if (depth == 0) {
      mov->score = -Qsearch(t, m, -beta, -alpha, depth);
    }
    else {
      snu.snu = Search(t, m, -beta, -alpha, depth);
      mov->score = -snu.sns.score;
    }
    TakeBack(t, mov);
    if (mov->score >= beta) { snu.sns.score = beta;  return snu.snu; }
    if (mov->score > sna.sns.score) sna.sns.score = snu.sns.score;
  }
  sna.sns.n = n;
  return sna.snu;
}

u64 Bricabrac(Thread* t) {
  Snu snu;

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

  bricabrac = MOVE;
  return snu.snu;
}

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

  match = false;

  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') {
    snu.snu = GenLegalQ(t, &move[0], -INF, INF, INF);
    for (i = OO; i < snu.sns.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]);
        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, Snu snu) {
  s32 n, i, j = 0, score;

  n = snu.sns.n;
  score = -INF;

  for (i = 0; i < n; i++) {
    if (move[i].score > score) {
      score = move[i].score;
      j = i;
    }
  }
  gameMoves[gamePly].fs = move[j].fs;
  gameMoves[gamePly].ts = move[j].ts;
  gameMoves[gamePly].type = move[j].type;
  MakeMove(t, &gameMoves[gamePly]);
  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;
  sd = 1;
  wtm = WHITE;
  ply = OO;
  InitPieceBB();
  NewGame(t);
}

s32 main() {
  Snu snu;

  snu.snu = 0;

  t = &thread;

  Initialize();

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

  return 0;
}

Mike Sherwin
Posts: 103
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: I don't want to give up

Post by Mike Sherwin » Tue Sep 15, 2020 9:16 pm

The search has been completely rewritten. GenLegalQ() is now GenMoves(). Searching 1 ply deep has identical results. Unfortunately, searching 2 ply deep also has the same result as after e2e4, d7d5, e4d5 and after typing go the Queen does not take the pawn. It has to be my memory problem. I'm not remembering something about negamax. I must be making the same mistake if the results are identical after such a change. Or it is one hell of a coincidence.

Code: Select all

// Bricabrac
// A chess engine by Michael J Sherwin

#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 = 0xffff;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 2000;
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];

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);
        captures |= bb;
        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]] + 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);
        captures |= bb;
        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]] + 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]] - 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);
        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]] - 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 = 40;
        m->status = false;
        m++;
      }
      if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
        m->fs = E1;
        m->ts = C1;
        m->type = WL;
        m->score = 40;
        m->status = false;
        m++;
      }
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        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]] - 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 = 40;
        m->status = false;
        m++;
      }
      if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
        m->fs = E8;
        m->ts = C8;
        m->type = BL;
        m->score = 40;
        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]] - 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);
    PrintBoard(t);
    if (!depth) {
      mov->score = -Qsearch(t, m + n, -beta, -alpha);
    }
    else {
      mov->score = -Search(t, m + n, -beta, -alpha, depth);
    }
    TakeBack(t, mov);
    PrintBoard(t);
    if (mov->score == ILLEGAL) continue;
    if (mov->score >= beta) return beta;
    if (mov->score > alpha) alpha = move->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;
  char data[256], mvstr[20];

  match = false;

  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') {
    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]);
        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;

  for (i = 0; move[i].status != STOP; i++) {
    if (move[i].score > score) {
      score = move[i].score;
      j = i;
    }
  }
  gameMoves[gamePly].fs = move[j].fs;
  gameMoves[gamePly].ts = move[j].ts;
  gameMoves[gamePly].type = move[j].type;
  MakeMove(t, &gameMoves[gamePly]);
  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;
  sd = 1;
  wtm = WHITE;
  ply = OO;
  InitPieceBB();
  NewGame(t);
}

s32 main() {

  t = &thread;

  Initialize();

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

  return 0;
}

TommyTC
Posts: 37
Joined: Thu Mar 30, 2017 6:52 am

Re: I don't want to give up

Post by TommyTC » Thu Sep 17, 2020 4:32 pm

In search:
if (mov->score > alpha) alpha = move->score;

Change to:
if (mov->score > alpha) alpha = mov->score;

Tommy

Mike Sherwin
Posts: 103
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: I don't want to give up

Post by Mike Sherwin » Fri Sep 18, 2020 5:57 am

TommyTC wrote:
Thu Sep 17, 2020 4:32 pm
In search:
if (mov->score > alpha) alpha = move->score;

Change to:
if (mov->score > alpha) alpha = mov->score;

Tommy
Such a simple mistake I made and I could not see it. I seem to be breaking more than I am fixing. Thanks again for your continued support.

TommyTC
Posts: 37
Joined: Thu Mar 30, 2017 6:52 am

Re: I don't want to give up

Post by TommyTC » Tue Sep 22, 2020 2:22 am

Hi Mike,

Do you prefer to find your own bugs in your code, or would you still like some help? I will assume you may still want some help, so here goes....

With sd (search depth) = 1, and typing "go" for each move, the following game is played:

1. Na3 a5 2. Rb1 a4 3. Ra1 b6 4. Rb1 c5 5. Ra1 d5 6. Rb1 c4 7. Ra1 e5 8. Rb1 c3 9. Ra1 cxb2 10. Rb1 bxc1=Q 11. Ra1 Qxa1 12. Qxa1

Questions to ask yourself:

0. Why is a2a3 searched before b1a3 on move 1?
1. Why is b1a3 played when a2a3 was examined first and has the same value as b1a3?
2. Why does Black play 8...c4c3 giving up the pawn?
3. Why doesn't White take it on move 9? or on move 10?
4. Why didn't Black play 7...c3 a move earlier, but waited until after 7...e5?

I think I can explain, but it's not easy.

=====

Moves are generated (in GenMoves) by examining pieces on the board starting with the A1 square and continuing to the H8 square. On move 1, the moves are generated in this order:

0. Na3
1. Nc3
2. Nf3
3. Nh3
4. a3
5. a4
6. b3
...and so on.

When they are generated, they are given a "score" so that Search will pick a move (Sort routine) with priority. See GenMoves:

m->score = value[board[m->ts]] - value[board[m->fs]];

Na3 == -300
Nc3 == -300
a3 == -100
a4 == -100

Therefore on move 1, all pawn moves will be examined before the knight moves.

a2a3 is chosen as the first move to Search and since depth is 1, Qsearch is called to look for captures and return the real value of a2a3. No captures are found, and the material is equal, so Qsearch returns 0 and the move a2a3 gets a RESOLVED score and alpha is updated to that value of 0.

The next move to examine is a2a4, with alpha == 0 and beta == +INF. The Qsearch call is made (negating and switching alpha and beta). Qsearch sees the material is equal, but that value of 0 is now ">= beta" so no searching is required. The move a2a4 cannot "beat" the previous move a2a3, BUT IT COULD BE WORSE, so Qsearch returns value 0 and a2a4 is given that score.

This process continues until all moves have been given a score of 0, but only a2a3 was given a resolved score.

Search eventually returns to Bricabrac, and DoMove is called to make the first move. But DoMove is simply given the list of generated moves with scores all 0. It starts with the first move on the list and searches for the highest score. Since 1. Na3 was the first move generated, that move is chosen! Based on the NegaMax, 1. a2a3 should have been played!

=====

We can now see the answer to question 4.
Hint: 7...e7e5 allows Black to play 8...f8a3.

On move 8 for Black, the first move generated is 8...c4c3, and later the move 8...f8a3 is generated. But now we see the initial scores given to the moves:

8...c4c3 == -100;
8...f8a3 == 0.

So now 8...f8a3 is the first move examined. With Qsearch, it resolves to a value of 0. And once again, all the moves for black are scored as 0 because of NegaMax, but only 8...f8a3 was fully resolved.

Once again, DoMove is only given the generated list, and all moves with score 0, so the first move generated is played, 8...c4c3, even though in this case IT IS WORSE than 8...f8a3.

Hopefully this makes some sense and that I'm not just talking nonsense.

Tommy

Mike Sherwin
Posts: 103
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: I don't want to give up

Post by Mike Sherwin » Wed Sep 23, 2020 1:55 am

TommyTC wrote:
Tue Sep 22, 2020 2:22 am
Hi Mike,

Do you prefer to find your own bugs in your code, or would you still like some help? I will assume you may still want some help, so here goes....

With sd (search depth) = 1, and typing "go" for each move, the following game is played:

1. Na3 a5 2. Rb1 a4 3. Ra1 b6 4. Rb1 c5 5. Ra1 d5 6. Rb1 c4 7. Ra1 e5 8. Rb1 c3 9. Ra1 cxb2 10. Rb1 bxc1=Q 11. Ra1 Qxa1 12. Qxa1

Questions to ask yourself:

0. Why is a2a3 searched before b1a3 on move 1?
1. Why is b1a3 played when a2a3 was examined first and has the same value as b1a3?
2. Why does Black play 8...c4c3 giving up the pawn?
3. Why doesn't White take it on move 9? or on move 10?
4. Why didn't Black play 7...c3 a move earlier, but waited until after 7...e5?

I think I can explain, but it's not easy.

=====

Moves are generated (in GenMoves) by examining pieces on the board starting with the A1 square and continuing to the H8 square. On move 1, the moves are generated in this order:

0. Na3
1. Nc3
2. Nf3
3. Nh3
4. a3
5. a4
6. b3
...and so on.

When they are generated, they are given a "score" so that Search will pick a move (Sort routine) with priority. See GenMoves:

m->score = value[board[m->ts]] - value[board[m->fs]];

Na3 == -300
Nc3 == -300
a3 == -100
a4 == -100

Therefore on move 1, all pawn moves will be examined before the knight moves.

a2a3 is chosen as the first move to Search and since depth is 1, Qsearch is called to look for captures and return the real value of a2a3. No captures are found, and the material is equal, so Qsearch returns 0 and the move a2a3 gets a RESOLVED score and alpha is updated to that value of 0.

The next move to examine is a2a4, with alpha == 0 and beta == +INF. The Qsearch call is made (negating and switching alpha and beta). Qsearch sees the material is equal, but that value of 0 is now ">= beta" so no searching is required. The move a2a4 cannot "beat" the previous move a2a3, BUT IT COULD BE WORSE, so Qsearch returns value 0 and a2a4 is given that score.

This process continues until all moves have been given a score of 0, but only a2a3 was given a resolved score.

Search eventually returns to Bricabrac, and DoMove is called to make the first move. But DoMove is simply given the list of generated moves with scores all 0. It starts with the first move on the list and searches for the highest score. Since 1. Na3 was the first move generated, that move is chosen! Based on the NegaMax, 1. a2a3 should have been played!

=====

We can now see the answer to question 4.
Hint: 7...e7e5 allows Black to play 8...f8a3.

On move 8 for Black, the first move generated is 8...c4c3, and later the move 8...f8a3 is generated. But now we see the initial scores given to the moves:

8...c4c3 == -100;
8...f8a3 == 0.

So now 8...f8a3 is the first move examined. With Qsearch, it resolves to a value of 0. And once again, all the moves for black are scored as 0 because of NegaMax, but only 8...f8a3 was fully resolved.

Once again, DoMove is only given the generated list, and all moves with score 0, so the first move generated is played, 8...c4c3, even though in this case IT IS WORSE than 8...f8a3.

Hopefully this makes some sense and that I'm not just talking nonsense.

Tommy
Hi Tommy, Yes it makes a lot of sense. It was kinda what I was thinking myself. It is just that it is too much for me to keep in my memory long enough to fix it and instead I keep breaking it even worse. I don't know what I am going to do at this point. I don't want anyone to use up anymore of their time on me if I can't be helped. I'm not ready to give up but at the same time I'm no longer optimistic. Thanks for all you have done! :D

TommyTC
Posts: 37
Joined: Thu Mar 30, 2017 6:52 am

Re: I don't want to give up

Post by TommyTC » Thu Sep 24, 2020 7:07 pm

Hi Mike,

Never give up! Never surrender!

I think I have a solution, or at least a work-around to some of the problems previously encountered. Let's revisit the issues.

GenMoves generates moves in a specific order by looking for pieces on squares from A1, B1, C1, and so on until H8. When each move is added to the list of "pseudo valid" moves, most are given a priority based on the following:

m->score = value[board[m->ts]] - value[board[m->fs]];

[It is different for pawn promotions and castling, but let's ignore those for now.]

Here is the general priority order:

1. A small piece capturing a big piece, with the bigger the piece captured having the higher priority (e.g. BxQ is higher than BxR)

2. A piece capturing a similar piece (e.g., PxP, BxB, QxQ, BxN, NxB).

3. A piece capturing a smaller piece (e.g., QxP, QxR, QxN, RxB, RxP).

4. A piece moving to an empty square, with the smaller the piece the higher the priority (e.g., moving a Pawn is higher priority than moving a Knight; moving a Knight is higher priority than moving a Queen).

The Sort routine doesn't actually sort the moves, but is used to select the highest priority move that has not previously been selected. Therefore the order the moves are generated in is not the order that the moves are searched in. For example, 1. Na3 is generated first, yet 1. a3 is searched first because it has higher priority.

At this point, you might want to compile and run the code I've included in this message. Type "go" and see the first move played is 1. Na3. This should be the same as the code you previously posted.

Code: Select all

// Bricabrac
// A chess engine by Michael J Sherwin

#include "stdafx.h"

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

#define TOMDEBUG 0

#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 = 0xffff;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 2000;
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;
#if TOMDEBUG > 0
  s32 order;
#endif
  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);
        captures |= bb;
        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]] + 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);
        captures |= bb;
        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]] + 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]] - 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);
        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]] - 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 = 40;
        m->status = false;
        m++;
      }
      if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
        m->fs = E1;
        m->ts = C1;
        m->type = WL;
        m->score = 40;
        m->status = false;
        m++;
      }
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        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]] - 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 = 40;
        m->status = false;
        m++;
      }
      if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
        m->fs = E8;
        m->ts = C8;
        m->type = BL;
        m->score = 40;
        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]] - 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;
#if TOMDEBUG > 0
    mov->order = i;
#endif
    MakeMove(t, mov);
#if TOMDEBUG == 0
    PrintBoard(t);
#endif
    if (!depth) {
      mov->score = -Qsearch(t, m + n, -beta, -alpha);
    }
    else {
      mov->score = -Search(t, m + n, -beta, -alpha, depth);
    }
    TakeBack(t, mov);
#if TOMDEBUG == 0
    PrintBoard(t);
#endif
    if (mov->score == ILLEGAL) continue;
    if (mov->score >= beta) return beta;
#if TOMDEBUG == 0
    if (mov->score > alpha) alpha = move->score;
#else
    if (mov->score > alpha) alpha = mov->score;
#endif
  }
  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;
  char data[256], mvstr[20];

  match = false;

  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') {
    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]);
        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;

#if TOMDEBUG > 1
  s32 PrevSearchOrder = 1000;
#endif

  score = -INF;

  for (i = 0; move[i].status != STOP; i++) {
#if TOMDEBUG > 0
      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);
#endif

#if TOMDEBUG == 2
      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;
      }
#elif TOMDEBUG > 2
      if ((move[i].score != ILLEGAL)
          && (move[i].score > score)) {
          score = move[i].score;
          PrevSearchOrder = move[i].order;
          j = i;
      }
      else if ((move[i].score != ILLEGAL)
          && (move[i].score == score)
          && (move[i].order < PrevSearchOrder)) {
          PrevSearchOrder = move[i].order;
          j = i;
      }
#else
    if (move[i].score > score) {
      score = move[i].score;
      j = i;
    }
#endif

  }

#if TOMDEBUG > 0
  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));
#endif

  gameMoves[gamePly].fs = move[j].fs;
  gameMoves[gamePly].ts = move[j].ts;
  gameMoves[gamePly].type = move[j].type;
  MakeMove(t, &gameMoves[gamePly]);
  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;
#if TOMDEBUG == 0
  sd = 1;
#endif
  wtm = WHITE;
  ply = OO;
  InitPieceBB();
  NewGame(t);
}

#if TOMDEBUG > 0
void TOMDebug2()
{
    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');
    }
}
#endif

s32 main() {

#if TOMDEBUG > 0
    printf("TOMDEBUG:  %i\n\n", TOMDEBUG);
    TOMDebug2(); // Init 'sd' (Search Depth)
#endif

  t = &thread;

  Initialize();

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

  return 0;
}

Make the following code change (near the top):
TOMDEBUG = 1

Compile and rerun.

Enter "1" to the "SEARCH DEPTH" inquiry.
Type "go".

You should now see the list of generated moves in the order they were generated. Also displayed is the final score value for each move. In addition, the code now keeps track of the "order" in which the moves were searched, and that number is also displayed. So we can see that A2A3 was searched first, and G1H3 was searched last. Finally we see the move played.

And we notice the first bug. If A2A3 was searched first, and all moves have the same score, why wasn't A2A3 chosen as the move to play?

There are several issues here.

Let's first think about the search. A2A3 is searched with a full alph-beta range (-INF, +INF). Qsearch is called and the initial value assigned to alpha is determined by:

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

The material is equal so alpha becomes 0. This is very important to note regarding subsequent Qsearch calls!

Since no captures are found, Qsearch returns 0 for the move A2A3.

The search continues by looking at A2A4. At the Qsearch call, the alpha beta range is (0, +INF). Within Qsearch beta is thus 0, and after calculating

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

...and comparing >= beta, Qsearch IMMEDIATELY returns (as it should) without looking at any captures. It doesn't need to since we now know the move A2A4 cannot beat A2A3. A2A4 could actually be a much worse move than A2A3 but we dont know and don't care. And here is the important part...the move is given the value of beta (0).

So at this point we have 2 moves in the list of generated moves each with the score 0. One of them had a "full" quiesent capture search performed on it, and the other did not.

The search continues with all the other moves, and like A2A4 Qsearch is called with (0, +INF) for each. So every move is given a score of 0. But once again, only the very first move, A2A3, had a Qsearch which examined moves/captures by Black.

The search is complete, and the value for the position is 0, and DoMove is called to play the best move. But it has no information about which move had the "full" Qsearch performed! All it has is the generated list of moves (without the "order:" column). It has no way of knowing that A2A3 was searched first and is the move that should be played.

Hmmm, if only DoMove had the "order:" column, it could look for the highest score, and also look to see which move found it first.

Set "TOMDEBUG = 2", recompile and run. Enter "1" for sd, and enter "go".

The change in code for "TOMDEBUG = 2" is just a few lines of code in DoMove.

If you continue to enter "go" you can begin to see that moves are analyzed in the order you would like, and that scores are given correctly to them. You can also see that the move played is the one that you would expect to be played based on the move ordering described earlier and the value of material on the board following a Qsearch.

The game played is:

1. a3 a5 2. b3 a4 3. bxa4 Rxa4 4. c3 b5 5. d3 c5 6. e3 d5 7. f3 c4 8. dxc4 dxc4 9. Qxd8+

...and here the move played is 9...B5B4 (Illegal!)

There is only 1 legal move in the position, E8D8 (with score 0), yet move B5B4 with score 65535 was played!

[Warning: Entering "go" again is not advised.]

You may want to revisit some of your definitions.

struct Move
s32 score

INF 0x7fff
ILLEGAL 0xffff

s32 is defined as "int". The first range for alpha beta is [-INF, +INF]. It's clear to see that ILLEGAL (0x0000ffff) is GREATER than +INF (0x00007fff).

I've kept the definitions as is, and updated the code in DoMove.

Set TOMDEBUG = 3, recompile, rerun, enter "1" for sd, and enter "go" until 9...E8D8 is played.

You can continue entering moves until both sides start repeating moves.

I've not examined much at sd=2 or sd=3 or higher, but it seems to play properly. Your code currently does not handle stalemate or checkmate so when those are reached bad things will happen.

It's clear that you have spent some time already on Bricabrac. It would be a shame if you gave up too soon.

If you have questions or comments, please let me know.

Kind regards,
Tommy

TommyTC
Posts: 37
Joined: Thu Mar 30, 2017 6:52 am

Re: I don't want to give up

Post by TommyTC » Thu Sep 24, 2020 8:08 pm

<message deleted>

Mike Sherwin
Posts: 103
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: I don't want to give up

Post by Mike Sherwin » Thu Sep 24, 2020 9:15 pm

TommyTC wrote:
Thu Sep 24, 2020 7:07 pm
Hi Mike,

Never give up! Never surrender!

I think I have a solution, or at least a work-around to some of the problems previously encountered. Let's revisit the issues.

GenMoves generates moves in a specific order by looking for pieces on squares from A1, B1, C1, and so on until H8. When each move is added to the list of "pseudo valid" moves, most are given a priority based on the following:

m->score = value[board[m->ts]] - value[board[m->fs]];

[It is different for pawn promotions and castling, but let's ignore those for now.]

Here is the general priority order:

1. A small piece capturing a big piece, with the bigger the piece captured having the higher priority (e.g. BxQ is higher than BxR)

2. A piece capturing a similar piece (e.g., PxP, BxB, QxQ, BxN, NxB).

3. A piece capturing a smaller piece (e.g., QxP, QxR, QxN, RxB, RxP).

4. A piece moving to an empty square, with the smaller the piece the higher the priority (e.g., moving a Pawn is higher priority than moving a Knight; moving a Knight is higher priority than moving a Queen).

The Sort routine doesn't actually sort the moves, but is used to select the highest priority move that has not previously been selected. Therefore the order the moves are generated in is not the order that the moves are searched in. For example, 1. Na3 is generated first, yet 1. a3 is searched first because it has higher priority.

At this point, you might want to compile and run the code I've included in this message. Type "go" and see the first move played is 1. Na3. This should be the same as the code you previously posted.

Code: Select all

// Bricabrac
// A chess engine by Michael J Sherwin

#include "stdafx.h"

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

#define TOMDEBUG 0

#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 = 0xffff;
constexpr auto VP = 100;
constexpr auto VN = 300;
constexpr auto VB = 300;
constexpr auto VR = 500;
constexpr auto VQ = 900;
constexpr auto VK = 2000;
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;
#if TOMDEBUG > 0
  s32 order;
#endif
  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);
        captures |= bb;
        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]] + 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);
        captures |= bb;
        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]] + 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]] - 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);
        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]] - 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 = 40;
        m->status = false;
        m++;
      }
      if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
        m->fs = E1;
        m->ts = C1;
        m->type = WL;
        m->score = 40;
        m->status = false;
        m++;
      }
      break;
    case BP:
      switch (fs >> 3) {
      case RANK1:
        break;
      case RANK2:
        bb = (bPawnMoves[fs] & empty) | (bPawnCapts[fs] & enemy);
        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]] - 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 = 40;
        m->status = false;
        m++;
      }
      if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
        m->fs = E8;
        m->ts = C8;
        m->type = BL;
        m->score = 40;
        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]] - 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;
#if TOMDEBUG > 0
    mov->order = i;
#endif
    MakeMove(t, mov);
#if TOMDEBUG == 0
    PrintBoard(t);
#endif
    if (!depth) {
      mov->score = -Qsearch(t, m + n, -beta, -alpha);
    }
    else {
      mov->score = -Search(t, m + n, -beta, -alpha, depth);
    }
    TakeBack(t, mov);
#if TOMDEBUG == 0
    PrintBoard(t);
#endif
    if (mov->score == ILLEGAL) continue;
    if (mov->score >= beta) return beta;
#if TOMDEBUG == 0
    if (mov->score > alpha) alpha = move->score;
#else
    if (mov->score > alpha) alpha = mov->score;
#endif
  }
  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;
  char data[256], mvstr[20];

  match = false;

  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') {
    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]);
        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;

#if TOMDEBUG > 1
  s32 PrevSearchOrder = 1000;
#endif

  score = -INF;

  for (i = 0; move[i].status != STOP; i++) {
#if TOMDEBUG > 0
      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);
#endif

#if TOMDEBUG == 2
      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;
      }
#elif TOMDEBUG > 2
      if ((move[i].score != ILLEGAL)
          && (move[i].score > score)) {
          score = move[i].score;
          PrevSearchOrder = move[i].order;
          j = i;
      }
      else if ((move[i].score != ILLEGAL)
          && (move[i].score == score)
          && (move[i].order < PrevSearchOrder)) {
          PrevSearchOrder = move[i].order;
          j = i;
      }
#else
    if (move[i].score > score) {
      score = move[i].score;
      j = i;
    }
#endif

  }

#if TOMDEBUG > 0
  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));
#endif

  gameMoves[gamePly].fs = move[j].fs;
  gameMoves[gamePly].ts = move[j].ts;
  gameMoves[gamePly].type = move[j].type;
  MakeMove(t, &gameMoves[gamePly]);
  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;
#if TOMDEBUG == 0
  sd = 1;
#endif
  wtm = WHITE;
  ply = OO;
  InitPieceBB();
  NewGame(t);
}

#if TOMDEBUG > 0
void TOMDebug2()
{
    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');
    }
}
#endif

s32 main() {

#if TOMDEBUG > 0
    printf("TOMDEBUG:  %i\n\n", TOMDEBUG);
    TOMDebug2(); // Init 'sd' (Search Depth)
#endif

  t = &thread;

  Initialize();

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

  return 0;
}

Make the following code change (near the top):
TOMDEBUG = 1

Compile and rerun.

Enter "1" to the "SEARCH DEPTH" inquiry.
Type "go".

You should now see the list of generated moves in the order they were generated. Also displayed is the final score value for each move. In addition, the code now keeps track of the "order" in which the moves were searched, and that number is also displayed. So we can see that A2A3 was searched first, and G1H3 was searched last. Finally we see the move played.

And we notice the first bug. If A2A3 was searched first, and all moves have the same score, why wasn't A2A3 chosen as the move to play?

There are several issues here.

Let's first think about the search. A2A3 is searched with a full alph-beta range (-INF, +INF). Qsearch is called and the initial value assigned to alpha is determined by:

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

The material is equal so alpha becomes 0. This is very important to note regarding subsequent Qsearch calls!

Since no captures are found, Qsearch returns 0 for the move A2A3.

The search continues by looking at A2A4. At the Qsearch call, the alpha beta range is (0, +INF). Within Qsearch beta is thus 0, and after calculating

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

...and comparing >= beta, Qsearch IMMEDIATELY returns (as it should) without looking at any captures. It doesn't need to since we now know the move A2A4 cannot beat A2A3. A2A4 could actually be a much worse move than A2A3 but we dont know and don't care. And here is the important part...the move is given the value of beta (0).

So at this point we have 2 moves in the list of generated moves each with the score 0. One of them had a "full" quiesent capture search performed on it, and the other did not.

The search continues with all the other moves, and like A2A4 Qsearch is called with (0, +INF) for each. So every move is given a score of 0. But once again, only the very first move, A2A3, had a Qsearch which examined moves/captures by Black.

The search is complete, and the value for the position is 0, and DoMove is called to play the best move. But it has no information about which move had the "full" Qsearch performed! All it has is the generated list of moves (without the "order:" column). It has no way of knowing that A2A3 was searched first and is the move that should be played.

Hmmm, if only DoMove had the "order:" column, it could look for the highest score, and also look to see which move found it first.

Set "TOMDEBUG = 2", recompile and run. Enter "1" for sd, and enter "go".

The change in code for "TOMDEBUG = 2" is just a few lines of code in DoMove.

If you continue to enter "go" you can begin to see that moves are analyzed in the order you would like, and that scores are given correctly to them. You can also see that the move played is the one that you would expect to be played based on the move ordering described earlier and the value of material on the board following a Qsearch.

The game played is:

1. a3 a5 2. b3 a4 3. bxa4 Rxa4 4. c3 b5 5. d3 c5 6. e3 d5 7. f3 c4 8. dxc4 dxc4 9. Qxd8+

...and here the move played is 9...B5B4 (Illegal!)

There is only 1 legal move in the position, E8D8 (with score 0), yet move B5B4 with score 65535 was played!

[Warning: Entering "go" again is not advised.]

You may want to revisit some of your definitions.

struct Move
s32 score

INF 0x7fff
ILLEGAL 0xffff

s32 is defined as "int". The first range for alpha beta is [-INF, +INF]. It's clear to see that ILLEGAL (0x0000ffff) is GREATER than +INF (0x00007fff).

I've kept the definitions as is, and updated the code in DoMove.

Set TOMDEBUG = 3, recompile, rerun, enter "1" for sd, and enter "go" until 9...E8D8 is played.

You can continue entering moves until both sides start repeating moves.

I've not examined much at sd=2 or sd=3 or higher, but it seems to play properly. Your code currently does not handle stalemate or checkmate so when those are reached bad things will happen.

It's clear that you have spent some time already on Bricabrac. It would be a shame if you gave up too soon.

If you have questions or comments, please let me know.

Kind regards,
Tommy
Hi Tommy,

First let me say that I never expected anyone to do that much work on my behalf, thank you! :D

I will be studying all your solutions and hopefully I will be able to get a handle on the situation. But for right now all I did was set TOMDEBUG to 3 and search depth to 8 just to get a feel how well it was working or not working. It played the following game.


Then I undid all the moves to make sure that there was not any corruption and there was none. That to me is a major victory! All moves played were legal. All moves did not lose any material. Only problem is black failed to regain material when it was on move a few times. Yet the black knight did go after material while the black queen rook just stood there looking at the white queen rook pawn. Still it looks like we are at 99% or better. Most moves were made in anywhere from about one second to about 30 seconds. Some moves took a little longer. Thanks to you my optimism level has increased quite a bit! Maybe now is a good point to work on a perft function to prove the move generation. 8-)

Post Reply