If I were a Professor of Computer Science

Discussion of chess software programming and technical issues.

Moderator: Ras

Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

If I were a Professor of Computer Science

Post by Mike Sherwin »

If I were a professor of computer science teaching a 101 level course for beginners this thread would be that course.
In this course we will be developing a simple multi file multi-threaded program (henceforth termed an engine) named Quixotic that plays chess. We will use the Microsoft free Community version of C++ as a better C, MSVS 2022. Let's get started.

First we will make some files.
Quixotic.cpp
Defines.cpp
Globals.cpp
Initialize.cpp
GetCommand.cpp
Move.cpp
Search.cpp
Main.cpp

Quixotic.cpp is the main program file. All other files will be brought into Quixotic using #include.
Defines.cpp will contain everything we define that helps us in the writing of the code.
Globals.cpp will be all the variables that can be accessed from anywhere in the program.
Initialize.cpp will contain all initialization code that almost all programs need to do.
GetCommand.cpp will handel all commands for this chess engine.
Move.cpp will will handle all moves, game moves and internal engine moves.
Search.cpp is all about deciding upon a game move to play.
Main.cpp contains only the required main function.

Code: Select all

// Quixotic.cpp

#include "Defines.cpp"
#include "Globals.cpp"
#include "Initialize.cpp"
#include "GetCommand.cpp"
#include "Move.cpp"
#include "Search.cpp"
#include "Main.cpp"
Next we need to define some obvious values and structures before we can start writing code.

Code: Select all

// Defines.cpp

// Type defines are used, by the professor's prerogative, to give alternate names to internal variable types
typedef char s08;
typedef int  s32;
typedef unsigned long long u64;

// There are 'black' and 'white' pieces that are enumerated as BLACK = 0 and WHITE = 1
enum { BLACK, WHITE };

// Some mode settings
enum { EXIT, GETCMD, SEARCH, MOVE };

// WP stands for white pawn ... WRC for a white rook that can castle ... ES for empty square
enum { WP, WN, WB, WRC, WR, WQ, WKC, WK,
       BP, BN, BB, BRC, BR, BQ, BKC, BK,
       ES };

// The names of the files
enum { FILEa, FILEb, FILEc, FILEd, FILEe, FILEf, FILEg, FILEh };

// The names of the ranks
enum { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };

// The names of the squares
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
};

// Structure to contain a single move
struct Move {
  s08 fs; // from square
  s08 ts; // to square
  s08 ft; // from square piece type
  s08 tt; // to square piece type including ES for no piece
  s32 sc; // score 
};

// A thread structure to allow for a multi-threaded engine
struct Thread {
  s32 stm; // side to move
  s32 ply; // a counter to denote how deep we are in the search
  s08 board[64]; // The chessboard
};

// Defines for cleaner looking code
#define stm   t->stm
#define ply   t->ply
#define board t->board

Code: Select all

//Globals.cpp

// Global variables
s32 mode; // tells the engine what mode it is in

Code: Select all

// Initialize.cpp

// Initialization code
void Initialize() {
  mode = GETCMD; // start the engine off in get command mode
}

Code: Select all

// GetCommand.cpp

// Tell the engine what to do
void GetCommand() {
   mode = Search; // temporary code to test program flow
}

Code: Select all

Move.cpp

// Performs a move in the game being played
void GameMove() {
  mode = EXIT; // temporary code to test program flow
}

Code: Select all

// Search.cpp

// Beginning of the code that will produce a move to be played
void StartSearch() {
  mode = MOVE; // temporary code to test program flow
}

Code: Select all

// Main.cpp

// Where the code starts running and controls the flow of the engine
s32 main() {

  Initialize();

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

  return 0;
}
That is it for today's class. Tonight's assignment is to download MSVS 2022 and compile the code and step through it in debug mode to see how it works. I assume that you all know how to do that from your CS100 class. Have a good night and be back fresh for tomorrow's class.
JoAnnP38
Posts: 253
Joined: Mon Aug 26, 2019 4:34 pm
Location: Clearwater, Florida USA
Full name: JoAnn Peeler

Re: If I were a Professor of Computer Science

Post by JoAnnP38 »

I think it would be a wonderful idea for a class, but it is probably too advanced for a freshman 101 class. You would have to dedicate a certain portion of the class to:
  • Learning C (someone will have javascript knowledge, but I doubt many will know C.)
  • Top-down design / bottom-up implementation (most have never designed a piece of software.)
  • How to use the tools and other resources available to them.
To be honest, my first course in AI was in graduate school where we used LISP to get cars/trucks and other vehicles out of a crowded parking lot. It's actually a board game which I have forgotten the name to. Search, eval, move generation etc. were all covered with this simple game but did not take nearly as long as creating a chess engine would have. However, I might have wished we had spent more time on search-based games, we had to move on to other concepts.
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: If I were a Professor of Computer Science

Post by Mike Sherwin »

JoAnnP38 wrote: Fri Dec 30, 2022 1:33 am I think it would be a wonderful idea for a class, but it is probably too advanced for a freshman 101 class. You would have to dedicate a certain portion of the class to:
  • Learning C (someone will have javascript knowledge, but I doubt many will know C.)
  • Top-down design / bottom-up implementation (most have never designed a piece of software.)
  • How to use the tools and other resources available to them.
To be honest, my first course in AI was in graduate school where we used LISP to get cars/trucks and other vehicles out of a crowded parking lot. It's actually a board game which I have forgotten the name to. Search, eval, move generation etc. were all covered with this simple game but did not take nearly as long as creating a chess engine would have. However, I might have wished we had spent more time on search-based games, we had to move on to other concepts.
Thanks for the comment JoAnn! :D

I am an imaginary professor at an imaginary university on an imaginary planet where this is 101 material. :lol:
There are several goals for this thread.

1. To write a chess engine.
2. To teach the novice wantabe how to go about writing a chess engine.
3. To be entertaining.
4. To foster participation in writing a chess engine.
5. As a notepad because I forget too much.
6. A place to test ideas that someone might have.
7. And more.

So treating this as me teaching a class is just part of the entertainment. 8-)

I'm certainly no professor.
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: If I were a Professor of Computer Science

Post by Mike Sherwin »

Today's lesson is a short lesson but a powerful one. Since Quixotic is to be a multithreaded application with a theoretically unlimited number of threads and since each thread structure can be quite large there needs to be a way of allocating thread memory safely so the engine will not crash or exit do to a failed memory allocation. For this reason the following code is added.

Code: Select all

// In Globals.cpp we add:

s32 maxThreads;

Thread** thread; 

// This is a pointer to a pointer of type Thread.

// Then in Initialize.cpp we add:

thread = new Thread * [MAX_THREADS];

// This creates an array of type pointer to Thread with the name thread, MAX_THREADS in size.

// Then we initialize maxThreads to MAX_THREADS.

MaxThreads = MAX_THREADS;

// Now we start allocating memory for each thread.

for (s32 i = 0; i < MAX_THREADS; i++) {
  thread[i] = new Thread;
  if (thread[i] == nullptr) {  // new returns nullptr on allocation failure.
    maxThreads = i - 1;
    break; // exits the for loop
  }
}
When the search starts it knows that the starting Thread pointer is always thread[0]
and passes that to the first search function that requires a thread pointer.

example:
FirstFunction(thread[0]);
Function(Thread* t) {}

After that all underneath functions are passed t.
User avatar
Ras
Posts: 2695
Joined: Tue Aug 30, 2016 8:19 pm
Full name: Rasmus Althoff

Re: If I were a Professor of Computer Science

Post by Ras »

Mike Sherwin wrote: Fri Dec 30, 2022 12:37 am // Type defines are used, by the professor's prerogative, to give alternate names to internal variable types
typedef char s08;
typedef int s32;
typedef unsigned long long u64;
Just don't. Use the portable data types provided by the compiler (C++: <cstdint>, C: <stdint>) because that will actually work cross-platform. E.g. assuming that int is 32 bits is already problematic - the standard only specifies at least 16 bits. Also, char is not standardised as signed, that's implementation specific.
// WP stands for white pawn ... WRC for a white rook that can castle ... ES for empty square
If you have to explain names, it means that the naming is bad. Don't use such names, write e.g. WPAWN. Similar with naming like fs, ts and the like. Otherwise, the source will become an unreadable mess further down the road, and your effort would be wasted because nobody can read that, in particular not beginners.
Rasmus Althoff
https://www.ct800.net
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: If I were a Professor of Computer Science

Post by Mike Sherwin »

Ras wrote: Fri Dec 30, 2022 12:31 pm
Mike Sherwin wrote: Fri Dec 30, 2022 12:37 am // Type defines are used, by the professor's prerogative, to give alternate names to internal variable types
typedef char s08;
typedef int s32;
typedef unsigned long long u64;
Just don't. Use the portable data types provided by the compiler (C++: <cstdint>, C: <stdint>) because that will actually work cross-platform. E.g. assuming that int is 32 bits is already problematic - the standard only specifies at least 16 bits. Also, char is not standardised as signed, that's implementation specific.
// WP stands for white pawn ... WRC for a white rook that can castle ... ES for empty square
If you have to explain names, it means that the naming is bad. Don't use such names, write e.g. WPAWN. Similar with naming like fs, ts and the like. Otherwise, the source will become an unreadable mess further down the road, and your effort would be wasted because nobody can read that, in particular not beginners.
Good points! I'll rework the code tomorrow. 8-)
For today there is a new lesson. :D
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: If I were a Professor of Computer Science

Post by Mike Sherwin »

Today we build the search infrastructure well enough to compile in debug mode so we can understand the program flow.
The engine will use the alpha/beta negamax algorithm to find, hopefully, the best move. The explanation of the negamax algorithm is beyond the scope of today's lesson. If you want to look ahead you can find an explanation online.

In Quixotic.cpp we add the source file GenMoves.cpp.

Code: Select all

// Quixotic.cpp

#include "Defines.cpp"
#include "Globals.cpp"
#include "Initialize.cpp"
#include "GetCommand.cpp"
#include "Move.cpp"
#include "GenMoves.cpp"
#include "Search.cpp"
#include "Main.cpp"
In Defines.cpp some new values are defined or added to.
1. A constant named INFINITY to represent the highest/lowest scores possible.
2. enum { PAWNS, KNIGHTS, BISHOPS, ROOKS, QUEENS, KING }; // to access the pieceBits array
3. Some additions to the Thread structure.
u64 pieceBits[2][6]; // each bit represents the square where a piece type is on the board
u64 moveBits[100][64]; // the to square bits generated are stored by ply and from square
u64 attackBits[100]; // all squares that are attacked by the side to move

Code: Select all

// Defines.cpp

typedef char s08;
typedef int  s32;
typedef unsigned long long u64;

constexpr auto MAX_THREADS = 4;
constexpr auto INFINITY = 10000;

enum { BLACK, WHITE };

enum { EXIT, GETCMD, SEARCH, MOVE };

enum { WP, WN, WB, WRC, WR, WQ, WKC, WK,
       BP, BN, BB, BRC, BR, BQ, BKC, BK,
       ES
};

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

enum { RANK1, RANK2, RANK3, RANK4, RANK5, RANK6, RANK7, RANK8 };

enum { PAWNS, KNIGHTS, BISHOPS, ROOKS, QUEENS, KING };

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

struct Move {
  s08 fs;
  s08 ts;
  s08 ft;
  s08 tt;
  s32 sc;
};

struct Thread {
  u64 pieceBits[2][6];
  u64 moveBits[100][64];
  u64 attackBits[100];
  s32 board[64];
  s32 stm;
  s32 ply;
};

#define pieceBits  t->pieceBits
#define moveBits   t->moveBits
#define attackBits t->attackBits
#define board      t->board
#define stm        t->stm
#define ply        t->ply
In globals.cpp a few global variables were added

Code: Select all

// Globals.cpp

s32 mode;
s32 sd; // search depth

Thread** thread; 
s32 maxThreads;

Move gameMove; // a game move the search will populate
Move gameMoves[500]; // list of game moves made
More Initializations in Initialize.cpp

Code: Select all

// Initialize.cpp

void NewGame() {
  Thread* t = thread[0]; // for writing cleaner code as in stm instead of t->stm and ply instead of t->ply
  stm = WHITE;
  ply = 0;
  mode = GETCMD;
  sd = 1; set to 1 for initial debugging
}

void Initialize() {
  Thread* t; // Temporary code for testing
  thread = new Thread * [MAX_THREADS];

  maxThreads = MAX_THREADS;
  for (s32 i = 0; i < MAX_THREADS; i++) {
	thread[i] = new Thread;
	if (thread[i] == nullptr) {
	  maxThreads = i - 1;
	  break;
	}
  }

  // Temporary code for testing
  t = thread[0];
  for (s32 i = 0; i < 6; i++) {
	pieceBits[BLACK][i] = 0;
	pieceBits[WHITE][i] = 0;
  }

  NewGame(); // some variables need reinitialized for a new game 
}
GetCommand.cpp no changes.

Code: Select all

// GetCommand.cpp

void GetCommand() {
  mode = SEARCH;
}
Move.cpp no changes.

Code: Select all

// Move.cpp

void GameMove() {
  mode = EXIT;
}
GenMoves.cpp added.

Code: Select all

// GenMoves.cpp

bool GenMoves(Thread* t) {
  u64 fsBits; // from square bits
  u64 attacks = 0;

  fsBits = pieceBits[stm][PAWNS]; // get the from square bits for the side to move for pawns
  while (fsBits) {
    // generate pawn moves
  }

  fsBits = pieceBits[stm][KNIGHTS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][BISHOPS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][ROOKS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][QUEENS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][KING];
  while (fsBits) {

  }
  // equates to 1 if true and 0 if false
  return (bool)((attacks & pieceBits[1 - stm][KING]) == 0);
}

// same as GenMoves ecept generates captures only
bool GenCaptures(Thread* t) {
  u64 fsBits;
  u64 attacks = 0;

  fsBits = pieceBits[stm][PAWNS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][KNIGHTS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][BISHOPS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][ROOKS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][QUEENS];
  while (fsBits) {

  }

  fsBits = pieceBits[stm][KING];
  while (fsBits) {

  }

  return (bool)((attacks & pieceBits[1 - stm][KING]) == 0);
}
Search.cpp created search infrastructure to test program flow.

Code: Select all

// Search.cpp

s32 Qsearch(Thread* t, s32 alpha, s32 beta) {
  bool ok;
  s32 score;

  ok = GenCaptures(thread[0]);
  if (!ok) return INFINITY;

  // loop for each capture, make capture
  score = 0; // -Qsearch(thread[0], -beta, -alpha);
  // take back capture
  if (score >= beta) return beta;
  if (score > alpha) alpha = score;
  // end loop

  return alpha;
}

s32 Search(Thread* t, s32 alpha, s32 beta, s32 depth) {
  bool ok;
  s32 score;

  if (depth == 0) return Qsearch(t, alpha, beta);

  ok = GenMoves(thread[0]);
  if (!ok) return INFINITY;

  // loop for each move, make move
  score = -Search(thread[0], -beta, -alpha, depth - 1);
  // take back move
  if (score >= beta) return beta;
  if (score > alpha) alpha = score;
  // end loop

  return alpha;
}

void RootSearch(s32 depth) {
  s32 alpha = -INFINITY;
  s32 beta = INFINITY;
  s32 score = 0;
  
  GenMoves(thread[0]);
  // for each move
  score = -Search(thread[0], -beta, -alpha, depth - 1);

}

void StartSearch() {
  s32 depth = sd;
  RootSearch(depth); // root search because it will do things differently than search.
  mode = MOVE;
}
Main.cpp no changes.

Code: Select all

// Main.cpp

s32 main() {

  Initialize();

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

  return 0;
}
Notes:

In the future the source code will be downloadable from MediaFire.

The imaginary professor got his wrist slapped for not making the code explicit enough and portable. The code will be rewritten before the next lesson.

The code as written compiles without errors, warnings or messages and can be stepped through in the debugger to verify program flow. And it works as expected.
Mike Sherwin
Posts: 965
Joined: Fri Aug 21, 2020 1:25 am
Location: Planet Earth, Sol system
Full name: Michael J Sherwin

Re: If I were a Professor of Computer Science

Post by Mike Sherwin »

Changes made.
Sources uploaded to MediaFire.
Link tested.
https://www.mediafire.com/file/i1gwj625 ... c.zip/file
User avatar
Bo Persson
Posts: 257
Joined: Sat Mar 11, 2006 8:31 am
Location: Malmö, Sweden
Full name: Bo Persson

Re: If I were a Professor of Computer Science

Post by Bo Persson »

Mike Sherwin wrote: Fri Dec 30, 2022 4:22 am

Code: Select all


  if (thread[i] == nullptr) {  // new returns nullptr on allocation failure.

new does not return at all on failure, but throws a bad_alloc exception. So this case never happens.
User avatar
Bo Persson
Posts: 257
Joined: Sat Mar 11, 2006 8:31 am
Location: Malmö, Sweden
Full name: Bo Persson

Re: If I were a Professor of Computer Science

Post by Bo Persson »

Another bit about using comments to explain code:

Code: Select all

// The names of the squares
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
};
What about using "enum square", and skip the comment? Then you could possibly also use "square" instead of "s08" elsewhere in the code, like turning "s08 fs;" into "square from;".