Learn Chess Programming – Shell Chess in C

[mdraith]

If you're interested in learning how to program a brute force chess game in C, take a look at my Linux-based project Shell Chess. It includes both source and executable.

The code is designed with speed and efficiency in mind.

Maybe you can make it even faster, add a proper GUI, or port it to Windows?

Check it out here:
https://github.com/mdraith/ShellChess

Have fun!
Thomas Starke

[Mike Sherwin]

If you're interested in learning how to program a brute force chess game in C, take a look at my Linux-based project Shell Chess. It includes both source and executable.

The code is designed with speed and efficiency in mind.

Maybe you can make it even faster, add a proper GUI, or port it to Windows?

Check it out here:
https://github.com/mdraith/ShellChess

Have fun!
Thomas Starke

I only have a windows 10 machine so I can't really get a feel for it by running it. I did look at the source code. If it plays a legal game of chess then congrats. If it can beat the average club player then kudos! If you hope that someone will use it as a learning example then you need to add comments. Is it really fast? Maybe someone here that has a Linux machine can comment. But it does not look fast. There are way way way too many if clauses. It surely must not be easy on the branch prediction logic of the CPU.

Let me show you a technique at the extreme (maybe too extreme) opposite of your code. I too lack the discipline to comment my code. And it is not beginner friendly. But what is different is that the entire move generator does not use a single if clause. Even the castling code does not use any if clauses! My AMD 3950x is busted so I'm on an INTEL 3930x that is about 14 years old. On this machine using a single thread it searches (PSTBLs only) roughly 10 million nodes per second.

Code: Select all

static s32 GenAllMoves(Thread* t, sMove* m) {
	sMove* n = m;
	u08 fs, ts, type;
	u64 bb = 0, b;

	u64 side = sides[stm];
	u64 enemy = sides[otm];
	u64 occ = side | enemy;
	u64 empty = ~occ;
	u64 notme = ~side;

	do {
		fs = std::countr_zero(side);
		side ^= 1ull << fs;
		type = board[fs];
		switch (type) {
		case ES:
			// unreachable
			break;
		case WP2:
			bb = wPawnCaptures[fs] & enemy;
			b = (1ull << (fs + 8)) & empty;
			bb |= b | (b << 8 & empty);
			break;
		case WP3: case WP4: case WP6:
			bb = wPawnCaptures[fs] & enemy;
			bb |= (1ull << (fs + 8)) & empty;
			break;
		case WP5:
			bb = wPawnCaptures[fs] & (enemy | epbit[sly]);
		    bb |= (1ull << (fs + 8)) & empty;
			break;
		case WP7:
			bb = wPawnCaptures[fs] & enemy;
			bb |= (1ull << (fs + 8)) & empty;
			while (bb) {
				ts = std::countr_zero(bb);
				bb ^= 1ull << ts;
				mfs = fs;
				mts = ts;
				mft = WPQ;
				msc = valq + value[mtt];
				m++;
				mfs = fs;
				mts = ts;
				mft = WPN;
				msc = valn + value[mtt];
				m++;
				mfs = fs;
				mts = ts;
				mft = WPR;
				msc = valr + value[mtt];
				m++;
				mfs = fs;
				mts = ts;
				msc = valb + value[mtt];
				mft = WPB;
				m++;
			}
			continue;
		case BP7:
			bb = bPawnCaptures[fs] & enemy;
			b = (1ull << fs >> 8) & empty;
			bb |= b | (b >> 8 & empty);
			break;
		case BP6: case BP5: case BP3:
			bb = bPawnCaptures[fs] & enemy;
			bb |= (1ull << fs >> 8) & empty;
			break;
		case BP4:
			bb = bPawnCaptures[fs] & (enemy | epbit[sly]);
			bb |= (1ull << fs >> 8) & empty;
			break;
		case BP2:
			bb = bPawnCaptures[fs] & enemy;
			bb |= (1ull << fs >> 8) & empty;
			while (bb) {
				ts = std::countr_zero(bb);
				bb ^= 1ull << ts;
				mfs = fs;
				mts = ts;
				msc = valq + value[mtt];
				mft = BPQ;
				m++;
				mfs = fs;
				mts = ts;
				msc = valn + value[mtt];
				mft = BPN;
				m++;
				mfs = fs;
				mts = ts;
				msc = valr + value[mtt];
				mft = BPR;
				m++;
				mfs = fs;
				mts = ts;
				msc = valq + value[mtt];
				mft = BPB;
				m++;
			}
			continue;
		case WN: case BN:
			bb = knightMoves[fs] & notme;
			break;
		case WB: case BB:
			bb = (
				dSubset[fs][(((occ & dMask[fs]) * file_b2_b7) >> 58)] |
				aSubset[fs][(((occ & aMask[fs]) * file_b2_b7) >> 58)]
				) & notme;
			break;
		case WRC: case WR: case BRC: case BR:
			bb = (
				hSubset[fs][(occ >> hShift[fs]) & 63] |
				vSubset[fs][((((occ >> (fs & 7)) & file_a2_a7) * diag_c2_h7) >> 58)]
				) & notme;
			break;
		case WQ: case BQ:
			bb = (
				dSubset[fs][(((occ & dMask[fs]) * file_b2_b7) >> 58)] |
				aSubset[fs][(((occ & aMask[fs]) * file_b2_b7) >> 58)] |
				hSubset[fs][(occ >> hShift[fs]) & 63] |
				vSubset[fs][((((occ >> (fs & 7)) & file_a2_a7) * diag_c2_h7) >> 58)]
				) & notme;
			break;
		case WKC:
			mft = ((u64)((board[h1] == WRC) && !(occ & owcs) && !AtkByBlack(t, awcs))) * WCS;
			m += (mft == WCS);
			mft = ((u64)((board[a1] == WRC) && !(occ & owcl) && !AtkByBlack(t, awcl))) * WCL;
			m += (mft == WCL);
			[[fallthrough]];
		case WK:
			bb = kingMoves[fs] & notme;
			break;
		case BKC:
			mft = ((u64)((board[h8] == BRC) && !(occ & obcs) && !AtkByWhite(t, abcs))) * BCS;
			m += (mft == BCS);
			mft = ((u64)((board[a8] == BRC) && !(occ & obcl) && !AtkByWhite(t, abcl))) * BCL;
			m += (mft == BCL);
			[[fallthrough]];
		case BK:
			bb = kingMoves[fs] & notme;
			break;
		}

		while (bb) {
			mfs = fs;
			mts = std::countr_zero(bb);
			mft = type;
			msc = value[board[mts]];
			bb ^= 1ull << mts;
			m++;
		}

	} while (side);

	mft = ES;

	return (s32)(m - n);
}

Another example of branchless code is this.

Code: Select all

static bool AtkByWhite(Thread* t, u64 b) {
	u64 atk = 0;
	u64 occ = sides[WHITE] | sides[BLACK];
	while (b) {
		s32 sq = std::countr_zero(b);
		b ^= 1ull << sq;
		atk |= (bPawnCaptures[sq] & pawns[WHITE]);
		atk |= (knightMoves[sq] & knights[WHITE]);
		atk |= (kingMoves[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);
}

And one more example to show what can be done with branchless programming. Even the capture en-passant code uses no if clauses in MakeMove();

Code: Select all

case WP5:
    sq = mts - ((epbit[sly] == (1ull << mts)) << 3);
    mtt = board[sq];
    board[mfs] = ES;
    board[sq] = ES;
    board[mts] = WP6;
    pawns[WHITE] ^= (1ull << mfs | 1ull << mts);
    sides[WHITE] ^= (1ull << mfs | 1ull << mts);
    *types[mtt] ^= (u64)(mtt != ES) << sq;
    sides[BLACK] ^= (u64)(mtt != ES) << sq;
    mat[BLACK] -= value[mtt];
    pos[WHITE] += (wptbl[mts] - wptbl[mfs]);
    pos[BLACK] -= tbls[mtt][sq];
    break;

Because of Qsearch() about 85% to 90% of all moves are capture moves. So in MakeMove() every move is processed as a capture move. If an empty square is captured then no change happens.

I don't know if you can use this. I just thought I'd show you another way of thinking.

[Roland Chastain]

Hello! It seems to work well. Unfortunately, I am too lazy and not good enough at chess to play a whole game by typing moves on keyboard. If you would add support of CECP or UCI protocol, it would be easier for us to use your program. (My two cents.)

[imnoumni]

But what is different is that the entire move generator does not use a single if clause. Even the castling code does not use any if clauses!

What you show may be less branchless than you think. All those match statements are while loops are branches. And all your branches have non-trivial code. I suspect if you inspect the assembly you would find many branches. Besides, modern processors optimize for predictable branching. Branches that are simple result in conditional move instructions which do not incur a branch penalty. Excessive branching will slow performance, but branching in itself need not be shunned nowadays.