Sunday, March 01, 2009

Ugly hacks, nice hacks

I'm translating a small python module that supports some chess intelligence generation into C++ because the speed is becoming a problem (when interfacing a digital board I need to do some search to guess what is the move that has been played and this includes looking one or two moves ahead and one move behind - that is moves that could have been played instead of the last move played).
The translation went fine so far with an almost 1-1 lines of code ratio between the two languages (not a surprise, given the problem) but I got a couple of surprises...

The bug

To check if a position cannot be win by either player I had to check whether two remaining bishops on the board were covering the same squares or not (that is if they were both light-square bishops or both dark-squares bishops or if they were covering the whole board).
This is needed because if there are two opposite-square-colors bishops on the board then a checkmate is still possible.
The code looked like this

if bc == 2 and nc == 0:
bp = [i for i, x in enumerate(pz) if x == BISHOP]
if (bp[1] - bp[0]) % 2 == 0:
# Just two bishops both dark squares or both light squares
return "material"
nc and bc are the number of knights and bishops on the board (pawns, rooks and queens are already known to be absent at this point). The board is represented using an array of 120 elements (12x10 representation) but it would be the same using an 8x8 approach... the bug is that just using the index "i" to check odd-even property is not correct, and "i//10 + i" should have been used instead. This shined apparent to me just by reading the code... however this code passed the tests because the test cases were all having the bishops on ranks with an even distance.
Now that I'm writing this post I also realize that there's even another bug at an higher logical level... it doesn't matter how many bishops are there: if they're all covering the same squares the checkmate is trivially impossible. It's not a 100% genuine bug because if the function returns a non-empty string then the position is impossible to win, but the converse is not true and it would be quite hard to fulfill such a contract.

Morale ? If it works is just because you didn't look closely enough.

The hack

In the same code I couldn't resist changing the handling of en-passant from

if x1 == self.epsq:
if np == WHITE+PAWN:
# White en-passant capture
self.board[x1+10] = EMPTY
elif np == BLACK+PAWN:
# Black en-passant capture
self.board[x1-10] = EMPTY
if np == WHITE+PAWN and x1 - x0 == -20:
# White double push
self.epsq = x0 - 10
elif np == BLACK+PAWN and x1 - x0 == 20:
# Black double push
self.epsq = x0 + 10
else:
self.epsq = -1
to

if ((np & PIECE) == PAWN)
{
if (x1 == epsq)
// En-passant capture
board[x1 - (((x1-x0)>>4)*20+10)] = EMPTY;
if (abs(x1-x0) == 20)
// Double push
epsq = x0 + (x1-x0)/2;
else
epsq = -1;
}
The C++ version is much more compact, but in the first part relies on a "trick" that for sure would look quite obscure for who reads the code... what the hell is "(((x1-x0)>>4)*20+10)" ?
The trick is that I know that the move was legal, so if a pawn goes to the en-passant square it must have been an en-passant capture and so the delta (x1 - x0) was either -9, -11, +9 or +11 depending on the color of the player. Then "(x1 - x0)>>4" is just the -1 if delta is negative or 0 otherwise; with "*20+10" and "x1 -" gets to the square where the captured double-pushed pawn was sitting.
Why do I think this trick is nice ? That's a good question...

I'll add a comment as a partial excuse to the poor future reader (which will probably be myself) :-)