End of day one. The Qsearch() is a little more tricky but not that bad. I try to do things in Qsearch that are normally done at the next ply in order to avoid making unnecessary recursive calls. I hope my thinking is correct. Tomorrow I'll start working on generating the move bits.
Here is Qsearch().
So far.
Code: Select all
// iPlayChess.cpp
// A Chess Egine
// By TalkChess members
// * Michael Sherwin
// 2021
// Both Intel and AMD processors x86/x64 are optimised for signed 32 bit integers
// Wherever using signed 32 bit variables is practical they will be used
#include <intrin.h> // compiler intrinsics
#include <time.h>
// Due to a compiler limitation #define will be used to define variable types
#define s08 __int8
#define u08 unsigned __int8
#define s16 __int16
#define u16 unsigned __int16
#define s32 __int32
#define u32 unsigned long // this is the culpret. The compiler only wants to see unsigned long for the bit scan intrinsics
#define u64 unsigned __int64
constexpr auto INF = 0x8000; // 32768
constexpr auto CHECKMATE = 0x7fff; // 32767
constexpr auto STALEMATE = 0;
constexpr auto one = 1ull; // better looking :)
// The move structure
struct SMove {
u08 from_square;
u08 to_square;
u08 move_type;
u08 capt_type;
u16 scratch;
s16 score;
};
// Move union
union Move {
SMove m;
u64 m64;
};
// Thread structure
struct Thread {
s32 wtm; // white to move
s32 ply; // search ply
s32 gly; // game ply
s32 board[64]; // chess board
Move game[1000]; // game record
u64 attacks; // attack bits per gen method
u64 king[2]; // where the kings are
};
// We will have a Thread* t in all functions that need it
// To avoid the ugliness and extra typing of t->wtm for example
// the t-> is defined away. Just have to be careful about naming locals
#define wtm t->wtm
#define ply t->ply
#define gly t->gly
#define board t->board
#define game t->game
#define attacks t->attacks
#define king t->king
enum { BLACK, WHITE };
enum { EXIT, GET_COMMAND, PLAY, MOVE };
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
};
// GLOABLE VARIABLES
Thread* thread[1024]; // might as well think big
time_t begin_t; // time search or perft begins
time_t end_t; // time search or perft ends
s32 play; // program control
s32 search_depth; // the max search depth while searching
s32 search_time; // the max search time while searching
u64 white_pawn_moves[64];
u64 white_pawn_capts[64];
u64 black_pawn_moves[64];
u64 black_pawn_capts[64];
u64 knight_moves[64];
u64 king_moves[64];
u64 pos_1_moves[64];
u64 pos_7_moves[64];
u64 pos_8_moves[64];
u64 pos_9_moves[64];
u64 neg_1_moves[64];
u64 neg_7_moves[64];
u64 neg_8_moves[64];
u64 neg_9_moves[64];
// Initialize the open board attack sets for classic bitboards
// Maybe someone can add magic or I'll do it later
void InitializeBB() {
s32 square, x, y, dx, dy;
for (square = a1; square <= h8; square++) {
// decompose square into x and y coordinates
x = square & 7;
y = square >> 3;
// pawns
// White Pawn Moves
white_pawn_moves[square] |= one << (square + 8);
if (square < a3) white_pawn_moves[square] |= one << (square + 16);
// White Pawn Captures
if (square < a8) {
if (x + 1 < +8) white_pawn_capts[square] |= one << (square + 9);
if (x - 1 > -1) white_pawn_capts[square] |= one << (square + 7);
}
// Black Pawn Moves
black_pawn_moves[square] |= one << (square - 8);
if (square > h6) black_pawn_moves[square] |= one << (square - 16);
// Black Pawn Captures
if (square > h1) {
if (x + 1 < +8) black_pawn_capts[square] |= one << (square - 7);
if (x - 1 > -1) black_pawn_capts[square] |= one << (square - 9);
}
}
// knights
knight_moves[square] = 0;
if (x - 2 > -1 && y - 1 > -1) knight_moves[square] |= one << (square - 10);
if (x - 2 > -1 && y + 1 < +8) knight_moves[square] |= one << (square + 6);
if (x - 1 > -1 && y - 2 > -1) knight_moves[square] |= one << (square - 17);
if (x - 1 > -1 && y + 2 < +8) knight_moves[square] |= one << (square + 15);
if (x + 2 < +8 && y - 1 > -1) knight_moves[square] |= one << (square - 6);
if (x + 2 < +8 && y + 1 < +8) knight_moves[square] |= one << (square + 10);
if (x + 1 < +8 && y - 2 > -1) knight_moves[square] |= one << (square - 15);
if (x + 1 < +8 && y + 2 < +8) knight_moves[square] |= one << (square + 17);
neg_9_moves[square] = 0;
for (dx = -1, dy = -1; dx > -1 && dy > -1; dx--, dy--) neg_9_moves[square] |= (((y + dy) << 3) + x + dx);
pos_7_moves[square] = 0;
for (dx = -1, dy = +1; dx > -1 && dy < +8; dx--, dy++) pos_7_moves[square] |= (((y + dy) << 3) + x + dx);
neg_7_moves[square] = 0;
for (dx = +1, dy = -1; dx < +8 && dy > -1; dx++, dy--) neg_7_moves[square] |= (((y + dy) << 3) + x + dx);
pos_9_moves[square] = 0;
for (dx = +1, dy = +1; dx < +8 && dy < +8; dx++, dy++) pos_9_moves[square] |= (((y + dy) << 3) + x + dx);
neg_1_moves[square] = 0;
for (dx = -1; x + dx > -1; dx--) neg_1_moves[square] |= ((y << 3) + x + dx);
pos_1_moves[square] = 0;
for (dx = +1; x + dx < +8; dx++) pos_1_moves[square] |= ((y << 3) + x + dx);
neg_8_moves[square] = 0;
for (dy = -1; y + dy > -1; dy--) neg_8_moves[square] |= (((y + dy) << 3) + x);
pos_8_moves[square] = 0;
for (dy = +1; y + dy < +8; dy++) pos_8_moves[square] |= (((y + dy) << 3) + x);
// kings
king_moves[square] = 0;
if (x - 1 > -1) king_moves[square] |= one << (square - 1);
if (x + 1 < +8) king_moves[square] |= one << (square + 1);
if (y - 1 > -1) king_moves[square] |= one << (square - 8);
if (y + 1 < +8) king_moves[square] |= one << (square + 8);
if (x - 1 > -1 && y - 1 > -1) king_moves[square] |= one << (square - 9);
if (x - 1 > -1 && y + 1 < +8) king_moves[square] |= one << (square + 7);
if (x + 1 > -1 && y - 1 > -1) king_moves[square] |= one << (square - 7);
if (x + 1 > -1 && y + 1 < +8) king_moves[square] |= one << (square + 9);
}
void Initialize() {
play = GET_COMMAND;
search_time = 1000000; // one million seconds
search_depth = 1; // for degugging search depth is set to 1 ply
thread[0] = new Thread;
InitializeBB();
}
s32 Eval(Thread* t) {
s32 score;
return score;
}
void Make_Move(Thread* t, Move* move) {
}
void Take_Back(Thread* t, Move* move) {
}
bool Attacked_By_White(Thread* t, u64 bb) {
return false;
}
bool Attacked_By_Black(Thread* t, u64 bb) {
return false;
}
// array of function pointers to use the Attacked By functions for determining in check status
bool (*In_Check[])(Thread* t, u64 bb) = { Attacked_By_Black, Attacked_By_White };
void Remove_Move(Move* move, Move* list, Move* last) {
}
void Game(Move move) {
}
void Get_Command() {
}
Move Get_Move_From_Move_Bits(Thread* t, u64* move_bits) {
Move move;
return move;
}
bool Gen_Capt_Bits(Thread* t, u64* move_bits) {
return true;
}
// It is important to use no more than 4 parameters for Qsearch because only 4 will be passed by register
s32 Qsearch(Thread* t, u64* move_bits, s32 alpha, s32 beta) {
Move move;
u64 move_bits[64];
move = Get_Move_From_Move_Bits(t, move_bits);
do {
Make_Move(t, &move);
if (!Gen_Capt_Bits(t, move_bits) || !attacks) {
Take_Back(t, &move]);
continue;
}
if (Eval(t) > alpha) {
move.m.score = -Qsearch(t, move_bits, -beta, -alpha);
}
else {
move.m.score = alpha;
Take_Back(t, &move);
continue;
}
Take_Back(t, &move);
if (move.m.score > alpha) {
if (move.m.score >= beta) return beta;
alpha = move.m.score;
}
move = Get_Move_From_Move_Bits(t, move_bits);
} while (move.m64);
return alpha;
}
bool Gen_Move_bits(Thread* t, u64* move_bits) {
return true;
}
void List_Moves(u64* move_bits, Move* list) {
}
s32 Search(Thread* t, u64* move_bits, s32 alpha, s32 beta, s32 depth) {
Move list[120];
u64 move_bits[64];
s32 list_index;
bool okay;
List_Moves(move_bits, list); // just for now -- something more advanced later
okay = false;
depth--;
for (list_index = 1; list_index <= list[0].m.scratch; list_index++) {
// Sort(list_index, list, list[0].m.scratch);
Make_Move(t, &list[list_index]);
okay = true;
if (depth < 0) {
if (!Gen_Capt_Bits(t, move_bits) || !attacks) {
Take_Back(t, &list[list_index]);
continue;
}
if (Eval(t) > alpha) {
list[list_index].m.score = -Qsearch(t, move_bits, -beta, -alpha);
}
else {
list[list_index].m.score = alpha;
Take_Back(t, &list[list_index]);
continue;
}
}
else {
if (!Gen_Move_bits(t, move_bits)) {
Take_Back(t, &list[list_index]);
continue;
}
list[list_index].m.score = -Search(t, move_bits, -beta, -alpha, depth);
}
Take_Back(t, &list[list_index]);
if (list[list_index].m.score > alpha) {
if (list[list_index].m.score >= beta) return beta;
alpha = list[list_index].m.score;
}
}
if (!okay) {
if (In_Check[wtm](t, king[wtm])) {
return -(CHECKMATE - ply);
}
else {
return STALEMATE;
}
}
return alpha;
}
Move Root_Search(Thread* t, Move* list, s32 alpha, s32 beta, s32 depth) {
Move best, *last, *move;
u64 move_bits[64];
last = list + list->m.scratch;
for (move = list + 1; list <= last; list++) {
Make_Move(t, move);
if (!Gen_Move_bits(t, move_bits)) {
Take_Back(t, move);
Remove_Move(move, list, last);
continue;
}
list->m.score = Search(t, move_bits, alpha, beta, depth - 1);
Take_Back(t, move);
if (move->m.score > alpha) {
alpha = move->m.score;
best = *move;
}
}
return best;
}
void Sort_Root_Moves(Move* move) {
}
Move I_Play_Chess(Thread* t) {
Move move, completed, list[120];
s32 depth;
u64 move_bits[64];
Gen_Move_bits(t, move_bits);
List_Moves(move_bits, list);
begin_t = clock();
for (depth = 1; depth <= search_depth; depth++) {
move = Root_Search(t, list, -INF, INF, depth);
if (clock() - begin_t < search_time) {
completed = move;
}
else {
break;
}
Sort_Root_Moves(list);
}
end_t = clock();
play = MOVE;
return completed;
}
s32 main() {
Move move;
Initialize();
while (play) {
Get_Command();
if (play == PLAY) move = I_Play_Chess(thread[0]);
if (play == MOVE) Game(move);
}
return 0;
}