Chapter One

[Mike Sherwin]

Chapter One is my interpretation of what a modern engine to learn chess programming should be, simple simple simple.

Here are some defines to get started.

Code: Select all

typedef int8_t s08;
typedef uint8_t u08;
typedef int32_t s32;
typedef uint64_t u64;

constexpr u64 one = 1ull;

constexpr s32 valp = 100;
constexpr s32 valn = 290;
constexpr s32 valb = 320;
constexpr s32 valr = 500;
constexpr s32 valq = 960;
constexpr s32 na = 0;

constexpr u64 file_b2_b7 = 0x0002020202020200;
constexpr u64 file_a2_a7 = 0x0001010101010100;
constexpr u64 diag_c2_h7 = 0x0080402010080400;

constexpr u64 occ_w_s = 0x0000000000000060; // occupied white short castling squares
constexpr u64 occ_w_l = 0x000000000000000e;
constexpr u64 occ_b_s = 0x6000000000000000;
constexpr u64 occ_b_l = 0x0e00000000000000;
constexpr u64 atk_w_s = 0x0000000000000070; // attacked white short castling squares
constexpr u64 atk_w_l = 0x000000000000001c;
constexpr u64 atk_b_s = 0x7000000000000000;
constexpr u64 atk_b_l = 0x1c00000000000000;

typedef struct {
	u08 fs; // from square
	u08 ts; // to square
	u08 ft; // from type
	u08 tt; // to type
} Move;

typedef struct {
	u64 epsq;
	u64 sides[2];
	u64 pawns[2];
	u64 knights[2];
	u64 bishops[2];
	u64 rooks[2];
	u64 queens[2];
	u64 kings[2];
	s32 board[64];
	s32 stm; // side to move
	s32 otm; // otherside to move
	s32 ply;
} Thread;

// some defines so t-> does not have to be typed everywhere
#define epsq t->epsq
#define sides t->sides
#define pawns t->pawns
#define knights t->knights
#define bishops t->bishops
#define rooks t->rooks
#define queens t->queens
#define kings t->kings
#define board t->board
#define stm t->stm
#define otm t->otm
#define ply t->ply

enum { EXIT, GETCMD, SEARCH, MOVE, RESIGN };

enum { BLACK, WHITE };

enum {
	WP2, WP3, WP4, WP5, WP6, WP7, WN, WB, WR, Wr, WQ, WK, Wk, // a WK is a king with castling rights, Wk can't castle
	ES,
	BP7, BP6, BP5, BP4, BP3, BP2, BN, BB, BR, Br, BQ, BK, Bk,
	WPd, WPe, WPq, WPn, WPr, WPb, WS, WL, // special case labels to handle some rules more efficiently
	BPd, BPe, BPq, BPn, BPr, BPb, BS, BL
};

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 { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };

enum { FILEa, FILEb, FILEc, FILEd, FILEe, FILEf, FILEg, FILEh };

Some arrays for move generation.

Code: Select all

u64 wPawnAtks[64];
u64 bPawnAtks[64];
u64 knightMvs[64];
u64 kingMvs[64];

u64 aMask[64]; // anti diagonal mask
u64 dMask[64]; diagonal mask
u64 aSubset[64][64]; // anti diagonal subset of possible move bits
u64 dSubset[64][64]; // diagonal Subset of possible move bits
u64 vSubset[64][64]; // vertical Subset of possible move bits
u64 hSubset[64][64]; // horizontal Subset of possible move bits

s32 hShift[64]; // necessary shift for horizontal move gen

The beginning of the engine so far.

Code: Select all

static void Resign() {

}

static void GameMove() {

}

static void MakeMove(Thread* t, Move* m) {
    

}

static void TakeBack(Thread* t, Move* m) {


}

static bool AtkByWhite(Thread* t, u64 bb) {
	u64 atk = 0;
	u64 occ = sides[WHITE] | sides[BLACK];
	while (bb) {
		s32 sq = std::countr_zero(bb);
		bb ^= 1ull << sq;
		atk |= (bPawnAtks[sq] & pawns[WHITE]);
		atk |= (knightMvs[sq] & knights[WHITE]);
		atk |= (kingMvs[sq] & kings[WHITE]);
		atk |= (dSubset[sq][(((occ & dMask[sq]) * file_b2_b7) >> 58)] & (bishops[WHITE] | queens[WHITE]));
		atk |= (aSubset[sq][(((occ & aMask[sq]) * file_b2_b7) >> 58)] & (bishops[WHITE] | queens[WHITE]));
		atk |= (hSubset[sq][(occ >> hShift[sq]) & 63] & (rooks[WHITE] | queens[WHITE]));
		atk |= (vSubset[sq][((((occ >> (sq & 7)) & file_a2_a7) * diag_c2_h7) >> 58)] & (rooks[WHITE] | queens[WHITE]));
	}
	return (atk != 0);
}

static bool AtkByBlack(Thread* t, u64 bb) {
	u64 atk = 0;
	u64 occ = sides[WHITE] | sides[BLACK];
	while (bb) {
		s32 sq = std::countr_zero(bb);
		bb ^= 1ull << sq;
		atk |= (wPawnAtks[sq] & pawns[BLACK]);
		atk |= (knightMvs[sq] & knights[BLACK]);
		atk |= (kingMvs[sq] & kings[BLACK]);
		atk |= (dSubset[sq][(((occ & dMask[sq]) * file_b2_b7) >> 58)] & (bishops[BLACK] | queens[BLACK]));
		atk |= (aSubset[sq][(((occ & aMask[sq]) * file_b2_b7) >> 58)] & (bishops[BLACK] | queens[BLACK]));
		atk |= (hSubset[sq][(occ >> hShift[sq]) & 63] & (rooks[BLACK] | queens[BLACK]));
		atk |= (vSubset[sq][((((occ >> (sq & 7)) & file_a2_a7) * diag_c2_h7) >> 58)] & (rooks[BLACK] | queens[BLACK]));
	}
	return (atk != 0);
}

static s32 GenAllMoves(Thread* t, u64* bb) {
	u64 atk = 0;
	u08 fs, ft;

	u64 friends = sides[stm];
	u64 enemies = sides[otm];
	u64 occupied = friends | enemies;
	u64 empty = ~occupied;
	u64 notme = ~friends;

	do {
		fs = std::countr_zero(friends);
		friends ^= 1ull << fs;
		ft = board[fs];
		switch (ft) {
		case WP2:
			atk |= bb[fs] = wPawnAtks[fs] & enemies;
			bb[fs] |= (one << (fs + 8)) & empty;
			bb[fs] |= (bb[fs] << 8) & (one << (fs + 16)) & empty;
			break;
		case WP3: case WP4: case WP6: case WP7:
			atk |= bb[fs] = wPawnAtks[fs] & enemies;
			bb[fs] |= (one << (fs + 8)) & empty;
			break;
		case WP5:
			atk |= bb[fs] = wPawnAtks[fs] & (enemies | epsq);
			bb[fs] |= (one << (fs + 8)) & empty;
			break;
		case WN: case BN:
			atk |= bb[fs] = knightMvs[fs] & notme;
			break;
		case WB: case BB:
			atk |= bb[fs] = (
				dSubset[fs][(((occupied & dMask[fs]) * file_b2_b7) >> 58)] |
				aSubset[fs][(((occupied & aMask[fs]) * file_b2_b7) >> 58)]
				) & notme;
			break;
		case WR: case Wr: case BR: case Br:
			atk |= bb[fs] = (
				hSubset[fs][(occupied >> hShift[fs]) & 63] |
				vSubset[fs][((((occupied >> (fs & 7)) & file_a2_a7) * diag_c2_h7) >> 58)]
				) & notme;
			break;
		case WQ: case BQ:
			atk |= bb[fs] = (
				dSubset[fs][(((occupied & dMask[fs]) * file_b2_b7) >> 58)] |
				aSubset[fs][(((occupied & aMask[fs]) * file_b2_b7) >> 58)] |
				hSubset[fs][(occupied >> hShift[fs]) & 63] |
				vSubset[fs][((((occupied >> (fs & 7)) & file_a2_a7) * diag_c2_h7) >> 58)]
				) & notme;
			break;
		case WK:
			atk |= bb[fs] = kingMvs[fs] & notme;
			bb[fs] |= ((u64)((board[h1] == WR) & !(occupied & occ_w_s) & !AtkByBlack(t, atk_w_s))) * g1;
			bb[fs] |= ((u64)((board[a1] == WR) & !(occupied & occ_w_l) & !AtkByBlack(t, atk_w_l))) * c1;
			break;
		case Wk:
			atk |= bb[fs] = kingMvs[fs] & notme;
			break;
		case BK:
			atk |= bb[fs] = kingMvs[fs] & notme;
			bb[fs] |= ((u64)((board[h8] == BR) & !(occupied & occ_b_s) & !AtkByWhite(t, atk_b_s))) * g8;
			bb[fs] |= ((u64)((board[a8] == BR) & !(occupied & occ_b_l) & !AtkByWhite(t, atk_b_l))) * c8;
			break;
		case Bk:
			atk |= bb[fs] = kingMvs[fs] & notme;
			break;
		}
	} while (friends);

}

static void StartSearch() {

}

static void GetCommand() {

}

static void NewGame() {
	mode = GETCMD;
}

static void InitBitboards() {
	s08 sq, ts, x, y, dx, dy;
	u64 occ;
	for (sq = a1; sq <= h8; sq++) {
		x = sq & 7;
		y = sq >> 3;

		// pawns
		if (sq >= a2 && sq <= h7) {
			wPawnAtks[sq] = ((u64)(x > FILEa) << (sq + 7)) | ((u64)(x < FILEh) << (sq + 9));
			bPawnAtks[sq] = ((u64)(x > FILEa) << (sq - 9)) | ((u64)(x < FILEh) << (sq - 7));
		}

		// knights
		knightMvs[sq] =
			((u64)(x > FILEb && y < RANK8) << (sq + 06)) |
			((u64)(x > FILEa && y < RANK7) << (sq + 15)) |
			((u64)(x < FILEh && y < RANK7) << (sq + 17)) |
			((u64)(x < FILEg && y < RANK8) << (sq + 10)) |
			((u64)(x < FILEg && y > RANK1) << (sq - 06)) |
			((u64)(x < FILEh && y > RANK2) << (sq - 15)) |
			((u64)(x > FILEa && y > RANK2) << (sq - 17)) |
			((u64)(x > FILEb && y > RANK1) << (sq - 10));

		// kings
		kingMvs[sq] =
			((u64)(x > FILEa) << (sq - 1)) |
			((u64)(x < FILEh) << (sq + 1)) |
			((u64)(y < RANK8) << (sq + 8)) |
			((u64)(y > RANK1) << (sq - 8)) |
			((u64)(x > FILEa && y < RANK8) << (sq + 7)) |
			((u64)(x < FILEh && y < RANK8) << (sq + 9)) |
			((u64)(x < FILEh && y > RANK1) << (sq - 7)) |
			((u64)(x > FILEa && y > RANK1) << (sq - 9));

		// diagonals
		for (ts = sq + 9, dx = x + 1, dy = y + 1; dx < FILEh && dy < RANK8; dMask[sq] |= 1ull << ts, ts += 9, dx++, dy++);
		for (ts = sq - 9, dx = x - 1, dy = y - 1; dx > FILEa && dy > RANK1; dMask[sq] |= 1ull << ts, ts -= 9, dx--, dy--);

		// anti diagonals
		for (ts = sq + 7, dx = x - 1, dy = y + 1; dx > FILEa && dy < RANK8; aMask[sq] |= 1ull << ts, ts += 7, dx--, dy++);
		for (ts = sq - 7, dx = x + 1, dy = y - 1; dx < FILEh && dy > RANK1; aMask[sq] |= 1ull << ts, ts -= 7, dx++, dy--);

		// diagonal indexes
		for (u64 index = 0; index < 64; index++) {
			dSubset[sq][index] = 0;
			occ = index << 1;
			if ((sq & 7) != FILEh && (sq >> 3) != RANK8) {
				for (ts = sq + 9; ; ts += 9) {
					dSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEh || (ts >> 3) == RANK8) break;
				}
			}
			if ((sq & 7) != FILEa && (sq >> 3) != RANK1) {
				for (ts = sq - 9; ; ts -= 9) {
					dSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEa || (ts >> 3) == RANK1) break;
				}
			}
		}

		// anti diagonal indexes
		for (u64 index = 0; index < 64; index++) {
			aSubset[sq][index] = 0;
			occ = index << 1;
			if ((sq & 7) != FILEa && (sq >> 3) != RANK8) {
				for (ts = sq + 7; ; ts += 7) {
					aSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEa || (ts >> 3) == RANK8) break;
				}
			}
			if ((sq & 7) != FILEh && (sq >> 3) != RANK1) {
				for (ts = sq - 7; ; ts -= 7) {
					aSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEh || (ts >> 3) == RANK1) break;
				}
			}
		}

		// vertical indexes
		for (u64 index = 0; index < 64; index++) {
			vSubset[sq][index] = 0;
			uint64_t blockers = 0;
			for (int i = 0; i <= 5; i++) {
				if (index & (1ull << i)) {
					blockers |= (1ull << (((5 - i) << 3) + 8));
				}
			}
			if ((sq >> 3) != RANK8) {
				for (ts = sq + 8; ; ts += 8) {
					vSubset[sq][index] |= (1ull << ts);
					if (blockers & (1ull << (ts - (ts & 7)))) break;
					if ((ts >> 3) == RANK8) break;
				}
			}
			if ((sq >> 3) != RANK1) {
				for (ts = sq - 8; ; ts -= 8) {
					vSubset[sq][index] |= (1ull << ts);
					if (blockers & (1ull << (ts - (ts & 7)))) break;
					if ((ts >> 3) == RANK1) break;
				}
			}
		}

		// horizontal indexes
		for (u64 index = 0; index < 64; index++) {
			hSubset[sq][index] = 0;
			occ = index << 1;
			if ((sq & 7) != FILEh) {
				for (ts = sq + 1; ; ts += 1) {
					hSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEh) break;
				}
			}
			if ((sq & 7) != FILEa) {
				for (ts = sq - 1; ; ts -= 1) {
					hSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEa) break;
				}
			}
		}

		// horizontal shift
		hShift[sq] = (sq & 56) + 1;
	}
}

static void Initialize() {
	InitBitboards();
	NewGame();
}

s32 main() {

	Initialize();

	while (mode != EXIT) {
		if (mode == GETCMD) GetCommand();
		if (mode == SEARCH) StartSearch();
		if (mode == MOVE) GameMove();
		if (mode == RESIGN) Resign();
	}

}

The move generator does not make a move list. It is designed with the philosophy, "never do anything until you have to. It only generates move bitboards. We also have the philosophy that we return legal or not legal at the end because the vast majority of positions will be legal. The same approach is used for the attacked by functions. Multiple squares can be passed to the attacked by functions. After the move bits have been generated the move ordering code turns the move bits into moves as needed. That means most of the time move bits never have to be spun into a move list. When hash moves are played but does not cutoff we just have to delete its ts bit from the move bits for that square so it won't be generated again.

[Mike Sherwin]

Chapter One is my interpretation of what a modern engine to learn chess programming should be, simple simple simple.

Here are some defines to get started.

Code: Select all

typedef int8_t s08;
typedef uint8_t u08;
typedef int32_t s32;
typedef uint64_t u64;

constexpr u64 one = 1ull;

constexpr s32 valp = 100;
constexpr s32 valn = 290;
constexpr s32 valb = 320;
constexpr s32 valr = 500;
constexpr s32 valq = 960;
constexpr s32 na = 0;

constexpr u64 file_b2_b7 = 0x0002020202020200;
constexpr u64 file_a2_a7 = 0x0001010101010100;
constexpr u64 diag_c2_h7 = 0x0080402010080400;

constexpr u64 occ_w_s = 0x0000000000000060; // occupied white short castling squares
constexpr u64 occ_w_l = 0x000000000000000e;
constexpr u64 occ_b_s = 0x6000000000000000;
constexpr u64 occ_b_l = 0x0e00000000000000;
constexpr u64 atk_w_s = 0x0000000000000070; // attacked white short castling squares
constexpr u64 atk_w_l = 0x000000000000001c;
constexpr u64 atk_b_s = 0x7000000000000000;
constexpr u64 atk_b_l = 0x1c00000000000000;

typedef struct {
	u08 fs; // from square
	u08 ts; // to square
	u08 ft; // from type
	u08 tt; // to type
} Move;

typedef struct {
	u64 epsq;
	u64 sides[2];
	u64 pawns[2];
	u64 knights[2];
	u64 bishops[2];
	u64 rooks[2];
	u64 queens[2];
	u64 kings[2];
	s32 board[64];
	s32 stm; // side to move
	s32 otm; // otherside to move
	s32 ply;
} Thread;

// some defines so t-> does not have to be typed everywhere
#define epsq t->epsq
#define sides t->sides
#define pawns t->pawns
#define knights t->knights
#define bishops t->bishops
#define rooks t->rooks
#define queens t->queens
#define kings t->kings
#define board t->board
#define stm t->stm
#define otm t->otm
#define ply t->ply

enum { EXIT, GETCMD, SEARCH, MOVE, RESIGN };

enum { BLACK, WHITE };

enum {
	WP2, WP3, WP4, WP5, WP6, WP7, WN, WB, WR, Wr, WQ, WK, Wk, // a WK is a king with castling rights, Wk can't castle
	ES,
	BP7, BP6, BP5, BP4, BP3, BP2, BN, BB, BR, Br, BQ, BK, Bk,
	WPd, WPe, WPq, WPn, WPr, WPb, WS, WL, // special case labels to handle some rules more efficiently
	BPd, BPe, BPq, BPn, BPr, BPb, BS, BL
};

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 { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };

enum { FILEa, FILEb, FILEc, FILEd, FILEe, FILEf, FILEg, FILEh };

Some arrays for move generation.

Code: Select all

u64 wPawnAtks[64];
u64 bPawnAtks[64];
u64 knightMvs[64];
u64 kingMvs[64];

u64 aMask[64]; // anti diagonal mask
u64 dMask[64]; diagonal mask
u64 aSubset[64][64]; // anti diagonal subset of possible move bits
u64 dSubset[64][64]; // diagonal Subset of possible move bits
u64 vSubset[64][64]; // vertical Subset of possible move bits
u64 hSubset[64][64]; // horizontal Subset of possible move bits

s32 hShift[64]; // necessary shift for horizontal move gen

The beginning of the engine so far.

Code: Select all

static void Resign() {

}

static void GameMove() {

}

static void MakeMove(Thread* t, Move* m) {
    

}

static void TakeBack(Thread* t, Move* m) {


}

static bool AtkByWhite(Thread* t, u64 bb) {
	u64 atk = 0;
	u64 occ = sides[WHITE] | sides[BLACK];
	while (bb) {
		s32 sq = std::countr_zero(bb);
		bb ^= 1ull << sq;
		atk |= (bPawnAtks[sq] & pawns[WHITE]);
		atk |= (knightMvs[sq] & knights[WHITE]);
		atk |= (kingMvs[sq] & kings[WHITE]);
		atk |= (dSubset[sq][(((occ & dMask[sq]) * file_b2_b7) >> 58)] & (bishops[WHITE] | queens[WHITE]));
		atk |= (aSubset[sq][(((occ & aMask[sq]) * file_b2_b7) >> 58)] & (bishops[WHITE] | queens[WHITE]));
		atk |= (hSubset[sq][(occ >> hShift[sq]) & 63] & (rooks[WHITE] | queens[WHITE]));
		atk |= (vSubset[sq][((((occ >> (sq & 7)) & file_a2_a7) * diag_c2_h7) >> 58)] & (rooks[WHITE] | queens[WHITE]));
	}
	return (atk != 0);
}

static bool AtkByBlack(Thread* t, u64 bb) {
	u64 atk = 0;
	u64 occ = sides[WHITE] | sides[BLACK];
	while (bb) {
		s32 sq = std::countr_zero(bb);
		bb ^= 1ull << sq;
		atk |= (wPawnAtks[sq] & pawns[BLACK]);
		atk |= (knightMvs[sq] & knights[BLACK]);
		atk |= (kingMvs[sq] & kings[BLACK]);
		atk |= (dSubset[sq][(((occ & dMask[sq]) * file_b2_b7) >> 58)] & (bishops[BLACK] | queens[BLACK]));
		atk |= (aSubset[sq][(((occ & aMask[sq]) * file_b2_b7) >> 58)] & (bishops[BLACK] | queens[BLACK]));
		atk |= (hSubset[sq][(occ >> hShift[sq]) & 63] & (rooks[BLACK] | queens[BLACK]));
		atk |= (vSubset[sq][((((occ >> (sq & 7)) & file_a2_a7) * diag_c2_h7) >> 58)] & (rooks[BLACK] | queens[BLACK]));
	}
	return (atk != 0);
}

static s32 GenAllMoves(Thread* t, u64* bb) {
	u64 atk = 0;
	u08 fs, ft;

	u64 friends = sides[stm];
	u64 enemies = sides[otm];
	u64 occupied = friends | enemies;
	u64 empty = ~occupied;
	u64 notme = ~friends;

	do {
		fs = std::countr_zero(friends);
		friends ^= 1ull << fs;
		ft = board[fs];
		switch (ft) {
		case WP2:
			atk |= bb[fs] = wPawnAtks[fs] & enemies;
			bb[fs] |= (one << (fs + 8)) & empty;
			bb[fs] |= (bb[fs] << 8) & (one << (fs + 16)) & empty;
			break;
		case WP3: case WP4: case WP6: case WP7:
			atk |= bb[fs] = wPawnAtks[fs] & enemies;
			bb[fs] |= (one << (fs + 8)) & empty;
			break;
		case WP5:
			atk |= bb[fs] = wPawnAtks[fs] & (enemies | epsq);
			bb[fs] |= (one << (fs + 8)) & empty;
			break;
		case WN: case BN:
			atk |= bb[fs] = knightMvs[fs] & notme;
			break;
		case WB: case BB:
			atk |= bb[fs] = (
				dSubset[fs][(((occupied & dMask[fs]) * file_b2_b7) >> 58)] |
				aSubset[fs][(((occupied & aMask[fs]) * file_b2_b7) >> 58)]
				) & notme;
			break;
		case WR: case Wr: case BR: case Br:
			atk |= bb[fs] = (
				hSubset[fs][(occupied >> hShift[fs]) & 63] |
				vSubset[fs][((((occupied >> (fs & 7)) & file_a2_a7) * diag_c2_h7) >> 58)]
				) & notme;
			break;
		case WQ: case BQ:
			atk |= bb[fs] = (
				dSubset[fs][(((occupied & dMask[fs]) * file_b2_b7) >> 58)] |
				aSubset[fs][(((occupied & aMask[fs]) * file_b2_b7) >> 58)] |
				hSubset[fs][(occupied >> hShift[fs]) & 63] |
				vSubset[fs][((((occupied >> (fs & 7)) & file_a2_a7) * diag_c2_h7) >> 58)]
				) & notme;
			break;
		case WK:
			atk |= bb[fs] = kingMvs[fs] & notme;
			bb[fs] |= ((u64)((board[h1] == WR) & !(occupied & occ_w_s) & !AtkByBlack(t, atk_w_s))) * g1;
			bb[fs] |= ((u64)((board[a1] == WR) & !(occupied & occ_w_l) & !AtkByBlack(t, atk_w_l))) * c1;
			break;
		case Wk:
			atk |= bb[fs] = kingMvs[fs] & notme;
			break;
		case BK:
			atk |= bb[fs] = kingMvs[fs] & notme;
			bb[fs] |= ((u64)((board[h8] == BR) & !(occupied & occ_b_s) & !AtkByWhite(t, atk_b_s))) * g8;
			bb[fs] |= ((u64)((board[a8] == BR) & !(occupied & occ_b_l) & !AtkByWhite(t, atk_b_l))) * c8;
			break;
		case Bk:
			atk |= bb[fs] = kingMvs[fs] & notme;
			break;
		}
	} while (friends);
        return (!(atk & kings[otm]));
}

static void StartSearch() {

}

static void GetCommand() {

}

static void NewGame() {
	mode = GETCMD;
}

static void InitBitboards() {
	s08 sq, ts, x, y, dx, dy;
	u64 occ;
	for (sq = a1; sq <= h8; sq++) {
		x = sq & 7;
		y = sq >> 3;

		// pawns
		if (sq >= a2 && sq <= h7) {
			wPawnAtks[sq] = ((u64)(x > FILEa) << (sq + 7)) | ((u64)(x < FILEh) << (sq + 9));
			bPawnAtks[sq] = ((u64)(x > FILEa) << (sq - 9)) | ((u64)(x < FILEh) << (sq - 7));
		}

		// knights
		knightMvs[sq] =
			((u64)(x > FILEb && y < RANK8) << (sq + 06)) |
			((u64)(x > FILEa && y < RANK7) << (sq + 15)) |
			((u64)(x < FILEh && y < RANK7) << (sq + 17)) |
			((u64)(x < FILEg && y < RANK8) << (sq + 10)) |
			((u64)(x < FILEg && y > RANK1) << (sq - 06)) |
			((u64)(x < FILEh && y > RANK2) << (sq - 15)) |
			((u64)(x > FILEa && y > RANK2) << (sq - 17)) |
			((u64)(x > FILEb && y > RANK1) << (sq - 10));

		// kings
		kingMvs[sq] =
			((u64)(x > FILEa) << (sq - 1)) |
			((u64)(x < FILEh) << (sq + 1)) |
			((u64)(y < RANK8) << (sq + 8)) |
			((u64)(y > RANK1) << (sq - 8)) |
			((u64)(x > FILEa && y < RANK8) << (sq + 7)) |
			((u64)(x < FILEh && y < RANK8) << (sq + 9)) |
			((u64)(x < FILEh && y > RANK1) << (sq - 7)) |
			((u64)(x > FILEa && y > RANK1) << (sq - 9));

		// diagonals
		for (ts = sq + 9, dx = x + 1, dy = y + 1; dx < FILEh && dy < RANK8; dMask[sq] |= 1ull << ts, ts += 9, dx++, dy++);
		for (ts = sq - 9, dx = x - 1, dy = y - 1; dx > FILEa && dy > RANK1; dMask[sq] |= 1ull << ts, ts -= 9, dx--, dy--);

		// anti diagonals
		for (ts = sq + 7, dx = x - 1, dy = y + 1; dx > FILEa && dy < RANK8; aMask[sq] |= 1ull << ts, ts += 7, dx--, dy++);
		for (ts = sq - 7, dx = x + 1, dy = y - 1; dx < FILEh && dy > RANK1; aMask[sq] |= 1ull << ts, ts -= 7, dx++, dy--);

		// diagonal indexes
		for (u64 index = 0; index < 64; index++) {
			dSubset[sq][index] = 0;
			occ = index << 1;
			if ((sq & 7) != FILEh && (sq >> 3) != RANK8) {
				for (ts = sq + 9; ; ts += 9) {
					dSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEh || (ts >> 3) == RANK8) break;
				}
			}
			if ((sq & 7) != FILEa && (sq >> 3) != RANK1) {
				for (ts = sq - 9; ; ts -= 9) {
					dSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEa || (ts >> 3) == RANK1) break;
				}
			}
		}

		// anti diagonal indexes
		for (u64 index = 0; index < 64; index++) {
			aSubset[sq][index] = 0;
			occ = index << 1;
			if ((sq & 7) != FILEa && (sq >> 3) != RANK8) {
				for (ts = sq + 7; ; ts += 7) {
					aSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEa || (ts >> 3) == RANK8) break;
				}
			}
			if ((sq & 7) != FILEh && (sq >> 3) != RANK1) {
				for (ts = sq - 7; ; ts -= 7) {
					aSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEh || (ts >> 3) == RANK1) break;
				}
			}
		}

		// vertical indexes
		for (u64 index = 0; index < 64; index++) {
			vSubset[sq][index] = 0;
			uint64_t blockers = 0;
			for (int i = 0; i <= 5; i++) {
				if (index & (1ull << i)) {
					blockers |= (1ull << (((5 - i) << 3) + 8));
				}
			}
			if ((sq >> 3) != RANK8) {
				for (ts = sq + 8; ; ts += 8) {
					vSubset[sq][index] |= (1ull << ts);
					if (blockers & (1ull << (ts - (ts & 7)))) break;
					if ((ts >> 3) == RANK8) break;
				}
			}
			if ((sq >> 3) != RANK1) {
				for (ts = sq - 8; ; ts -= 8) {
					vSubset[sq][index] |= (1ull << ts);
					if (blockers & (1ull << (ts - (ts & 7)))) break;
					if ((ts >> 3) == RANK1) break;
				}
			}
		}

		// horizontal indexes
		for (u64 index = 0; index < 64; index++) {
			hSubset[sq][index] = 0;
			occ = index << 1;
			if ((sq & 7) != FILEh) {
				for (ts = sq + 1; ; ts += 1) {
					hSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEh) break;
				}
			}
			if ((sq & 7) != FILEa) {
				for (ts = sq - 1; ; ts -= 1) {
					hSubset[sq][index] |= (1ull << ts);
					if (occ & (1ull << (ts & 7))) break;
					if ((ts & 7) == FILEa) break;
				}
			}
		}

		// horizontal shift
		hShift[sq] = (sq & 56) + 1;
	}
}

static void Initialize() {
	InitBitboards();
	NewGame();
}

s32 main() {

	Initialize();

	while (mode != EXIT) {
		if (mode == GETCMD) GetCommand();
		if (mode == SEARCH) StartSearch();
		if (mode == MOVE) GameMove();
		if (mode == RESIGN) Resign();
	}

}

The move generator does not make a move list. It is designed with the philosophy, "never do anything until you have to. It only generates move bitboards. We also have the philosophy that we return legal or not legal at the end because the vast majority of positions will be legal. The same approach is used for the attacked by functions. Multiple squares can be passed to the attacked by functions. After the move bits have been generated the move ordering code turns the move bits into moves as needed. That means most of the time move bits never have to be spun into a move list. When hash moves are played but does not cutoff we just have to delete its ts bit from the move bits for that square so it won't be generated again.

[PK]

My theory is that "a modern engine to learn chess programming" would be influenced by what new programmers are taught, for better or worse. In best case, it would be C++ that looks like Java. At some stage someone would say thigs like "hide that bitboard code in a class, nobody wants to see that on full display", perhaps adding "oh, and add some unit tests in case somebody wants to change it" (the contradiction between these two sentences is deliberate). Or perhaps you would hear "use full words instead of abbreviations in variable names, someone will need to read that code when you get fired" In other words, it would look sobloated.

[Bo Persson]

Or perhaps you would hear "use full words instead of abbreviations in variable names

Yes. As a rule of thumb, when you have to comment what a variable really means, you could just choose a better name.

Code: Select all

u08 tt; // to type

vs

Code: Select all

u08 to_type;

[Mike Sherwin]

MakMove() has just been completed.

Some notes:
-- The code is optimized for captures because ~85% to ~90% of all moves are captures in the search considering Qsearch().
When a non capture occurs nothing is changed.
-- It looks like a very long function but the amount of code executed every call is very small. Let's look at one case.

case WP5: // pawn that may be able to capture en-passant
sq = m->ts - ((epsq == (one << m->ts)) * 8); // sq sets to the ts or to the capture square of the ep-pawn
*types[board[sq]] ^= one << sq; // removes the ep-pawn's (or other type) bit from pawns[BLACK]
sides[BLACK] ^= (sides[BLACK] & one << sq) << sq; // removes it from sides[BLACK]
mat[otm] -= material[board[sq]]; // if no capture subtracts zero
board[m->fs] = ES; // empty square
board[m->ts] = WP6; // places a WP6 on the ts
pawns[WHITE] ^= (one << m->fs | one << m->ts); // one is defined as 1ull
sides[WHITE] ^= (one << m->fs | one << m->ts);
break;

Code: Select all

	
static void MakeMove(Thread* t, Move* m) {
	s32 sq = 0;
	switch (m->ft) {
	case WP2:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = WP3 + (m->ts - m->fs == 16);
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		sides[BLACK] ^= one << m->ts;
		epsq = (u64)(m->ts - m->fs == 16) << (m->fs + 8);
		break;
	case WP3: case WP4: case WP6:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = m->ft + 1;
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		break;
	case WP5:
		sq = m->ts - ((epsq == (one << m->ts)) * 8);
		*types[board[sq]] ^= one << sq;
		sides[BLACK] ^= (sides[BLACK] & one << sq) << sq;
		mat[otm] -= material[board[sq]];
		board[m->fs] = ES;
		board[m->ts] = WP6;
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		break;
	case WP7:
		// can't get here
		break;
	case WPq:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = WQ;
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		queens[WHITE] ^= one << m->ts;
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		break;
	case WPn:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = WN;
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		knights[WHITE] ^= one << m->ts;
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		break;
	case WPr:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = Wr;
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		rooks[WHITE] ^= one << m->ts;
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		break;
	case WPb:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = WB;
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		bishops[WHITE] ^= one << m->ts;
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		break;
	case BP7:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = BP6 + (m->fs - m->ts == 16);
		pawns[BLACK] ^= (one << m->fs | one << m->ts);
		sides[BLACK] ^= (one << m->fs | one << m->ts);
		epsq = (u64)(m->fs - m->ts == 16) << (m->fs - 8);
		break;
	case BP6: case BP5: case BP3:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = BP6 + 1;
		pawns[BLACK] ^= (one << m->fs | one << m->ts);
		sides[BLACK] ^= (one << m->fs | one << m->ts);
		break;
	case BP4:
		sq = m->ts + ((epsq == (one << m->ts)) * 8);
		*types[board[sq]] ^= one << sq;
		sides[BLACK] ^= (sides[BLACK] & one << sq) << sq;
		mat[otm] -= material[board[sq]];
		board[m->fs] = ES;
		board[m->ts] = BP3;
		pawns[BLACK] ^= (one << m->fs | one << m->ts);
		sides[BLACK] ^= (one << m->fs | one << m->ts);
		break;
	case BP2:
		// can't get here
		break;
	case BPq:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = BQ;
		pawns[BLACK] ^= (one << m->fs | one << m->ts);
		queens[BLACK] ^= one << m->ts;
		sides[BLACK] ^= (one << m->fs | one << m->ts);
		break;
	case BPn:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = BN;
		pawns[BLACK] ^= (one << m->fs | one << m->ts);
		knights[BLACK] ^= one << m->ts;
		sides[BLACK] ^= (one << m->fs | one << m->ts);
		break;
	case BPr:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = Br;
		pawns[BLACK] ^= (one << m->fs | one << m->ts);
		rooks[BLACK] ^= one << m->ts;
		sides[BLACK] ^= (one << m->fs | one << m->ts);
		break;
	case BPb:
		*types[m->tt] ^= one << m->ts;
		sides[BLACK] ^= (sides[BLACK] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = BB;
		pawns[BLACK] ^= (one << m->fs | one << m->ts);
		bishops[BLACK] ^= one << m->ts;
		sides[BLACK] ^= (one << m->fs | one << m->ts);
		break;
	case WN: case BN:
		*types[m->tt] ^= one << m->ts;
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = m->ft;
		knights[stm] ^= (one << m->fs | one << m->ts);
		sides[stm] ^= (one << m->fs | one << m->ts);
		break;
	case WB: case BB:
		*types[m->tt] ^= one << m->ts;
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = m->ft;
		bishops[stm] ^= (one << m->fs | one << m->ts);
		sides[stm] ^= (one << m->fs | one << m->ts);
		break;
	case WR: case BR:
		*types[m->tt] ^= one << m->ts;
		mat[otm] -= material[m->tt];
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		board[m->fs] = ES;
		board[m->ts] = m->ft + 1;
		rooks[stm] ^= (one << m->fs | one << m->ts);
		sides[stm] ^= (one << m->fs | one << m->ts);
		break;
	case Wr: case Br:
		*types[m->tt] ^= one << m->ts;
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = m->ft;
		rooks[stm] ^= (one << m->fs | one << m->ts);
		sides[stm] ^= (one << m->fs | one << m->ts);
		break;
	case WQ: case BQ:
		*types[m->tt] ^= one << m->ts;
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = m->ft;
		queens[stm] ^= (one << m->fs | one << m->ts);
		sides[stm] ^= (one << m->fs | one << m->ts);
		break;
	case WK: case BK:
		*types[m->tt] ^= one << m->ts;
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = m->ft + 1;
		kings[stm] ^= (one << m->fs | one << m->ts);
		sides[stm] ^= (one << m->fs | one << m->ts);
		break;
	case Wk: case Bk:
		*types[m->tt] ^= one << m->ts;
		sides[otm] ^= (sides[otm] & one << m->ts) << m->ts;
		mat[otm] -= material[m->tt];
		board[m->fs] = ES;
		board[m->ts] = m->ft;
		kings[stm] ^= (one << m->fs | one << m->ts);
		sides[stm] ^= (one << m->fs | one << m->ts);
		break;
	case WS:
		board[e1] = ES;
		board[g1] = Wk;
		kings[WHITE] ^= (one << e1 | one << g1);
		sides[WHITE] ^= (one << e1 | one << g1);
		board[h1] = ES;
		board[f1] = Wr;
		rooks[WHITE] ^= (one << h1 | one << f1);
		sides[WHITE] ^= (one << h1 | one << f1);
		break;
	case WL:
		board[e1] = ES;
		board[c1] = Wk;
		kings[WHITE] ^= (one << e1 | one << c1);
		sides[WHITE] ^= (one << e1 | one << c1);
		board[a1] = ES;
		board[d1] = Wr;
		rooks[WHITE] ^= (one << a1 | one << d1);
		sides[WHITE] ^= (one << a1 | one << d1);
		break;
	case BS:
		board[e8] = ES;
		board[g8] = Bk;
		kings[BLACK] ^= (one << e8 | one << g8);
		sides[BLACK] ^= (one << e8 | one << g8);
		board[h8] = ES;
		board[f8] = Br;
		rooks[BLACK] ^= (one << h8 | one << f8);
		sides[BLACK] ^= (one << h8 | one << f8);
		break;
	case BL:
		board[e8] = ES;
		board[c8] = Bk;
		kings[BLACK] ^= (one << e8 | one << c8);
		sides[BLACK] ^= (one << e8 | one << c8);
		board[a8] = ES;
		board[d8] = Br;
		rooks[BLACK] ^= (one << a8 | one << d8);
		sides[BLACK] ^= (one << a8 | one << d8);
		break;
	}
	ply++;
	otm = stm;
	stm = 1 - stm;
}

All that needs to be done before a simple search can be written is TakeBack(). I'm trying to decide between a copy and forget method or one similar to MakeMove() that undoes everything. I have never done a copy and forget method before so I'm not sure how to go about that. I have to give it some thought.

[Mike Sherwin]

I added GenCaptures() and did a little cleanup of the code.
https://www.mediafire.com/file/eiqlx7ih ... 1.cpp/file

[Mike Sherwin]

Correcting an oversight. I forgot to add the following lines to WP5 and BP4.

m->tt = board[sq];
board[sq] = ES;

This is needed because the captured piece may not be on the ts. Note: sq and ts may be the same but in case of a cep they are not the same.

Later today I should have TakeBack() finished.

Also in the Thread struct I had to change U64 epsq; to U64 epsq[100];.

[Mike Sherwin]

My brain was not functioning very well yesterday as I see now that I made numerous blunders in the code. Sorry to those few that did download the source. Here is some corrected code to show how it works.

Code: Select all

// this is a pawn on the 5th rank that may be able to capture en-passant
// it is not known if this is a move or a capture or an ep capture
	case WP5:
	
// first we get the normal sq (ts) or we get the cep sq m->ts - (0 * 8) or m->ts - (1 * 8)	
		s32 sq = m->ts - ((epsq[ply] == (one << m->ts)) * 8);
		
// then we get what is at board[sq] and assign it to m->tt		
		m->tt = board[sq];
		
// board[sq] is cleared no matter what is there		
		board[sq] = ES;
		
// *types indexed by m->tt points to one of the piece types like pawns[BLACK] or dummy if it is not a capture
// if it is a capture then the bit for that type is zeroed	 if not then dummy is written to which has no effect	
		*types[m->tt] ^= (u64)(m->tt != ES) << sq;
		
// if not a capture (u64)(0) << sq has no effect		
		sides[BLACK] ^= (u64)(m->tt != ES) << sq;
		
// the material for BLACK is updated by the value of the to-type		
		mat[BLACK] -= material[m->tt];
		
// the from square is emptied		
		board[m->fs] = ES;
		
// the WP5 pawn becomes a WP6 pawn and placed on its new square		
		board[m->ts] = WP6;
		
// the pawns[WHITE] and sides[WHITE] are updated		
		pawns[WHITE] ^= (one << m->fs | one << m->ts);
		sides[WHITE] ^= (one << m->fs | one << m->ts);
		break;

Let me know if you see any mistakes in this code. I think I got it right this time but I never know until debugging is done.
The most cool thing about this code is that it never "knows" if it is a move, a normal capture or a cep capture. But it handles it correctly anyway.

My self appointed mission for better or worse is to show an alternative approach to traditional coding technique.