iPlayChess - A TalkChess Community Engine

[Mike Sherwin]

Goals
1. Bug free
2. Fast
3. A bit different
4. Simple

Language
1. C - cpp as a better C
2. MSVS 2019
3. bitboard

Participation
1. Anyone can contribute
2. Ultimately I choose what goes in
3. Unless I'm outvoted

Initial code skeleton

Code: Select all

// iPlayChess.cpp
// A Chess Engine
// 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>

// 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 

// 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
};

// 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

// might as well think big
Thread* thread[1024];

enum { EXIT, GET_COMMAND, PLAY, MOVE };

// GLOABLE VARIABLES
s32 play; // program control

void Initialize() {
  play = GET_COMMAND;
  thread[0] = new Thread;
}

void Game(Move move) {

}

void Get_Command() {

}

Move iPlayChess(Thread* t) {
  Move move;

  play = MOVE;
  return move;
}

s32 main() {
  Move move;

  Initialize();

  while (play) {
    Get_Command();
    if (play == PLAY) move = iPlayChess(thread[0]);
    if (play == MOVE) Game(move);
  }

  return 0;
}

[Mike Sherwin]

As it seems that 90% of authors prefer UCI protocol I guess I'll have to learn UCI, ouch. Maybe someone can contrib some UCI code to Get_Command()?

The "a bit different" part is that iPlayChess will be an engine that learns in real time. Also it will be an analysis engine. So not only will it be able to use multithreading on just one root position it will be able to use one thread on any number of root positions up to the maximum number of threads in a GUI specifically written for this purpose. So two versions of the engine.

This means that every thread will need its own complete game record. And Loadfen() will have to load for any thread. Therefore we can add game[1000] to the Thread structure.

Code: Select all

// Thread structure
struct Thread {
  s32 wtm; // white to move
  Move game[1000]; // game record
};
  
// 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 game t->game

[Mike Sherwin]

Part of going fast means not making a move list before needed. I do this same thing in RomiChess. At first only the move bits are generated. This is very handy during search as moves like the hash move can be verified quickly and its bit removed before the remaining moves are listed. For the root this does not matter so upon return from Gen_Move_Bits() the bits are immediately listed. The list of root moves is generated in the iteration function iPlayChess();

Code: Select all

Move iPlayChess(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 = RootSearch(t, list, -INF, INF, depth);
    if (clock() - begin_t < search_time) {
      completed = move;
    }
    else {
      break;
    }
  }

  end_t = clock();

  play = MOVE;
  return completed;
}

[Mike Sherwin]

The RootSearch() is rather straightforward. The only thing of note is that Gen_Move_bits() is called before calling Search() to check the legality of the pseudo legal move and removing it from the list if illegal.

Code: Select all

Move RootSearch(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++) {
    MakeMove(t, move);
    if (!Gen_Move_bits(t, move_bits)) {
      TakeBack(t, move);
      Remove_Move(move, list, last);
      continue;
    }
    list->m.score = -Search(t, move_bits, -beta, -alpha, depth - 1);
    TakeBack(t, move);
    if (move->m.score > alpha) {
      alpha = move->m.score;
      best = *move;
    }
  }
  
  return best;
}

[Mike Sherwin]

What there is 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 = 0x7fff; // 32767

// 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
  Move game[1000]; // game record
};

// 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 game t->game

enum { EXIT, GET_COMMAND, PLAY, MOVE };

// GLOABLE VARIABLES
Thread* thread[1024]; // might as well think big
time_t begin_t;
time_t end_t;
s32 play;             // program control
s32 search_depth;
s32 search_time;

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

void Make_Move(Thread* t, Move* move) {

}

void Take_Back(Thread* t, Move* move) {

}

void Remove_Move(Move* move, Move* list, Move* last) {

}

void Game(Move move) {

}

void Get_Command() {

}

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) {

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

Move I_Play_Chess(Thread* t) {
  Move move, completed, list[120];
  s32 depth;
  u64 move_bits[2][64];

  Gen_Move_bits(t, move_bits[0]);

  List_Moves(move_bits[0], 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;
    }
  }

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

[Mike Sherwin]

Here is Search().

Code: Select all

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++) {
    Make_Move(t, &list[list_index]);
    if (!Gen_Move_bits(t, move_bits)) {
      Take_Back(t, &list[list_index]);
      continue;
    }
    okay = true;
    if (depth < 0) {
      list[list_index].m.score = -Qsearch(t, move_bits, -beta, -alpha);
    }
    else {
      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;
}

What we have 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;

// 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 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 king  t->king

enum { BLACK, WHITE };

enum { EXIT, GET_COMMAND, PLAY, MOVE };

// GLOABLE VARIABLES
Thread* thread[1024]; // might as well think big
time_t begin_t;
time_t end_t;
s32 play;             // program control
s32 search_depth;
s32 search_time;

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

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() {

}

bool Gen_Move_bits(Thread* t, u64* move_bits) {

  return true;
}

void List_Moves(u64* move_bits, Move* list) {

}

// 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) {

}

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++) {
    Make_Move(t, &list[list_index]);
    if (!Gen_Move_bits(t, move_bits)) {
      Take_Back(t, &list[list_index]);
      continue;
    }
    okay = true;
    if (depth < 0) {
      list[list_index].m.score = -Qsearch(t, move_bits, -beta, -alpha);
    }
    else {
      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;
}

[Mike Sherwin]

Going to start with Classic Bitboards then do Magic later.
Here is the initialization for Classic.

Code: Select all

// 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);
  
  // ray wise
  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);
}

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 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 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();
}

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() {

}

bool Gen_Move_bits(Thread* t, u64* move_bits) {

  return true;
}

void List_Moves(u64* move_bits, Move* list) {

}

// 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) {

}

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++) {
    Make_Move(t, &list[list_index]);
    if (!Gen_Move_bits(t, move_bits)) {
      Take_Back(t, &list[list_index]);
      continue;
    }
    okay = true;
    if (depth < 0) {
      list[list_index].m.score = -Qsearch(t, move_bits, -beta, -alpha);
    }
    else {
      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;
}

[Mike Sherwin]

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().

Code: Select all

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)) {
      Take_Back(t, &move);
      move.m.score = -(CHECKMATE - ply);
      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;
}

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

[mvanthoor]

Code: Select all

  if (!okay) {
    if (In_Check[wtm](t, king[wtm])) {
      return -(CHECKMATE - ply);
    }
    else {
      return STALEMATE;
    }

  }

Shouldn't that be "return -(CHECKMATE + ply);" ?

[Joost Buijs]

Code: Select all

  if (!okay) {
    if (In_Check[wtm](t, king[wtm])) {
      return -(CHECKMATE - ply);
    }
    else {
      return STALEMATE;
    }

  }

Shouldn't that be "return -(CHECKMATE + ply);" ?

Don't think so. It should be "-CHECKMATE + ply" which is of course the same as "-(CHECKMATE - ply)".