Making a Mhess – Chess Engines and Board Representations

Mhess is a stupid messy chess game about giving your pieces superpowers and fighting robot masters. It’s been the center of my attention for the past month or so, and it seemed fitting to share a few of the things I’m learning about the good, the bad, and the ugly of chess engine programming.

As a caveat, I deliberately did not look at any existing implementations. I was hoping that avoiding them would prevent having any pre-conceived notions about the best approach and would lead to a more novel, interesting implementation. If you’re interested in writing your own chess game, I would recommend looking at The Chess Programming Wiki.

Implementing a chess game and a chess engine are very different problems, though a chess game needs a chess engine, the design rules for a fully functional game are slightly different than those of a pure chess engine. For starters, something I had not thought about when building out the engine component was how difficult keeping the internal board representation and external board representation in sync would be. I spent a significant amount of time debugging why things in the game world would disappear or refuse to move. This challenge was compounded, or perhaps made more subtle by what I think are, in hindsight, bad decisions.

Bad Decision 1: Game State representation.

I use the following to represent a game state. It’s designed to be light weight and quick to clone so that when we start looking at trees of depth 14 we don’t blow out our compute time.

#[derive(Clone, Eq, Hash)]
pub struct GameState {
	pub board_width: u8,
	pub board_height: u8,
	pub board_holes: vec![],
	pub board_state: Vec<(u8, u8, Piece)>,
	pub en_passant_space: Option<(u8, u8)>,
	pub black_can_queenside_castle: bool,
	pub white_can_queenside_castle: bool,
	pub black_can_kingside_castle: bool,
	pub white_can_kingside_castle: bool,
	pub halfmove_count: u8,
	pub fullmove_count: u8,
	pub current_player: PlayerColor,
}

The board_state is worth highlighting. I had started with a vector of tuples of u16,Piece. That proved to be an unnecessary optimization since we always immediately converted the idx into x,y. Note that there’s a deliberate choice to have x,y in the board state and NOT inside the piece. This is done to make cloning the board state a shallow operation and really fast. Generating 11 million moves takes less than 700ms in debug mode.

A piece does not know its position in the world. Instead, a move generator takes a game state and produces a bunch of “gamemove” items. A gamemove item takes a gamestate and produces from it a new state. If this whole thing seems roundabout, that’s because it is. Complexity of defining moves is generally localized to the gamemove.rs code, but there’s a LOT of complexity to be localized. Implementing castling has been a mess because checking whether pieces are being attacked involves generating all of the possible moves for the next state. Similarly, checking for checkmate (or check) involves basically first generating the next moves and then determining which result in the king being able to be captured. This is not a great solution.

The next experiment will be a lengthy one and will probably involve trying to switch from the current gamestate + move generator to a gamestate + heavy piece system. If that works out, or if it doesn’t, I’ll be sure to post an update here.