eschac

Hello everyone!

I would like to introduce eschac, a Rust library I wrote for computing chess moves!

Why another one?! shakmaty exists and it is great!

Indeed, and in most cases it is definitely a better option! For one, the scope of eschac is a lot smaller than that of shakmaty. I focused on move generation for standard chess and that is about it. shakmaty has also been deployed in real-life applications for a long time where eschac is probably full of bugs (eschac is not currently nor should be deployed in production for any reason).

eschac started as a toy project to learn about move generation. shakmaty (and the work of @revoof in general) was a great inspiration for me, and you may notice that a lot of the vocabulary in eschac comes directly from shakmaty. I think that I ended up diverging from shakmaty in some ways that were worth sharing though!

To be precise, there are three ideas that I implemented in eschac that I want to present.

Playing moves

In my opinion, the most interesting difference between shakmaty and eschac is the interface for playing moves.

In shakmaty, the Position trait offers two options:

1. fn play(self, m: Move) -> Result<Self, PlayError<Self>>

This comes with a heavy runtime overhead to check for the move's legality. This can be frustrating to use in terms of performance as the move was probably generated on the same position just a few lines before.

2. fn play_unchecked(&mut self, m: Move)

This does not check for the move's legality, but might cause panics down the line. Even though the overhead is smaller it is not zero, as panicking still implies some runtime checks. Removing that overhead entirely would probably require this function to be unsafe.

I started experimenting to write a safe interface with no performance compromise, and I ended up bundling the move data with a reference to the position:

pub struct Move<'l> {
    position: &'l Position,
    raw: RawMove, // holds the same data as `shakmaty::Move`
}

This ensures that the position is not mutated until the move is played, and since the move is necessarily legal on its associated position it can be played safely with a copy-make interfarce. Upon making the move, the position is cloned and the move is played with the internal unsafe api. The public function is safe:

impl<'l> Move<'l> {
    pub fn make(self) -> Position {
        let mut position = self.position.clone();
        unsafe { position.play_unchecked(self.raw) };
        position
    }
 }

I think that this is pretty comfortable to use:

let m = san.to_move(&position)?; // legality is checked only once
position = m.play(); // no result, no panic, no unsafe

Representing moves

Move representation is very similar between shakmaty and eschac, but I pushed an idea already present in shakmaty a little bit further. In shakmaty, moves are represented with an enum discriminating between normal moves and special moves like castling or en passant:

pub enum Move {
    Normal {
        role: Role,
        from: Square,
        capture: Option<Role>,
        to: Square,
        promotion: Option<Role>,
    },
    EnPassant {
        from: Square,
        to: Square,
    },
    Castle {
        king: Square,
        rook: Square,
    },
    Put {
        role: Role,
        to: Square,
    },
}

Looking at the code for playing moves, I saw this runtime test for a double pawn advance, in order to set the en passant target square if necessary. I thought that, since it is known at generation time whether the move is a double pawn advance or not, and since we are branching on the enum anyway, this could be a variant of the enum too. Pushing this logic even further, we can also discriminate between pawn advances and pawn captures. In the case of an advance, we can spare the cost of removing the piece from the target square, since there isn't any!

When representing moves like this, most variants hold the same data though, so I ended up with the following definition for the RawMove type mentioned above:

struct RawMove {
    kind: MoveType,
    role: Role,
    from: Square,
    to: Square,
}

With MoveType being quite exhaustive:

enum MoveType {
    CastleShort,
    CastleLong,
    KingMove,
    PieceMove,
    PawnAdvance,
    PawnAttack,
    PawnAdvancePromotion,
    PawnAttackPromotion,
    PawnDoubleAdvance,
    EnPassant,
}

This allows to remove a few runtime checks, at the cost of a slightly larger move type.

The board

When representing the board with bitboards, making a move usually implies removing the target square from all the pieces' bitboards since the type of the captured piece (or if the move is a capture to begin with) is not known. The most straightforward approach, involving on bitboard per piece, requires six operations to do this. Provided a few binary operations for decoding, we can represent the chessboard with fewer bitboards, and since I had already commited to a copy-make interface, I thought that reducing the size of the board, even if it added a small cost when generating moves, could be beneficial.

Starting with twelve bitboards (one for each color and piece), we can start by removing four of them: six bitboards (one for each piece), one bitboard for white pieces and one bitboard for black pieces, for a total of eight bitboards. This is what shamaty does. The bitboard for Black is actually redundant, so we can remove this one too. This comes down to seven with just a few binary operations necessary for decoding, but we can actually go as low as four bitboards with just a few more AND operations:

• One bitboard with pawns, bishops and queens
• One bitboard with knights, bishops and kings
• One bitboard with rooks, queens and kings
• One bitboard with White's pieces

When adding the space necessary for the rest of the position, and with alignment, this makes for a 40 bytes position. It is possible to compress positions even further, but I stopped there as the overhead of decoding the positions seemed too high.

Apart from reducing the number of operations for making moves, this representation also enables a nice trick to get the occupant of a square. Instead of checking every bitboard in order, and if we define our Role enum carefully, we can get the type of a piece on any given square with just bitwise operations:

let role = unsafe {
    std::mem::transmute(
        (((r_q_k & (1 << sq)) >> sq) << 2) |
        (((n_b_k & (1 << sq)) >> sq) << 1) |
        ((p_b_k & (1 << sq)) >> sq)
    )
};

Benchmarks

When I started experimenting with these ideas, I thought that matching shakmaty's performance while removing the possibility for panics would be worth sharing. I will show two benchmarks. First the mean perft times at depth 4 for all positions listed here, then the parsing and playing of 100,000 games in standard algebraic notation downloaded from lichess. This was done on my laptop equipped with an AMD Ryzen 5 PRO 8640HS, compiling in release mode with rustc v1.86.

perft at depth 4

replaying 100,000 games in algebraic notation

Finally, I wanted to show perft results for an alternative implementation that counts leaf moves without iterating through all of them (using Position::count_legal_moves).

Conclusion

As you can imagine, I am very happy with those numbers! This was very interesting to work on, and I hope that this idea for a copy-make interface will be of interest to other chess programmers.

Best,
PNM