Chess programming is a weird subset of general programming, it's where everyone is trying to hyper-optimize every section and making complete rewrites just for a +3 ELO gain, let's make our own but be less radical about it!

  • Goals: 2000+, 5M nips

Board Representation

The popular "high efficient" representation is BitBoard, which is basically a normal Piece-centeric board, but uses bitwise tricks to find stuff like attacking squares, which modern computers are super good at, but humans struggle with it a lot since it requires a lot of complex algorithms to function properly, that's why we'll use 0x88 instead, which is basically:

Piece[128] Board;

it uses the left section as the actual board and the right stays garbage that will allow us later to do some good speedups! also it's more easier to handle than BitBoards, our board will look something like:

using u8 = unsigned char; // BYTE
enum Piece : u8 {
	EMP = 0,
	P = 1,
	N = 2,
	B = 3,
	R = 4,
	Q = 5,
	K = 6,
};

using BBT = Piece[128];

Move Generation

In here we want to generate all pseudo-legal moves, which are moves that don't take into account the king being checked after doing the move, in order to make them legal, we can just see if the king is in check after the move

there is a lot of methods, some are efficient, and some are mine, but first let's define a move, i think we can't the debate this:

struct CMove {
	u8 from; // from
	u8 to; // to
	Piece promo; // piece we're promoting to (EMP else pawn promotion)
	u8 flag; // 1 = en passant, 2 = long castle, 3 = short castle
};

ok now to move generation, notice that we can model all directions using addition and subtraction in 0x88:

// E, W, N, S, NE, NW, SE, SW
int dirs[8] = {1, -1, 16, -16, 17, 15, -15, -17};

next thing we can do is setup up a ray array, which is basically how pieces should move in case they are slidable, like bishop and rook for example, they slide using a ray direction, so we can declare if a piece is slid-able and follow the ray array!

bool slide[6] = {0, 0, 1, 1, 1, 0};
int ray[6][8] = {
	{   0,   0,  0,  0, 0,  0,  0,  0 },
	{ -21, -19,-12, -8, 8, 12, 19, 21 }, // knight
	{ -11,  -9,  9, 11, 0,  0,  0,  0 }, // bishop
	{ -10,  -1,  1, 10, 0,  0,  0,  0 }, // rook
	{ -11, -10, -9, -1, 1,  9, 10, 11 }, // queen
	{ -11, -10, -9, -1, 1,  9, 10, 11 }  // king
};

one nice feature about 0x88 is that if pos&0x88 > 0 it means that we're in an invalid square due to the nature of the 0x88 board, so our move generation simplifies to a neat ~20 lines function:

bool side; // which side's turn
int rays_s[6] = {0, 8, 4, 4, 8, 8}; // size, slight optimization
for(int i = 0 ; i < 128 ; i++) {
	if(i&8) continue;
	Piece p = Board[i];
	if(color[i] != side) continue;
	if(p == EMP) continue;
	if(p == PAWN) continue;
	for(int j = 0 ; j < ray_s[p] ; j++) {
		int cur = i;
		for(;;) {
			cur += ray[p][j];
			if(cur & 0x88) break; // outside the board
			if(Board[cur] != EMP) {
				if(color[i] != color[cur]) {
					AddMove(i, cur); // capture
					break;
				}
			}
		
			AddMove(i, cur); // quiet move
			if(!slide[p]) break; // not slidable
		}
	}
}

all is left is to handle pawns and castling, which are not that much of a headache! (small note: since castling requires checking for a check, you kinda are forced to do it outside movegen)

also you're forced to implement Zobrist Hashing in order to draw in case of Three-fold repetition, and also there is some cool stuff we can do with it!

for check you can exploit the fact that we can reverse the roles, so let the king be a queen, if it touches the opponent's queen then he's in check! you can do this for all pieces except pawn, easy edge case!

we're going to use fans favorite Minimax, there does exist other methods, but all of them are incredibly complicated and mostly use Policy NNUEs and Probabilistic methods, which are far from what a toy chess engine should touch.

the way Minimax works is easy, let's define score as a number that the bigger the better for white and the smaller the better for black, let's say you have a some position as white, then you want to maximize the score, so you take the maximum of the positions you can reach in the recursion, but black must take minimum of the boards he can reach, and the recursion continues until some fixed depth!

in terms of code it will look something like this: 
int minimax(int depth, bool turn) {
    if (depth == DEPTH_LIMIT) return evaluate();
    int best_score = INF * (turn ? 1 : -1);
    for (move mv: moves) {
        score = minimax(depth-1, turn ^ 1);
        if(turn) best_score = max(best, score); // white
        else best_score = min(best, score); // black
    }
    
    return max;
}

but wait, what is evaluate()? it's an approximation of how good a board is for black or white, stockfish uses a complicated NNUE, but we're not complicated to let's instead make our hand-made one!

first off, who has more pieces should be better, so let's do that!

int evaluate(BBT &Board) {
    const int Pvals[13] = {0, 10, 32, 33, 50, 6000};
    int score_w = 0, score_b = 0;
    for(int i = 0 ; i < 128 ; i++) {
        if(i&8) continue;
        if(Board[i] == EMP) continue;
        if(color[i]) score_w += Pvals[tp];
        else score_b += Pvals[tp];
    }

    return score_w - score_b;
}

this might be good alone actually, but it doesn't encourage the engine to promote pieces or any good-chess principals, a solution is to reward it also for where the pieces are at, so for example a knight is good in the center while the king should stay in his initial rank, there already exists hand-made functions for this, so we can just use it instead!

Actually playing against it

what's the point of an engine if we can't play against it? a way to fix this is to make a CLI interface, but that's boring!

we can instead use UCI, which will allow us to play with our engine in Lichess using a UCI to Lichess gateaway, but now let's implement UCI, it's basically a protocol that allows GUIs to talk with engines so that humans, and other engines, can play against our engine

details of implementation are boring, if you're nerdy enough go read them, i already did so please trust that your GUI will work with only these:

int main() {
    BBT Board;
    build_board(Board);
    for(;;) {
        string inp;
        getline(cin, inp);
        if(inp == "quit") {
            return 0;
        }

        else if(inp == "uci") {
            cout << "id name BriwatsCE\n";
            cout << "id author Anass Zakar\n";
            cout << "uciok\n";
            cout << flush;
        }

        else if(inp == "isready") {
            cout << "readyok" << endl;;
        }

        else if(inp == "ucinewgame") {
            build_board(Board);
        }

        else if(inp.substr(0, 23) == "position startpos moves") {
            // take last move in inp and do it
            // convert from UCI notation to CMove
            domove( inp.last );
        }

        else if(inp.substr(0, 2) == "go") {
            // return move in UCI notation
            cout << minimax(Board) << flush;
            domove( minimax(Board) );
        }
    }
}

and that's it Folks! here is a game between the engine and itself: (its so smart ik) it's done