Bitboards for beginners

[lucasart]

OK here's my version of generating all legal moves for pieces, when the current position isn't a check. And I insist on *legal* moves, not *pseudo-legal*. With all due respect, I find it more readable and easier to write than your mailbox hell

What I'm trying to say here is that with bitboards, you basically:
* write the hardcode low level stuff. it's the hard part, but once it's done you never need to go back into it.
* then all the board related functions (move generation for example, but really everything) consists of easy to write, easy to read, easy to maintain/debug high level code.
* and of course it's very fast.

[hgm]

And my point was that this "hard part" is far more work than writing an entire beginner's engine. So not recommended. Beginners better start with the "easy part".

[lucasart]

Except of course that the code you show does not really do anything at all. All the work is done by the routines next_bit, serialize_moves, piece_attack... Note that there is not a single function call in the code I showed. That code is not just a facade, but the real thing.

If I would show my code at the same level as yours, it would look like

Code: Select all

GenMoves(stm);

Which code is simpler now?

* next_bit and piece_attacks aretrivial and defined above in bitboard.h
* OK here's my serialize_moves... But it's very readable high level code, there's no complicated bitboard manipulation there

Code: Select all

static inline move_t *serialize_moves(const Board *B, int fsq, int tsq, move_t *mlist)
/* Centralise the move generation here: given (fsq,tsq) the rest follows. We handle here all the
 * annoying cases (indirect self-check through fsq, or through the ep captured square). Note that
 * direct self-checks aren't generated, so we don't check them here. In other words, we never put
 * our King on squares attacked by the enemy before calling this function */
{
	assert(square_ok(fsq) && square_ok(tsq));
	const int us = B->turn, them = opp_color(us),
		kpos = B->king_pos[us];

	if ((test_bit(B->st->pinned, fsq))			// pinned piece
	&&	(!test_bit(Direction[kpos][fsq], tsq)))	// moves out of pin ray
		return mlist;	// illegal move by indirect self check

	move_t m;
	m.fsq = fsq;
	m.tsq = tsq;
	m.piece = B->piece_on[fsq];
	m.capture = B->piece_on[tsq];
	m.ep = Pawn == m.piece && tsq == B->st->epsq;

	if (m.ep) {
		occ_t occ = B->occ;
		// play the ep capture on occ
		clear_occ(&occ, m.fsq);
		clear_occ(&occ, m.tsq + (us ? 8 : -8));	// remove the ep captured enemy pawn
		set_occ(&occ, m.tsq);
		// test for check by a sliding enemy piece		
		if ((get_RQ(B, them) & RPseudoAttacks[kpos] & rook_attack(&occ, kpos))
		|| (get_BQ(B, them) & BPseudoAttacks[kpos] & bishop_attack(&occ, kpos)))
			return mlist;	// illegal move by indirect self check (through the ep captured pawn)
	}

	// promotions
	if (Pawn == m.piece && test_bit(PPromotionRank[us], tsq)) {
		m.promotion = Knight; *mlist++ = m;
		m.promotion = Bishop; *mlist++ = m;
		m.promotion = Rook;	  *mlist++ = m;
		m.promotion = Queen;  *mlist++ = m;
	}
	// all other moves
	else {
		m.promotion = NoPiece;
		*mlist++ = m;
	}

	return mlist;
}

[lucasart]

Except of course that the code you show does not really do anything at all. All the work is done by the routines next_bit, serialize_moves, piece_attack... Note that there is not a single function call in the code I showed. That code is not just a facade, but the real thing.

If I would show my code at the same level as yours, it would look like

Code: Select all

GenMoves(stm);

Which code is simpler now?

* next_bit and piece_attacks aretrivial and defined above in bitboard.h
* OK here's my serialize_moves... But it's very readable high level code, there's no complicated bitboard manipulation there

Code: Select all

static inline move_t *serialize_moves(const Board *B, int fsq, int tsq, move_t *mlist)
/* Centralise the move generation here: given (fsq,tsq) the rest follows. We handle here all the
 * annoying cases (indirect self-check through fsq, or through the ep captured square). Note that
 * direct self-checks aren't generated, so we don't check them here. In other words, we never put
 * our King on squares attacked by the enemy before calling this function */
{
	assert(square_ok(fsq) && square_ok(tsq));
	const int us = B->turn, them = opp_color(us),
		kpos = B->king_pos[us];

	if ((test_bit(B->st->pinned, fsq))			// pinned piece
	&&	(!test_bit(Direction[kpos][fsq], tsq)))	// moves out of pin ray
		return mlist;	// illegal move by indirect self check

	move_t m;
	m.fsq = fsq;
	m.tsq = tsq;
	m.piece = B->piece_on[fsq];
	m.capture = B->piece_on[tsq];
	m.ep = Pawn == m.piece && tsq == B->st->epsq;

	if (m.ep) {
		occ_t occ = B->occ;
		// play the ep capture on occ
		clear_occ(&occ, m.fsq);
		clear_occ(&occ, m.tsq + (us ? 8 : -8));	// remove the ep captured enemy pawn
		set_occ(&occ, m.tsq);
		// test for check by a sliding enemy piece		
		if ((get_RQ(B, them) & RPseudoAttacks[kpos] & rook_attack(&occ, kpos))
		|| (get_BQ(B, them) & BPseudoAttacks[kpos] & bishop_attack(&occ, kpos)))
			return mlist;	// illegal move by indirect self check (through the ep captured pawn)
	}

	// promotions
	if (Pawn == m.piece && test_bit(PPromotionRank[us], tsq)) {
		m.promotion = Knight; *mlist++ = m;
		m.promotion = Bishop; *mlist++ = m;
		m.promotion = Rook;	  *mlist++ = m;
		m.promotion = Queen;  *mlist++ = m;
	}
	// all other moves
	else {
		m.promotion = NoPiece;
		*mlist++ = m;
	}

	return mlist;
}

Note the inline, that allows the compiler to optimize with the body of the calling function, making most of it trivial in a lot of cases.

[lucasart]

And my point was that this "hard part" is far more work than writing an entire beginner's engine. So not recommended. Beginners better start with the "easy part".

Anyway, you're probably right about beginners
But I'm sure *intermediate* will find this helpful.

[ethanara]

thanks a lot!
Is this under any license etc.?

[bob]

And my point was that this "hard part" is far more work than writing an entire beginner's engine. So not recommended. Beginners better start with the "easy part".

I'm not sure I agree. For decades, computer scientists have debated where a person should start their programming career with regard to programming languages. And for years, many very well-known schools answered "assembly language". As once you learn things at that level, you are a better programmer at the next level. Others have opined the opposite, that it is quicker to get going using a high-level language. And quicker to learn bad habits. And to never have any idea of what your program might look like from the machine's point of view, and could you have made it any more efficient.

It's always been a lively debate. I started CS in 1968, and our first course was a 2-hour (3 was normal) course in FORTRAN. The second was a 3 hour course in IBM /360 assembly language. At the time, some used basic (Dartmouth, for example) rather than FORTRAN. And we have been through Pascal, then C, then C++, and now Java. At the bottom of the pile, and just as important today as ever, is still assembly language. And it gets overlooked too often.

Some of the _best_ programming students I had back in the 80's and 90's were the guys that were at home hacking on their 8080/z80 boxes in assembly language, learning how the thing _really_ worked.

[lucasart]

thanks a lot!
Is this under any license etc.?

You are free to use this code for any purpose. So long as you give credit where credit is due (like a comment line in source code to say this function was taken from there etc.), that's fine by me.
However, if I ever finish my program, the entire source code will be released under the GNU GPL.

[hgm]

I'm not sure I agree. For decades, computer scientists have debated where a person should start their programming career with regard to programming languages. And for years, many very well-known schools answered "assembly language". As once you learn things at that level, you are a better programmer at the next level. Others have opined the opposite, that it is quicker to get going using a high-level language.

Well, I guess that if those wanting to start with a high-level language would be required to write their own compiler first, the debate would be quickly decided...