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
