I don't want to give up

[Mike Sherwin]

Well I thought i had found a bug.
In Search() sna (score, move-count, alpha) was being returned without including n from snu. But that change changed nothing as far as I could tell. Also I created the Snu union so I could return a u64 value with the score and the move count. Instead I was returning the structure. So I changed the return value to u64 and return snu; to return snu.snu (or sna.snu). No change in behavior.

So entering go 3 times then putting a break at MakeMove() in Search() and after 21 "f5" the assert() is triggered. So I'll try single stepping after 20 "f5"'.

I think I might have found it ...

In the loop body of Search() you reuse the "snu" variable that has been passed as a parameter to store the return value of the recursive call to Search() itself. This will overwrite the move list length (snu.sns.n) to the value that GenLegalQ() defines. After returning to the caller his move list size has now been modified, and the next call to Sort() may lead to surprising results, especially if the move list size has been increased so that Sort() accesses moves that are out of range.

The solution is simple: use a local "snu2" variable instead of overwriting the function parameter "snu".

I found this by adding a couple of assertions and debugging code, where most of it did not help but adding a function "isValidMoveAddress()" did (the function checks whether the given Move pointer is within the range of the thread structure's "move[]" array).

Hi Sven, Yes I see it now! Thank you. Wow, what a noob mistake on my part.

A few months ago I wrote a very simple real-time space conquest game using QB64. There are always 100 stars but I wanted 200 star names to randomly pick from. When I got to the j's there were not enough real star names that started with j so I named one Jumbo after your engine.

https://www.qb64.org/forum/index.php?to ... #msg113228
The latest version is at the bottom of the first page. If someone tries it and thinks it is fun please leave a comment.

[Sven]

Well I thought i had found a bug.
In Search() sna (score, move-count, alpha) was being returned without including n from snu. But that change changed nothing as far as I could tell. Also I created the Snu union so I could return a u64 value with the score and the move count. Instead I was returning the structure. So I changed the return value to u64 and return snu; to return snu.snu (or sna.snu). No change in behavior.

So entering go 3 times then putting a break at MakeMove() in Search() and after 21 "f5" the assert() is triggered. So I'll try single stepping after 20 "f5"'.

I think I might have found it ...

In the loop body of Search() you reuse the "snu" variable that has been passed as a parameter to store the return value of the recursive call to Search() itself. This will overwrite the move list length (snu.sns.n) to the value that GenLegalQ() defines. After returning to the caller his move list size has now been modified, and the next call to Sort() may lead to surprising results, especially if the move list size has been increased so that Sort() accesses moves that are out of range.

The solution is simple: use a local "snu2" variable instead of overwriting the function parameter "snu".

I found this by adding a couple of assertions and debugging code, where most of it did not help but adding a function "isValidMoveAddress()" did (the function checks whether the given Move pointer is within the range of the thread structure's "move[]" array).

Hi Sven, Yes I see it now! Thank you. Wow, what a noob mistake on my part.

A few months ago I wrote a very simple real-time space conquest game using QB64. There are always 100 stars but I wanted 200 star names to randomly pick from. When I got to the j's there were not enough real star names that started with j so I named one Jumbo after your engine.

Another bug: in Qsearch() the line

Code: Select all

if (move->score == ILLEGAL) continue;

should be changed into

Code: Select all

if (mov->score == ILLEGAL) continue;

since "move" is not the current move but a macro that always resolves to the move entry no. 0 of the current thread's move array (so always the same). This leads to a beta cutoff caused by an illegal move, resulting in other dubious behaviour.

I found it by setting sd to 3.

EDIT: one more note on your move generator function GenLegalQ() - it calls Qsearch() for legality checking, I guess this is an intermediate solution which you will replace by something faster? I see that Qsearch() has an early exit if the enemy king is under attack but you need a full capture generation to reach that point - a simple "does the moving side attack the enemy king?" should be sufficient instead ...

[Mike Sherwin]

Well I thought i had found a bug.
In Search() sna (score, move-count, alpha) was being returned without including n from snu. But that change changed nothing as far as I could tell. Also I created the Snu union so I could return a u64 value with the score and the move count. Instead I was returning the structure. So I changed the return value to u64 and return snu; to return snu.snu (or sna.snu). No change in behavior.

So entering go 3 times then putting a break at MakeMove() in Search() and after 21 "f5" the assert() is triggered. So I'll try single stepping after 20 "f5"'.

I think I might have found it ...

In the loop body of Search() you reuse the "snu" variable that has been passed as a parameter to store the return value of the recursive call to Search() itself. This will overwrite the move list length (snu.sns.n) to the value that GenLegalQ() defines. After returning to the caller his move list size has now been modified, and the next call to Sort() may lead to surprising results, especially if the move list size has been increased so that Sort() accesses moves that are out of range.

The solution is simple: use a local "snu2" variable instead of overwriting the function parameter "snu".

I found this by adding a couple of assertions and debugging code, where most of it did not help but adding a function "isValidMoveAddress()" did (the function checks whether the given Move pointer is within the range of the thread structure's "move[]" array).

Hi Sven, Yes I see it now! Thank you. Wow, what a noob mistake on my part.

A few months ago I wrote a very simple real-time space conquest game using QB64. There are always 100 stars but I wanted 200 star names to randomly pick from. When I got to the j's there were not enough real star names that started with j so I named one Jumbo after your engine.

Another bug: in Qsearch() the line

Code: Select all

if (move->score == ILLEGAL) continue;

should be changed into

Code: Select all

if (mov->score == ILLEGAL) continue;

since "move" is not the current move but a macro that always resolves to the move entry no. 0 of the current thread's move array (so always the same). This leads to a beta cutoff caused by an illegal move, resulting in other dubious behaviour.

I found it by setting sd to 3.

Made the change and set sd (search depth) to 3 and typed go a bunch of times and it works (making sensible moves) so far without crashing. There must be a runaway Qsearch as it is taking way too long at 3 ply sd. But still this is huge, thanks! But, be warned if you do much more I'm going to list you as coauthor!! Actually I would like it if you were coauthor, if you're interested, as you have helped me quite a bit over the years. Just say the word and it is done.

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 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 = 0x000000000000000c;
constexpr auto BATKS = 0x7000000000000000;
constexpr auto BATKL = 0x0c00000000000000;

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, OO, OO, VP, VN, VB, VR, VR, VQ, OO, OO,
                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;
    piece[WHITE] ^= one << H1;
    piece[WHITE] ^= one << F1;
    break;
  case WL:
    ctype = OO;
    board[C1] = WK;
    board[A1] = OO;
    board[D1] = WR;
    piece[WHITE] ^= one << A1;
    piece[WHITE] ^= one << D1;
    break;
  case BS:
    ctype = OO;
    board[G8] = BK;
    board[H8] = OO;
    board[F8] = BR;
    piece[BLACK] ^= one << H8;
    piece[BLACK] ^= one << F8;
    break;
  case BL:
    ctype = OO;
    board[C8] = BK;
    board[A8] = OO;
    board[D8] = BR;
    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;
    piece[WHITE] ^= one << H1;
    piece[WHITE] ^= one << F1;
    break;
  case WL:
    board[C1] = OO;
    board[E1] = WC;
    board[A1] = WRC;
    board[D1] = OO;
    piece[WHITE] ^= one << A1;
    piece[WHITE] ^= one << D1;
    break;
  case BS:
    board[G8] = OO;
    board[E8] = BC;
    board[H8] = BRC;
    board[F8] = OO;
    piece[BLACK] ^= one << H8;
    piece[BLACK] ^= one << F8;
    break;
  case BL:
    board[C8] = OO;
    board[E8] = BC;
    board[A8] = BRC;
    board[D8] = OO;
    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;
            MakeMove(t, m);
            m->score = -Qsearch(t, m + 1, -beta, -alpha, depth);
            TakeBack(t, m);
            if (m->score == ILLEGAL) break;
            if (!depth && m->score >= beta) { snu.sns.score = beta; snu.sns.n = ++n; return snu.snu; }
            if (m->score > score) score = m->score;
            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;
        MakeMove(t, m);
        m->score = -Qsearch(t, m + 1, -beta, -alpha, depth);
        TakeBack(t, m);
        if (!depth && m->score >= beta) { snu.sns.score = beta; snu.sns.n = ++n; return snu.snu; }
        if (m->score > score) score = m->score;
        m->status = false;
        m++;
        n++;
      }
      if (board[A1] == WRC && !(WOCCL & aPieces) && !AtkByBlack(t, WATKL)) {
        m->fs = E1;
        m->ts = C1;
        m->type = WL;
        MakeMove(t, m);
        m->score = -Qsearch(t, m + 1, -beta, -alpha, depth);
        TakeBack(t, m);
        if (!depth && m->score >= beta) { snu.sns.score = beta; snu.sns.n = ++n; return snu.snu; }
        if (m->score > score) score = m->score;
        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;
            MakeMove(t, m);
            m->score = -Qsearch(t, m + 1, -beta, -alpha, depth);
            TakeBack(t, m);
            if (m->score == ILLEGAL) break;
            if (!depth && m->score >= beta) { snu.sns.score = beta; snu.sns.n = ++n; return snu.snu; }
            if (m->score > score) score = m->score;
            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;
        MakeMove(t, m);
        m->score = -Qsearch(t, m + 1, -beta, -alpha, depth);
        TakeBack(t, m);
        if (!depth && m->score >= beta) { snu.sns.score = beta; snu.sns.n = ++n; return snu.snu; }
        if (m->score > score) score = m->score;
        m->status = false;
        m++;
        n++;
      }
      if (board[A8] == BRC && !(BOCCL & aPieces) && !AtkByWhite(t, BATKL)) {
        m->fs = E8;
        m->ts = C8;
        m->type = BL;
        MakeMove(t, m);
        m->score = -Qsearch(t, m + 1, -beta, -alpha, depth);
        TakeBack(t, m);
        if (!depth && m->score >= beta) { snu.sns.score = beta; snu.sns.n = ++n; return snu.snu; }
        if (m->score > score) score = m->score;
        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;
      MakeMove(t, m);
      m->score = -Qsearch(t, m + 1, -beta, -alpha, depth);
      TakeBack(t, m);
      if (m->score == ILLEGAL) continue;
      if (!depth && m->score >= beta) { snu.sns.score = beta; snu.sns.n = ++n; return snu.snu; }
      if (m->score > score) score = m->score;
      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;

  sna.sns.score = alpha;

  snu.snu = GenLegalQ(t, m, alpha, beta, depth);
  if (depth == OO) return snu.snu;
  n = snu.sns.n;
  m = m + n;
  for (i = n; i > 0; i--) {
    mi = Sort(t, m, n);
    MakeMove(t, m - mi);
    snu.snu = Search(t, m, -beta, -alpha, depth - 1);
    snu.sns.score = -snu.sns.score;
    TakeBack(t, m - mi);
    if (snu.sns.score >= beta) { snu.sns.score = beta;  return snu.snu; }
    if (snu.sns.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 = 0;

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

Hi Sven, The legality check does more than legality checking. It scores each move. The idea is since this is done at the leaves anyway doing it all the time does not cost much and gives the added benefit of good move ordering. But if I am wrong about this untested assumption it can be changed later.

[Sven]

As to the speed, see my EDIT in my previous post above ...

Changing the move generator from

Code: Select all

m->score = -Qsearch(t, m + 1, -beta, -alpha);

into something like this:

Code: Select all

s32 KingInCheck(Thread * t, s32 side)
{
    return (side == BLACK) ? AtkByWhite(t, one << king[BLACK]) : AtkByBlack(t, one << king[WHITE]);
}
...
// at several places
m->score = (KingInCheck(t, 1 - wtm)) ? ILLEGAL : 0;

allows to start searching with sd=7 and an acceptable response time but after few plies the engine replies instantly so there are certainly more problems around ... I'll take my sleep now (and choose to stay away from co-authorship ).

[Sven]

Hi Sven, The legality check does more than legality checking. It scores each move. The idea is since this is done at the leaves anyway doing it all the time does not cost much and gives the added benefit of good move ordering. But if I am wrong about this untested assumption it can be changed later.

You are not just "doing it at the leaves" but everywhere. And the major point is, most moves are not illegal so for these the whole Qsearch() is performed. That is, for a full-width node with N legal moves you do N * (MakeMove + Qsearch + TakeBack) before starting any other work.

[Mike Sherwin]

As to the speed, see my EDIT in my previous post above ...

Changing the move generator from

Code: Select all

m->score = -Qsearch(t, m + 1, -beta, -alpha);

into something like this:

Code: Select all

s32 KingInCheck(Thread * t, s32 side)
{
    return (side == BLACK) ? AtkByWhite(t, one << king[BLACK]) : AtkByBlack(t, one << king[WHITE]);
}
...
// at several places
m->score = (KingInCheck(t, 1 - wtm)) ? ILLEGAL : 0;

allows to start searching with sd=7 and an acceptable response time but after few plies the engine replies instantly so there are certainly more problems around ... I'll take my sleep now (and choose to stay away from co-authorship ).

Thanks and sleep well!

[Mike Sherwin]

I found a performance bug. In Search() was this.

snu.snu = GenLegalQ(t, m, alpha, beta, depth);
if (depth == 0) return snu.snu;

Since GenLegalQ() does the work of "1" returning when depth is 0 is not correct. Changing it did make it work a lot faster though it still is not fast. So I've started the work of making it work more like RomiChess.

[TommyTC]

I think I have found a bug in your code.
When the king is in check, your code allows queenside castling.

You probably need to change the following:

From:
constexpr auto WATKL = 0x000000000000000c;
constexpr auto BATKL = 0x0c00000000000000;

To:
constexpr auto WATKL = 0x000000000000001c;
constexpr auto BATKL = 0x1c00000000000000;

This will include the square e1 (and e8) when checking if castling is allowed.

Tommy

[Mike Sherwin]

I think I have found a bug in your code.
When the king is in check, your code allows queenside castling.

You probably need to change the following:

From:
constexpr auto WATKL = 0x000000000000000c;
constexpr auto BATKL = 0x0c00000000000000;

To:
constexpr auto WATKL = 0x000000000000001c;
constexpr auto BATKL = 0x1c00000000000000;

This will include the square e1 (and e8) when checking if castling is allowed.

Tommy

Excellent find, ty!