Architecture

Deno Chess has a long list of little choices that cumulatively add up to some pretty solid improvement. (Especially for a library with no WASM or anything.)

Requirements:

• Support all the basic chess engine stuff:
  • End-game detection (checkmate, stalemate, 50-move rule, 3 repetitions, ...)
  • Move enumeration. (list all possible moves from this position.)
  • Accepting moves in a variety of formats:
    • JS objects: { from: "e2", dest: "e4" }
    • SAN: "Nf3"
    • UCI: "b8c6"
  • Output the board in a variety of formats:
    • FEN strings, to show the state of the current board.
    • PGN strings, to show the full move history in a standardized format.
  • Parse PGN strings.
• We should be as fast as possible.
• Pure TS.

Basic Types

There are a number of fundamental types. Whenever possible, I packed these values into JS numbers. Why?

• I can't use enums, since Typescript transpiles enum types into an object, and al uses of the enum values will get transpiled into a keyed lookup into that object. I didn't want the library to be constantly doing key lookups in objects, so I just stuck with literal numbers. (Aside: Typescript DOES have a solution to this called 'const enums' which should transpile into literal numbers. This sounds great, however, nothing other than TSC supports them, since they force the module system to be more aware of the type system. IIRC, deno at the time simply ignored the 'const' bit, and emitted standard enums, and esbuild + webpack did the same.)
• Numbers are great, since they are simple scalars that are trivially created, copied, etc. Plus, they don't require any use of the heap.
• Numbers also make another architectural decision easier: I want to store most critical-path logic in simple top-level functions, and not in classes or their methods. This is so the hot path of the library doesn't have to do any prototype traversals, and the JS JIT optimizer only has to deal with functions, which is way easier for it to optimize.

Piece Color

Color is a number. 0 is white. 8 is black. Why those numbers? Because those numbers work well for the bit-math later on...

Piece Type

The type of a piece is another number. 1 = Pawn, 2 = Bishop, 3 = Knight, 4 = Rook, 5 = Queen, and 6 = King.

0 is not used so it can be used to represent an empty space on the board.

Coordinates

A coordinate in chess is the rank & file of a square on the board. (Rank being the row, and file being the column.) Typically, these are shown to the user as a short string, like "E6". Internally, we use what's called "0x88 notation", which packs the coordinate into a single byte, storing rank in the most significant nibble, and the file in the least significant one.

This notation is clever because it leaves a sizable gap between coordinates at the edge of the table. That greatly simplifies bounds checking, since we don't have to check if x < 0 or x >= 8 or y ... etc. We only have to check if xy & 0x88, and that cleanly will detect any out-of-bounds access. That is super useful, since we're going to be doing a LOT of bounds checking...

Space

A space on the board is represented as an 8-bit integer.

(MSB) 000M CTTT (LSB)

• 000: unused.
• M: a "moved" flag. Set to 1 if this piece has ever moved. (Needed for castling.)
• C: the color (1 for black, 0 for white. - so we can bitwise-or the color and the type together)
• TTT: the piece type, packed into 3 bits.

Enum values

This is why the enum value for "black" in the color section was 8: So we can extract the cell color with a simple & 0x8, and a space can be assembled with type | color.

The Board

Ultimately, the board's state is packed into a Uint8 array. Now, since a chess board is 8x8, it would seems like a good idea to create a 64 cell array. However, our coordinate system is 0x88, and so the max legit coord is 0x77 or 119. To make it so the coord can still directly index into the board struct without translation, we allocate a 128 cell array for the board. This avoids extra math to figure out the correct index, which improves performance.

There are all sorts of other things that represent the board state: counters, turn colors, attack maps (more on that later), caches for move lists, and so on. All of these are stored in a stack, so we can trial out changes, and trivially revert them with .save() and .restore() functions. It's very common for pieces to need to be hypothetically moved, to check for checks and so forth.

One performance hack with the save and restore functionality: When you restore, we only decrement the index and update a current pointer - we don't actually remove anything. The next save can then reuse that previously allocated object by overwriting the values. This prevents needless allocations for super-common operations.

The Castle Map

We need to know whether a king is capable of castling on particular sides. The rules for castling are simple:

• The king must never have moved.
• The rook that is participating in the castle must never have moved.
• The king cannot start in check, cannot end in check, and no space that the king travels through can be under attack.

To help keep track of the king's castling eligibility, we maintain the "castle map", which is a JS number, treated as a 16-bit integer.

(MSB) dddd cccc bbbb aaaa (LSB)

• aaaa: White kingside
• bbbb: White queenside
• cccc: Black kingside
• dddd: Black queenside

The most significant bit in each section is 1 when that side is still eligible, and 0 otherwise. The rest of the bits store the column (aka: file) that this rook is in currently. (The rook might not be in the left-most or right-most file if chess960 is being played...) Storing that file in the map makes future move generation easier.

The Attack Map

Probably the most novel optimization in this library is its Attack Map. It's the bit of code that is responsible for detecting if a move puts the king in danger. Ideally, this logic should be as fast as possible - when doing chess library stuff, you ALWAYS need to be aware of which spaces can be attacked. This is because a king cannot move into a space that is actively under attack, and pieces cannot move if that movement would put their king in danger. Plus, the attack map is a key part of being able to detect things like check, checkmate, and stalemates. So it is referenced frequently.

An easy algorithm for this would be to just make your move, and then iterate over all enemy pieces, and see if they can attack your king. This approach would technically work. However, this logic would need to be done for every hypothetical move that could happen whenever we are listing out valid moves, which is one of the most fundamental things that a chess library needs to do. Doing the king-in-danger check this way is simply way too slow.

Another naive approach would be to keep an integer counter of all attackers for each cell. When we move a piece, we iterate over all cells that this piece could have attacked, and decrement the counters. We can then move the piece, and iterate all the cells it can be attacked from that piece's new position, and increment those counters. A cell is in danger if the counter is above 0. One advantage to this approach is that updating the set of counters can be done incrementally. (ie: we don't have to revisit EVERY piece on the board, we only have to consider the piece that is currently moving.) This approach almost works. The problem arises from discovered attacks. If I move my bishop to the side, there could have been a rook hiding behind it. This will expose a whole bunch of new cells to attack, that have nothing to do with the bishop being moved. To fix this, we would need to iterate all other pieces, and consider whether the bishop's movement could have affected their attacked spaces... and supporting all of these cases gets really complex, and we lose a lot of our incremental advantage...

And so I came up with my own approach. The underlying idea is: there are two types of chess pieces - sliders, and steppers. Sliders (bishops, queens, and rooks) have a large range, but can be blocked. The other pieces (pawns, kings, and knights) are all steppers. The thing about steppers is, their attacks don't really get blocked, and so the counting approach would actually work for them.

For example, here we have a knight in the middle of the board, and all the spaces it can attack have a counter that is incremented by 1.

Now, sliders are the tricky bit. To support them, we will keep a directional bitmap for each cell. 8 directions, 8 bits. These bits ((MSB) N E S W NE SE SW NW (LSB)) will track the rays emanating from each sliding piece, and that travel through or end on each space.

When a slider piece is placed on the board, we'll cast "rays" out from it, and mark all the spaces it can reach in the correct bit for the direction that the ray traveled. When casting out the ray, we'll never set the directional bit on the space that the piece is currently on, and if the ray gets blocked by another piece, we'll mark the directional bit on the space that blocked the ray. That way, whenever a piece gets moved, it need only look at the directional bits for its old location to know which rays that it was blocking. I then has all the info necessary to "recast" those rays, so that newly revealed attacks can be registered. Similarly, when a piece is placed somewhere new, it can look at the rays passing through its new location, and now has enough information to unmark all the directional bits that have now been blocked.

In this example, let's say that the pawn wants to move up one space. We would first decrement the two attack counters that the pawn can currently target. We'd then remove the pawn from the board, and prepare to place it in its new location. While removing the piece from the board, we would check the directional bits of the pawn's old location to see if there are any directional attacks from a slider piece that'd need to be continued. We'd see that the "East" bit is set, and so we'd then recast the directional attack towards the East. This new directional attack would reach the King, and so we now know that this move is illegal.

To store all of this information, I pack all of this data into a Uint8Array with 256 cells. I purposely abuse the 0x88 coordinate system, and pack values into the invalid indexes. The slide bitmaps are stored in cells indexed by coord & 0x8, and a full copy of the board from the black piece's perspective is stored at coord & 0x80. Why did I do that? This allows all the data to be stored in a far more compact manner, making the board save() operation take less time, since less data needs to be copied.

In the end, we can easily check if a space is being attacked by checking if either the steps counter is above 1 (ie: a knight can reach this space) or if any of the directional bits for a spot is set. (ie: a bishop is passing through this space.) Those 2 checks can be done in constant time, which is fantastic. What's better: the amount of book-keeping necessary to keep the structure up-to-date is minimal, and is mostly constrained to the piece being moved.

On maintaining good documentation

It has been several years since I wrote this code, and I remembered very little about it. The bits that I thought I'd remember, I had forgotten. The comments that I thought I made, didn't exist. All documentation was non-existent. The commit messages were terse and useless. I eventually tracked down my old pencil-and-paper notes, but they were sparse and cryptic, and then abruptly cut off to talk about the needed enchantments for my then-current Skyrim mage build. Dang it, Past-Raymond.

Anyways, let this be a lesson to keep good documentation. Future-You will thank you.