Move Generation Optimization

[theturk1234]

Hi,

I'm trying to optimize my perft speed, naturally I'm working on my move generation speed.
One function in particular is taking a long time--It checks if the move passed to it leaves the king in check.
Right now in that function I'm making the move, checking if the king is attacked, then returning.
Is there a faster/better way to do this whole function?
It takes up 25% of the perft time.

Any random thoughts on tricks to make move generation go faster?

Thanks,
David Cimbalista

[brtzsnr]

You can probably speedup most attack checks (magic bitboards computation) by looking whether the king can be attacked on an empty board by an enemy piece.

With bitboards it is something like:

Code: Select all

        enemy := pos.ByColor[them] // all enemy pieces
	enemy &^= pos.ByFigure[Pawn]  // exclude pawns
	enemy &^= pos.ByFigure[Knight]  // exclude knights
	if enemy&bbSuperAttack[sq] == 0 {   // bbSuperAttack is queen's attack from sq on empty board
		return NoFigure // not attacked
	}

[Henk]

Use the last move information.

[Sven]

Hi,

I'm trying to optimize my perft speed, naturally I'm working on my move generation speed.
One function in particular is taking a long time--It checks if the move passed to it leaves the king in check.
Right now in that function I'm making the move, checking if the king is attacked, then returning.
Is there a faster/better way to do this whole function?
It takes up 25% of the perft time.

Any random thoughts on tricks to make move generation go faster?

Thanks,
David Cimbalista

Yes, there is a faster way. If you promise that you postpone all other optimizations for at least one year then I'll tell you this one, almost the only optimization that should not be postponed too long

The trick is that there is only a small subset of pseudo-legal moves that can ever be illegal:
- king moves (including castling),
- check evasions,
- moves of a pinned piece, and
- en passant captures.

If you implement pin detection for the moving side (and maybe store all locations of pieces that are pinned to the king in a single 64 bit integer) then it will be easy to write a function "moveCanBeIllegal(move)". You will most probably already have tested whether the king of the moving side is in check prior to starting move generation (in full-width search as well as qsearch), so that information could be stored in a boolean flag "inCheck". Then you can replace your "makeMove - wasKingLeftInCheck - unmakeMove" by a similar sequence that uses "moveCanBeIllegal". This will save a lot of unnecessary calls.

Since you are doing legal move generation I guess that you already use the "bulk counting" improvement for perft (at depth=1 do not make/unmake moves but simply return the number of legal moves found by the move generator).