Writing Color Blind Chess Code

Back in 1999 I created the first version of Monarch in Delphi.  At that time I wondered just how fast the Delphi code would be.  Would it be able to compete with the then rapidly improving C compilers.  So I wanted my code to be as fast as possible.  While the debate over brute force vs. selective search in computer chess was all but over, I believe a hangover from those times was an industry-wide obsession with speed.  For example, there were still some engines coded purely in assembler (Fritz, Rebel, M-Chess and Genius).  So I wasn’t alone in my “need-for-speed”.  One of the ways I thought I could squeeze out a little extra speed by writing code which is specific for white and black e.g. a white move generator and a black move generator.  Of course it was a nightmare to maintain.  When I found a bug in one part of the code I needed to change it in another part of the code (if I remembered) – a veritable nightmare!!

I believe Fabian Letouzey can take the credit for shifting my mindset away from trying to create ultra-optimized code at all cost.  Back in 2004 I was gobsmacked when I first saw the clarity of Fabian’s code.  And the resulting engine, Fruit 1.0, was strong.  As a result there was a significant shift in computer chess, away from over optimizing and towards clarity and bug free code.

So in Maverick I’m attempting to make the code as clear as possible.  To this end, one of the aims is to write color-blind code i.e. wherever possible try to have one routine which accomplishes the task for both white and black.  An obvious task is move generation, and pawn move generation in particular.  I’ve managed to accomplish this using the following code.  There were some helpful hints from this thread on CCC (I went with H. G. Muller‘s approach):

int forward = 8 - 16 * to_move;
moves = (((board->piecelist[piece] << 8) >> 16 * to_move) & ~(board->all_pieces));

So the left shift by 8 occurs for both white and black pawn, and the right shift is for black only pawn since (16 * t_move) will be zero when to_move is white.  It all works nicely!  Also worth noting – there are no bits lost by the first shift since there are never any pawns on the 8th rank – beautiful!!

All I need to do now is generate castling moves and e-p captures and the basic move generator will be complete!

  • Patrick

    Line 1 seems irrelevant?

    • Steve Maughan

      True – in my previous implementation I used forward, now it’s redundant.

  • I personally find if/else on color easier to read.

    I recently modified my move generator to use bitboards (using kogge-stone approach for sliding pieces).
    I was earlier planning to go for a color-blind approach like you described but some of the cases were becoming too complex so I decided to stick with simple if/else (thinking that I will optimize it later).
    I later had an idea of making the move generator templated on color and for my program it gives a decent performance improvement (~7%).
    With templated move-generator on color, if/else checks on color is effectively free (as the color is known at compile time and the branch is optimized out) – so it should be at least as fast as if not faster than color-blind approach.
    The only drawback I see is increased (doubled?) code size which might cause instruction cache trashing in some cases.

    • Steve Maughan

      Hi Ankan – if “if / then” work for you then use it! It is a branch in the code, whereas the two shifts are not. Since, from your other comment, your perft speed is fast I wouldn’t worry about it.

      • What I meant is that although there is a branch in the C code, the branch is removed by the compiler when generating machine code if the move generator is templated on color.
        There is a single branch at the start of move generation code to decide which template instance to call.